CS547 Computer Algorithms (Fall 2006)
Course Prerequisites: CS344 Algorithms and Data Structures and (MA211
Foundations or MA346 Applied Algebra and Discrete Mathematics)
Course Contact InformationInstructor: Chris
Lectures: MWF 10am SC 344
Office hours: MW 3-5pm and F
3-4pm SC 377
Contact: SC 377, firstname.lastname@example.org
Text: Jon Kleinberg, Eva Tardos , Algorithm
Design Addison Wesley (2005).
Topical OutlineThis 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 network flow. Some emphasis
will be put on graph-theoretic problems and data structures that are relevant to
them. We will discuss the theory of NP-completeness on the limitations of
solving problems efficiently. Then we will discuss mehtods for overcoming
intractibility, such as approximation, local search and randomized algorithms.
Objectives and outcomesThe 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 and greedy algorithms
- Graph theory and some of its algorithmic problems.
- Network flow
- Rudimentary theory of NP-completeness.
- Extending limites of tractiblility: approximation, local search and
Requirements and PoliciesAlthough attendance is not mandatory, students
are responsible for all course materials covered in lectures 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. If a student exchanges ideas with another student or gets
ideas from another source, then that source must be mentioned on the homework
paper. If that is not done, then it is consdidered cheating. Of course it is
also considered cheating to copy something even if the source is referenced.
Please refer to the Clarkson University Regulations for more guidelines on
academic integrity and related matters.
Grading SchemeThere is no final exam in this course (pending approval).
- Test 1: 20% (early October)
- Test 2: 20% (early November)
- Homework: 30%
- Final Exam: 30%
Tentative Course Schedule
- (Chapter 1) Introduction.
- (Chapter 2) Basics of Algorithm Analysis.
- (Chapter 3) Graphs.
- (Chapter 4) Greedy Algorithms.
- (Chapter 5) Divide and Conquer.
- (Chapter 6) Dynamic Programming.
- (Chapter 7) Network Flow.
- (Chapter 8) NP and Computational Intractability.
- (Chapter 9) PSPACE (briefly).
- (Chapter 10) Extending limits of tractability.
- (Chapter 11) Approximation Algorithms.
- (Chapter 12) Local Search.
- (Chapter 13) Randomized Algorithms.