Skip to content Skip to navigation

Design and Analysis of Computer Algorithms

01:198:344

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
Prerequisite: 

01:198:11201:198:206.

Please note that courses for which a student has received a grade of D cannot be used to satisfy prerequisite requirements.

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 (See Instructor's Class URL for more details)
Learning Goals: 
Computer Science majors ...
  • will be prepared to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and foundations of computer science (e.g., techniques of program design, creation, and testing; key aspects of computer hardware; algorithmic principles).
  • will acquire a deeper understanding on (elective) topics of more specialized interest, and be able to critically review, assess, and communicate current developments in the field.
  • will be prepared for the next step in their careers, for example, by having done a research project (for those headed to graduate school), a programming project (for those going into the software industry), or some sort of business plan (for those going into startups).
Semester: 
Fall
Spring
Course Type: 
Undergraduate

Check the University Schedule of Classes to see if this course is open.

Request an Special Permission Number here if the class is full.