Online Book

Owlspace (for supplementary materials)

Office Hours

SVN Guide

Scheme HW Guide

Java HW Guide

HW Checklist

HW Grading

Discussion Archive

COMP 211: Principles of Program Design

Instructors:	Prof. Robert "Corky" Cartwright	Staff:	Cherif Salama
	Prof. Walid Taha		Angela Zhu
	Dr. Dung "Zung" Nguyen		Jun Inoue
			Travis Martin
			Justin Faulkner
Lectures:	Duncan Hall (DH) 1064	Time:	MWF 11:00-11:50 am
Labs:	Sewell Hall 101	Times:	Monday 2:00-3:20 pm, Monday 3:30-4:50 pm, Tuesday 2:30-3:50 pm. (sign up sheet)

Introduction

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, Felleisen et al. QA76.6 .H697 2001 (Available online; no purchase is necessary

DrScheme: Please download and use the DrScheme system embedded in Version 4.1.3. To avoid compatability problems, please make sure you use Version 4.1.3 (as of 1-5-09, the latest version).

Notes for Java: Object-oriented Design

References for Java

• [[http://cnx.org/content/col10213/1.31] [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.
• 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 {\em 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. If you machine is running some flavor of Windows or Linux, go to the http://java.sun.com/javase/downloads/index.jspSun Download Site for the Java SE 6.0^?. 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 a Java 5.0 or Java 6.0 JDK.

Course Schedule

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.

#	Day	Date(2009)	Topic	Reading	Lectures	Problems	Due(2009)	Lab	Supplements
1	Mon	Jan 05	Introduction		L 1	HW 0	W Jan 07	Lab 0	Pair Programming
2	Wed	Jan 07	Scheme primitives; function and data definitions	Skim Chs. 1-10	L 2	HW 1	W Jan 14
3	Fri	Jan 09	Inductive data, conditionals, and the design recipe	Review Chs. 1-10	L 3
4	Mon	Jan 12	Data-directed design I	Read Chs. 11-13	L 4			Lab 1
5	Wed	Jan 14	Data-directed design II	Read Chs. 14-15	L 5	HW 2 (Solution to 12.4.2)	Th Jan 22
6	Fri	Jan 16	Mutually Referential Data Definitions	Skim Chs. 16-17	L 6
-	Mon	Jan 19	School Holiday	Review Chs. 16-17				Lab 2
7	Wed	Jan 21	Local definitions and Lexical Scope	Read Chs. 18-19	L 7	HW 3	Mon Feb 2
8	Fri	Jan 23	Functional Abstraction and Polymorphism	Read Ch. 20	L 8
9	Mon	Jan 26	Functions as Values	Read Chs. 21-22	L 9			Lab 3
10	Wed	Jan 28	Lambda the Ultimate	Study Chs. 21-22	L 10
11	Fri	Jan 30	Generative Recursion	Read Chs. 25-28	L 11	HW 4	Mon Feb 9
12	Mon	Feb 02	Generative Recursion Illustrated	Study Chs. 25-28	L 12			Lab 4
13	Wed	Feb 04	Complexity and Accumulators	Read Chs. 29.1-2; Skim Chs. 30-32	L 13
14	Fri	Feb 06	Accumulators and Tail Calls	Read Chs. 30-32	L 14
15	Mon	Feb 09	Review and First-Class Functions	Review prior readings	L 15	HW 5	Mon Feb 16	Lab 5	210 Exam 1, 210 Exam 2
16	Wed	Feb 11	Powerful Functionals	Review prior readings	L 16
17	Fri	Feb 13	Exam Review	Review prior readings	L 17	Take-home exam			Exam Errata
18	Mon	Feb 16	On to Java	OO Design Notes, Ch 1.1-1.4.1	L 18	HW 6 (Extra Credit)	Mon Feb 23	Lab 6	parse/unparse
19	Wed	Feb 18	Java Design Recipe	OO Design Notes, Ch 1.1-1.4	L 19
20	Fri	Feb 20	Defining Inductive Data in Java	OO Design Notes, Ch 1.5	L 20	HW 7			IntList IntListTest
21	Mon	Feb 23	Static Class Members and the Singleton Pattern	OO Design Notes, Ch 1.6	L 21			Lab 7	ObjectList ObjectListTest
22	Wed	Feb 25	Polymorphism and Interfaces	OO Design Notes, Ch 1.8	L 22				ComparableList ComparableListTest
23	Fri	Feb 27	Loose Ends and First-class Functions	OO Design Notes, Ch 1.9-1.10, 1.12	L 23	HW 8	Fri Mar 13
24	Mon	Mar 9	The Strategy and Visitor Patterns	OO Design Notes, Ch 1.9, 1.11	L 24			Lab 8	IntList.dj1 IntListTest.dj1
25	Wed	Mar 11	Visitors, Visitors, Vistors ...	OO Design Notes, Ch 1.11	L 25
26	Fri	Mar 13	Full Java	OO Design Notes, Ch 1.13	L 26	HW 9	Wed Mar 25
27	Mon	Mar 16	Visibility, Type-Checking, and Generics	OO Design Notes, Ch. 1.10, 1.13	L 27			Lab 9	List.java ListTest.java
28	Wed	Mar 18	Generics with Discretion		L 28
29	Fri	Mar 20	Mutation: Succumbing to the Dark Side?	OO Design Notes, Ch 1.13	L 29
30	Mon	Mar 23	Arrays as Bounded Sequences	OO Design Notes, Ch 2.1	L 30			Lab 10
31	Wed	Mar 25	Mutable Linked Lists	OO Design Notes, Ch 2.1	L 31	HW 10			BigBiList.java BigBiListTest.java
32	Fri	Mar 27	Mutable Trees	OO Design Notes, Ch 2.1	L 32				TreeMap.java TreeMapTest.java
33	Mon	Mar 30	Designing OO Data Structures		L 33			Lab 11	OOTreeMap.java OOTreeMapTest.java
34	Wed	Apr 1	Efficient Representations of Maps and Sets		L 34	HW 11			Okasaki's Red-Black Trees
35	Fri	Apr 3	Rice Board Game Framework
36	Mon	Apr 5	OO Design Retrospective	OO Design Notes	L 36			Lab 12
37	Wed	Apr 7	Faster Searching Methods	OO Design Notes	L 37
38	Fri	Apr 9	The Othello Game Framework	The Othello Game Framework		HW 12
39	Mon	Apr 13	Faster Searching Methods (Updated with code)	OO Design Notes	L 37			Lab 13	MyHashMap.java MyHashMapTest.java
40	Wed	Apr 15	Fast Sorting Methods	OO Design Notes	L 40
41	Fri	Apr 17	Graphical User Interfaces	OO Design Notes, Ch. 3	L 40
41+	Fri	Apr 24	Optional Othello Tournament		Tournament Rules

Exit Survey

Please take the exit survey to help us improve this course and the core programming curriculum. Follow this link: Exit Survey

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.

Mailing Lists:

• comp211-discussion-l@mailman.rice.edu (subscribe here):
  • This is where important announcements related to the class will be posted.
  • Students are required to sign up to this list.
  • You may use this list for open discussions relating to the course. Postings are expected to abide by standard Netiquette.
• comp211-teachers@mailman.rice.edu:
  • Any questions relating to the course can be sent to this list.
  • Specific questions about homework problems and grading can be directed here.
• cs-events-l@mailman.rice.edu:
  • Announcements relating to talks and other interesting events hosted by the CS departments.
  • Subscription to this list is optional but highly recommended

Questions

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 teachers mailing list (questions of general interest may alternately be raised on the discussion mailing list). If, after doing so, you don't feel that your concerns have been addressed, you may wish to contact Prof. Cartwright or Prof. Taha directly.

Homeworks:

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 Mondays, and will be due before class the following Monday.

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 15 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.

Other Resources:

• Practical matters:
  • DrScheme Programming Environment
• Special interest groups:
  • CSters
  • Computer Science Club
  • ... (please send in suggestions!)

Additional References:

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
	Gödel, Escher, Bach: An Eternal Golden Braid, Douglas Hofstadter	QA9.8 .H63 1980
	Metamagical Themas, Douglas Hofstadter	Q335 .H63 1985
If you liked Scheme, you'll love these resources:	Google's MapReduce	(Online)
	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 Java:	Principles of Object-Oriented Programming: The Connexions Curriculum for the former Comp 212 course
	The Java Programming Language: Book written by James Gosling the father of Java himself!
	Thinking In Java: A Java Book by Bruce Eckel, a well-known and seasoned professional programmer. Look for the link to free book downloads on this page
	Design Patterns: Elements of Reusable Object-Oriented Software: This is the "Bible" of OO software design. The authors (all four of them) of the book are affectionately referred to as the Gang of Four (GoF?).
	Head First Design Patterns (by O'Reilly): A very accessible introduction to Design Patterns using Java.
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.

Accomodations 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.

---

Access Permissions: (Please don't edit)

• Set ALLOWTOPICCHANGE = TeachersComp211Group