Fall 2005
Unique Numbers 53975 to 54000
CS 337
Theory in Programming Practice


 

ANNOUNCEMENT (12/7/2005): Since the university has decided to close at 2pm due to the cold weather, today's class is canceled. Today's lecture will not be made up at a future date. The third test will go ahead as planned on Friday. The third test will cover the material on the last three modules (relational database, parallel recursion, string matching), except that there will not be any questions related to the second set of lecture slides on the Boyer/Moore algorithm (i.e., the material that I was going to cover today).

To prepare for the third test, I suggest that you look over the relevant portions of Spring 04 Test 2 (questions 4 to 10) and Spring 05 Test 3 (all questions). Remember to look at the sample solutions as well. All of this material can be found by going to the Links section of the class website to access the websites for previous versions of the course. Of course, you should not limit your study to the material on the old tests; you should also study the lecture material and the relevant sections of the course packet. Remark: Don't be misled by the fact that there are no questions on the relational database section on the Spring 04 test; this module was not added to the course until Fall 05. Also, I would like to add that the style of the third test will not be as unorthodox as that of the second test, which threw a lot of students off.

Instructor Greg Plaxton (office hours W 5-6, F 4-5, TAY 3.132; email: plaxton at cs)
   
Teaching Assistants Ned Dimitrov (office hour W 2-3, ESB 229, desk 3; email: ned at cs), Warren Hunt (office hour M 1-2, ESB 229, desk 3; email: whunt at cs), Jack Sarvela (office hour Th 4-5, Taylor Hall basement, in the blackboard area; email: sarvela at cs)
   
Class Time MWF 3-4
   
Class Location WEL 3.502
   
Discussion Sections The TAs will hold a total of five one-hour discussion sections each Tuesday. The sections are at 10 in WEL 3.402 (Jack), 11 in BEN 1.126 (Ned), 12 in RAS 312 (Ned), 1 in RAS 211A (Warren), 2 in RAS 310 (Warren). 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 2005 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 projects 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 Projects There will be four programming projects. Each project is due by 8pm on the date indicated on the class schedule. Programming projects may be done individually or in pairs. If you choose to work in a pair, it is recommended that you employ the "pair programming" approach in which team members together on all portions of the project, as opposed to simply dividing the project into pieces and working on them separately. If you have questions regarding a given project, feel free to bring them up at the discussion sections or at office hours. In addition, you may use the newsgroup utexas.class.cs337 to ask your fellow students or the project instructor for clarifications.

   
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 10, and will cover compression, error detection and correction, and cryptography. [NOTE ADDED 9/20/05: As determined by the class vote on 9/19/05, the date for the first test has been moved to October 10.] The second test will be held on Friday, November 4, and will cover finite state machines and recursion and induction. The third test will be held on Friday, December 9, and will cover relational database, parallel recursion, and string matching. If possible, 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 test then the final course grade of the student will be based on their performance in the remaining parts of the course. (In effect, we will "fill in" such a missing score by some reasonable form of interpolation.) In the event of a non-excused absence, a score of zero will be assigned.
   
Grading Scheme The overall course grade will be determined from performance on the four programming projects (10% each, 40% total) and three tests (20% each, 60% total). NOTE ADDED 11/11/05: As discussed in the 11/9/05 lecture, I have amended the preceding weighting scheme in order to allow students who performed poorly on the Haskell-related Test 2 to improve their overall score by doing well on the two Haskell-related programming projects, Projects 3 and 4. The amendment says that if a student achieves a better percentage score on Project 3 than on Test 2, then the Project 3 weight is increased to 15% and the Test 2 weight is decreased by 5%. Similarly for Project 4. So, for example, if a student performs better on both Projects 3 and 4 than on Test 2, then each of Projects 3 and 4 is assigned a weight of 15% and Test 2 is assigned a weight of 10%. As another example, if a student does better on Project 4 than on Test 2, but worse on Project 3 than on Test 2, then Project 3 is assigned a weight of 10%, and Project 4 and Test 2 are each assigned a weight of 15%. If a student does worse on both Projects 3 and 4 than on Test 2, then the original weighting scheme applies.
   
Academic Dishonesty Cheating on the assignments or tests will result in severe academic penalties.