TA: | Jade Cheng 成玉 (yucheng@hawaii.edu) |

Instructor: | Kyungim Baek (kyungim@hawaii.edu) |

Course: | Discrete Mathematics for Computer Science II |

TA Office: | POST Building Room 303-3 (cubicle 3) |

TA Hours: | Tuesday 11:00 to 12:00 |

Thursday 11:00 to 12:00 |

Recurrence relations and their solutions, divide-and-conquer relations, equivalences and partitions, elementary notions of the graph theory, connectedness, subgraphs and isomorphisms of graphs, shortest path problems, trees and their applications, tree traversal, spanning trees, Boolean algebra, introduction to formal languages, and automata theory.

Date | Topics | Deliverable |
---|---|---|

Week 1 (8/24, 26) | Introduction, Programming Correctness | |

Week 2 (8/31, 9/2) | Recurrence relation, Divide-and-Conquer | Homework 0 |

Week 3 (9/9) | Inclusion and Exclusion, Relations | |

Week 4 (9/14, 16) | n-ary Relations, Closure of Relations | Homework 1 |

Week 5 (9/21, 23) | Equivalence Relations, Exam I | |

Week 6 (9/28, 30) | Partial Ordering | Homework 2 |

Week 7 (10/5, 7) | Graphs: Representation & Isomorphism | |

Week 8 (10/12, 14) | Graph Connectivity, Euler and Hamiltonian Paths | Homework 3 |

Week 9 (10/19, 21) | Shortest Path Problems, Exam II | |

Week 10 (10/26, 28) | Planar Graphs, GraphColoring, Trees, Tree Traversal | Homework 4 |

Week 11 (11/2, 4) | Spanning Trees, Minimum Spanning Trees | |

Week 12 (11/9) | Boolean Algebra | Homework 5 |

Week 13 (11/16, 18) | Boolean Algebra, Exam III | |

Week 14 (11/23, 35) | Languages and Grammars, Finite-State Machines | |

Week 15 (11/30, 12/2) | Language Recognition | Homework 6 |

Week 16 (12/7, 9) | Turing Machines, Review |

Homework assignments: 25%

Exams: 45%

Final Exam: 30% (

*Monday Dec. 14, 9:45 - 11:45*)

*No makeup exams*. A missed exam will be credited as a zero.

A: 88 ≤ total grade

B: 77 ≤ total grade < 88

C: 65 ≤ total grade < 77

D: 55 ≤ total grade < 65

F: 0 ≤ total grade < 55

If you hand in late work without the approval of the instructor, you may receive zero credit. Homework is due at the beginning of class on the assigned due date.

You are allowed to discuss strategies for solving assignments with other students, but collaboration on solutions/code and the sharing or copying of solutions/code is not allowed. This policy will be strictly enforced.

*Cheating will be punished with an F grade and reported to the dean*. (This policy will be equally applied to those who copy other’s work and those who allow their work to be copied.)

You may consult public literature (books, articles, etc.) for information, but you must cite each source of ideas you adopt.

- recitation-01.pdf
- recitation-02.pdf
- recitation-03.pdf
- recitation-04.pdf
- recitation-05.pdf
- recitation-06.pdf
- recitation-07.pdf
- recitation-08.pdf
- recitation-09.pdf
- recitation-10.pdf
- recitation-11.pdf
- recitation-12.pdf
- recitation-13.pdf
- recitation-14.pdf

The course text book — K. H. Rosen’s

*Discrete Mathematics and its Applications*, 6^{th}EditionLauima — The Learning & Collaboration Server for the University of Hawaii.