Fall 2017

Sukumar Ghosh, 201P Maclean Hall, 319-335-0738, sukumar-ghosh@uiowa.edu

Class meeting time: 10:30 - 11:20 AM MWF in 112 MH (Macbride Hall)

Semester hours: 3

Office hours: 2:30-3:45 PM Mondays and Fridays, or by appointment

1 Junbin Ma, junbin-ma@uiowa.edu 101N MLH, Office hrs: W 2:00-3:00 PM, F 4.00-5.00 PM

2 Xin Jin, xin-jin@uiowa.edu 101N MLH, Office hrs: M 11:30AM-12:30PM, Th 11:30AM-12:30PM

Discrete Mathematics and Its Applications (7th Edition), by Rosen, McGraw-Hill, ISBN 978-0-07-338309-5

This is an introduction to mathematical methods used in studying problems of computer science. The topics covered include: mathematical logic; proof techniques, especially mathematical induction; set theory, functions, and relations; procedures, recursion, discrete probability; recurrence relations; analysis of algorithms; counting methods, permutations and combinations; graphs and trees.

There will be six home assignments (3% x 6=18%), four quizzes (5% x 4 = 20%), two midterm exams (16% x 2 = 32%) and a final exam (30%). Quizzes and midterm examinations will be held during the class period. The duration of each quiz is 15 minutes and will be given at the beginning of a class period. One of the four quizzes will not be announced ahead of time.

Exam 2: October 23, 2017, Monday (in class)

Final Exam date to be announced

Letter grades will be tentatively assigned roughly as follows:

A+ = 95-100 B+ = 80-84 C+ = 65-69 D+ = 50-54 A = 90-94 B = 75-79 C = 60-64 D = 45-49 A- = 85-89 B- = 70-74 C- = 55-59 D- = 40-44 F = 0-39

The instructor reserves the right to make minor modifications in the grading scale.

Course webpage http://www.cs.uiowa.edu/~ghosh/1917.html

Assignments will also be posted on CANVAS, and completed assignments must be submitted via ICON/CANVAS. Late assignments will not be accepted without prior approval.

August 21-25, 2017 Week 1. Introduction and Scope Read Chapters 1.1-1.3 |

August 28-September 1, 2017 Week 2. Logic and Proof Read Chapters 1.4-1.8 |

September 4-9, 2017 Week 3. Sets and Functions Read Chapters 2.1-2.3 |

September 11-16, 2017 Week 4. Sequences and Sums Read Chapters 2.4 |

September 18-23, 2017 Week 5. Algorithms and Complexity Read Chapters 3.1-3.3 |

September 25-October 6, 2017 Weeks 6-7. Modular Arithmetic, GCD, Prime numbers, Cryptography Read Chapters 4.1-4.6 |

October 9-13, 2017 Week 8. Induction and Recursion Read Chapters 5.1-5.4 |

October 16-20, 2017 Week 9. Counting Read Chapters 6.1-6.5 |

October 23-November 3, 2017 Week 10-11. Discrete Probability Read Chapters 7.1-7.4 |

November 6-10, 2017 Week 12. Advanced Counting Tower of Hanoi example Read Chapters 8.1-8.2, 8.5 |

November 13-17, 2017 Week 13. Relation Read Chapters 9.1-9.6 |

November 27-December 8, 2017 Week 14-15. Graphs and Trees Read Chapters 10 and 11 |