4190.101 Discrete Mathematics (2016 Spring)

Course Information
  • Lecturer: Gunhee Kim [email]
  • Location: 301 building 203 room
  • Time: Mon/Wed 11:00 AM ~ 12:15 PM
  • Teaching Assistants: Jongho Park, Yunseok Jang
  • Email: ta.dm@vision.snu.ac.kr
  • Office Hour: Mon 9:30~11:00 AM
  • Textbook: Discrete Mathematics and Its Applications, Kenneth Rosen (7th GLOBAL edition), McGraw Hill

Grade

  • 7 homework assignments (20%).
  • 3 Exams: Midterm I (25%), Midterm II (25%), Final (30%).
  • Attendance: -1 (-0.5) per absence (out of 100) randomly at the beginning of every class.
  • Cheating includes copying other students' solutions, googling for solutions, and omitting key citations of references. Anyone who cheats on any assignment or exam will receive a score of zero.
  • Final grads will be assigned based on the earned scores. A: 30%, B: 40%, C or below: 30%.
    (subject to change according to the University's rule). 
Policy
  • Class notes and assignments will be posted via ETL
  • If you have any homework questions, please ask TAs or use the board of ETL.
  • Students are allowed to discuss with others about the problems, but must hand in their own answers. 
  • Homework should be submitted at the beginning of class on due date. 
  • Within 24 hours after the deadline, you can still submit the homework directly to TAs, but your credits will be half.

Schedule


Date

Lecture Contents

Homework

3/2  Course Introduction 
Propositional logic (sec 1.1)

3/7 Propositional equivalence (sec 1.2, 1.3) 

3/9 Predicate logic and nested quantifiers (sec 1.4 and 1.5)

3/14 Rules of inference (sec 1.6) HW1 out
3/16 Mathematical proofs and proof strategies  (sec 1.7 and 1.8)
3/21 Sets (sec 2.1 and 2.2) HW1 due / HW2 out
3/23 Functions and sequences (sec 2.3 and 2.4)
3/28 Cardinality and matrices (sec 2.5 and 2.6) HW2 due / HW3 out 
3/30  Algorithms (sec 3.1)
4/4 Midterm I HW3 due
4/6  The growth of functions (sec 3.2)
4/11 Complexity of algorithms (sec 3.3)
4/13  Election day (No class)

4/18 Mathematical induction and strong induction (sec 5.1 and 5.2) HW4 out
4/20 Recursive definitions (sec 5.3)
4/25 Recursive algorithms (sec 5.4) HW4 due
4/27 Counting: basic counting rules (sec 6.1 and 6.2) HW5 out
5/2 Counting: permutations and combinations (sec 6.3, 6.4, and 6.5)
5/4 Discrete probability (sec 7.1 and 7.2) HW5 due
5/9 Midterm II

5/11 Bayes' theorem (sec 7.3 and 7.4) HW6 out
5/16 Advanced counting (sec 8.1 and 8.2)
5/18 Advanced counting (sec 8.3, 8.5, and 8.6) HW6 due
5/23  Relations I (sec 9.1 and 9.3) HW7 out
5/25 Relations II (sec 9.5 and 9.6)
5/30 Graphs (sec 10.1 and 10.2)  HW7 due
6/1 Graph isomorphism and connectivity (sec 10.3 and 10.4)
6/6 Review  
6/8 Final Exam