Back
to the top 
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
Back
to the top
| Homeworks | 25 % |
| Quizzes | 10 % |
| Midterm | 30 % |
| Final | 35 % |
Back
to the top
| 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) |
Back to
the top
Lecture notes from UC Berkeley's cs70 course
Extra optional reading:
Back to
the top
| 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. |
Back to
the top
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.
Back
to the top