This is an old revision of the document!


Discrete Mathematics (CS204C) in Fall 2018 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 and Svetlana Selivanova
  • Lectures: classroom #111 in building N1
  • Schedule: Mondays and Wednesdays 14h30 to 15h45
  • Language: English only
  • Teaching Assistant: Dongseong Seon, Hyun Woo Lee, Seungwoo Schin
  • Office hours: TBA
  • Homework Box: TBA
  • Quiz: On random lecture sessions we will conduct short written quizzes.
  • Homework: Of the 3 weekly homework problems, a random one will be graded.
  • Grading: The final grade will (essentially) be composed as follows: Quiz: 20%, Homework 20%, Midterm exam 30%, Final exam 30%.
  • Exams: All exams are closed book!
    • Midterm exam (Wednesday, October 17, 13h00-15h45)
    • Final exam (Wednesday, December 12, 13h00-15h45)
  1. Basic Structures: Sets
  2. Logical Foundations, propositions, quantifiers
  3. Proof strategies: constructive, indirect/contradiction, cases, induction
  4. Relations, order, equivalence
  5. Functions, sequences, strings
  6. Elementary algorithms and their analysis

    Mid-term

  7. Combinatorics
  8. Advanced Counting
  9. Discrete probabilities
  10. Recursion
  11. Graph Theory
  12. Trees
  13. 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 please bind them. Submit them in the E3-1, first floor, box #6 near SoC Lounge. Submissions won't be returned.

Will accept late submission with 50% point deduction by the end of the class. 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.