Design and Analysis of Algorithms

Offered during Fall and Spring Semesters each year.

1. Credits and contact hours: 3 credits, 4 contact hours
2. Instructor’s or course coordinator’s name: Samik Basu, Pavankumar Aduri
3. Text book, title, author, and year: Algorithm Design, Kleinberg and Eva Tardos
4. Other supplemental materials: None

Specific course information

1. Brief description of the content of the course: Basic techniques for design and analysis of algorithms. Sorting, searching, graph algorithms, string matching, and NP-completeness. Design techniques such as dynamic programming, divide and conquer, greedy method, and approximation. Asymptotic, worst-case, average-case and amortized analyses. Topics from advanced data structures such as balanced trees and hashing.
2. Prerequisites or co-requisites: Minimum of C – in COM S 228; MATH 166, ENGL 250, and COM S 230 or CPR E 310
3. Required, elective, or selected elective? Required

Specific goals for the course

1. Specific outcomes of instruction: Algorithms are the basic recipes for solving computational problems.  Upon completion of this course, students should:

• Know a set of “standard algorithms” (and data structures) and be able to model a problem to use them.
• Gain a strong foundation in designing algorithms based on common techniques, including greedy, divide and conquer, dynamic programming, etc. (1)
• Be able to reason about correctness of algorithms, either by proof or providing a counter example. (6)
• Be able to recognize intractable problems and have an idea on how to develop approximation algorithms.
• Be able to implement algorithms given their description.

Brief list of topics to be covered

• Run time, Big O and asymptotic bounds
• Sorting and searching
• Divide and conquer
• Graphs and graph algorithms
• Greedy algorithms
• Public Key cryptography, RSA algorithm
• Dynamic programming
• NP-Completeness 
• Approximation algorithms & heuristics