Discrete Structures, CSCI-150.

Lecture 1. Jan 30, 2017. Propositional Logic.
Reading: R(ed6): 1.1-1.2; R(ed7): 1.1-1.3.
HW1. Due Monday, Feb 6. (Notice that only problems 2, 3, and 5 will be graded; you don’t have to write your solutions for the other problems).

Lecture 2. Feb 1, 2017. Satisfiability and Rules of Inference. [handout].
Reading: R(ed6): 1.5; R(ed7): 1.6.
Useful links: Tutorial. You may also read more in depth on Natural Deduction proofs, it’s using tree-like proof structure instead of the linear one, but fear not.

Also, you can play this logical game: http://incredible.nomeata.de/, where you are constructing proofs out of blocks (an example). Those blocks are essentially the inference rules we learned in Lecture 2, but you are provided with only some of those rules.

Lecture 3. Feb 6, 2017. Predicates and Quantifiers.
Reading: R(ed6): 1.3-1.4; R(ed7): 1.4-1.5.
HW2. Due Wednesday, Feb 15.

Practice exam problems from the previous semesters were posted on Blackboard (in the Course Materials section).

Lecture 4. Feb 8, 2017. Proofs.
Reading: LL: Chapter 1; R(ed6): 1.6-1.7; R(ed7): 1.7-1.8.

Lecture 5. Feb 15, 2017. Counting. Sets.
Reading: R(ed6): 5.1; R(ed7): 6.1.
HW3. Due Wednesday, Feb 22.

Lecture 6. Feb 22, 2017. Permutations and Combinations. The Pigeonhole Principle..
Reading: R(ed6): 5.1; R(ed7): 6.1.
HW4. Due Monday, Feb 27.

A video about the 6 persons theorem: Friends and Strangers Theorem.

Lecture 7. Feb 27, 2017. Binomial Theorem. Combinations with repetition.
Reading: R(ed6): 5.4-5.5; R(ed7): 6.4-6.5.

Lecture 8. Mar 1, 2017. Counting. Problem solving. [problem set].
HW5. Due Monday, Mar 6.

Lecture 9. Mar 6, 2017. Induction.
Reading: LL: Chapter 2; R(ed6): 4.1; R(ed7): 5.1.

Here’s a very nice example of a nested inductive proof: Buckets of fish by Joel Hamkins. (In a nested induction proof, you are using another induction argument within the inductive step. It is not going to be in the tests, but it’s a nice example so it’s recommended to read.)

Lecture 10. Mar 8, 2017. Recurrences.
Reading: LL: Chapter 12; R(ed6): 4.4; R(ed7): 5.4.
Towers of Hanoi
HW6. Due Monday, Mar 13.

Lecture 11. Mar 13, 2017. Fibonacci Numbers. Solving Linear Recurrences.
Reading: LL: Chapter 13; R(ed6): 7.2; R(ed7): 8.2.

Lectures 12 and 13. Mar 15, 2017. Strong Induction. Recursion in Mathematics and Programming. Source code in Julia: sum.jl, fact.jl, fib.jl, mset.jl, graph.jl, lsys.jl, turtle.jl.

• Here’s a nice video on L-systems rewriting: Doodling in Math Class: DRAGONS.
• Another interesting link: “Context-free art” is a program for creating images using a simple declarative/recursive description language. See some examples, they are very cool!

No homework this week, but you can do supplementary exercises on linear recurrences (and there is a recursive programming exercise there as well if you are interested).

Midterm I. Mar 20, 2017.
will cover lectures 1 through 11 (until and including linear recurrences).
There are practice tests posted on Blackboard. No notes, no textbooks allowed. However, you will be provided with a formula sheet with all logical identities and inference rules.
Midterm 1 - Statistics.

Lecture 14. Mar 22, 2017. Intro to Number Theory.
Reading: Lecture notes by Prof. Saad Mneimneh;
LL: Chapters 4 and 5; R(ed6): 3.4-3.5; R(ed7): 4.1-4.3.
HW7. Due Monday, Mar 27.

Lecture 15. Mar 27, 2017. Modular arithmetic.
Reading: the same.
Source code of the extended Euclid’s algorithm in C.

Lecture 15. Mar 29, 2017. Modular arithmetic and Extended Euclidean algorithm (continued).
Reading: the same.
HW8. Due Monday, Apr 3.

Lecture 16. Apr 3, 2017. Fermat’s little theorem. RSA.
Reading: The previous reading, and also LL: pp.67-68 for the fundamental theorem of arithmetic.

Lecture 17. Apr 5, 2017. Sets. Ordered pairs.
Reading: R(ed6): 2.1-2.2; R(ed7): 2.1-2.2.
HW9. Due Wednesday, Apr 19.

Lecture 18. Apr 19, 2017. Relations. Functions. Bijection and counting.
Reading: R(ed6): 2.3, 8.1; R(ed7): 2.3, 9.1; LL: Chapter 14.
Also: Bijections by Yufei Zhao.

