Fall 2006
Unique Numbers 56310 to 56330
CS 337
Theory in Programming Practice

Instructor Greg Plaxton (office hours T 4-5 and F 12-1, TAY 3.132; email: plaxton at cs)

Teaching Assistants Ned Dimitrov (office hour W 2:30-3:30, ESB 229, Desk 2; email: ned at cs), Indrajit Roy (office hour M 4-5, ESB 229, Desk 1; email: indrajit at cs)

Extended Office Hours Each of the four office hours listed above will be extended half an hour (e.g., T 4-5:30 instead of T 4-5) if there is a test or project due during the week following the office hour. Example: Suppose that a project is due on Wednesday, September 27 at 8pm. Then every office hour between 8pm on Wednesday, September 20 and 8pm on Wednesday, September 27 will be extended by half an hour.

Class Time MWF 10-11

Class Location TAY 2.006

Discussion Sections The TAs will hold a total of four one-hour discussion sections each Tuesday. The sections are at 10 in WAG 308 (Ned), 11 in BEN 1.126 (Indrajit), 1 in MEZ 1.208 (Indrajit), 2 in RAS 310 (Ned). You may attend any discussion section that you wish, regardless of the unique number for which you are registered. While attendance at the discussion sections is not mandatory, it is strongly encouraged. The TAs will be reviewing the lecture material, discussing approaches to the programming assignments, and discussing the solutions to sample test problems.

Textbook The primary text for the course is the Fall 2006 CS 337 course packet authored by Professor Jayadev Misra. The textbook "Haskell: The Craft of Functional Programming" by Simon Thompson is a useful reference for the section of the course related to recursion and induction. In addition, at least one of the four programming assignments will be done in Haskell.

Catalog Description Application of program analysis theory to program design. Methodologies for large-scale program design. Designed to help students bring together theoretical and programming skills.

Prerequisites The following courses, with a grade of at least C in each: CS 315 or 315H, CS 336 or 336H, and M 408C.

Course Outline The course may be viewed as presenting case studies in which the establishment of a firm theoretical foundation has led to the development of correct and efficient programs for practical applications. The course covers specific topics related to compression, error detection and correction, cryptography, finite state machines, recursion and induction, relational database, string matching, and parallel recursion.

Programming Assignments There will be four programming assignments. Each assignment is due by 8pm on the date indicated on the class schedule. Programming assignments may be done individually or in groups of two. If you choose to work with a partner, it is recommended that you employ the "pair programming" approach in which team members work together on all portions of the assignment, as opposed to simply dividing the assignment into pieces and working on them separately. If you have questions regarding a given assignment, feel free to bring them up at the discussion sections or at office hours.

Quizzes Most of the lectures will include a brief quiz based on material from the previous lecture. The quizzes are open book/notes. In each lecture I will indicate the nature of the question to be posed in the following lecture, so you will only need to review a small amount of material in order to prepare for the next quiz. As explained in the section below entitled "Overall Raw Score", all of your low quiz scores will be dropped in the computation of your course grade. If you miss a quiz for any reason (legitimate or otherwise), your score for that quiz will be a zero, so it will be dropped.

Tests There will be three in-class tests. The tests will be closed book and closed notes; you are only allowed to bring one page of notes (both sides may be used). The first test will be held on Monday, October 2 and will cover the lecture material (including lectures devoted to project discussion) up to and including September 27. The second test will be held on Wednesday, November 8 and will cover the lecture material from September 29 to November 1. The third test will be held on Friday, December 8 and will cover the lecture material from November 3 onward. Please try to arrive in class a few minutes early on the test dates; this will allow us to start the test right at the beginning of the class period.

Make-Up Tests Please note that no make-up tests will be given in this course. If a student has a legitimate and properly documented excuse for missing a one of the tests, the missing test score will be estimated as the average of the other two test scores. More complicated scenarios, e.g., where a student misses two tests for legitimate reasons, will be treated on a case-by-case basis. In the event of a non-excused absence, a score of zero will be assigned.

