# CMSC 15300 Foundations of Software

## Overview

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

## Syllabus

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

## Homework assignments

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), 14
Wed. 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).
Prove member function 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.