Course Contents

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.

Course Synopsis

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.