204211 - Discrete Mathematics - 1st Semester 2005

Kasetsart University
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
 

ANNOUNCEMENTS :

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.

DESCRIPTION :

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



GRADING POLICY:
Homeworks 25 %
Quizzes 10 %
Midterm 30 %
Final 35 %

Back to the top


SYLLABUS:

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

READINGS:

Discrete Mathematics and its Applications, 5th Edition (Kenneth H. Rosen, McGraw-Hill, Inc., New York, 2003) is recommended but not required.

Lecture notes from UC Berkeley's cs70 course

Extra optional reading:

Back to the top

IMPORTANT DATES :

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

IMPORTANT RULES :

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


Last updated: June 11, 2005