Overall Raw Score Each student's overall raw score, out of 100 points, will be determined from performance on the four programming projects, the quizzes, and the three tests. Each programming project is worth 10 points, for a total of 40. The remainder of the raw score is determined as follows. Let x denote your average score on the tests (expressed as a fraction, e.g., if you have a 70% test average, then x is 0.7), let n denote the total number of quizzes, let A denote the set of quizzes on which you scored higher than your test average, let y denote your average score (again expressed as a fraction) over the quizzes in set A, and let w denote 30 * |A| / n. Then your raw score out of 60 for the quizzes and tests is (60 - w) * x + w * y. Example 1: Mary doesn't take any of the quizzes, but she scores 100% on all three tests. Mary's raw score for the quizzes and tests is 60 out of 60. Example 2: Joe enjoys a brief quiz -- and aces all of them -- but, for unknown reasons, he refuses to participate in any sort of "test". Joe's raw score for the quizzes and tests is 30 out of 60. Example 3: Pat has a test average of 75%, and gets better than 75% on 20 out of a total of 30 quizzes. The average of Pat's top 20 quiz scores is 90%. Pat's raw score for the quizzes and tests is 40 * 0.75 + 20 * 0.9 = 48 out of 60, or 80%.

Letter Grades The nominal cutoff for getting an A in the course is 90. For a B, it is 80, and for a C, it is 60. These nominal cutoffs will not be increased; for example, a student achieving a raw score of 91 is guaranteed to get an A in the course. These cutoffs might be lowered if necessary in order to improve the grade distribution. A typical grade distribution might consist of 25-30% A's, 30-35% B's, 35-40% C's, and a few D's or F's.

Feedback Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course. If you wish to provide feedback anonymously, feel free to turn in an extra sheet of comments whenever a quiz is being collected.

Academic Dishonesty Cheating on the programming assignments, quizzes, or tests will not be tolerated. If you find yourself overwhelmed by coursework or other special circumstances, do not resort to cheating. Instead, make an appointment to see the instructor to discuss your situation.

Instructor	Greg Plaxton (office hours T 4-5 and F 12-1, TAY 3.132; email: plaxton at cs)

Teaching Assistants	Ned Dimitrov (office hour W 2:30-3:30, ESB 229, Desk 2; email: ned at cs), Indrajit Roy (office hour M 4-5, ESB 229, Desk 1; email: indrajit at cs)

Extended Office Hours	Each of the four office hours listed above will be extended half an hour (e.g., T 4-5:30 instead of T 4-5) if there is a test or project due during the week following the office hour. Example: Suppose that a project is due on Wednesday, September 27 at 8pm. Then every office hour between 8pm on Wednesday, September 20 and 8pm on Wednesday, September 27 will be extended by half an hour.

Class Time	MWF 10-11

Class Location	TAY 2.006

Discussion Sections	The TAs will hold a total of four one-hour discussion sections each Tuesday. The sections are at 10 in WAG 308 (Ned), 11 in BEN 1.126 (Indrajit), 1 in MEZ 1.208 (Indrajit), 2 in RAS 310 (Ned). You may attend any discussion section that you wish, regardless of the unique number for which you are registered. While attendance at the discussion sections is not mandatory, it is strongly encouraged. The TAs will be reviewing the lecture material, discussing approaches to the programming assignments, and discussing the solutions to sample test problems.

Textbook	The primary text for the course is the Fall 2006 CS 337 course packet authored by Professor Jayadev Misra. The textbook "Haskell: The Craft of Functional Programming" by Simon Thompson is a useful reference for the section of the course related to recursion and induction. In addition, at least one of the four programming assignments will be done in Haskell.

Catalog Description	Application of program analysis theory to program design. Methodologies for large-scale program design. Designed to help students bring together theoretical and programming skills.

Prerequisites	The following courses, with a grade of at least C in each: CS 315 or 315H, CS 336 or 336H, and M 408C.

