Discrete Mathematics (CS204C) in Fall 2017 at KAIST's School of Computing

Discrete Mathematics is the background of digital computers:
the mathematical foundation for specifying program languages and problems, and for describing, analyzing, and verifying their algorithmic solutions.

As opposed to computing with continuous data (such as real numbers), it is concerned with discrete structures such as integers, finite sequences, graphs, and also algorithms themselves — as well as with their (e.g. combinatorial) properties.

• Lecturer: Martin Ziegler
• Lectures: classroom #1101 in building E3
• Schedule: Wednesdays and Fridays 2:30pm to 3:45pm
• Language: English only
• Teaching Assistants: Chansu Park, Dongsong Seon, Donghyeon Lim
• Office hours: Tue 18:30-20:00 (Other slot is replaced to the recitation class)
• Homework Box: No. 18 @ E3-1 3rd floor(next to the elevator). Students must submit their assignments into the Homework Box. (Homework 1~)
• Attendance: 10 points for missing less than 5 lectures, 9 when missing 5 lectures, 8 when missing 6, and so on: 14 or more missed lectures earn you no attendance points.
• Grading: The final grade will (essentially) be composed as follows: Homework 20%, Midterm exam 30%, Final exam 40%, Attendance 10%.
• Exams: All exams are closed book.
  • Midterm exam (Wednesday, Oct 18, 13:00~15:45 or shorter) @ E3-1 #1101
  • Final exam (Wednesday, Dec 13, 13:00)

1. Basic Structures: Sets, Functions, Sequences
2. Logical Foundations, propositions, quantifiers
3. Proof strategies: constructive, indirect/contradiction, cases, induction
4. Relations, order, equivalence
5. Elementary algorithms and their analysis
   
   Mid-term
   
   
6. Combinatorics and Counting
7. Discrete probabilities
8. Recursion
9. Graph Theory
10. Trees/Automata
    
    Final

Regularly recalling, applying, and extending the definitions, theorems, and proofs from the lecture is essential for comprehension and successful study. Therefore consider it as a courtesy that we will create homework assignments and publish them on this web page.

Write your submission number (like “Assignment #?”) to make TAs easily recognize the submissions and submit them in box #18 near E3-1 elevator. Submissions won't be returned.

• Honor Code + Homework 0 (Due: 14:40 September 8)
• Homework 1 (Due: 14:40 September 15) (Changed due to the coverage, 16:00 September 8)
• Homework 2 (Due: 14:40 September 22) (Condition edited on Problem 2©, 03:40 September 17)
• Homework 3 (Due: 14:40 September 29) (Hints Added on Problem 2, 16:05 September 23)
• Homework 4 (Due: 14:40 Octover 13)
• Homework 5 (Due: 23:59 November 12) (Edited, 18:30 November 10)
• Homework 6 (Due: 14:40 November 17)
• Homework 7 (Due: 14:40 November 24)
• Homework 8 (Due: 09:00 December 4) (Edited at 23:23 November 24)

In collaboration with CS204A and CS204B, TAs will offer optional recitation classes: Wednesdays 7~8pm #1220, starting September 6.
From November on, attending recitation on time will be counted as 5% bonus: 1% for each of Nov.08, Nov.15, Nov.22, Nov.29, Dec.06

Late homework submissions will be ignored (for grading: you could still win an award). Copied homework solutions receive 0 points. Cheating during the exam results in expulsion and 0 points.

Students will be required to sign an Academic Honour Code together with their first homework submission.

• Kenneth H. Rosen: Discrete Mathematics and Its Applications (mandatory! any edition)
• Richard Johnsonbaugh: Discrete Mathematics, Pearson.
• David J. Hunter: Essentials of Discrete Mathematics, Jones&Bartlett.

For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course.

• KAIST Learning Management System