CS417
- Advanced Algorithms and Their Complexity
Algorithms
(Richard Johnsonbaugh and Marcus Schaefer)
This class is
heavy on problem solving since most algorithms are designed to solve some
particular problem. Most of the work in this class will be either to design an
algorithm for a problem or to analyze a known or proposed algorithm.
Quizzes, homework and a
short program or two 30%
Presentation (mid-April) 10%
Midterm - Thursday,
Final – Thursday,
Goals of this class:
- Understand the
different complexity classes.
- Learn how to count
basic operations, and place an algorithm into a complexity class.
- Understand classes
of algorithms and when they can be applied to solving a problem.
- To see many ways
to solve a problem and to work on many different types of problems.
First 4 weeks - Algorithm
complexity and analysis of sorting strategies.
Chapters 1 & 2 should be a review of material covered in MA207
and CS211 (sections 3.1-3.4), so you should be able to skim/read through them
quickly. You should know what information is in these chapters in case you need
to refer to them later on! The first week will cover selected topics from those
sections as well as some areas that are covered in chapters 1-4. The next three
weeks will present some algorithms that are not in the book, and from chapters
4-6 and section 3.5.
Next 3 weeks - Searching
techniques, disjoint sets, and pattern matching.
Advanced search tree data structures, hashing, section 3.6 and
pattern matching strategies (Chapter 9). The midterm will follow, and will
include the preceding topics.
Next 5 weeks – Graph
Algorithms, Greedy algorithms and Dynamic Programming: chapters 5 and 7-8.
Last 2 weeks - Probabilistic
and approximate algorithms - chapters 10 and 11.
Cover some (NP) problems where exhaustive searching is prohibitive
due to the exponential growth of the search space as the data set increases.
Web site: http://academics.smcvt.edu/jtrono/courses/cs417.htm
Office Hours: MW 1:30-3pm, T & TH
1-2pm (or by appointment): JeanMarie 267 (x2432)