This course provides foundations of the practical implementation and usage of advanced Algorithms and Data Structures
Objectives
The course is intended to provide the foundations of the practical implementation and usage of Algorithms and Data Structures. One objective is to ensure that the student evolves into a competent programmer capable of designing and analyzing implementations of algorithms and data structures for different kinds of problems. The second objective is to expose the student to the algorithm analysis techniques, to the theory of reductions, and to the classification of problems into complexity classes like NP.
Important Links
Course Contents
The content of this course can be viewed in four different threads each telling a different story of the same material. The first one is based on the design paradigms of algorithms, the second one based on task of choosing the right data structure, the third one based on the type of analysis (like worst case, amortized etc) that one would like to do and the fourth one based on the domain from which the algorithmic problems come from.
We will follow the first one and describe the thread relates to the other views too, during the course. Here is the outline, based on this view.
Introduction and Review of Basics (5 Lectures, 1 Tutorial)
Algorithms, Programs, Correctness, Efficiency. The major challenges. A quick recap of the basics. Asymptotic notation, Big O, Theta, Omega, little o, Recurrence relations, Master theorem. Algorithmic upper bounds, lower bounds, adversarial arguments.
Divide and Conquer (5 Lectures, 1 Tutorial)
Simple examples of Divide and Conquer Technique. Analysis. Sorting Algorithms, Lower Bounds. Median in Linear time. Maximum Sub-array and Closest Pair of points. Decrease and Conquer variants.
Greedy Technique (10 Lectures, 3 Tutorials)
Minimum Spanning Tree problem, Prims and Kruskals algorithms. Improving Kruskals algorithm using Union-Find data structure (log*(n) analysis). Splay Trees amortized analysis, Shortest Paths in Graphs, quick recall of BFS as shortest paths for unweighted graphs, Dijkstra’s algorithm, Improving Dijsktra’s algorithm with Fibonacci heaps.
Dynamic Programming (12 Lectures, 3 Tutorials) :
Bellman Ford Algorithm. Network Flows problem, Ford Fulkerson Method, Maxflow-MinCut Theorem, Edmonds-Karp implementation of Ford Fulkerson. Longest increasing subsequence, Knapsack with and without repetition, Independent set in trees. String Matching Algorithms. Naive String matching, motivation for KMP, Knuth Morris Pratt.
NP Completeness and Reductions (5 Lectures, 1 Tutorial)
Classes P, NP, co-NP. NP-Completeness and Reducibility, Cook’s Theorem without proof. Example reductions between problems. Coping with NP-completeness (5 Lectures, 0 Tutorials) Approximation Algorithms. Set Cover log(n) approximation, 2-approximation for TSP,2-approximation for Vertex Cover. Parameterized Algorithms
Learning Outcomes:
By the end of the course, the students will be able to :
- formulate, design and analyze algorithms for problem statements.
- choose appropriate data structures and algorithms, understand the ADT/libraries, and use it to design algorithms for a specific problem.
- understand the necessary mathematical abstraction to solve problems.
- come up with analysis of efficiency and proofs of correctness
- comprehend and select algorithm design approaches in a problem specific manner.
