Design and Analysis of Algorithms

COM S 311

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 yearAlgorithm 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