General Information

• Instructor: Ilia Vovsha (iv2121 at columbia dot edu)
  
• Office Hours: Thu. 1:00pm-3:00pm (850 Interchruch Center)
  
• Lecture: Mon & Wed 11:40-12:55am
  
• Classroom: 417 International Affairs Building (Altschul Auditorium)
  


• TAs (email @columbia.edu -- unless specified otherwise):
      Venkata Sreeram Joopudi (vnj2101)
      Dylan Yiyang Qiu (yq2183)
      Jeffrey Scott Handler (jsh2190)
      Prachi Shukla (ps2829)
      Rishina Tah (rt2545)
      Adam Joseph Incera (aji2112)
      Rhea Goel (rg2936)
      Michael Jay Saltzman (mjs2287)
      Natasha Kenkre (nsk2141)
  
  
  
• TA Office Hours (TA Room, Mudd 122 -- unless specified otherwise):
  
  Mon.   8:00am-10:00am   (Rishina)
  Mon.   10:00am-11:00am   (Prachi)
  Mon.   2:00pm-4:00pm   (Michael)
  Mon.   6:00pm-6:50pm   (Jeffrey)
  Tue.   10:00am-11:00am   (Prachi)
  Tue.   2:40pm-3:50pm   (Jeffrey)
  Tue.   6:00pm-8:00pm   (Natasha)
  Wed.   9:00am-11:00am   (Dylan)
  Wed.   4:00pm-6:00pm   (Rhea)
  Thu.   4:30pm-6:30pm   (Adam)
  Fri.   3:00pm-5:00pm   (Sreeram)
  
  
• Textbook:
  
  • K. H. Rosen, Discrete Mathematics and its Applications, 7th Edition, McGraw-Hill (available for download on courseworks)
    
  • Mathematics for Computer Science by Eric Lehman, F. Thomson Leighton, Albert R. Meyer, revised 2013 (freely available online, on courseworks as well).
    
  
  

Lectures

Rough list of topics to be covered in this class: Syllabus

Lecture Notes:

• Lectures 1-4:  Notes
  Content: Logic and Proofs
      Readings: Chapters #1 (Rosen); #1-3 (Lehman)
      Topics: Propositional Logic, Operators, Truth Tables, Equivalences, Rules of Inference, Quantifiers, Proofs.
  
• Lectures 5-7:  Notes
  Content: Set Theory
      Readings: Ch. #2 (Rosen); #4, #7 (Lehman)
      Topics: Sets, Set operations, Sequences, Functions, Relations, Cardinality, Infinite sets.
  
• Lectures 8-10:  Notes
  Content: Induction, Recursion, and Algorithms
      Readings: Ch. #3, #5 (Rosen); #5-6 (Lehman)
      Topics: Ordinary & strong induction, Recursion, Strings, Algorithms, Big-O notation, Complexity, Recursive Algorithms.
  


• MIDTERM #1: see courseworks for sample midterm and solutions.    
  


• Lectures 11-14:  Notes
  Content: Number Theory
      Readings: Ch. #2 (Rosen); #8 (Lehman)
      Topics: Cryptography, Divisibility, Primes, Greatest Common Divisor, Euclidean Algorithm, Modular Arithmetic, Euler's totient, RSA Cryptosystem.
  
• Lectures 15-17:  Notes
  Content: Counting
      Readings: Ch. #6.1-6.5 (Rosen); #14 (Lehman)
      Topics: Counting rules, Permutations and Combinations, Sequences, The Pigeonhole Principle, Binomial Theorem, Pascal's Identity, Combinatorial Proofs, Inclusion-Exclusion.
  
• Lectures 18-19:  Notes
  Content: Probability
      Readings: Ch. #7 (Rosen); #16-18 (Lehman)
      Topics: Probability spaces & events, Measures, Conditional probability, Distributions, Bayes' Theorem, Random variables, Expected value, Variance.
  


• MIDTERM #2: see courseworks for sample problems and solutions
  


• Lectures 20-21:  Notes 1,   Notes 2
  Content: Relations
      Readings: Ch. #8.1-8.4 and 9 (Rosen); #15, 21 (Lehman)
      Topics: Recurrence systems and types, Generating functions, Relation properties, Equivalence classes, Digraphs, Partial orders.
  
• Lectures 22-25:  Notes
  Content: Graphs
      Readings: Ch. #10 (Rosen); #11,12 (Lehman)
      Topics: Graph terminology, Graph types & representation, Isomorphism, Connectivity, Eulerian Hamiltonian and planar graphs, Coloring.
  

Homework

Instructions:

Please see the general instructions first.
All HWs are due at 5:00pm. There is a designated box in the TA room where you can drop off your set.
Solutions are posted on courseworks (resources page) five days after the due date.

Problem Sets:

1. Due date: Feb. 4th, 5:00pm.   Cover page,   Problem set
   
2. Due date: Feb. 25th, 5:00pm.   Cover page
   
3. Due date: Mar. 25th, 5:00pm.   Cover page
   
4. Due date: Apr. 8th, 5:00pm.   Cover page
   
5. Due date: Apr. 23rd, 5:00pm.   Cover page
   
6. Due date: Apr. 30th, 5:00pm.   Cover page
   

Exams

All exams are open book and open notes. See policy below. Sample problems and exam solutions will be posted on courseworks.

• Midterm #1: covers material from lectures 1-10
    Date:   Wed. Mar. 4th
  


• Midterm #2: covers material from lectures 11-18
    Date:   Wed. Apr. 15th
  


• Final: emphasizes material not covered in the midterms
    Date:   Friday, May 8th, 9:00am - 12:00pm at IAB 417
  

Grading

You can read about the grading policy and other details here: Policy