This page, http://www.cs.uiowa.edu/~hzhang/c19/, is always under construction.

22C:19 - Descrete Structures, Spring 2006

Prerequisites

Grades of C- or higher in Computer Science I.

12:30-13:20 MWF, Room 213, MacLean Hall

Attention The time for the final exam will be 2:15-4:15pm, Wednesday, May 10 2006.
Please use ICON to check your scores.
Homework 12 is assigned.

I need to hear from anyone who has a disability, which may require some modification of seating, testing or other class requirements so that appropriate arrangements may be made. Please contact me during my office hours.

Textbooks

• D.S. Malik and M.K. Sen, Discrete Mathematical Structures: Theory and Applications, Course Technology, 2004

Course Syllabus

Students should be prepared to put in considerable time and effort into reading to become familiar with these topics and gain experience with these techniques. At the end of the semester, students should have the knowledge required to identify areas which they would like to investigate in more depth in related courses.

Homeworks (12 homeworks, each counts for TWO percent of final score)

LATE-DUE HOMEWORK ARE NOT ACCEPTED.

• Homework 1: (due 01/27/06)
  Page 24-25: 2, 6, 10, 12, 14, 16, 20, 24, 26, 28(a), 30.
  Sample solution
• Homework 2: (due 02/03/06)
  Page 43-44: 8, 16, 28, 32
  Page 52: 2, 4, 8, 10
  Page 62-63: 8, 10, 12, 14, 24, 26
  Page 72: 24, 38.
  Sample solution
• Homework 3: (due 02/10/06)
  Page 111: 4, 14, 18, 24, 30, 32;
  Page 133: 6, 8, 16, 26, 30, 32.
  Sample solution
• Homework 4: (due 02/24/06)
  Page 205-206: 4, 6, 8, 10, 14, 16, 18(a)(d)(h), 26.
  Sample solution
• Homework 5: (due 03/03/06)
  Page 225-226: 2, 4, 6(a)(d), 8, 12, 14, 18, 22, 24, 28.
  Sample solution
• Homework 6: (due 03/10/06)
  Page 256: 18, 24 (see 23 for "idempotent"), 28, 40
  Page 275-276: 2, 4, 6, 12, 14 (When an entry is changed from 0 to 1, please provide the values of (k, i, j) in Warshall's Algorithm).
  Sample solution
• Homework 7: (due 03/22/06)
  Page 297-298: 12, 16, 18, 22
  Page 314-315: 6, 8, 12, 14, 20, 24, 26, 28
  Page 330-331: 20, 24, 32, 34.
  Sample solution
• Homework 8: (due 03/31/06)
  Page 339: 6, 8
  Page 358: 6, 8, 10, 12, 18
  Page 377: 6, 18
  Page 400: 2, 4, 10, 16.
  Sample solution
• Homework 9: (due 04/7/06)
  Page 429: 2, 6, 8, 12, 16, 20, 22, 26, 30, 36, 40
  Page 437: 8, 10, 12, 20, 22.
  Sample solution
• Homework 10: (due 04/14/06)
  Page 442: 4, 6, 14, 18
  Page 447: 2, 4, 12, 14, 20
  Page 455: 4, 6, 10
  Page 468: 2, 4, 8
  Sample solution
• Homework 11: (due 04/24/06)
  Page 487: 6, 8, 12, 14, 16, 20
  Page 511: 6, 18
  Page 527: 4, 6
  Hint to the last problem: If the three roots of the charateristic equation are identical, say r, then the general solution is
  a_n = c₀ rⁿ + c₁ n rⁿ + c₂ n² rⁿ
  
• Homework 12: (due 04/28/06) The solution will be posted on 04/28/06.
  Page 563-564: 8, 18, 26
  Page 618-619: 24, 30
  Page 635: 10, 12, 16
  Page 643: 8
  Page 684: 2
  Sample solution
• Exercise Problems: (These problems will help you to prepare the final exam)
  Page 712: 6, 7, 9, 10, 12, 16
  Page 730-731: 6, 10, 12, 13, 14, 16, 18, 22
  Page 743: 16, 18
  Page 784-785: 6, 7, 8, 9, 11, 12, 14
  Page 822-823: 2, 4, 6, 12

Exams

There will be two midterm exams and one final exam. All midterms will be held during class time.

First Midterm on 02/15/06 (20 percent of final score)

Second Midterm on 03/29/06 (20 percent of final score)

The Final Exam is in the week of 05/08-12/06

Class Participation (6 percent of final score)

Lecture Notes

You are expected to study all the material in each chapter covered in the readings even if that material is not explicitly discussed in class or in the homework. You are also expected to study the extra material presented in class which is not in the textbook. Material presented in class, but not in the book may appear on tests.

The lecture notes are a supplement to the course textbook. They are supposed to help you understand the textbook material better, they are not a replacement for either the textbook or the lecture itself.

• Ch01: Sets and Logic 3-in-1 PDF
• Ch02: Integers and Induction 3-in-1 PDF
• Ch03: Relations and Posets 3-in-1 PDF
• Ch04: Matrices and Closures of Relations 3-in-1 PDF
• Ch05: Functions and Sequences 3-in-1 PDF
• Ch06: Congruences 3-in-1 PDF
• Ch07: Counting Principles 3-in-1 PDF
• Ch08: Recurrence Relations 3-in-1 PDF
• Ch09: Time Complexity Analysis of Algorithms 3-in-1 PDF
• Ch10: Graph Theory 3-in-1 PDF
• Ch11: Trees 3-in-1 PDF
• Ch12: Boolean Algebra and Logical Gates 3-in-1 PDF