CS31005: Algorithms -Ii

From Metakgp Wiki
Jump to navigation Jump to search
CS31005
Course name Algorithms -Ii
Offered by Computer Science & Engineering
Credits 4
L-T-P 3-1-0
Previous Year Grade Distribution
16
29
19
26
8
8


EX A B C D P F
Semester Autumn


Syllabus[edit | edit source]

Syllabus mentioned in ERP[edit | edit source]

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[edit | edit source]

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[edit | edit source]

How to Crack the Paper[edit | edit source]

Classroom resources[edit | edit source]

Additional Resources[edit | edit source]

Class Test-1

Midsem

Class Test-2

Endsem

Time Table[edit | edit source]

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