Course Outline	The course may be viewed as presenting case studies in which the establishment of a firm theoretical foundation has led to the development of correct and efficient programs for practical applications. The course covers specific topics related to compression, error detection and correction, cryptography, finite state machines, recursion and induction, relational database, string matching, and parallel recursion.

Programming Assignments	There will be four programming assignments. Each assignment is due by 8pm on the date indicated on the class schedule. Programming assignments may be done individually or in groups of two. If you choose to work with a partner, it is recommended that you employ the "pair programming" approach in which team members work together on all portions of the assignment, as opposed to simply dividing the assignment into pieces and working on them separately. If you have questions regarding a given assignment, feel free to bring them up at the discussion sections or at office hours.

Quizzes	Most of the lectures will include a brief quiz based on material from the previous lecture. The quizzes are open book/notes. In each lecture I will indicate the nature of the question to be posed in the following lecture, so you will only need to review a small amount of material in order to prepare for the next quiz. As explained in the section below entitled "Overall Raw Score", all of your low quiz scores will be dropped in the computation of your course grade. If you miss a quiz for any reason (legitimate or otherwise), your score for that quiz will be a zero, so it will be dropped.

Tests	There will be three in-class tests. The tests will be closed book and closed notes; you are only allowed to bring one page of notes (both sides may be used). The first test will be held on Monday, October 2 and will cover the lecture material (including lectures devoted to project discussion) up to and including September 27. The second test will be held on Wednesday, November 8 and will cover the lecture material from September 29 to November 1. The third test will be held on Friday, December 8 and will cover the lecture material from November 3 onward. Please try to arrive in class a few minutes early on the test dates; this will allow us to start the test right at the beginning of the class period.

Make-Up Tests	Please note that no make-up tests will be given in this course. If a student has a legitimate and properly documented excuse for missing a one of the tests, the missing test score will be estimated as the average of the other two test scores. More complicated scenarios, e.g., where a student misses two tests for legitimate reasons, will be treated on a case-by-case basis. In the event of a non-excused absence, a score of zero will be assigned.

Overall Raw Score	Each student's overall raw score, out of 100 points, will be determined from performance on the four programming projects, the quizzes, and the three tests. Each programming project is worth 10 points, for a total of 40. The remainder of the raw score is determined as follows. Let x denote your average score on the tests (expressed as a fraction, e.g., if you have a 70% test average, then x is 0.7), let n denote the total number of quizzes, let A denote the set of quizzes on which you scored higher than your test average, let y denote your average score (again expressed as a fraction) over the quizzes in set A, and let w denote 30 * \|A\| / n. Then your raw score out of 60 for the quizzes and tests is (60 - w) * x + w * y. Example 1: Mary doesn't take any of the quizzes, but she scores 100% on all three tests. Mary's raw score for the quizzes and tests is 60 out of 60. Example 2: Joe enjoys a brief quiz -- and aces all of them -- but, for unknown reasons, he refuses to participate in any sort of "test". Joe's raw score for the quizzes and tests is 30 out of 60. Example 3: Pat has a test average of 75%, and gets better than 75% on 20 out of a total of 30 quizzes. The average of Pat's top 20 quiz scores is 90%. Pat's raw score for the quizzes and tests is 40 * 0.75 + 20 * 0.9 = 48 out of 60, or 80%.

Letter Grades	The nominal cutoff for getting an A in the course is 90. For a B, it is 80, and for a C, it is 60. These nominal cutoffs will not be increased; for example, a student achieving a raw score of 91 is guaranteed to get an A in the course. These cutoffs might be lowered if necessary in order to improve the grade distribution. A typical grade distribution might consist of 25-30% A's, 30-35% B's, 35-40% C's, and a few D's or F's.

Feedback	Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course. If you wish to provide feedback anonymously, feel free to turn in an extra sheet of comments whenever a quiz is being collected.

Academic Dishonesty	Cheating on the programming assignments, quizzes, or tests will not be tolerated. If you find yourself overwhelmed by coursework or other special circumstances, do not resort to cheating. Instead, make an appointment to see the instructor to discuss your situation.