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.

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.

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 16. Mar 28, 2017. Fermat’s little theorem. RSA.
Reading: The previous reading, and also LL: pp.67-68 for the fundamental theorem of arithmetic.

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

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.