CS 35 Algorithms and Object-Oriented Programming
TR 11:20-12:35, Sproul 201
Spring 2002
Swarthmore College

Professor: Tia Newhall
email: newhall AT cs.swarthmore.edu
Office: 36 Sproul (3rd floor)
Phone: 690-5637
Office hours: Wed. 2-4pm, or by appointment



Course Description

This course continues the broad introduction to computer science begun in CS 21 and CS 22. It is also designed to provide a good general background for further study in the field. You will be learning data structures and algorithms which are important in the construction of sophisticated computer programs. The underlying themes of the course will be program design, abstraction, analysis, and an introduction to object-oriented programming. Techniques to analyze various algorithms and data structures will be presented.

There will be numerous homework exercises and programming projects illustrating the concepts presented. We will use the Computer Science Lab on the second floor of Sproul Observatory as the classroom and laboratory for this course. If you work somewhere else, you are responsible for obtaining and learning how to use the software. Since one of the goals of the course is to learn how to write large, reliable programs, we will emphasize (in class and grading) the development of clear, modular, well-documented programs that are easy to read, verify, analyze, debug, and modify.

Required Text

Useful Java Links

Useful Unix Links


20%: Exam I in class
20%: Exam II in class
20%: Exam III Wed. May 15, 9am
35%: Homework
5%: Class Participation

Homework Policy

Homework will generally be assigned at the end of the week and will be due the middle of the following week. You will turn in your homework assignments electronically, using a special handin program

Late homework is not accepted, except if an extension is requested and granted prior to the due date. Even if you miss a deadline, you are strongly encouraged to complete the assignment anyway, since this really is the only effective way to learn the material.

Programs will be graded with respect to both style (30%) and correctness/efficiency (70%). Good programming style includes the following features:


Under no circumstances may you hand in work done with (or by) someone else under your own name. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes sharing solutions after the due date of the assignment. Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's code or let anyone else read your code. If you are in doubt about some help that you received, then credit the person(s) from whom you got help by citing them in a comment at the top of the file and discuss the situation with your instructor.


On some homework assignments you may work jointly with one other student (with each assignment we will explicitly tell you if working with a partner is allowed). If you work with a partner, then you and your partner may share code for that particular assignment. When you work with someone else, submit a single, joint assignment with both names clearly indicated at the top of your program file(s) and README file. Both individuals will receive the same grade for that assignment.

To safely share code with your partner, you should use the Unix setfacl command:

  1. Run easysetfacl, it will build the Unix setfacl command for you (and optionally execute it).
  2. Read this information about what setfacl does and how you should use it in combination with chmod to give your partner access to your private directories: setfacl


Clinics will be held in the Sun lab each weekly on Monday nights at 7pm.

Schedule (tentative)

1 (1/22) Intro. to Java Programming Chapt. 1 & 2 HW1
2 (1/29) More Intro. to Java Chapt. 1 & 2 HW2
Add/Drop ends: 2/1
3 (2/5) Complexity Analysis Chapt. 3 HW3
4 (2/12) Stacks and Queues Chapt. 4 HW4
5 (2/19) GUI
Vectors, Lists and Sequences
Chapt. 5 ---
6 (2/26) Vectors, Lists and Sequences Chapt. 5 HW5
no class Thursday
7 (3/5) Trees Chapt. 6 and 9.1
(in 9.1, a Dictionary ADT stores (key, element) pairs)
Exam I, Thursday in class
(3/12) --- --- SPRING BREAK
8 (3/19) More Trees --- HW6
9 (3/26) Priority Queues and Heaps Chapt. 7 HW7
Last day to withdraw: 3/29
10 (4/2) Dictionaries and Hashing Chapt. 8 .
11 (4/9) More Dictionaries and Hashing Chapt. 8 HW9
12 (4/16) Graphs Chapt. 12 Exam II, Tuesday in class
13 (4/23) More Graphs Chapt. 12 HW10
14 (4/30) Searching and Sorting Chapt. 10

Sorting Animations:
merge sort
quick sort(animation is near bottom of page, choose Animation->disable to make it run faster)
compare many algs

Finals Week --- --- Final Exam, Wed. May 15, 9am-noon