Instructor: Konstantin (=
Nickname: Kostya
You are welcome to call me by my first name or
nickname.
Class meets: Olsen Hall
Monday, Wednesday, Friday
Office: Olney 428 K
Office Hours: Monday, Friday 2:30-4 PM or by appointment (email at least 2 days in advance)
Email: Konstantin_Rybnikov@uml.edu (please, do not send emails regarding this course to other email addresses of mine)
Homework can be submitted in the traditional form or by email. The subject line
must contain the following sentence:
"Homework for DS-2
assigned on DATE from
If I am unable to attend the
class due to unforeseen circumstances such as, e.g., car malfunction, sudden illness,
or family emergency, there will be a cancellation notice posted on my main
web-site: faculty.uml.edu/krybnikov
Required: L. Lovasz,
J. Pelikan
, K. Vestergombi
"Discrete Mathematics", Springer 2003
Recommended: D. Jungnickel
"Graphs, Networks, and Algorithms",
Springer 2005
K. Rosen ``Discrete Mathematics and its
Applications",
edition 5 or 6, Mcgraw-Hill
You are strongly encouraged to take
advantage of additional resources available on the Web.
Exams and Grading
Your grade in the course will be determined by your performance on the homework (15%), three midterms (45%), final exam (30%), and your lecture grade (10%). You can substitute the grade for one of the midterm with your final exam score (weighted by a factor of 0.5 – see the percentage split above). Homework will be given on almost every lecture, but, most of it will not be collected. Some of homework papers will be collected and graded. As a rule, I will not let you know in advance which homework assignments will be collected and which will not be collected. The lecture grade consists of the attendance (50%) and participation (50%) components.
A homework problem is considered mandatory unless specified otherwise. Mandatory homework is necessary for understanding the course material and is essential for understanding the lectures and solving exam problems. You are expected to do all of the mandatory homework. I will also suggest non-mandatory homework problems. You will be able to get extra points for such problems. Problems solved in the book or in class will not be graded and need not be handed in.
I will check non-graded homework only on the basis of individual requests. The same applies to the solutions -- I will solve problems in class or post solutions on this web-site if asked to. Requests should be sent by email and should include not only the number of the problem, but also some reminder about the contents of the problem -- this way I will not have to waist my time searching for the problem in the book.
Attendance is required.
A significant part of your work in this course will take place outside the classroom: it will consist of your working on the homework problems, reading and thinking about the course material, talking to each other, talking to me, etc. It is highly recommended that you also use Internet resources for learning the subject on your own. Therefore, you should expect to work approximately two hours outside of class for every hour we spend in class. You are not in competition for a limited number of good grades. If everyone does well, everyone will get a good grade.
Please ask lots of questions! Interruptions are highly encouraged! If I have not answered your questions during class time or you have new ones, please see me during my office hours or email your questions.
At the end of the course I will decide if the final is to be taken with the aid of books or notes. You should be prepared to take it without aid of books and notes.
Homework
Most of what you learn in this course will be the result of working on exercises that are designed to reinforce key concepts, develop skills, and test your understanding of the material. Before you try an exercise, however, read the corresponding section (sections, if this is a problem from “Review Problems” ) of the textbook. Reading the text will help you review the important concepts before you start on the exercises. Sometimes you will be told to use Internet to learn about things. Some of the exercises are straightforward, others are more difficult.
You are encouraged to talk with your classmates about the homework. However, you should write it yourself and alone.
If you have difficulties, do not waste time --- get help! You can obtain a lot of help on WWW by using, for example, one of the sites recommended on the RESOURCE LINKS page for this course.
I expect you to attend class regularly. Besides being nearly essential for developing your understanding of the material, your regular attendance in class is good for the morale of the class and is indicative of your interest in the subject and your engagement in the course. You are responsible for the material discussed in class and in the assigned reading in the text. In addition, there may be quizzes and other assignments that will be announced in class. Your feedback is essential to the success of the course. Do not hesitate to interrupt me! Although many students are hesitant to interrupt the instructor being afraid “to look stupid or non-competitive”, my experience shows that students who ask the most questions do the best.
Below
is an approximate description of the course contents. Some topics may be
omitted due to time limitations.
Sets and Lists.
Basic Counting:
Permutations. Number of Permutations
Number of Subsets of a
Given Size
Interpretations of binomial coefficients and factorials
Combinations
with Repetitions Allowed.
Distributing Presents,
Distributing Money
Number of Ways to Distribute n Identical
Objects between k Distinct Persons
(combinations with repetitions).
Induction:
Some Inductive Proofs
Methods of Counting:
Inclusion-Exclusion
Methods of Approximate Estimation:
Logarithmic Scale and Use of Logarithms. Change of Base in Logarithms.
Asymptotics of Logarithms
Asymptotic Notation for Complexity: big-O, big-Omega, big-Theta. Big-O and big-Theta as preorders. big-Theta as partial order.
Combinatorial Probability:
Events and Probabilities
Notion of Probability Measure (formal treatment only in the finite case)
Applications of Inclusion-Exclusion Principle in Probability
Measures in Diverse Contexts: there more similarities than
differences between Continuous and Discrete.
Remarks (brief) on Countable and Non-countable Sets.
Repetitions of
an Experiment.
The Twin Paradox (if time permits)
Division with Remainder:
Euclidean Algorithm.
Extended Euclidean Algorithm. Practicing
Proofs by Induction on Euclidean Algorithm. Induction
in Different Parameters. Two Forms of the Principle;
Equivalence between them (without proof). Importance
of Correctness of "Boundary Conditions". Dealing with
non-standard (not 0) initial value: (i) shifting, (ii) giving formal meaning to
degenerate or "non-existing" cases.
Primes:
Divisibility of Integers. GCD and LCM.
Factorization into Primes: Fundamental Theorem of Arithmetic (without proof)
Distribution of Primes
Prime Number Theorem (formulation, history, crude intuition)
Distribution of Primes from the Probabilistic Prospective (very briefly)
Modular Arithmetic:
Fermat’s “Little” Theorem .
Euler's Generalization of Fermat's Theorem (without proof). Notion of coset.
Numbers
in Zm Additive and Multiplicative
Inverses in Zm Use of Extended Euclidean
Algorithm for Finding Multiplicative Inverse modulo m.
Criterion
for the Existence of Multiplicative Inverse modulo m. Chinese
Remainder Theorem.
RSA:
RSA encryption and decryption algorithms. Fast Modular Exponentiation.
Probabilistic Argument for
Applicability of
RSA for content protection
RSA as a secure (?) public key signature system
Discussion of sizes of primes used in modern communication software
Time Complexity:
How long the key should be? What is difficult? Bit complexity. Notion of Turing Machine (with very small examples) Thesis. Distinction between unitape and multitape Turing Machines. Polynomial equivalence of Turing machines. Complexity of primality testing and that of factoring. Complexity of Euclidean Algorithm and its modular version.
Discussion of perceived complexity of RSA; empirical evidence. Mentioning of Polynomiality of Factoring in the present Mathematical Model of Quantum Computer.
Graphs:
Examples. Difference between a graph and a depiction of a graph. Notational conventions. Problem of absence of unified terminology. Simple graphs, directed graphs, etc. Notions of walk, path. Closed walks. Eulerian closed walks. Euler's "even vertex degree" theorem.
Storing Graphs in Computers. Adjacency Matrix, Incidence Matrix, Adjacency List. Size of an adjacency list in robust implementations (example of LEDA). Speed / memory tradeoff.
Greedy algorithm for finding an Eulerian circuit in the recursive form. Benefits and Drawbacks of Recursion. Existence of a general de-recursivization method based on stacks (if time permits). Importance of being able to rewrite a recursive procedure iteratively (e.g. if using a language prohibiting recursion, like Fortran 77 or an Assembly Language). What is greedy in graph theoretic algorithms. Finding a spanning tree by a greedy algorithm. General notion of Graph (with everything allowed). Five-valued logic as a natural language for graph theory.
Notion of graph homomorphism (morphism). Graph homomorphism as an analog of a continuous map from R to R. Isomorphisms. Automorphisms.
Unity of continuous and discrete mathematics.
Hasse
diagrams for posets. Monotonic maps between posets as morphisms of posets. Examples of poset
morphisms. Rooted trees as posets.
Hamiltonian Cycles. Hamiltonian Cycle as an archetype of a hard combinatorial problem. Peterson's graph. Peterson's graph from permutations of (12345). Notion of symmetry of a graph. The group of automorphisms of a graph. Group of Peterson's graph (proving only that S5 is a subgroup of the full group of automorphisms of Peterson's graph). "Law of Small Numbers".
Matchings in Graphs.
Elements of Combinatorial Geometry.
Trees:
Trees, forests. Rooted Trees, Binary rooted trees and binary arithmetic. Spanning Trees. Finding a spanning tree by a greedy algorithm. A spanning tree and the corresponding basis of binary cycle space (informally).
How to Count Trees. Cayley's formula. Cayley's research on asyclic carbohydrates. Trees versus forests.
Importance of trees and forests in statistical learning and, in particular, in bioinformatics.
Prüfer code (with some proofs). How does Prüfer code change under relabeling?