Syllabus / Home Page

Topics in Computer Science: Data Structures and Algorithms

CMPU-125

Vassar College: Fall 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/~cs125/

Section:	01
Professor:	Jenny Walter (my homepage)
Office:	OLB 124
Office hours:	Mon-Thu 2:00 - 4:30pm; and by appointment
Phone:	437 7449
Email:	walter at cs dot vassar dot edu or jewalter at vassar dot edu
Class meeting times:	Tues/Thurs 12-1:15am, OLB 105
Lab meeting times:	Fri 3:10-4:40pm, Asprey Lab

Coaches: Sonia Roberts (lab coach), Ade Raphael, Lea Wiemann

Coaching hours (coaches stationed in the cs lounge for office hours):

Sonia Roberts: 5 to 7 pm Wednesday evenings
Ade Raphael: 7 to 9 pm Thursday evenings
Lea Wiemann: 8:30 pm to midnight Thursday evenings

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

Resources:

Tutorial for acm.jar package
Java 1.5 API: http://java.sun.com/j2se/1.5.0/docs/api/
acm.jar
acm.jar API: http://jtf.acm.org/javadoc/student/index.html
NetBeans download site
Textbook supplements:

Author's slides for first 8 chapters
Code (by chapter)

Assignments
Labs
Schedule

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 is the unification of Computer Science I and II. 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, an important problem-solving technique for computer scientists and mathematicians. 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. You will also learn one of the most important techniques used by computer scientists to describe algorithm performance -- asymptotic notation.

Course Description:
This course emphasizes the development of data structures and algorithms in an object-oriented programming language -- Java. 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 is 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 from the text and from lecture. 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 hinder 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 me know and we can informally arrange another time. Email is generally the best way to reach me and I will strive to answer emails quickly. My e-mail address is 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 on October 3, during October break, or during Thanksgiving 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:

25%	Weekly Assignments
10%	Weekly Labs
5%	Participation
20%	Midterm 1 (Thu, Oct 2)
20%	Midterm 2 (Thu, Nov 20)
20%	Final Exam (time and date to be determined by registrar's office)

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. 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)	Tue	Thu (Labs on Friday at 3:10 - 4:40 pm)
1. (Sep 2)	Sep 2 Introductions Course overview PPT PDF Reading assignment: Chap. 1 of our text	Sep 4 Ch 1: Java Review PPT PDF Lab0: Hello, NetBeans World! Guest lecture (~45 min.): Greg Priest-Dorman Overview of Your Computer Science Account Homework1: Calculating BMI Index
2. (Sep 9)	Sep 9 Java Review: Variables, Types, Expressions, Precedence and Evaluation PPT PDF	Sep 11 Java Review: Flow of Control Constructs, Event-driven programming PPT PDF Lab1: Event-driven programming Homework2: Breakout
3. (Sep 16)	Sep 16 Java Review: Arrays, Exceptions, More Event-Driven Programming PPT PDF	Sep 18 Read Chapter 3 Java Review: Java Interfaces, Polymorphism, File input and output PPT PDF Lab2: Reverse Polish calculator, writing loops and adding JButtons Homework3: Validating Checksums
4. (Sep 23)	Sep 23 Recursion (Chapter 3): PPT PDF File demonstrated in class: TestRecursion.java	Sep 25 Recursion (cont.) Lab3: Recursion practice Homework4: Finding the kth smallest element using recursion Midterm 1 next week: review next class
5. (Sep 30)	Sep 30 Handout of last year's Midterm 1. Midterm I next class! Promises: 75 minutes / 75 points (1 point/minute) Open book, open notes 5 single and multi-part questions: Q1: Write 2 recursive methods that work together Q2: Write a non-recursive method that works on a two-dimensional array Q3: Write a non-recursive method that works on a one-dimensional array Q4: Multi-part short answer question about a recursive method. Q5: Multi-part short answer question about 2 recursive methods, including a trace of one method. This exam stresses the material we covered in Ch. 3	Oct 2 Midterm 1 Read Chapters 4 and 5 No Lab this week
6. (Oct 7)	Oct 7 Finish recursion, review Chapter 4 PPT PDF Read Chapter 5: Linked lists	Oct 9 Finish Chapter 4, start Chapter 5 PPT PDF Lab4: Set ADT Read Chapter 6
7. (Oct 14)	Oct 14 Chapter 5 PPT PDF	Oct 16 Finish Chapter 5 Read Chapter 7 Lab5: Using Generic classes
8. (Oct 21)	Oct 21 October break	Oct 23 October break
9. (Oct 28)	Oct 28 Start Ch 7: Stacks PPT PDF Homework5: Implementing the game of Go Fish, Part I	Oct 30 Ch 7: Stacks Homework6: Implementing the game of Go Fish, Part II Read Chapter 8
10. (Nov 4)	Nov 4 Start Ch. 8: Queues PPT PDF Homework7: Infix to postfix calculator	Nov 6 Ch. 8: Queues Read Chapter 10: Algorithm efficiency
11. (Nov 11)	Nov 11 Ch. 10: Measuring efficiency of algorithms PPT PDF Read Chapter 11: Binary Trees	Nov 13 No class
12. (Nov 18)	Nov 18 Ch. 10 - sorting algorithms	Nov 20 Finish Ch. 10 Lab6: Experimenting with sorting algorithms
13. (Nov 25)	Nov 25 Start Ch. 11 Trees PPT PDF Take-home midterm covers mainly chapters 5, 7, 8, and 10	Nov 27 Thanksgiving Holiday
14. (Dec 2)	Dec 2 Midterm exam due	Dec 4 Finish Trees, Start Ch. 13: Hash Tables PPT PDF Homework8: Expert System -- the animal game
15. (Dec 9)	Dec 9 (Last class)	Dec 10 (last lab)
16. (Dec 16)	Dec 16 - Final Exam 9-11am, OLB 105 Promises: 120 minutes / 100 points Open book, open notes 6 single and multi-part questions: Q1: 4 questions about binary search trees, in particular about inserting nodes into binary search trees Q2: 4 questions about max-heaps Q3: 3 questions about hash tables Q4: 4 questions about binary trees, including tree traversals Q5: Write 2 methods for class BTNode Q6: Interpret output of traversal on binary tree This exam stresses the material covered after the last exam and the only cumulative aspect is that you are expected to be able to write some code.	Dec 18