Discrete Mathematics (CS204C) in **Spring** 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
• Lectures: classroom #112 in building N1
• Schedule: Tuesdays and Thursdays 14h30 to 15h45 (No class on March 1(holiday))
• Language: English only
• Teaching Assistants: Dongseong Seon, Donghyeon Lim, Ivan Koswara
• Office hours: Thursday 4pm~5:30pm at N1#402
• Homework Box: Box#6 in E3-1 near SoC Lounge. Students must submit their assignments into the Homework Box until Tuesday 2pm or submit in class (Tuesday 2:35 pm).
• Attendance: 10 points for missing less than 15% of randomly sampled lectures, 9 when missing <19%, 8 when missing <23%, and so on: 50% or more missed randomly sampled lectures earn you no attendance points. (No need for excused misses, these are accounted for in the free 15%)
• 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 (Thursday, April 19, 13h00-15h45)
    • If your student ID is less than 20170750, go to N1#102 (recitation classroom). If it is bigger than 20170750, go to N1#112 (lecture room).
  • Final exam (Thursday, June 14, 13h00-15h45)
    • (Same as midterm) If your student ID is less than 20170750, go to N1#102 (recitation classroom). If it is bigger than 20170750, go to N1#112 (lecture room).
• Recitation (optional) from 7pm to 8pm in N1 #102:
  • March 8, March 15, March 22, March 29, April 5
  • April 26, May 3, May 10, May 24, May 31

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.

Recitation is on every Thursday 7pm to 8pm in N1, #102. Recitation is optional.

Honor Code + Homework#0 (Due: March 6 2pm in homework box or 2:30pm in class)

Homework #1 (Due: March 13, 2pm in homework box or 2:30pm in class)

Recitation #1 problems and (partial) solutions

Homework #2 (Due: March 20, 2pm in homework box or 2:35pm in class) (updated March 16, 6pm)

Recitation #2 problems and solutions

Homework#3 (Due: March 27, 2pm in homework box or 2:35pm in class) (updated March 22, 10:17pm)

Recitation #3 problems and (partial) solutions

Homework #4 (Due: April 3, 2pm in homework box or 2:35pm in class)

Recitation #4 problems and (partial) solutions

Homework #5 (Due: April 10, 2pm in homework box or 2:35pm in class)

Recitation #5 problems and (partial) solutions

Homework #6 (Due: May 1, 2pm in homework box or 2:35pm in class)

Homework #7 (Due: May 8 ⇒ May 15, 2pm in homework box or 2:35pm in class)

Homework #8 (Due: May 15 ⇒ May 17, 2pm in homework box or 2:35pm in class)

Homework #9 (Due: May 24, 2pm in homework box or 2:35pm in class)

Homework #10 (Due: May 31, 2pm in homework box or 2:35pm in class)

Homework #11 (Due: June 7, 2pm in homework box or 2:35pm in class)

Late homework submissions will be ignored for grading. ⇒(Changed) 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.

• KAIST Learning Management System