DSA and Algorithms

Discrete Mathematics or equivalent. Abstract data types: lists, stacks, queues, trees, heaps. Basic proof techniques. Bubble, selection, insertion, counting, radix, bucket, merge and quick sorts; binary search. Graphs: representation and algorithms.

· Introduction, Asymptotic notation for Execution time analysis. Function hierarchy. Forming and solving recurrences. Recursion tree and substitution method. Master theorem. Amortized cost.

· Inversions and sorting. Sorting algorithms: bubble, selection, insertion, counting, radix, and bucket. A lower bound for sorting by comparison. Heap sort.

· Divide and conquer: merge sort, quick sort, binary search, linear time rank, Strassen’s matrix multiplication, Closest pair of points in 2D.

· Dynamic programming: Fibonacci numbers, longest common substring, longest common subsequence, 0-1 Knapsack, matrix-chain multiplication, party planning and bitonic TSP.

· Greedy algorithms: Activity selection, Fractional Knapsack.

· Graphs: Representation. Graph explorations: DFS, BFS and their applications. Shortest paths: BFS, Dijkstra, Bellman-Ford, Floyd-Warshall. Minimum spanning trees: Prim’s and Kruskal’s.

· Maximum flow problems. Introduction, Ford Fulkerson method, Edmonds Karp algorithm, max flow min cut theorem. Applications.

· Introduction to NP-completeness. NP-Complete reductions 3SAT, clique, vertex Cover, maximum independent set.

· Introduction to Algorithms, 3rd ed., Cormen, Leiserson, Rivest, and Stein. MIT Press.

· Brassard, Gilles, and Paul Bratley. Fundamentals of algorithmics. Vol. 524. Englewood Cliffs: Prentice Hall, 1996.

· Jon Kleinberg, Éva Tardos. Algorithm Design.

· Problems on algorithms. Ian Parberry.

· Dasgupta, Sanjoy, Christos H. Papadimitriou, and Umesh Virkumar Vazirani. Algorithms. McGraw-Hill Higher Education, 2008.