COMP 211: Principles of Program Design
Duncan Hall (DH) 1075
- Dr. Cartwright: MWF 9:00 AM - 10:00 AM
- Dr. Wong: See home page
- Alina: MWF 11:00 AM -12:00 PM
- Kamal: MF 3:00 PM - 5:00 PM
- Nicholas: TR 7:00 PM - 8:30 PM
e-mail the entire class: comp211s11 at owlspace-ccm.rice.edu
e-mail just the staff: comp211 at rice.edu
This course is an introduction to the fundamental principles of programming. The focus is on systematic methods for developing robust solutions to computational problems. Students are expected to have experience writing interesting programs in some credible programming language (e.g., Python, Java, Scheme, C#, C++, Visual Basic .NET, PRL, Scheme, Lisp, etc.) but no specific programming expertise is assumed. The course is targeted at potential Computer Science majors but mathematically sophisticated non-majors are welcome. We expect students to be comfortable with high-school mathematics (primarily algebra, mathematical proofs, and induction) and the mathematical rigor and vocabulary of freshman calculus. Success in the course requires a deep interest in the foundations of computer science and software engineering, self-discipline, and a willingness to work with other people on programming projects. Topics covered include functional programming, algebraic data definitions, design recipes for writing functions, procedural abstraction, reduction rules, program refactoring and optimization, object-oriented programming emphasizing dynamic dispatch, OO design patterns, fundamental data structures and algorithms from an OO perspective, simple Grapical User Interfaces (GUIs), and an exposure to the challenges of concurrent computation.
Students will learn the practical skills required to write, test, maintain, and modify programs. Labs and assignments use the Scheme and Java programming languages.
Text For Scheme: How to Design Programs by Felleisen et al. QA76.6 .H697 2001 (Available online; no purchase is necessary.)
DrScheme/DrRacket: Please download and use the DrScheme/DrRacket system available from the Racket download site. To avoid compatibility problems, please make sure you use a Version numbered 5.0.2
Notes for Java: Object-oriented Design
References for Java
- Principles of Object-Oriented Programming by Zung Nguyen and Stephen Wong. An online self-contained introduction to OOP in Java roughly corresponding to the former Comp 212 course. It is reasonably complete, but still under construction.
- Design Patterns Lens - A collection of short descriptions of the design patterns covered in the course.
- Index to online Java Tutorials by Sun Microsystems The Sun tutorials refer to the full Java language not the Elementary and Intermediate language levels supported by DrJava.Nevertheless, they cover many important language details in depth, such as the complete collection of primitive operators on primitive data types.
- Java Basics by Fred Swartz is a clearly written traditional introduction to Java that focuses on Java mechanics rather than OO Design. It can be helpful in learning the mechanics of writing full Java code. Please ignore what he says about program design.
- Java Notes by Fred Swartz is a reasonably comprehensive Java reference that is a good supplement to the official Sun documents.
DrJava: Please download and use the DrJava pedagogic programming environment available from drjava.org. You must install either the Java 5 or Java 6 JDK on your machine for DrJava to work. (Addendum: DrJava releases starting in 2011 can also run using a Java 7 JDK.) If you machine is running some flavor of Windows or Linux, go to the \[Sun Download Site for the Java SE 6.0 (http://java.sun.com/javase/downloads/index.jsp\]). Make sure that you download the JDK not the JRE. If you have a Mac, a Java JDK is available from Apple. In fact, it is part of the standard Mac OS X software package. DrJava will run on either the Apple Java 5.0 or Java 6.0 JDK.
Please fill out this survey.
Confirm that You Can Attend Lab
The lab is an essential component of the course. Every student should attend lab on Tuesday 10:50-12:05 in Ryon 102.
If you have a conflict, you probably should drop the course. If you have a conflict, but still want to take the course, please come see Prof. Cartwright or Prof. Wong to evaluate your options.
All Comp 211 programming assignments will be run and graded on the CLEAR (Linux) educational computing facility. The Ryon 102 lab is equipped with machines connected to the CLEAR network. For instructions on how to use CLEAR, see the CLEAR web page.
This wiki for Comp 211 is a revision of last year's and may contain a significant number of broken links and typos. If you notice an error in the wiki, please send email to the Comp 211 staff.
Note that future date schedules are only guidelines. Future homeworks and slides may contain materials from previous Comp 210 and Comp 212 classes. New material will be provided before the corresponding class. There will only be two exams in the course: one given on functional programming during week 7 and one on object-oriented programming given during in the last week of the course. Both are take-home exams. There is no final examination.
Introduction & Scheme Primitives
W Jan 12
Function definitions and conditionals
F Jan 21
Data Definitions & The Design Recipe
Data-directed design: trees
Mon Jan 31
Mutually Referential Data Definitions
Local Definitions and Lexical Scope
Functional Abstraction and Polymorphism
Mon Feb 7
Functions as Values
Lambda the Ultimate
Mon Feb 14
Complexity and Accumulators
Accumulators and Tail Calls
Clever Programming With Functions
Review prior readings
Mon Feb 21
Review prior readings
On to Java
OO Design Notes Ch 1.1-1.4
OO Design Notes Ch 1.1-1.4
HW 6 (Optional)
Mon Mar 07
Java Design Recipe
OO Design Notes Ch 1.1-1.4
Defining Inductive Data in Java
OO Design Notes Ch 1.5
Feb 28-Mar 4
Static Class Members and the Singleton Pattern
OO Design Notes Ch 1.6
Mon Mar 14
Polymorphism and Interfaces
OO Design Notes Ch 1.8
Handling Exceptions and Errors
OO Design Notes Ch 1.9-1.10, 1.12
The Strategy and Visitor Patterns
OO Design Notes Ch 1.9, 1.11
Mon Mar 21
Visitors, Visitors, Vistors ...
OO Design Notes Ch 1.11
Accepting Reality: Full Java
OO Design Notes Ch 1.13
OO Design Notes Ch. 1.10, 1.13
Fri Apr 4
Simple Generics in Java
OO Design Notes Ch 1.13.4 (contains advanced material as well)
lec29_code.zip (incl. genList)
Mutation and Bi-Directional Linked Lists
OO Design Notes Ch 1.13
OO Design Notes Ch 2.1
OO Design Notes Ch 2.1
Wed. Apr 13
Mutable Trees and OO Data Structure Review
OO Design Notes
OO Sorting Algorithms
CNX Module on Sorting (incl. insertion and selection sort animations)
Milestone 1: Mon. Apr 18
Graphical User Interfaces
Fast Searching and Memoization
Fast Sorting Methods
Grading, Honor Code Policy, Processes and Procedures
Grading will be based on your performance on homeworks (worth 50%) and exams (20% for first exam, and 30% for the second exam).
Take-home exams, which are pledged under the honor code, test your individual understanding and knowledge of the material. Collaboration on exams is strictly forbidden.
We will normally use the OwlSpace Comp 211 Announcements and General Discussion forum to post important announcements and discussions related to the
class, particularly Q&A on class assignments. The Owlspace e-mail alias to the entire class (see above) will also be used.
Other Mailing Lists:
- Announcements relating to talks and other interesting events hosted by the CS departments.
- Subscription to this list is optional but highly recommended
If you have a question about homework – you're not sure what is expected for a given problem, you haven't received feedback from a previous assignment, or you don't understand or agree with the assessment of your work, for example – you can raise the question with a TA in lab or on the class mailing list. It is preferable to send a question out for the whole class to discuss so that everyone can benefit from eachother's contributions as well the responses from the staff. Please restrict messages sent to only the staff to more sensitive matters that do not warrant viewing by the entire class. If you still don't feel that your concerns have been addressed, you may wish to contact Prof. Cartwright or Prof. Wong directly.
Homeworks help you verify your understanding of the material and prepare you for the exams. You are encouraged to discuss the homework problems with the instructors and staff. Help from other students, including Comp 211 graduates, is also encouraged (but should be cited), although that does not include giving or receiving complete answers. All homework partners are responsible for knowing all the submitted material. If you fail to understand the homework solutions, you won't succeed on the exams.
Homeworks will generally be handed out on Fridays, and will be due before class the following Friday.
You are expected to work in groups of two.
You may change partners during the semester.
Partners should work together on all aspects of the homework -- all students are expected to contribute equally. You and your partner should hand in exactly one solution.
Late homework will not be accepted with one exception. Every student is allotted 7 slip days. Each whole day or fraction of a day that an assignment is late counts as a slip day. Each student in the pair submitting a late assignment must spend the requisite number of slip days. Since assignments get progressively harder during the semester, we strongly encournage you to hoard your slip days for use near the end of the term.
We recommend that you review the homework guide as you develop your solutions. Review the submission checklist when you turn in your homework. Your work will be graded as documented on the grading page.
Reading: For each lecture, there is associated reading. Students are required to complete the reading before the class associated with this reading.
- Practical matters:
- Special interest groups:
- Computer Science Club
- ... (please send in suggestions!)
Here is a nice article about the basic approach taken in this course.
More on CS
The New Turing Omnibus, A. K. Dewdney
QA76 .D448 1993
Algorithmics: The Spirit of Computing, David Harel
QA76.9 .A43 H37 2004
Computers Ltd.: What They Really Can't Do, David Harel
QA76.5 .H3575 2000
Great Ideas in Computer Science, Alan W. Biermann
QA76 .B495 1997
Computer Science: An Overview, J. Glenn Brookshear
QA76 .B743 1997
Godel, Escher, Bach: An Eternal Golden Braid, Douglas Hofstadter
QA9.8 .H63 1980
Metamagical Themas, Douglas Hofstadter
Q335 .H63 1985
More on Functional Programming
The Little Schemer, Friedman & Felleisen
QA76.73 .S34 F75 1996
The Seasoned Schemer, Friedman & Felleisen
QA76.73 .S34 F77 1996
Developing Applications with Objective Caml, Emmanuel Chailloux, Pascal Manoury, and Bruno Pagano
The Haskell School of Expression: Learning Functional Programming Through Multimedia, Paul Hudak
QA76.62 H83 2000
More on Object-Oriented Design in Java
The Connexions Curriculum for the former Comp 212 course
The Java Programming Language, Arnold & Gosling
Gosling was the principal designer of Java 1.0
Thinking In Java, Bruce Eckel
The 3rd edition is available free.
Design Patterns: Elements of Reusable Object-Oriented Software, Gamma, Helm, Johnson & Vlissides
The "Bible" of OO software design.
Head First Java, Bert Bates & Kathy Sierra
A fun read while you get introduced to Java and learn how to think like a Java Programmer.
Head First Design Patterns, Freeman & Freeman
An accessible introduction to Design Patterns.
More on Data Structures and Algorithms
Introduction to Algorithms: Book written by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. The authoritative reference on algorithms.
Accommodations for Students with Special Needs
Students with disabilities are encouraged to contact me during the first two weeks of class regarding any special needs. Students with disabilities should also contact Disabled Student Services in the Ley Student Center and the Rice Disability Support Services.