COURSE TITLE
============

Algorithms and Data

COURSE DESCRIPTION
==================

Introduces the basic principles and techniques for the design,
analysis, and implementation of efficient algorithms.  Introduces
information theory and covers fundamental structures for representing
data.  Concludes with a discussion of complexity theory and the notion
of hardness of problems.

COURSE SYLLABUS
===============

REQUIRED: The following is a list of required topics.  Under each
topic, there is a collection of sub-topics.  In cases where the
sub-topic is suggested and not required, sub-topic is enclosed is
square brackets ("[]").

-- Asymptotic analysis

	O-notation, recurrences, Master theorem

-- Formal methods for establishing algorithm correctness

	mathematical induction, loop invariants

-- Divide-and-conquer paradigm

	[sorting and searching]

	[selection]

	[matrix multiplication]

	[Fast Fourier transform]

-- Data representations

	Abstract data types and representation of fundamental structures

	Flat and hierarchical representations

	Lossless & lossy compression: [Huffman's encoding],
	[Liv-Zempel], [JPEG], [MPEG]

-- Introduction to information theory

	Shannon's theorem, entropy

	[Digital representation of analog data, Nyquist's theorem]

-- Maintenance of dynamic data

	[balanced binary search trees]

	[hash tables]

-- Basic graph algorithms

	graph traversals

	graph optimization problems: [minimum spanning trees],
	[shortest paths], [network flows]

-- Optimization techniques

	greedy algorithms

	[dynamic programming]

OPTIONAL: Here is a partial list of optional topics.

-- Introduction to NP-completeness: This topic is covered in the
"Theory of Computation" course.  Toward the end of the "Algorithms &
Data" course, time-permitting, covering this topic would reinforce the
concepts taught in the Theory course and also connect them well with
the "upper bound" results taught throughout the course.

	P and NP classes

	polynomial-time reduction

	NP-hardness proofs

-- High-level conceptual data models: e.g., relational data model.

-- Amortized analysis

-- Coding theory

-- Cryptography

-- Special topics

	linear programming
	
	string algorithms (compression, string matching)
	
	approximation algorithms

	computational geometry
	
	numerical algorithms

RECOMMENDED TEXTBOOK:

T. Cormen, C. Leiserson, and R. Rivest, "Introduction to Algorithms",
MIT Press/McGraw-Hill (latest edition expected in Fall 2001).

EXPECTATIONS FOR STUDENT PREPARATION
====================================

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

The courses Fundamentals of CS 2 and Discrete Structures (offered by
the Math department?) satisfy the prerequisites.

OUTCOMES
========

A major objective of this course is to provide solid theoretical
foundations and technical knowledge that form the basis of effective
problem-solving in all areas of computer science.  Techniques for
abstraction, design and analysis, data representation and notions of
complexity of information and problems are covered, which enable the
students to formally analyze problems and attack them.  It is expected
that the systematic coverage of algorithmic techniques and underlying
theoretical concepts in the course will vastly enhance the
problem-solving skills of the students.

Specific goals:

-- Understand asymptotic notation, be able to express running times of
algorithms as recurrences, and solve basic recurrence relations.

-- Be able to establish loop invariants for simple iterative
algorithms.

-- Understand algorithm design paradigms such as divide-and-conquer,
the use of data structures in managing dynamic data sets, and be able
to apply it in practical scenarios.

-- Know the basic ideas of Shannon's theory of information and
entropy.

-- Know universal techniques for finitely-valued and infinitely-valued
abstract data types.

-- Know examples of hierarchical data representations and understand
basic compression techniques.

-- Understand graph representations, be able to express problems in
terms of graphs (wherever applicable), and know basic graph traversal
algorithms.

-- Understand the notion of optimization and be familiar with the
greedy approach.