1. Course Number & Title
------------------------

CSU690
Algorithms & Data

2. Course Description
---------------------

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.

3. Prerequisites:
-----------------

CSU200 Discrete Structures 
CSU212 Fundamentals of CS 2 
MTHU481 Probability & Statistics

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

4. Textbooks:
-------------

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.

5. Topics Covered
-----------------

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]

6. Course Outcomes
------------------

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.

7. Measurement of Course Outcomes
---------------------------------

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