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.


Synopsis (tentative)

  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

  6. Combinatorics and Counting
  7. Discrete probabilities
  8. Recursion
  9. Graph Theory
  10. Trees/Automata


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. Submissions won't be returned.

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


Academic Honesty

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.


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