Syllabus / Home Page

Computer Science II: Data Structures and Algorithms

CMPU-102 Sections 51 and 52

Vassar College: Spring 2008

Throughout the semester this web page will be updated with important course information. Please check it regularly.

Course home page: http://www.cs.vassar.edu/~cs102/

Section:	51
Professor:	Marc Smith (my homepage)
Office:	OLB 122
Office hours:	Tue 3:30-5pm; Wed 2:30-5pm; and by appointment
Phone:	437 7497
Email:	mlsmith at cs dot vassar dot edu
Class meeting times:	Mon/Wed 12-1:15am, OLB 105
Lab meeting times:	Mon 3:10-4:40pm, Asprey Lab

Section:	52
Professor:	James Ten Eyck
Office:	OLB 106
Office hours:	Mon 3:30-4:30pm; Tue 12-1pm; and by appointment
Phone:	437 5986 (at Vassar) 575 3000 x2606 (at Marist)
Email:	teneyck at cs dot vassar dot edu
Class meeting times:	Tue/Thu 10:30-11:45pm, EH 200
Lab meeting times:	Mon 4:45-6:15pm, Asprey Lab

Coaches: Anca Sarb / Zach Pattison-Gordon / Adam Favaloro / Olivia Gillham
Sonia Roberts / Lea Wiemann / Irina Dumitrescu

Section 51 lab coaches: Anca Sarb, Adam Favaloro, Olivia Gillham
Section 52 lab coaches: Adam Favaloro, and usually Olivia Gillham
Coaching hours: (updated!)

Mon: Adam (12-3pm)
Tue: Olivia (2-5:30pm), Sonia (3-5pm)
Wed: Sonia (4-6pm), Olivia (5:30-8:30pm), Anca (7-10pm), Irina (7-10pm), Lea (8pm-12am)
Thu: Adam (10am-12pm), Sonia (4-6pm), Lea (9pm-12am)
Fri: Adam (12-2pm), Sonia (2-4pm), Lea (3-5pm)
Sat:
Sun: Zach (7-10pm),

Text:
Frank M. Carrano and Janet J. Prichard. Data Abstraction & Problem Solving with Java 5: Walls & Mirrors, Second Edition. Addison-Wesley. Copyright © 2006, by Pearson Education, Inc.

Resources:

Java 1.5 API: http://java.sun.com/j2se/1.5.0/docs/api/
Textbook supplements:

Author's slides
Code (by chapter)

The Elements of Style, by William Strunk, Jr.
Assignments
Labs
Schedule

Two Sections, One Course:
As indicated at the top of this syllabus, your professors are Marc Smith and Jim Ten Eyck. We are each teaching our own section of this course, though we are coordinating both sections. This means we are using the same text, following the same lecture schedule, developing common course materials, and sharing this syllabus.

Overview:
The following is a quote by Eric Raymond, from The Cathedral and the Bazaar, 1997:

"Show me your code and conceal your data structures, and I shall continue to be mystified.
Show me your data structures, and I won't usually need your code; it'll be obvious."

This course begins where Computer Science I leaves off. This semester we formally introduce the computer scientist's tools for data abstraction and problem-solving: data structures and algorithms. Walls and Mirrors (from the subtitle of our text) refer to these tools and capture the essence of this course. The walls refer to data abstraction--the separation between a program and the data structures it uses. The mirrors refer to recursion, one of the most important problem-solving techniques available to the computer scientist. This semester, you will come to understand how recursive thinking is useful in the development of algorithms to solve problems, whether the final solution ends up being recursive or iterative.

Course Description:
This course emphasizes the development of data structures and algorithms in an object-oriented programming language. Topics include hierarchic program refinement, preconditions, postconditions and invariants; data encapsulation and fundamental data structures (e.g., lists, queues, trees, sets, maps, heaps, search trees, hash tables, and graphs); fundamental algorithms (e.g., searching and sorting) and analysis of algorithm complexity.

Course prerequisites are completion of CMPU 101, or permission of the department. The course web page will be updated regularly throughout the semester with assignments, deadlines, and other important information. Please check it frequently. You will also need to check your email regularly for important class announcements.