Lecture 19. Apr 20, 2017. Partial orders.
Reading: LL: Chapter 9. R(ed6): 8.1, 8.6; R(ed7): 9.1, 9.6.
HW10. Due Wednesday, Apr 26.

Lecture 20. Apr 24, 2017. Graphs. Bipartite graphs. Paths.
Reading: R(ed6): 9.1-9.3, 9.8; R(ed7): 10.1-10.3, 10.8; LL: Chapters 6, 7.

Lecture 21. Apr 26, 2017. Paths. Connectivity. Euler and Hamilton Paths. Planar graphs.
Reading: R(ed6): 9.4-9.7; R(ed7): 10.4-10.7; LL: Chapters 6, 7.
The Wolverine Problem and Graph Coloring [video].
HW11. Due Monday, May 8.

May 1, 2017. There is no class on Monday. The midterm is on Wednesday.

Midterm 2. May 3, 2017.

• Covers lectures from 14 to 21.
• For this exam, you can prepare a formula sheet (a standard piece of paper, Letter size or A4), you can write on both sides. It must be made individually by you. The formula sheet should be handed in after the exam.

Lecture 22. May 8, 2017. Trees. Huffman coding.
Reading: R(ed6): 10.1-10.2; R(ed7): 11.1-11.2; LL: Chapters 6, 7.

Lecture 23. May 10, 2017. Probability.
No slides, only supplementary notes.
Reading: R(ed6): 6.2 ; R(ed7): 7.2. LL: Chapters 18, 19.
HW12. Due Wednesday, May 17.

Lecture 24. May 15, 2017. Probability (Continued). Review Session.

Lecture 25. May 17, 2017. Projects Presentation. Review Session.

Final exam. May 24, 2017. Same room. 7:30 – 9:30pm.

Possible Project Topics.

[Discussion Board] <- you may ask questions here

Syllabus

Mon, Wed, 8:25 - 9:40 pm. Hunter North C107.
Office hours: after the class or by appointment.

Instructor: Alexey Nikolaev
Website: http://a-nikolaev.github.io/ds/
Email: a(my last name)@gradcenter.cuny.edu
Office: HN 1000C

Literature

1. Rosen “Discrete Mathematics and its Applications” edition 6 or 7.
2. Lehman and Leighton “Mathematics for Computer Science” (2004).

Grading Policy

Homeworks once a week. No late homeworks accepted. Homeworks must be handed in at the beginning of the class.

Distribution
HWs: 25%
Midterm I + Midterm II + Final: 37.5% + 37.5%.

The Final is cumulative. The worst exam out of three will be dropped, so the total final score is computed as follows:

X = HW * 0.25 + MAX{(M1 + M2), (M1 + F), (M2 + F)} * 0.5 * 0.75

However, you still have to attend and write the final exam, even if you already have 100% for the midterms.

Project
An optional project is a possibility to improve your grade, and (hopefully) do something fun. More details about projects & possible topics.

Tentative Course Content

Jan 30 (Mon). Propositional Logic.
Feb 1 (Wed). Satisfiability and Rules of Inference.
Feb 6 (Mon). Predicates and Quantifiers.
Feb 8 (Wed). Proofs.

Feb 13 (Mon). College is closed.
Feb 15 (Wed). Counting. Intro. (Classes follow Monday schedule.)
Feb 20 (Mon). College is closed.
Feb 22 (Wed). The Pigeonhole Principle. Permutations and Combinations.
Feb 27 (Mon). Binomial Theorem. Combinations with repetition.
Mar 1 (Wed). Counting. Practice session.

Mar 6 (Mon). Induction.
Mar 8 (Wed). Recurrences.
Mar 13 (Mon). Fibonacci Numbers. Solving Linear Recurrences.
Mar 15 (Wed). Strong Induction. Recursion in Mathematics and Programming.

Mar 20 (Mon). Midterm 1.

Mar 22 (Wed). Intro to Number Theory.
Mar 27 (Mon). Modular arithmetic.
Mar 29 (Wed). Modular arithmetic and Extended Euclidean algorithm.
April 3 (Mon). Fermat’s little theorem. RSA.
April 5 (Wed). Sets. Ordered pairs.

April 10 - April 18. Spring recess.

April 19 (Wed). Relations. Functions. Bijection and counting.
April 20 (Thr). Relations and partial orders. (Classes follow Monday schedule.)
April 24 (Mon). Graphs. Bipartite graphs. Paths.
April 26 (Wed). Paths. Connectivity. Euler and Hamilton Paths. Planar graphs.
May 1 (Mon). Trees. Huffman coding.

May 3 (Wed). Midterm 2.

May 8 (Mon). Probability.
May 10 (Wed). Conditional Probability. Independent Bernoulli trials. Expected value.
May 15 (Mon). Infinity. Countable sets. Diagonalization.
May 17 (Wed). Review session.

May 24 (Wed). Final Exam. Same room. 7:30 – 9:30pm.