S-Q 1998 Expanded Syllabus

Handouts

6/22 - Introduction, Big-O, and ADTs

• Reading: Weiss 1-2, Ellard 1-2
• 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:
  • Syllabus and course info. Changes, if any, will be reflected in the on-line copy of the syllabus.
  • Assignment 1 (pdf, ps)
  • Assignment 2 (pdf, ps)
  • Course Book, chapters 1-5. Chapter 1 is course info, and chapter 2 is related to the 6/22 lecture material. Chapter 3 should be review-- if not, please review this material immediately! Chapters 4 and 5 are related to 6/24 lecture material.
  • Student questionaire.
  • Excerpts from Academic honesty and Rules and Regulations Concerning Computer Use.
  • UNIX tools for S-Q. Specific utilities we'll be using for S-Q.

• Lecture notes: introduction, course overview, big-O notation, and ADTs (pdf, ps)
• Online references:
  • Contact information for Professors Dan Ellard and Penny Ellard.
  • Examples from Weiss
  • A Brief UNIX tutorial for people who are new to UNIX. This page only scratches the surface-- for a real tutorial, consult the Harley Hahn book.
  • A UNIX quick reference card.
  • A GDB quick reference card.
  • A guide to vi. Terse, but covers a lot.
  • A make tutorial. You don't need to know much about make for this course, but you might find this interesting.
  • Notes on programming style from Brian Kernighan. Even though this is not a programming course, style is always important.

6/24 - Proofs, Linked Lists, Dynamic Memory Allocation in C.

• Reading: Weiss 3.1-3.4
• Handouts:
  • Notes on proofs (pdf, ps)
  • Notes on singly-linked lists (pdf, ps)
  • Notes on doubly-linked 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 6-9

7/1 - Trees

• Reading: Weiss 4.1-4.3, Ellard 6
• Handouts:
  • Notes on trees, binary trees, binary search trees, and tries. (pdf, ps)
  • Practice midterm questions.
• Other reading:
  • Solutions to 1997 Hourly #1
  • A sample solution for assignment 1: (pdf, ps), array.c, string.c.

7/6 - Balanced Trees and Related Topics

• Reading: Weiss 4.5-4.7
• Due: Assignment 2
• Handouts:
  • Notes on B-trees and splay trees (pdf, ps)
  • Notes on tries (pdf, ps)

7/8 - Heaps and Priority Queues

• Reading: Weiss 6.1-6.4
• The First Hourly (pdf, ps)
• Handouts:
  • Lecture notes on heaps and priority queues (pdf, ps)
  • Assignment 3 (pdf, ps)
• Animated heap demos

7/13 - Searching and Sorting

• Reading: Weiss 7.1-7.3, 7.6-7.7
• Handouts:
  • Lecture notes on searching and sorting (pdf, ps)
  • A sample solution for assignment 2 (pdf, ps), dllist.c, deque.c.
  • Solution set for the first hourly (pdf, ps)
  • Graduate paper assignments. (pdf, ps)
• Animated sorting demos

7/15 - Radix Sort and Heap Sort

• Reading: Weiss 7.5, 7.8-7.11
• Due: Assignment 3.
• Handouts:
  • Lecture notes on bucketsort and radixsort (pdf, ps)
  • Assignment 4 (pdf, ps)

7/20 - Introduction to Graphs

• Reading: Weiss 9.1-9.3
• Handouts:
  • Notes on graphs (pdf, ps)
  • A sample solution for assignment 3 (pdf, ps), animals.c, tree_utils.c.
• Sample paper topics

7/22 - Graph Algorithms

• Reading: Weiss 9.5-9.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:
  • Number 3.b (Topological Sort),
  • Number 4.b (Dijkstra's Algorithm), and
  • Number 4.d (Prim's Algorithm)
  • Corrected Solution to 2.a

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

• Reading: Ellard 8 (if necessary), 9
• Handouts:
  • Course book: chapters 10-11
  • Notes on data structures and I/O (pdf, ps)
  • Notes on data compression (pdf, ps)
  • A sample solution for assignment 4 (pdf, ps), radixsort.c, mergesort.c.
  • Solution set for the second hourly (pdf, ps)
• Assignment 5 hints

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
• Drop-dead date for assignment 5

8/10 - Course Review

• Handouts:
  • A sample solution for assignment 5 (pdf, ps), graph_con.c, hash_bit.c.
  • Sample solution to the 1997 practice exam (pdf, ps)
  • Sample solution to the 1997 final exam (pdf, ps)

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's home page
• Penny Ellard's home page