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.
- Data structures and algorithms for data stores, including
balanced trees and hash-based structures; specializations for
- Persistence: Data structures and algorithms using secondary
storage and retrieval techniques; performance impact of memory
hierarchy and IO; the role and use of data stores in
databases and caches.
- Graphs: representation techniques including those for
weighted and directed graphs; algorithms for traversal, spanning
trees, paths, and flow; auxiliary data structures and
algorithms, including those for priority queues and set
- Algorithms for data streams, including string matching and
- Algorithmic strategies, including combinatorial, greedy,
divide-and-conquer, dynamic programming.
- Analysis: Uses and extensions of Big-O notation, analysis of
iterative and recursive algorithms; NP Completeness.
- Applying data structures and algorithms in networked and
interactive applications, including review of relevant
networking APIs and GUI frameworks
Upon completion of this course, students will demonstrate ability to:
- [Design] Choose among relevant algorithmic strategies to
approach problems; apply data structure invariants such as tree
balance to design efficient operations; represent and solve
problems using graph algorithms, including search, traversal,
spanning trees, and paths.
- [Analysis] Determine asymptotic upper bounds on time and space
complexity; choose among algorithms in a given context based on
efficiency and applicability; recognize NP-completeness when
attempting to solve a given problem.
- [Development] Incorporate specializations of data structures
and algorithms (including those for persistent data stores and
graphs) in support of interactive and network-based
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 /
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
- 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.
- Assignment 1
- Assignment 2
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 http://www.oswego.edu/integrity
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.
- Overview; Interfaces vs implementations; applications
- Bitsets: relation to discrete math structures, big-O analysis
- Hashing: probabilistic analysis, chained tables
- Hashing: hash functions, non-chained tables
- Balanced trees: average vs worst case analysis; 2-3-4 trees
- Red-black trees; as 2-3-4 emulation; graphical and code views
- Traversal, range queries, and deletion for (balanced) trees
- Secondary storage: latencies, buffering, file systems, data representation
- Data representations for persistence; marshalling, Java APIs
- B-tree and hash based persistent data stores
- Overview other data structures for data stores: tries, prefix, skiplists
- Graph terminology, properties, representations
- Graph traversal: depth-first, breadh-first, paths
- Spanning trees and cycles; union-find algorithms
- Priority queues and their role in weighted graph problems; Kruskal MST
- Weighted graph path and tree algorithms: Prim/Dijkstra
- Network Flow: Edmonds/Karp; overview of others and applications
- Dynamic programming; application to all-pairs paths
- Algorithm design techniques: divide & conquer, greedy, etc
- Analysis for general techniques; including overview of master theorem
- NP complete problems; definitions, examples
- Approximation and probabilistic approaches to NP-complete problems
- Compression: Huffman, LZW, overview of others
- Strings: exact matching; overview of other problems and algorithms
- Storage management and garbage collection