Description
To study a variety of useful algorithms and analyze their complexity; by that experience to gain insight into principles and data-structures useful in algorithm design.
Credits: 4
01:198:112; 01:198:206.
Please note that courses for which a student has received a grade of D cannot be used to satisfy prerequisite requirements.
Semesters Offered:Spring and fall
Topics: Methods for expressing and comparing complexity of algorithms: worst and average cases, lower bounds on algorithm classes, verification of correctness. Application of such analysis to variety of specific algorithms: searching, merging, sorting (including quick and heap internal and Fibonacci external sorts); graph problems (including connected components, shortest path, minimum spanning tree. and biconnected components); language problems (including string matching and parsing).
Consideration of a number of hard problems: knapsack, satisfiability, traveling salesman problems.
Development of NP-complete classification and its consequence.
Approximation algorithms.
Expected Work: Regular exercises, (about) 6 small programs
Exams: Short quizzes, midterm and final exam
