Sorry, you need to enable JavaScript to visit this website.

  • 8:45 AM, Wednesday, 22 Jan 2020


Course Postgraduate
Semester Electives
Subject Code MA874
Subject Title Theory of Algorithms

Syllabus

Greedy and dynamic programming algorithms; Kruskals algorithm for minimum spanning trees; the
folklore algorithm for the longest common subsequence of two strings; Dijstras algorithm and
other algorithms for the shortest path problem; divide-and-conqueror and checkpoint al-
gorithms; the Hirshbergs algorithm for aligning sequences in linear space; quick sorting; the
Knuth-Morrison-Pratt algorithm; suffix trees; data structures: chained lists, reference lists, hash- ing;
the Chomsky-hierarchy of grammars; parsing algorithms; connections to the automaton theory;
Turing-machines; complexity and intractability; complexity of algorithms; the complex- ity classes
P and NP. 3-satisfiability, and NP-complete problems; stochastic Turing machines; the complexity
class BPP; counting problems; #P, #P-complete; FPRAS; discrete time Markov chains; reversible
Markov chains; Frobenius theorem; relationship between the second largest eigenvalue modulus and
convergence of Markov chains; upper and lower bounds on the second largest eigenvalue; the
Sinclair-Jerrum theorem: relationship between approximate counting and sampling

Text Books
References

1. Dasgupta, S. S., Papadimitriou, C. H., Vazirani, U. V., Algorithms, McGraw-Hill Higher Education (2006).
2. Kleinberg , J. and Tardos, E., Algorithm Design, Addison-Wesley (2006)

3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C., Introduction to Algorithms, 3rd Ed., The MIT Press (2009)