CSC365

Instructor: Doug Lea
Class: 9:35 T-Th
Office/Lab hours. Normally T-W-Th 11-12:30, but send mail at any time with questions or to set up online meeting
Course home page: http://gee.cs.oswego.edu/dl/csc365
Prereqs: CSC241 (CSC221 also strongly encouraged).

Overview

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.

Topics

Data structures and algorithms for data stores, including balanced trees and hash-based structures; specializations for strings.
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 membership.
Algorithms for data streams, including string matching and compression
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

Outcomes

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 applications.

Readings

Notes and links for most topics are available in the course notes. However, you may consider buying 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.

See also files from in-class coding: BitSet64, HT, DigitalTree, Persistent HT

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

Requirements

Subject to minor change:

Two exams (30%)

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.

Exercises (10%)

Very short in-class or take-home exercises extending examples covered in class. About one per week. Ungraded but discussed in follow-up classes.

3 programming assignments (60%)

Projects entail specialized versions of data stores and graphs in support of interactive network-based applications. You may work with a partner, but must also submit a brief writeup (or internal documentation) explaining collaboration strategy. Programs may not be submitted unless they successfully run according to specification. Two percent credit is taken off per day late.

You must demo within 2 days of submitting. As a substitute for live demos, you may accompany your program source and screenshots or remote screenshare of successful operation with a brief (approx one-page) design and experience account of your approach and how it changed over time. (This may be embedded as main program documentation.) If you maintain commit logs or time logs every time you work on project, a lightly edited collection of these should suffice. I may send follow-up questions before accepting.

Lectures

As detailed in course notes, 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. Some or all of the final three topics will be presented if time is available.

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, search
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
NP complete problems; definitions, examples
Algorithm design techniques: divide and conquer, greedy, etc
Analysis for general techniques; overview of master theorem
Probabilistic and approximate algorithms
Compression: Huffman, LZW, overview of others
Strings: exact matching; overview of other problems and algorithms
Storage management and garbage collection

Campus references

The CS and College policies and resources pages provide more information about:

If you have a disabling condition, which may interfere with your ability to successfully complete this course, please contact the Office of Accessibility Services.
SUNY Oswego is committed to enhancing the safety and security of the campus for all its members. In support of this, faculty may be required to report their knowledge of certain crimes or harassment. Reportable incidents include harassment on the basis of sex or gender prohibited by Title IX and crimes covered by the Clery Act. For more information about Title IX protections contact the Title IX Coordinator, 405 Culkin Hall, 315-312-5604, titleix@oswego.edu. For more information about the Clery Act and campus reporting, see the University Police annual report.
SUNY Oswego is committed to Intellectual Integrity. Any form of intellectual dishonesty is a serious concern and therefore prohibited.

Doug Lea