This course aims to teach you mathematical foundations appropriate for specifying, describing, and reasoning about computer software and computation.
The course meets during the Spring Quarter of 2004, at 9:30 MWF in Ryerson 251.
The instructors for the course are Stuart Kurtz and John Reppy. The course TAs are Gohar Margaryan and Lingyun Yang.
Office hours are as follows:
Monday 11:30-12:30 Gohar Margaryan Ryerson 255 Tuesday 1:30-2:30 John Reppy Hinds 033 Thursday 1:00-2:00 Stuart Kurtz Hinds 039 Thursday 2:00-3:00 Lingyan Yang Hinds 018
The required text is Discrete Structures, Logic, and Computability, 2nd edition, by James L. Hein.
There is a course mailing list, which you should subscribe to. To add yourself to the list, go to
Grading for the course will be based on:
Percentage Component 50% Homework: Daily & Chapter assignments 20% Midterm Exam (May 5, 2004; 7:30pm; Ry 276) 30% Final Exam (Friday June 11, 2004; 8:00am; Ry 251)
The chapters mentioned in the syllabus below correspond those of the text, although the lectures may not.
Topic Instructor Chapter 1. Elementary notions and notation 1.1-1.2 A Proof Primer & Sets Kurtz 1.3-1.4 Ordered Structures & Graphs and Trees Reppy Standard ML Introduction Reppy Chapter 2. Functions and Functional Programming Reppy Chapter 3. Constructive Techniques Reppy inductive definitions recursion grammars Chapter 4. Equivalence, Order, and Inductive Proof Kurtz binary relations equivalence relations order relations inductive proof Chapter 6. Propositional Logic Kurtz Classical and Intuitionistic Logics Chapter 7. Predicate Logic Kurtz Chapter 8. Applied Logic Reppy Chapter 10. Algebraic Structures and Techniques Reppy boolean algebra algebra of abstract datatypes Chapter 11. Regular Languages and Finite Automata Kurtz
Date Assignment Due date Mar. 29 assignment Mar. 31 Mar. 31 Section 1.1: 2a, b, d; 3d; and 7b. Apr. 2 Apr. 2 Section 1.2: 1b,f; 3b,d,f,h; and 15. Apr. 5 Apr. 5 Section 1.3: 2b,f; 4d; 10b; and 16b. Apr. 7 Apr. 7 Section 1.4: 4b and 6. Apr. 9 Apr. 7 assignment Apr. 14 Apr. 12 Section 2.1: 13b,d; 18b; and 19d. Apr. 14 Apr. 14 Section 2.2: 9b. Apr. 16 Section 2.3: 4b,d and 17b. Apr. 16 Section 3.1: 7d; 14; 18b. Apr. 19 Apr. 19 assignment Apr. 21 Apr. 21 Section 3.3: 6b and 10. Apr. 23 Apr. 23 ?? Apr. 26 Apr. 26 Section 4.1: 16 Apr. 28 Apr. 28 Section 4.2: 7b Apr. 30 Apr. 30 assignment May 3 May 3 assignment May 5 May 5 Section 6.2: 7b,d and 9b,d. May 10 May 10 Section 6.3: 5f and 6f. May 12 May 14 assignment May 17 May 19 Section 7.1: 9b, 10b, and 12d,f May 21 Section 7.2: 1b, 4b, and 7b,d. May 21 Section 7.3: 3a,b. May 24 May 24 Read Section 8.1 May 26 Section 8.1: 2, 4b, and 6b. May 26 assignment May 28 May 28 Section 8.2: 3b, 6b, and 8b. June 2
The University of Chicago is a scholarly academic community. You need to both understand and internalize the ethics of our community. A good place to start is with the Cadet's Honor Code of the US Military Academy: "A Cadet will not lie, cheat, or steal, or tolerate those who do." It is important to understand that the notion of property that matters most to academics is ideas, and that to pass someone else's ideas off as your own is to lie, cheat, and steal.
The University has a formal policy on Academic Honesty, which is somewhat more verbose than West Point's. Even so, you should read and understand it.
We believe that student interactions are an important and useful means to mastery of the material. We recommend that you discuss the material in this class with other students, and that includes the homework assignments. So what is the boundary between acceptable collaboration and academic misconduct? First, while it is acceptable to discuss homework, it is not acceptable to turn in someone else's work as your own. When the time comes to write down your answer, you should write it down yourself from your own memory. Moreover, you should cite any material discussions, or written sources, e.g.,
Note: I discussed this exercise with Jane Smith.
The University's policy, for its relative length, says less than it should regarding the culpability of those who know of misconduct by others, but do not report it. An all too common case has been where one student has decided to "help" another student by giving them a copy of their assignment, only to have that other student copy it and turn it in. In such cases, we view both students as culpable and pursue disciplinary sanctions against both.
For the student collaborations, it can be a slippery slope that leads from sanctioned collaboration to outright misconduct. But for all the slipperyness, there is a clear line: present only your ideas as yours and attribute all others.
If you have any questions about what is or is not proper academic conduct, please ask your instructors.