Swarthmore CS 35.2, Spring '99
Algorithms and Object-Oriented Programming

synopsis of this page in postscript (for printing)

Time and Locations

Tu/Th 1:15-2:30
Location alternates between Kohlberg 116 on Tuesdays and Sproul CS Lab on Thursdays.

Description

CS 35 introduces fundamental concepts in computer science that together form a solid basis for further study in the field. In particular, we will examine the data structures -- and the algorithms that operate with them -- that are central to contemporary software. This course develops abstract thinking so that the design and implementation of large robust software systems occurs at the conceptual level -- rather than at the level of bits and bytes. To do so, we will progressively encapsulate low-level data and instructions as reusable objects. All the while, we will consider algorithms in terms of their resource (time and space) costs and emphasize techniques for writing correct and modular code. Toward course end, we will study the basics of concurrency, user-interface construction, and network programming. Where appropriate, research issues in computer science will be discussed.

Instructor

Lorenz Huelsbergen
lorenz@cs.swarthmore.edu or lorenz@research.bell-labs.com; please place "cs35" in subject if you use the latter

Office Hours: Tu/Th 12:30-1:15, Sproul CS lab/seminar room; or by appointment
Phone: (908) 582-4628 MWF

Texts

Required text
Data Structures and Algorithms in Java, by Goodrich and Tamassia, John Wiley and Sons, ISBN 0-471-19308-9. (errata)

Auxiliary texts
Introduction to Algorithms, by Cormen, Leiserson, and Rivest. MIT Press, 1990, ISBN 0-262-03141-8.

The Java Programming Language, by Arnold and Gosling. Addison-Wesley, ISBN 0-201-63455-4.

Writing solid code : Microsoft's techniques for developing bug-free C programs, by Maguire. Microsoft Press, ISBN 1-55615-551-4.

Tentative Syllabus

syllabus in postscript (for printing)
Week I: INTRODUCTION
Jan. 19: Lecture: course organization, Java types and control flow
Jan. 21: Lab (reading)
Week II: OBJECTS
Jan. 26: Lecture: Java objects, inheritance, polymorphism (reading)
Jan. 28: Lab (reading)
Week III: LINEAR STRUCTURES
Feb. 2: Lecture: arrays, vectors, stacks (reading)
Feb. 4: Lab (reading)
Week IV: MORE LINEAR STRUCTURES
Feb. 9: Lecture: lists, queues (reading)
Feb. 11: Lab (reading)
Week V: APPLICATIONS OF LINEAR STRUCTURES
Feb. 16: Lecture: searching, sorting (reading)
Feb. 18: Lab (reading)
Week VI: EXAM WEEK
Feb. 23: Exam 1, Kohlberg 116
Feb. 25: Lab
Week VII: ACYCLIC STRUCTURES
Mar. 2: Lecture: trees (reading)
Mar. 4: Lab (reading)
Week VIII: SPRING BREAK
Week IX: MORE ACYCLIC STRUCTURES
Mar. 16: Lecture: trees, string matching (reading)
Mar. 18: Lab (reading)
Week X: APPLICATIONS OF ACYCLIC STRUCTURES
Mar. 23: Lecture: priority queues, heaps (reading)
Mar. 25: Lab (reading)
Week XI: DICTIONARIES
Mar. 30: Lecture: sequences, hash tables, tree-based dictionaries (reading)
Apr. 1: Lab (reading)
Week XII: EXAM WEEK
Apr. 6: Exam 2, Kohlberg 116
Apr. 8: Lab
Week XIII: CYCLIC STRUCTURES
Apr. 13: Lecture: graphs (reading)
Apr. 15: Lab (reading)
Week XIV: NO LECTURE/LAB
Apr. 20: Work on homework/project (reading)
Apr. 22: Work on homework/project (reading)
Week XV: SYSTEM PROGRAMMING
Apr. 27: Lecture: spanning trees/string matching (reading)
Apr. 29: Lab
Week XVI: READING PERIOD
Week XVII: FINAL EXAMS/PROJECTS DUE

Grading

Programs and assignments: 40%
Two exams: 10% each
Final exam: 15%
Project: 20%
Contributions in lecture/lab, etc.: 5%

Homework

Assignments will be made every week and a half, approximately. They will appear here as they are given.

Instructions on submitting homework

Homework 1 (given January 26; due February 4 before class); basic object-oriented design and programming
Homework 2 (given February 9; due February 18 before class); big-O notation, stacks, exceptions
Homework 3 (given February 18; due February 25 before class); singly and doubly linked lists, queues
Homework 4 (given February 25; due March 4 before class); merge sort, binary search, recursion
Homework 5 (given March 16; due March 23 before class); tree properties and datatypes
Homework 6 (given March 25; due April 1 before class); binary decision trees
Homework 7 (given April 8; due April 15 before class); hash tables
Homework 8 (given April 15; due April 27 before class); graphs and graph search

Exams

There will be two in-class exams during the semester (Feb. 23 and Apr. 6) and a final exam (details, TBA).

Programming Project

Overview
Frequently asked questions

Resources

Java Links

Java Workshop, an environment for building Java programs and applets, can be run locally as /usr/local/depot2/Java-WorkShop2.0/JWS/sparc-S2/bin/jws

Rules

Polices and Regulations for CS 35.2 homework, labs, and exams.
lorenz@research.bell-labs.com