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

Algo_Book_1.jpeg
textbook_1.jpg
textbook_2.jpg

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
Whether the solution is unique? https://cs.stackexchange.com/questions/88215/unique-stable-solution-in-stable-marriage-problem-is-it-pareto-efficient-and-a
Jan 1, 0001