This course places emphasis on complexity analysis, sorting, graph theory and problem-solving strategies. Comparison of various sorting and graph algorithms, with focus on complexity and space versus time trade-offs is made. A special effort is made to formulate and design algorithms and use of approximate algorithms where the problem cannot be solved by an exact algorithm.
This course focuses on the complexity and correctness of algorithms: big oh, big omega, and big theta notations, recurrence relations and their solutions, and worst, average and amortized analysis of algorithms with examples. Basic and advanced data structures for searching, sorting, and compression and graph algorithms.
Course Learning Outcomes
On successful completion of this course unit students will:
• Understand the general notion of complexity classes, P and NP, completeness and hardness, and the relationships between classes by reduction. You will also have seen how to show tasks are NP-complete
• Be able to develop, and reason about the correctness and performance, of algorithms for string searching and for calculating over graphs
• Have studied a range of distributed and probabilistic algorithms, understand the key issues involved, and be able to use distributed and probabilistic techniques to develop algorithms.
Introduction to Algorithms - 3rd Edition
NP complete problems
Bellman Ford algorithm, PPT Slide name Single source Shortest path L2
Knuth-Morris-Pratt KMP String Matching Algorithm , PPT Slide name: String Matching Algorithms L1
Robin Karp Algorithm, PPT Slide String Matching Algorithms L2
finite automata, PPT Slide String Matching Algorithms L2
Book Title : Introduction to algorithms
Author : Thomas H.Cormen, Charles E.Leisorson, Ronald L.Rivest, Clifford Stein
Book Title : Algorithms and Complexity
Author : HerbertS.Wilf
Publisher : University of PennsylvaniaPhiladelphia, PA
Book Title : Algorithms in C++
Author : Robert Sedgewick