Instructor: Doug Lea
Class: 9:35am T-Th
Office/Lab hours. Normally every day 11-12
Course home page:
Prereqs: CSC241 (CSC221 also strongly encouraged).


The design, implementation, and analysis of data structures and algorithms for data stores, data streams, graphs, and related domains, along with their use in interactive networked applications.



Upon completion of this course, students will demonstrate ability to:


Background on most data structures and algorithms is easily found on the web; useful resources on particular topics are mentioned in class. However, I recommend that you buy the following book that will be referred to as a basic source on most topics, and that you might want to keep around as a good reference: Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. MIT Press / McGraw-Hill.

You will also be expected to work through several online tutorials and related readings.


Subject to minor change:
Two exams (35%)
Exam questions cover the design and theory of operation of data stores, graphs, and related data structures and algorithms, as well as comparison of different algorithms with respect to algorithmic efficiency and appropriateness for solving given problems. See Practice exam.
3-4 programming assignments (if 3, the third has multiple parts) (65%)
Projects entail specialized versions of data stores and graphs in support of interactive network-based applications. Programs may not be submitted unless they successfully run according to specification. You must demo your program to me within 2 days of submitting it. Five percent credit is taken off per day late.
  1. Assignment 1
  2. Assignment 2
  3. Assignment 3

Campus references

See the CS and College course policies and resources.

If you have a disabling condition, which may interfere with your ability to successfully complete this course, please contact the Office of Disability Services.

SUNY Oswego is committed to Intellectual Integrity. Any form of intellectual dishonesty is a serious concern and therefore prohibited. The full policy can be found at


Here are the targeted topics for lectures, not including classes for review, exams, or coverage of project-specific applications for data analytics. Topics don't always fit exactly into class times, so these don't always exactly correspond to dates.
  1. Overview; Interfaces vs implementations; applications
  2. Bitsets: relation to discrete math structures, big-O analysis
  3. Hashing: probabilistic analysis, chained tables
  4. Hashing: hash functions, non-chained tables
  5. Balanced trees: average vs worst case analysis; 2-3-4 trees
  6. Red-black trees; as 2-3-4 emulation; graphical and code views
  7. Traversal, range queries, and deletion for (balanced) trees
  8. Secondary storage: latencies, buffering, file systems, data representation
  9. Data representations for persistence; marshalling, Java APIs
  10. B-tree and hash based persistent data stores
  11. Overview other data structures for data stores: tries, prefix, skiplists
  12. Graph terminology, properties, representations
  13. Graph traversal: depth-first, breadh-first, paths
  14. Spanning trees and cycles; union-find algorithms
  15. Priority queues and their role in weighted graph problems; Kruskal MST
  16. Weighted graph path and tree algorithms: Prim/Dijkstra
  17. Network Flow: Edmonds/Karp; overview of others and applications
  18. Dynamic programming; application to all-pairs paths
  19. Algorithm design techniques: divide & conquer, greedy, etc
  20. Analysis for general techniques; including overview of master theorem
  21. NP complete problems; definitions, examples
  22. Approximation and probabilistic approaches to NP-complete problems
  23. Compression: Huffman, LZW, overview of others
  24. Strings: exact matching; overview of other problems and algorithms
  25. Storage management and garbage collection

Doug Lea