Department of Computer Engineering

Tuesdays 1:00-4:00 PM Room E202

Dr. Monchai Sopitkamon

Office: Room 306

Course office hours Tuesdays 5:00 to 6:00 PM or by appt; e-mail at all times

Phone: 02-942-8555 x 1432

E-mail: fengmcs at ku dot ac dot th (please prefix the subject of your message with 204211)

204211 Home Page

11/10/2005: Final exam will be on chapters 2, 5, 6, and 8

06/21/2005: First assignment has been posted onto http://course.ku.ac.th. Please download the pdf file under the Assignment folder.

204211 is a 3-credit course with no prerequisites. This course aims to introduce students to mathematical thinking and problem solving. Various ideas and techniques from discrete mathematics will be presented along with specific applications in Computer Science. With this parallel approach, students would be able to see the connections between the theory and practice.

List of course topics:

• Propositions and proofs

• Mathematical induction and recursion

• Combinatorics : counting techniques

• Probability

• Number theory : gcd, primality testing, RSA

• Graphs

Homeworks | 25 % |

Quizzes | 10 % |

Midterm | 30 % |

Final | 35 % |

Week 1 | Introduction / Logic / Basic proof techniques (pdf, ppt) |

Week 2 | Induction (pdf, ppt) |

Week 3 | Strong induction and recursion (pdf, pdf2, ppt) |

Week 4 | Recursive definition, Recurrence Relation, Divide and conquer (pdf, ppt) |

Week 5 | Counting: permutation, inclusion-exclusion, pigeonholes (pdf, ppt) |

Week 6 | Counting: binomial coefficients, Pascal’s triangle, Fibonacci numbers |

Week 7 | Probability: concepts, probability, conditional probability (ppt) |

Week 8 | Probability: random variables, expectations, linearity of expectation (pdf) |

Week 9 | Probability: variance, polling and voting |

Week 10 | Midterm |

Week 11 | Recurrence Relations (ppt) |

Week 12 | Number theory: Algorithms, Growth Orders, Complexity, Fermat’s Little Theorem, primarily testing, GCD, RSA (1, 2, 3) |

Week 13: | Graphs: basics, counting trees (ppt, Updated 20/9/48) |

Week 14 | Graphs: connectivity, shortest-path problems |

Week 15 | Final exam (Chapters 2, 5, 6, 8) |

Lecture notes from UC Berkeley's cs70 course

Extra optional reading:

- Notes on distributions [ps] [pdf]
- Lenstra's notes on probability [ps] [pdf].
- For fun: The Infinite Hotel.

First Day of Classes | June 14, 2005. |

No Class | July 12, 2005 |

Midterm | August 2, 2005. |

Last day of classes | September 20, 2005. |

Final exam | September 27, 2005. |

No collaboration is allowed among students in any of the individual exams. Students are allowed to discuss with other students the solution of homework assignments. You may not share written work or programs with anyone else. You may not receive help on homework assignments from students who have taken the course in previous years, and you may not review homework solutions from previous years.

In writing up your homework you are allowed to consult any book, paper, or published material. If you do so, you are required to cite your source(s). Simply copying a proof is not sufficient; you are expected to write it up in your own words, and you must be able to explain it if you are asked to do so. Your proofs may refer to course material and to homeworks from earlier in the semester. Except for this, all results you use must be proved explicitly.

Copying solutions or code, in whole or in part, from other students or any other source without acknowledgment constitutes cheating. Any student found to be cheating in this class will automatically receive an F grade and will also be referred to the Office of Student Conduct.