Foundations of Software

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 2003, at 9:30 MWF in Ryerson 251.

The instructors for the course are Stuart Kurtz and John Reppy. The course TA is Jonathan Riehl.

TA office hours will be held in Ry 257 as follows:

Tuesday 2-4pm Jon Riehl Thursday 2-4pm Jon Riehl

The required text is **Discrete Structures, Logic, and Computability, 2nd edition**,
by James L. Hein.

Grading for the course will be based on:

Percentage Component 50% Homework: Daily & Chapter assignments 20% Midterm Exam (May 9, 2003) 30% Final Exam

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 A Proof Primer Reppy 1.2-1.3 Sets & Ordered Structures Kurtz 1.4 Graphs and Trees 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 Mon. 3/31 Section 1.1 (p11-12); Problems 3(d), 5, 8(b) Wed. 4/2 Wed. 4/2 Section 1.2 (p31-35); Problems 2(b,d), 6(a,d), 12, 15, 25 Fri. 4/4 Fri. 4/4 Section 1.3 (p52-55). Problems 11(a,b) and 16b. Mon. 4/7 Mon. 4/7 Section 1.4 (p70-71). Problems 4(b), 6, and 8. Wed. 4/9 Wed. 4/9 Section 2.1 (pp 88-90). Problems 1(b,d), 13(b,d), and 18(b). Fri. 4/11 Fri. 4/11 Section 2.2 (pp 98-100). Problem 8(b).

Section 2.3 (pp 111-115). Problems 2(b,d) and 5(d,f).Mon. 4/14 Mon. 4/14 Section 2.3 (pp 111-115): Problem 15(b).

Section 3.1 (pp 142-145): Problems 2(b), 7(d), 14Wed. 4/16 Wed. 4/16 Section 3.2 (pp 168-172): Problems 5(b) and 6(b, d). Fri. 4/18 Fri. 4/18 Section 3.2 (pp 168-172): Problems 16(d) and 18(a).

Section 3.3 (pp 188-191): Problem 10.Mon. 4/21 Mon. 4/21 Section 4.1 (pp 209-213): Problems 16, 22(b,c), and 25(a,b). Wed. 4/23 Wed. 4/23 Section 4.2: Problems 7(b), 8, and 10. Fri. 4/25 Fri. 4/25 Section 4.3: Problems 6, 8, and 10. Mon. 4/28 Mon. 4/28 Section 4.4: Problems 2(b,f), 16, and 18. Wed. 4/30 Wed. 4/30 Section 6.2: Problems 7(b), 8(b), 9(d), and 10(d). Fri. 5/2 Fri. 5/2 Section 6.3: Problems 5(b,d). Mon. 5/5 Mon. 5/5 Intuitionism handout, Problems 1, 4, 5. Wed. 5/7 Wed. 5/14 Section 7.2: Problems 4(b,d) and 7(b,d). Fri. 5/16 Fri. 5/16 Section 7.3: Problems 3(b), 5, 7(b), and 8(b). Mon. 5/19 Mon. 5/19 Section 8.1: Problems 2, 4(b,d), and 6(b). Wed. 5/21 Wed. 5/21 Section 8.2: Problems 2(a), 5(b), 8(b), and 16(b). Fri. 5/23 Fri. 5/23 Section 8.2: Problem 17(b).

Provememberfunction correct [see handout].Wed. 5/28 Wed. 5/28 Section 10.1: 6(b,d)

Section 10.2: 10 and 12.Fri. 5/30 Fri. 5/30 Section 10.3: 4, 12, and 14. Mon. 6/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.

Last revised: May 30, 2003.