### CS447/CS647/EE667 Computer Algorithms (Fall 2003)

#### Course Prerequisites: CS344 Algorithms and Data Structures and (MA211
Foundations or MA346 Applied Algebra and Discrete Mathematics)

### Course Contact Information

**Instructor**: Christino
Tamon

**Lectures**: MWF 11am SC 362

**Office hours**: MW 9-11am and
F 9-10am SC 373

**Contact**: SC 373, tino@clarkson.edu

**Text:** *Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
Clifford Stein*, **Introduction to Algorithms**
(2nd ed.) MIT Press (2001).

### Topical Outline

This course studies the algorithmic techniques for
solving computational problems efficiently. In particular, the following
techniques are covered: basic divide-conquer techniques and analysis using
recurrences, dynamic programming, greedy methods, and amortized analysis. Some
emphasis will be put on graph-theoretic problems and data structures that are
relevant to them. Finally, a discussion of the theory of NP-completeness on the
limitations of solving problems efficiently will end the course.

### Objectives and outcomes

The objective of this course is to learn
fundamental algorithmic techniques, to gain the ability to evaluate the
efficiency of algorithms, and to understand certain intractability issues
concerning hard algorithmic questions.
The specific outcomes are basic knowledge of the following:

- Asymptotic notation for comparing cost measures.
- Tools for dealing with summations and recurrences.
- Design and analysis techniques: dynamic programming, greedy algorithms,
and amortized analysis.
- Graph theory and some of its algorithmic problems.
- Rudimentary theory of NP-completeness.

### Requirements and Policies

Although attendance is not mandatory, students
are responsible for all course materials covered in lectures and any quizzes
given during class periods. Students that need to make up missing course work
must provide the required Clarkson official exempt form. All students must
submit their own work; the exchange of ideas are encouraged but ultimately the
submitted work must be the student's own. Please refer to the Clarkson
University Regulations for more guidelines on academic integrity and related
matters.

### Grading Scheme

There is no final exam in this course (pending approval).
- Tests (2): 50% (tentative dates: October 17th and November 28th)
- Assignments and Quizzes: 40%
- Project: 10% (due early December)

### Tentative Course Schedule

- (Chapters 1,2) Basic divide-conquer and recurrence
analysis for MIN-MAX problem. Lower bounds for comparison-based algorithms
(MIN, SORTING, and MIN-MAX). The SELECTION problem..
- (Chapter 3) Asymptotic growth of functions: big-Oh,
big-Omega, little-oh, little-omega, and big Theta. Summations (Appendix A):
arithmetic, geometric, Harmonic, bounding by integrals, splitting techniques,
telescoping sums.
- (Chapter 4) Recurrences: substitution method, recursion
tree method, the Master Theorem.
- (Chapter 15) Dynamic Programming: assembly line
scheduling, longest common subsequence, matrix chain multiplication..
- (Chapter 16) Greedy algorithms: activity selection
problem, fractional knapsack.
- (Chapter 17) Amortized analysis: splay trees. (ERC
reserve has handout on splay trees).
- (Chapter 34) NP-Completeness; efficient reductions:
CLIQUE, INDEPENDENT SET, VERTEX COVER.
- (Chapters 22-26) Graph algorithms: basic searches: BFS,
DFS. Topological sorting. Strongly connected components. Minimum Spanning
Trees (Kruskal & Prim). Single-source Shortest Paths (Dijkstra). All-pairs
Shortest Paths: matrix multiplication, Floyd-Warshall. Maximum Flow: Edmonds-Karp algorithm.