MA211 Foundations or MA346 Applied Algebra and Discrete Mathematics

CS344 Algorithms and Data Structures

**INFORMATION****Instructor** Christino
Tamon**Lectures** MWF 08:00 Snell 169**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, and
Clifford Stein, *Introduction to Algorithms*, 2nd edition (Cambridge,
Massachusetts: The MIT Press, 2001).
**RECOMMENDED**

Michael R. Garey and David S. Johnson,
*Computers and Intractability: A Guide to the Theory of
NP-Completeness* (New York: W.H. Freeman, 1979).

**TOPICAL OUTLINE**

This course studies advanced algorithmic
techniques for solving computational problems efficiently. Some emphasis will be
given on graph-theoretic problems and data structures that are relevant to them.
The theory of NP-completeness on the limitations of solving problems efficiently
will also be discussed.

**OBJECTIVE & 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:

- Asymptotics and tools for analyzing complexities of algorithms.
- Advanced design and analysis of algorithms.
- Theory of NP-completeness.
- Graph theory and some of its algorithmic problems.

**REQUIREMENTS & 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 (TENTATIVE)**

Midterm Test: 20%

Final
Exam: 40%

Assignments and Quizzes: 40%

**SCHEDULE OF TOPICS**

(Chapter 3 & 4) Asymptotics and
Recurrences

(Chapter 15, 16, 17) Dynamic programming, Greedy algorithms,
Amortized analysis

(Chapters 22-26) Graph algorithms

(Chapter 29) Linear
programing

(Chapter 34) NP-Completeness

(Time permitting) Randomized
algorithms