Discrete Structures II    


Fall 2008


Instructor: Konstantin (=Constantine) Rybnikov
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 YourFirstName YourLastName"


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.


Course Structure

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.  


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
            Stirling Formula   Binomial Formula and Pascal's Triangle.

            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).


Some Inductive Proofs



Methods of Counting:


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.  



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 encryption and decryption algorithms. Fast Modular Exponentiation.

Probabilistic Argument for Applicability of Fermat's Little Theorem

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.



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, 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?