CS 35: Algorithms and Object-Oriented Programming

Spring 2000
Swarthmore College
Professor Jim Marshall

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. We will be studying data structures and algorithms that 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 for analyzing various algorithms and data structures will also be presented.

There will be weekly homework exercises and programming projects illustrating the concepts presented. We will be using the Java programming language on the Computer Science Suns as our principal programming environment. 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 in grading) the development of clear, modular, well-documented programs that are easy to read, analyze, debug, and modify.

Textbooks

Contact Info

Office Hours: 4:00-5:00pm Monday, Wednesday, and Thursday.
Office: Sproul Observatory Room 6
Office Phone and Voice Mail: (610) 328-8665
E-mail: marshall@cs.swarthmore.edu (or jmarsha1@swarthmore.edu)
If you need to see me but can't make it to my office hours, I'll be happy to schedule an appointment. Please contact me by e-mail or leave a message on my voice mail.

Grading

30% Homework Assignments
20% Exam 1 (Thursday, February 10, in class)
20% Exam 2 (Tuesday, March 28, in class)
25% Final Exam
5% Class Participation

Homework Policy

Homework will generally be assigned at the beginning of the week by email and will be due the following Sunday by midnight. You will turn in your homework assignments electronically (no hardcopy printout is necessary), as will be explained in class. Late homework is not accepted, unless 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.

Academic Integrity

The utmost level of academic integrity is expected of every student. Under no circumstances may you hand in work done with (or by) someone else under your own name. If in doubt, credit the person(s) from whom you got help. Discussing ideas and approaches to problems with others on a general level is fine (in fact, encouraged) but you should never read anyone else's code or solutions, or show your code or solutions to anyone else in the class. Failure to abide by these rules constitutes academic dishonesty, and will be dealt with severely. Please do not put me or yourself in this unpleasant situation.

Good Programming Style

In its purest form, programming is the art of expressing abstract ideas about computation in language that is as clear, unambiguous, and explicit as possible. To become a expert programmer, it is not enough simply to write programs that work correctly when run on a computer. Your programs must also be easy for other humans to read and understand. Indeed, good programming is as dependent on a deeply-developed sense of aesthetics as is good writing or other types of artistic activity. In short, style matters. Accordingly, programs will be graded with respect to both style (40%) and correctness/efficiency (60%). Good object-oriented programming style typically includes the following:

On-Line Java Resources

Java Tutorial
Java Language Reference
Debugging Java Programs
Java Platform2 API Specification
More Java Platform2 Documentation
Other Java Documentation

Schedule of Topics (subject to change)

Key: JS = Java Structures, JPL = Java Programming Language

WEEK DATES TOPICS READINGS and ANNOUNCEMENTS
1 1/18 - 1/20 Introduction to Java JS Chapters 0, 1; JPL Chapters 1, 2, 3
2 1/25 - 1/27 Introduction to Java (continued) JS 2; JPL 4, 7, 12; skim JPL 5, 6, 8 (Drop/add ends Friday 1/28)
3 2/1 - 2/3 Vectors and lists JS 3, 6
4 2/8 - 2/10 Lists (continued) EXAM 1 Thursday 2/10 in class
5 2/15 - 2/17 Induction, complexity, and sorting JS 4.1, 4.2, 5
6 2/22 - 2/24 GUI programming and applets JPL 10, 17
7 2/29 - 3/2 Stacks and queues JS 7
- 3/7 - 3/9 Fun and relaxation SPRING BREAK
8 3/14 - 3/16 Iterators and trees JS 8, 10, 12.1 (Last day to withdraw Monday 3/13)
9 3/21 - 3/23 Priority queues and heaps JS 11
10 3/28 - 3/30 Balanced trees EXAM 2 Tuesday 3/28 in class
11 4/4 - 4/6 Dictionaries and hashing JS 13
12 4/11 - 4/13 Graphs JS 14
13 4/18 - 4/20 Graphs (continued) JS 14
14 4/25 - 4/27 Threads JPL 9
-TBA-FINAL EXAM