Syllabus for CS 305 & 503
Data Structures & Algorithms

Spring 2010

---

The syllabus is broken up into five sections:

1. Introduction

2. Linked Lists, Stacks, and Queues

3. Analysis and Estimation

4. Trees

5. Sorting and Searching

Section 1: Introduction, Tuesday, 19 January through Thursday, 28 January.

Class notes

Introduction, audio (33 mbytes)
Classes and ADTs
A Code Duplication Experiment
Interfaces, audio (31.4 mbytes)
Generics, audio (40.4 mbytes)

Section 2: Linked Lists, Stacks, and Queues, Tuesday, 2 February through Thursday, 18 February.

Class notes

Linked lists
List Traversal, audio (39.8 mbytes)
Stacks, audio (42.3 mbytes)
Queues, audio (41.2 mbytes)
Odds and Ends, audio (22.7 mbytes)
Java Collections, audio (41.9 mbytes)

Assignment

Assignment 1 (last modified on 17 February 2010) available on Tuesday, 2 February; due on Tuesday, 23 February at 11:30 p.m.
A solution
The grades.

Quiz — Tuesday, 23 February

The answers.
The grades.

Section 3: Analysis and Estimation, Tuesday, 23 February through Thursday, 18 March.

Spring Break — Tuesday and Thursday, 9 and 11 March

Mid-term Grades — due Tuesday, 16 March.

Class notes

Asymptotic Estimates, audio (12.1 mbytes), audio (33 mbytes), audio (34.2 mbytes)
Asymptotic Estimates in Practice, audio (42.9 mbytes), audio (24.8 mbytes)
Performance Measurement
Performance Measurement in Practice

Assignment

Assignment 2 (last modified on 14 March 2010) available on Tuesday, 23 February; due on Tuesday, 23 March at 11:30 p.m.
A solution.
The grades.

Quiz — Tuesday, 23 March

The answers.
The grades.

Section 4: Trees, Tuesday, 23 March through Thursday, 8 April.

Drop day — Monday, 29 March

Class notes

Tree Basics, audio (42.9 mbytes), , audio (37.1 mbytes)
Binary Search Trees, audio (41.6 mbytes)
Heaps and Priority Queues
Treaps, audio (43.5 mbytes)
Balanced Trees

Assignment

Assignment 3 (last modified on 27 April 2010) available on Tuesday, 30 March; due on Tuesday, 20 April at 11:30 p.m.
The grades.

Quiz — Tuesday, 13 April

The answers.
The grades.

Section 5: Sorting and Searching, Tuesday, 13 April through Thursday, 29 April.

Class notes

Sorting Basics, audio (14.7 mbytes)
Faster Sorting
Hashing, audio (41.3 mbytes)
Hashing In Practice, audio (26.7 mbytes)

Assignment

Assignment 4 (last modified on 12 April 2010) available on Tuesday, 13 April; due on Tuesday, 4 May at 11:30 p.m.
The grades.

Quiz — Thursday, 29 April

The answers.
The grades.

Open Lecture about finger trees at 5:30 to 7:30 on Thursday, 6 May in HH C-1.