CS 840: Advanced
Topics in the Theory of Computation
Syllabus: Spring 2006
Time:
Room: 406 Russ
Instructor: Professor Sudkamp
Office Hours:
Office: 431 Russ
Engineering Center
email:
tsudkamp@cs.wright.edu
phone:
775-5118
The text for this
class is Introduction to Algorithms
by Cormen, Leiserson, Rivest, and Stein (2nd edition). There is an
enormous amount of pertinent material in Part I, Foundations, and the Appendix Mathematical
Background. Many of these topics have
been introduced in previous courses, in particular in Data Structures and
Discrete Mathematics. You may often find
it necessary to refer to the sections in the book covering these topics. We will briefly review the first four
chapters in class.
The course begins by
introducing the following general strategies for solving problems and analyzing
the complexity of these approaches:
Chapter
2. Divide and conquer algorithms
Chapter
15. Dynamic programming
Chapter
16. Greedy algorithms
After covering these
basic problem-solving strategies, we will apply these techniques to a number of
applications. Applications that may be
considered include
* Parallel algorithms
* Graph algorithms
(chapters 22--26)
* String matching
algorithms (chapter 32)
Grading: A midterm exam, a final exam, and two
homework assignments will be used to determine the grades for this class. The
grade will be determined in following manner
Midterm 35%
Final 45%
Homework 20% (10% each)
The dates for the
exams are
Midterm: Monday, April 24
Final: Wednesday, June 7,
The final may be in
class, take home, or a combination of the two.
This will be discussed in class.
There will be no
make-up exams (other than for documented emergencies). Be sure to arrange your schedule to be
available for the exam periods.
In class exams will be
open book and open notes.
Attendance: Attendance at classes
is strongly recommended. If you miss a
class, it is your responsibility to obtain class notes from other students to
be prepared for subsequent topics. There
will be no make-up exams except for documented emergencies.