Spring 2004 Course Description
22C:34 Discrete Structures
Instructor: Arthur C. Fleck; Office: 201D MLH;
Office hours: 10:45-11:30 AM M-W-F or by arrangement;
email: firstname.lastname@example.org; Ph: 335-0718.
Wenli He; Office: 101J MLH; Office hours: 12-2 PM T-Th or by arrangement; email: email@example.com; Ph: 335-2549.
Saurav Pandit; Office: 101N MLH; Office hours: 11 AM-12:30 M-W or by arrangement; email: firstname.lastname@example.org; Ph: 335-2839.
Grassman & Tremblay, Logic and Discrete Mathematics, Prentice-Hall, 1996.
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 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
Tenative topic schedule (42 sessions)
- reasoning techniques (chapters & sections 1.1, 1.2, 2.1) -- 1 lecture (approx.)
- counting and induction (chapter sections 3.1-3.4) -- 5 lectures (approx.)
- sets, functions, relations (chapters & sections 5, 6.1, 6.2, 6.4, 6.5) -- 8 lectures (approx.)
- exam I
- graphs & trees (chapter sections 7.1-7.6) -- 10 lectures (approx.)
- exam II
- formal logic (chapters & sections 1, 2, 4.1-4.6, 9) -- 16 lectures (approx.)
- 20% - Exam I -- date 3/1/04
- 20% - Exam II -- date 4/2/04
- 20% - Projects & Homework (weekly)
- 35% - Final exam (PDF) -- 9:45 AM, 5/10/04, in our classroom
- 5% - Qualitative
Links to Related Web Sources