CSU690 Algorithms & Data

Introduces the basic principles and techniques for the design and analysis of efficient algorithms and data representations. Discusses asymptotic analysis and formal methods for establishing the correctness of algorithms. Considers divide-and-conquer algorithms, graph algorithms, and optimization techniques. Introduces information theory and examines methods for representing, organizing, and compressing data.

CSU200, CSU213, MTHU481 Prerequisites by topic: Discrete mathematics (sets, functions, elementary combinatorics) Elementary data structures (arrays, linked lists, trees, hashing, priority queues) Encapsulation and abstraction Programming Recursion and induction Elementary probability theory

Recommended textbook: T. Cormen, C. Leiserson, R. Rivest, and C. Stein, "Introduction to Algorithms", MIT Press/McGraw-Hill, second edition, 2001. For the component of the course covering information theory and data compression, the following books are suggested references: T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley, 1991. I. Witten, A. Moffat, and T. Bell, "Managing Gigabytes", Academic Press, second edition, 1999. D. Salomon, "A Guide to Data Compression Methods", Springer-Verlag, 2000.

The list below does not provide a chronological order for covering the course material. Optional topics are enclosed in square brackets ("[]"). Analysis techniques Asymptotic notation Recurrences Formal methods for establishing algorithm correctness Mathematical induction Loop invariants [Amortized analysis] Algorithm design paradigms Divide-and-conquer Sorting [Other examples such as selection and FFT] Greedy algorithms Graph algorithms Graph traversals Selected graph optimization problems [Dynamic programming] Data representation and maintenance Data structures Binary search trees Hashing Basic information theory Entropy Source coding [Digital representation of analog data, Nyquist's theorem] Lossless and lossy compression [Advanced topics Introduction to NP-completeness Approximation algorithms Domain-specific problems: E.g., Computational geometry String algorithms Cryptography]

Upon completion of this course, a student should: Be familiar with O-notation, be able to express running times of algorithms as recurrences, and solve simple recurrence relations. Be able to establish loop invariants for simple iterative algorithms. Understand the divide-and-conquer algorithm design paradigm and be able to apply it in practical scenarios. Understand graph representations, be able to express simple problems in terms of graphs (wherever applicable), and know basic graph traversal (search) algorithms. Understand the notion of optimization and be familiar with the greedy approach. Be familiar with basic ideas of information theory and the notion of entropy. Be aware of commonly used compression techniques. Understand basic data structures for managing dynamic data sets and be able to apply them in practical scenarios.

The course outcomes will be measured and verified by: Written homework assignments (5-10 recommended) Programming assignments (1-2 optional at discretion of instructor) Quizzes (optional at discretion of instructor) Major exams during the term (1-2) Final exam