Spring 2004 Course Description
22C:34 Discrete Structures

Teaching staff

Instructor: Arthur C. Fleck; Office: 201D MLH; Office hours: 10:45-11:30 AM M-W-F or by arrangement; email: fleck@cs.uiowa.edu; Ph: 335-0718.
TAs:
Wenli He; Office: 101J MLH; Office hours: 12-2 PM T-Th or by arrangement; email: whe@cs.uiowa.edu; Ph: 335-2549.
Saurav Pandit; Office: 101N MLH; Office hours: 11 AM-12:30 M-W or by arrangement; email: spandit@cs.uiowa.edu; Ph: 335-2839.

Text

Grassman & Tremblay, Logic and Discrete Mathematics, Prentice-Hall, 1996.

Course goals

The purpose of the course is to introduce fundamental formal concepts of importance in computing, and to gain experience with rigorous and formal deduction. The major topics include proof methods with emphasis on mathematical induction, solving recurrence relations, important properties of sets, functions and relations, connectivity properties of graph structures, and formal logical systems.

Course administration

Course grading is based on two mid-terms and a final exam, plus regular homework. The assignments in the course emphasize conceptual problem solving, but also include small computer programs. The process of carefully proving what conclusions can be drawn from precise definitions of computing models will be augmented by consideration of logic programs for some tasks. Programs will be written in Prolog and run on the cluster of Linux workstations in 105/301 MLH. A class directory containing related course material is located at /group/class/c034.

Tenative topic schedule (42 sessions)

  1. reasoning techniques (chapters & sections 1.1, 1.2, 2.1) -- 1 lecture (approx.)
  2. counting and induction (chapter sections 3.1-3.4) -- 5 lectures (approx.)
  3. sets, functions, relations (chapters & sections 5, 6.1, 6.2, 6.4, 6.5) -- 8 lectures (approx.)
  4. exam I
  5. graphs & trees (chapter sections 7.1-7.6) -- 10 lectures (approx.)
  6. exam II
  7. formal logic (chapters & sections 1, 2, 4.1-4.6, 9) -- 16 lectures (approx.)

Grading

Links to Related Web Sources