CS31005: Algorithms -Ii
| CS31005 | |||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Course name | Algorithms -Ii | ||||||||||||||||||||||||||
| Offered by | Computer Science & Engineering | ||||||||||||||||||||||||||
| Credits | 4 | ||||||||||||||||||||||||||
| L-T-P | 3-1-0 | ||||||||||||||||||||||||||
| Previous Year Grade Distribution | |||||||||||||||||||||||||||
| |||||||||||||||||||||||||||
| Semester | Autumn | ||||||||||||||||||||||||||
Syllabus
Syllabus mentioned in ERP
Models of computation: RAM model and its logarithmic cost.Formal introduction to algorithmic paradigms: divide and conquer, recursion, dynamic programming, greedy, branch and bound, etc.Advanced data structures: Fibonacci heap, unionfind, splay trees.Amortized complexity analysisRandomized algorithms: Randomized algorithms to be introduced a bit early, i.e. before NP completeness to highlight randomization as an algorithmic technique. Application areas(i)Geometric algorithms: convex hulls, nearest neighbor, Voronoi diagram, etc.(ii)Algebraic and number-theoretic algorithms: FFT, primality testing, etc.(iii)Graph algorithms: network flows, matching, etc.(iv)Optimization techniques: linear programming Reducibility between problems and NPcompleteness: discussion of different NP-complete problems like satisfiability, clique, vertex cover, independent set, Hamiltonian cycle, TSP, knapsack, set cover, bin packing, etc. Backtracking, branch and boundApproximation algorithms: Constant ratio approximation algorithms.Miscellaneous: Introduction to external memory algorithms, parallel algorithms.References1.Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press.2.Allan Borodin, Ran El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press.3.Nancy Lynch, Distributed Algorithms, Morgan Kaufmann.4.Robert Endre Tarjan, Data Structures and Network Algorithms, SIAM.5.L. Grotchel, L. Lovasz, and A. Schrijver, Geometric algorithms and Combinatorial Optimization, Springer.6.M. Kearns and U. Vazirani, An Introduction to Computational Learning Theory. MIT Press.7.N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley.8.Vijay Vazirani, Approximation Algorithms, Springer.9.Fan Chung, Spectral Graph Theory, American Mathematical Society.
Concepts taught in class
This course deals primarily with the analysis of algorithms as opposed to design which is taught in Algorithms I. Standard techniques used to analyze algorithms are covered. Randomized and approximate algorithms are introduced. Standard notions of complexity classes are introduced. Some geometric problems are covered too, along with their associated data structures. Prof SPP maintains a nice well documented list of resources on the course's Moodle page. Overall, a highly mathematically stimulating course with a background context of algorithms.
Student Opinion
How to Crack the Paper
Classroom resources
Additional Resources
Time Table
| Day | 8:00-8:55 am | 9:00-9:55 am | 10:00-10:55 am | 11:00-11:55 am | 12:00-12:55 pm | 2:00-2:55 pm | 3:00-3:55 pm | 4:00-4:55 pm | 5:00-5:55 pm | |
|---|---|---|---|---|---|---|---|---|---|---|
| Monday | NC232 | |||||||||
| Tuesday | ||||||||||
| Wednesday | NC232 | NC232 | ||||||||
| Thursday | NC232 | |||||||||
| Friday |