In lectures, labs, and programming assignments, we will use the Java programming language to describe the data structures and algorithms we study. There continues to be nothing special about our choice of Java. While we learn about more sophisticated features of the language than were covered in Computer Science I, this course is not about learning to program in Java.

To reinforce the concepts we will be studying, you will construct programs of increasing complexity and sophistication throughout the course. In a weekly 90 minute lab session we will cover practical issues, such as how to use the computing environment and development tools, and work on practical programming exercises designed to reinforce concepts. The weekly programming assignments will rely on the concepts we've learned to date--and practiced in the labs--to test your ability to solve larger and more complex problems.

Attendance:
We are a community of learners, but you must be present to help one another. You provide a unique and valuable contribution to every class. The questions you ask help us all understand better the course material. Missing class deprives this community of your insights and understanding. So, please notify your professor before any classes or labs you know you will miss. We worry about you when you're not present. More practically, part of your grade (5%) is based on participation, and you must be present to participate. Excessive absences tend to hurt one's overall performance in this class.

Advice:
Keep up with the reading and assignments. Topics tend to build on one another. Missing one lecture or lab may preclude fully understanding the next, so do your best to attend every class meeting. Make arrangements with a classmate to copy material you miss when you can't attend. Please contact or visit your professor if you have any questions, or if there is anything you would like to discuss. If you can't make it to office hours, let us know and we can arrange another time. Email is generally the best way to reach us. We will strive to answer emails quickly. Our e-mail addresses are given at the top of this page.

Elements of Style:
Writing a program to solve a problem is in many ways analogous to writing an essay. In fact, both acts share the notion of composition and involve a problem-solving process. Therefore, just as you would in other classes, in this class we will strive to write elegant code. One reason for this goal is because, over time, we need to read more code than we write, and so we write code with this realization in mind.

Coursework and Grades:
To assess your understanding of the topics presented in this course, there will be frequent written or programming assignments, weekly labs (no lab the first week, or during spring break), two midterms (dates already set--see below and schedule), and a final exam (during the final exam period). If you are unable to attend class on the day of an exam, it is your responsibility to notify the instructor in advance to make other arrangements. Late assignments will be penalized, and will not be accepted once solutions have been discussed in class. Your final grade for the course will be calculated according to the following distribution of coursework:

35%	Weekly Assignments
10%	Weekly Labs
5%	Participation
15%	Midterm 1 (Wed/Thu, Feb 20/21)
15%	Midterm 2 (Wed/Thu, Apr 9/10)
20%	Final Exam

Based on the weighted average of your graded coursework, your letter grade will be determined according to the standard 90, 80, 70, 60 cutoffs. For example, 90% or above is an A; 80% or above, but below 90%, is a B; etc. Pluses or minuses may be added at the instructor's discretion.

Academic Integrity:
Don't cheat. Read Originality and Attribution: A guide for student writers at Vassar College. It should come as no surprise, after reading the "Language usage and elegance" section of this syllabus, that what we learn in this course is another form of composition: the art of programming computers to solve problems at a meaningful level of abstraction. Since we are concerned with composition, the guidelines that apply to writing in general, apply equally to the writing of computer programs. Copying someone else's code without attribution amounts to plagiarism. Likewise, give proper attribution for the help you receive. School policy dictates instructors must report all suspected incidents of cheating to their department chair. Did you read the previous sentence? Please don't put yourself or your professor in that position. When in doubt, ask your professor before seeking any help from another source.

Students with disabilities:
Academic accommodations are available for students with disabilities who are registered with the Office of Disability and Support Services. Students in need of disability accommodations should schedule an appointment with me early in the semester to discuss any accommodations for this course which have been approved by the Office of Disability and Support Services, as indicated in your DSS accommodation letter.

Weekly Schedule: readings, lecture topics, labs, assignments

Please note: the exact topics of future lectures are tentative, although exam dates are firm.

