Syllabus

Course: CS 336H: Analysis of Programs – Honors Section

Time: Tu-Th 9:30-11

Instructor: A. K. Cline

Office: Taylor 3.104 A

Office Hours: Th 11-12, W 2-3, and by appointment

Web Site: TBA

Email: cline@cs.utexas.edu

Assistant: Selim Erdogan

Office: TBA

Office Hours: TBA

Web Site: TBA

Email: selim@cs.utexas.edu

Prerequisite: CS 313H or PHL 313K and consent of the instructor

Purpose: To teach students how to argue rationally about programs.

Topics:

1. Combinatorics

A. Permutations and Combinations

B. Rudimentary Combinatorial Probability

2. Cardinality

A. Countable and uncountable infinities

B. The Cantor diagonalization argument

3. Asymptotic Dominance

A. f = O(g) and f = o(g)

4. Program Verification

A. Assertions and Hoare triples

B. Axioms for sequential

composition, assignment, branching

C. Verification of loop-free programs

D. Loops and invariants

E. Total correctness

Grading:

Exam 1: 20%

Exam 2: 20%

Final Exam: 40%

Homework: 20%

Comments:

1. Good homework cannot make up for poor exams nor good exams for poor homework. To do well in the course grade, students must have good homework and exams.

2. There will be approximately three homework problems assigned at every class. These will be due at the beginning of the following class. Solutions for each problem set will be distributed.

3. There will be no regular text for the class although notes will be distributed on occasion. It is very important that students attend each class.

4. It is expected that every student will contribute to the class.

5. An excellent summary of expectations is found at

http://www.cs.utexas.edu/users/ear/CodeOfConduct.html

Homework Specifications

1. Your solutions must be legible. If your writing is not legible, use a word processor.

2. Do not employ any pictures. Pictures can have value for presenting overall ideas about proofs - they cannot substitute for the text of the proof.

3. Every sentence - even those using mathematical notation - must be readable. There must be clear subjects and verbs - not just random phrases.

4. Every claim you make must follow from the hypothesis or from the previous claims. When you believe you have completed a solution, test yourself by reading it and ensuring that it is clear how the claims follow one another one-by-one.

5. Criticize your own solutions. You should be learning not only how to create solutions but how to recognize correct ones. If you wonder about having too much or too little detail, err always on the side of too much detail.

6. If you realize that your logic has gaps, admit that. Put comments about such omissions or possible errors in boxes.