CS2210:0001 Discrete Structures
Fall 2017

Instructor

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

Teaching Assistants

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

Textbook

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

Course Outline

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.

Tests and assignments

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.

Examination Schedule Exam 1: September 25, 2017, Monday (in class)
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.

Lecture Notes

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 8. Counting
Read Chapters 6.1-6.5