Week # (of)	Mon/Tue (Labs on Monday for both sections)	Wed/Thu
1. (Jan 21)	Jan 21/22 No class No Lab	Jan 23/24 (First class) Introductions Course overview Ch 3: Recursion (The Mirrors) PPT PDF Read for next class: Chapters 1-3 (skim 1-2)
2. (Jan 28)	Jan 28/29 Ch 3: Recursion (The Mirrors) PPT PDF Assignment 1: kSmall due: Fri, Feb 8 Read for next class: Chapter 4 Lab 0: Hello, NetBeans World! Guest lecture (~45 min.): Greg Priest-Dorman Overview of Your Computer Science Account	Jan 30/31 Today: Finish up Ch 3 slides: Recursion (The Mirrors) PPT PDF Recursion exercise: in class (15 min.) Here's the PDF HW for next class: `power3` Go over Assignment 1: kSmall due: Fri, Feb 8 Downloading and unbundling Opening in NetBeans Partitioning strategies Ch 4: Data Abstraction (The Walls) PPT PDF
3. (Feb 4)	Feb 4/5 Today: Coaching hours Written assignment: power3() Discuss Assignment 1: partitioning strategies Ch 4: Data Abstraction (The Walls) PPT PDF Lab 1: Mr. Spock's Dilemma	Feb 6/7 Assignment 1: due: tomorrow Read Ch 5 for next class Assignment 2: IList implementation of a List ADT due: Fri, Feb 15
4. (Feb 11)	Feb 11/12 Ch 5: Linked Lists PPT PDF Lab 2: Set ADT implementation	Feb 13/14 Ch 5: Linked Lists PPT PDF Read for next class: Chapter 6 Midterm 1 next week: review next class
5. (Feb 18)	Feb 18/19 Ch 6: Recursion as a Problem-Solving Technique PPT PDF Assignment 3: due Feb 25 Handout of last year's Midterm 1. Midterm I next class! Promises: 75 minutes / 75 points (1 point/minute) Open book, open notes Chapters 1-5, with emphasis on 3-5: Mirrors (recursion), Walls (ADTs), Linked Lists and ILists, and Java 1.5 support of walls and mirrors Q1: Understanding reference types. Given some code that uses reference type variables, follow the assignment statements and trace its output. Q2: Implement recursive method(s) to produce the desired output. Q3: Provide two implementations (one recursive, one iterative) for a method that computes some property of a (singly) linked list. Q4: Implement a recursive method that computes some function over an IList. You will implement this method for both MTList and ConsList. Q5: Implement a method that modifies a singly linked list according to the given requirement. Hint: working on Assignment 3 will help you be prepared for this question. Q6: Recursive thinking / problem solving. This question will be a variation on the "Organizing a Parade" problem from the book, and like we worked out in class. Lab 3: Generics, Collections, Iterators, for-each loop	Feb 20/21 Midterm 1 Assignment 4: due Feb 27/28
6. (Feb 25)	Feb 25/26 Review of Midterm 1 Assignment 3 due: today (11:59pm) Ch 6: Recursion as a Problem-Solving Technique PPT PDF Assignment 4: due Fri, Mar 7 (before Spring break) Lab 4: Recognizing simple languages using grammars and recursion	Feb 27/28 Ch 6: Recursion as a Problem-Solving Technique PPT PDF (finish up) Read for next class: Ch 7
7. (Mar 3)	Mar 3/4 Reminder: Assignment 4 due: Fri, Mar 7 (before Spring break) Ch 7: Stacks PPT PDF Lab 5: IList-based Stack ADT implementation	Mar 5/6 Ch 7: Stacks PPT PDF Read for next class: Ch 8
8. (Mar 10)	Mar 10/11 Spring break	Mar 12/13 Spring break
9. (Mar 17)	Mar 17/18 Spring break	Mar 19/20 Spring break
10. (Mar 24)	Mar 24/25 Ch 8: Queues PPT PDF Announcements: Asprey Lectures this week! (please make every effort to attend) Computer Science Department: details Shriram Krishnamurthi, Brown Kathi Fisler, WPI Thu, Mar 27, 5pm (tea 4:30), "A Programming Language for the New Web" Fri, Mar 28, 12:30pm (lunch 11:30), "Policies and Their Analysis" Math Department: Avi Wigderson, Institute for Advanced Study, Princeton Thu, Mar 27, 6:30pm, RH 200, "Algorithms: a Common Language for nature, man, and computer" Fri, Mar 28, 3:30pm, RH 300, "Time, Space, and the cosmology of computational problems" Assignment 5: due Mon/Tue, Mar 31/Apr 1 Lab 6: Resizable, Circular Array-Based Implementation of a Queue ADT	Mar 26/27 Ch 8: Queues PPT PDF Assignment 5: due Mon/Tue, Mar 31/Apr 1 Questions? Alternative wording for Rule 3: (infix to postfix conversion) 3. if it's an operator--pop operators of greater or equal precedence and append to postfix expression, until a '(' or empty stack is encountered, then push nextCh onto stack Breadth-First-Search (Ch 14 excerpt): PPT PDF Read for next class: Ch 10 (we'll come back to Ch 9)
11. (Mar 31)	Mar 31 / Apr 1 Ch 10: Algorithm Efficiency and Sorting PPT PDF Lab 7: Insertion sort for the IList hierarchy	Apr 2/3 Ch 10: Algorithm Efficiency and Sorting PPT PDF Assignment 6: due Apr 7/8 Ch. 10, Exercises 1, 2, and 3; pp. 512-513
12. (Apr 7)	Apr 7/8 Ch 9: Advanced Java Topics Skim/review on your own, not covered in class Assignment 6 due today Solution handed out + review Midterm 2 next class! Promises: (not binding until today at noon) 75 minutes / 75 points (1 point/minute) Open book, open notes Chapters 1-8, and 10. Emphasis on lists, stacks, recursive problem-solving, algorithm efficiency (Big Oh), and sorting. Q1: (10 points) Trace the given sorting algorithms on the given arrays. Q2: (10 points) Implement the Stack ADT on the given data structure. Writing code. Q3: (10 points) Analyze the given algorithm, counting number of times each statement is executed, and overall "Big Oh". Q4: (10 points) Questions about efficiency of a particular sorting algorithm we've discussed. Q5: (20 points) Recursive problem-solving for two sorting algorithms. Q6: (10 points) Implement an algorithm using lists and iterators from the Java Collections Framework. Lab: Review session with Jim for Midterm 2	Apr 9/10 Midterm 2 Marc's section will be proctored by Luke Hunsberger (I'll be out of town at Cold Spring Harbor Laboratory) Assignment 7: due Fri, Apr 18 (Airline Sched Prob) Reading assignment: Ch 11 (Trees)
13. (Apr 14)	Apr 14/15 Assignment 6: handed back Midterm 2: handed back Assignment 7: Sorting due: Fri, Apr 18 Ch 11: Trees PPT PDF Lab 8: ABST (Abstract Binary Search Tree) class hierarchy	Apr 16/17 Ch 11: Trees PPT PDF Reading Assignment: Ch 12: Tables and Priority Queues Assignment 7 due Fri, Apr 18
14. (Apr 21)	Apr 21/22 Ch 11: Trees (finish up) PPT PDF Ch 12: Tables and Priority Queues PPT PDF Assignment 8: ABST Phonebook due: Mon Apr 28 Lab 9: Binary Tree Traversals	Apr 23/24 Ch 12: Tables and Priority Queues PPT PDF Reading Assignment: Ch 13: Advanced Implementations of Tables
15. (Apr 28)	Apr 28/29 Ch 12: Tables and Priority Queues PPT PDF Ch 13: Advanced Implementations of Tables PPT PDF (Excerpt) Assignment 9: Short Document Concordance due: Mon May 5 Lab 10: Finish up Assignment 8 (due today)	Apr 30 / May 1 Ch 13: Advanced Implementations of Tables PPT PDF (Excerpt)
16. (May 5)	May 5/6 (Last class) Wrap-up (Final Exam coverage) Course Evaluations Review session: tbd Lab 11: Finish up Assignment 9 (due today)	May 7/8 Study period
17. (May 12)	May 12/13 Study period	May 14/15 Final Exam: (both sections together) Friday, May 16 1:00pm - 3:00pm RH 203