CS2210:0001 (22C:019:001) Discrete Structures
Spring 2015

Instructor

Sukumar Ghosh, 201P Maclean Hall, 319-335-0738, sukumar-ghosh@uiowa.edu
Class meeting time: 2:00 - 3:15 PM TTh in 110 MLH
Semester hours: 3
Office hours: 3:30-5:00 PM Tuesdays and Thursdays, or by appointment

Teaching Assistants

1. Thamer Alsulaiman, Office and Office hours to be announced.
2. Chao Yang, Office and Office hours to be announced

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 (4% x 6=24%), four quizzes (4% x 4 = 16%), two midterm exams (15% x 2 = 30%) and a final exam (30%).

Exam 1: February 24, 2015, Tuesday, (in class)
Exam 2: March 31, 2015, Tuesday, (in class)
Final Exam: May 13, 2015, Wednesday, 3:00-5:00PM in LR2 VAN

Letter grades will be assigned roughly as follows:

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

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

First day handout
Frequently asked questions
Tentative Course Plan

Home Assignments

Homework 1 Assigned, see ICON
Homework 2 Assigned, see ICON
Homework 3 Assigned, see ICON
Homework 4 Assigned, see ICON
Homework 5 Assigned, see ICON
Homework 6 To be assigned

Lecture Notes

January 20-23, 2015
Week 1. Introduction and Scope
Read Chapters 1.1-1.3
January 26-30, 2015
Week 2. Logic and Proof
Read Chapters 1.4-1.8
February 2-6, 2015
Week 3. Sets and Functions
Read Chapters 2.1-2.3, 2.5
February 9-13, 2015
Week 4. Sequences and Sums
Read Chapters 2.4
February 16-20, 2015
Week 5. Algorithms and Complexity
Read Chapters 3.1-3.3
February 23-27, 2015
Week 6. Integers, Modular Arithmetic and Cryptography
Read Chapters 4.1-4.2
March 1-5, 2015
Week 7. Integers, Modular Arithmetic and Cryptography
Read Chapters 4.3-4.6
March 8-12, 2015
Week 8. Induction and Recursion
Read Chapters 5.1-5.4
March 22-26, 2015
Week 9. Recursion, Counting
Read Chapters 6.1-6.5
March 29-April 3, 2015
Week 10. Counting
Read Chapters 6.1-6.5
April 6-April 10, 2015
Week 11. Discrete Probability
Read Chapters 7.1-7.4
April 13-April 17, 2015
Week 12. Advanced Counting
Read Chapters 8.1-8.2, 8.5
April 20-April 24, 2015
Week 13. Relations
Read Chapters 9.1-9.3
April 27-May 8, 2015
Week 14-15. Graphs and Trees
Read Chapters 10.1-10.8, 11.1-11.5