SQ 1998 Expanded Syllabus
This page gives an expanded syllabus, listing all of the readings and
handouts, as well as some notes about the readings and suggested
related readings. Consult the syllabus and
information page for assignments and due dates.
This section lists all the handouts that have been distributed in
class, along with a brief description of each. This list will be
updated as the semester progresses.
 6/22  Introduction, BigO, and ADTs

 Reading: Weiss 12, Ellard 12
 Tasks (to be done before lecture on Wednesday, 6/24):
 Get a computer account by logging in to
fas.harvard.edu as user
register (no password). You must
have an FAS computer account in order to do the
homework for this course.
 Purchase the textbook (Data Structures and Algorithm
Analysis in C (2nd edition) by Mark Allen Weiss)
at the Harvard Coop.
 Fill out the student survey (passed out in lecture).
 Handouts:
 Lecture notes: introduction, course overview,
bigO notation, and ADTs
(pdf,
ps)
 Online references:
 6/24  Proofs, Linked Lists, Dynamic Memory Allocation in C.

 Reading: Weiss 3.13.4
 Handouts:
 Notes on proofs
(pdf,
ps)
 Notes on singlylinked lists
(pdf,
ps)
 Notes on doublylinked lists
(pdf,
ps)
 Notes on dynamic memory allocation in C
(pdf,
ps)
 6/29  Properties and Implementation of Stacks, Queues
and Sparse Arrays

 Reading: Ellard 3 (if necessary), 4, 5
 Due: Assignment 1.
 Handouts:
 Lecture overview, notes on reversing and rotating lists
(pdf,
ps)
 More linked lists notes_1998
(pdf,
ps)
 Notes on stacks
(pdf,
ps)
 Notes on queues
(pdf,
ps)
 Still more notes on queues
(pdf,
ps)
 Notes on amortized analysis
(pdf,
ps)
 Course book: chapters 69
 7/1  Trees

 Reading: Weiss 4.14.3, Ellard 6
 Handouts:
 Notes on trees, binary trees,
binary search trees, and tries.
(pdf,
ps)
 Practice midterm questions.
 Other reading:
 7/6  Balanced Trees and Related Topics

 Reading: Weiss 4.54.7
 Due: Assignment 2
 Handouts:
 Notes on Btrees and splay trees
(pdf,
ps)
 Notes on tries
(pdf,
ps)
 7/8  Heaps and Priority Queues

 7/13  Searching and Sorting

 7/15  Radix Sort and Heap Sort

 Reading: Weiss 7.5, 7.87.11
 Due: Assignment 3.
 Handouts:
 Lecture notes on bucketsort and radixsort
(pdf,
ps)
 Assignment 4
(pdf,
ps)
 7/20  Introduction to Graphs

 7/22  Graph Algorithms

 Reading: Weiss 9.59.6
 Due: Assignment 4.
 Handouts:
 Notes on graphs algorithms
(pdf,
ps)
 Hourly #2 Practice problems
(pdf,
ps)
 Some solutions to the practice hourly.
 Other reading:
Solutions to the Hourly #2 practice problems:
 7/27  Hashing and Hash Tables

 Reading: Weiss 5, Ellard 7
 The Second Hourly
(pdf,
ps)
 Handouts:
 Assignment 5
(pdf,
ps)
 Notes on hash tables
(pdf,
ps)
 7/29  I/O of Data Structures

 8/3  String Searching

 Reading: Ellard 10
 Due: Assignment 5.
 Handouts:
 Notes on string searching
(pdf,
ps)
 Practice final from 1997
(pdf,
ps)
 Final from 1997
(pdf,
ps)
 8/5  Randomized Algorithms

 Reading: Weiss 10.4, Ellard 11
 Handouts:
 Cookies of various kinds
 Notes on randomized algorithms
(pdf,
ps)
 8/7  Last Day of Classes

 Graduate paper due
 Dropdead date for assignment 5
 8/10  Course Review

 8/12  Final Exam  SciCen 102b

 The exam is closed book, closed notes. No calculators or
other aids will be allowed.
 The exam will begin at 6:15, and be three hours in
length.
 Handouts: 1998 Final Exam
(pdf,
ps)
Recommended Reading and References
 Hahn

Harley Hahn's Student Guide to UNIX (second edition), by
Harley Hahn. A valuable reference for anyone who wants to
learn more about UNIX.
 Lewis and Denenberg
 Data Structures and Their Algorithms, by Harry Lewis and
Larry Denenberg. This book deserves a place on every computer
scientist's bookshelf.
 Lewis and Papadimitriou
 Elements of the Theory of Computation, by Harry Lewis and
Christos Papadimitriou. The first chapter of this book gives
a good review of the mathematics relevant to data structures
and algorithms. (I haven't seen the 2nd edition, which came
out in 1997, but the original edition included this review.)
 Cormen, Leiserson, Rivest
 Introduction to Algorithms, by Cormen, Leiserson, and
Rivest. An large, encyclopedic survey of algorithms.
Mathematically advanced. If you pursue computer science,
eventually you will own a copy.
 Kernighan and Ritchie
 The C Programming Language (second edition), by Brian
Kernighan and Dennis Ritchie. The definitive reference
for the C language.
 Harbison and Steele
 C: A Reference Manual (fourth edition), by Samuel
Harbison and Guy Steele. If you can't figure it out from K+R,
this book is the next place to check.
Other Links
Daniel Ellard