CS314: Algorithm Design & Analysis

  • Credits L-T-P [C]: 3-0-0 [3]
  • Where: Room-207, Lecture Hall Building
  • When: 9:00AM - 9:50AM, Mon-Wed-Fri
Pre-requisite: CS112, CS121, CS222

Syllabus

  • Advanced Data Structures:
    • Amortize Analysis
    • Binomial Heaps
    • Fibonacci Heaps
    • Splay Trees
  • Dynamic Programming
  • Lower bounds and NP-completeness
  • Linear-programming
    • Definitions of canonical and standard forms
    • Feasibility and optimization
    • Structure of optima
    • Duality theory and Duality applications
    • Simplex Algorithm
  • Approximation Algorithms
    • Relative Approximations
    • PAS and FPAS Scheduling
  • Randomized Algorithms
    • Kargers min-cut
    • Balls and Bins model and its applications
    • Hashing
    • Bloom filters
    • Quick sort
    • Quick select
    • Markov, Chebyshev and Chernoff and their applicaions in finding upper bounds on algorithmic errors
  • String matching algorithms
  • Network flow and matching

Text Books

Jon Kleinberg and Eva Tardos, Algorithm Design, Pearson Education, 2014

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Introduction to Algorithms, MIT Press 2009

Self-learning Materials

  1. Lecture slides that accompany the textbook

Grading Policy

Quiz Social Engagement Assignments Exams
10% 10% 30% 10% + 10% + 30%
at Classroom at Piazza at Your Place Will be Announced

Last updated on Jul 30, 2019