Prerequisites: This course is primarily meant for students who have done basic courses in Programming and Data Structures.

What will  the students learn in the course?

In this course, the students will study some well known fundamental algorithms. They will also learn various algorithm design techniques and
use these techniques to design algorithms for various problems. They will learn to analyze  complexity  of algorithms including worst case, average case and amortized complexity. They will also learn about NP-Completeness and approximation algorithms.

What will the course cover?

Algorithm Analysis. Asymptotic Notations: Big-Oh, Big-Omega, Little-Oh, Little-Omega, Theta.

Solving Recurrences. Tricks and short cuts.

Sorting: Merge Sort, Quicksort, Heapsort, Lower Bounds.

Searching: Variants of  Binary Search,  Skip Lists, Analysis.

Variants of Binary Search Trees: Range, Segment and Interval Trees.

Divide and Conquer.

Dynamic Programming. Matrix Chain Multiplication, 0/1 Knapsack pseudo-polynomial algorithm.

Greedy Method:  Fractional Knapsack Problem, Scheduling Problems

Amortized Analysis: Aggregate, Accounting, Potential methods.

Disjoint Set Manipulation: UNION-FIND, Union by Rank, Path Compression.

Graph Algorithms including DFS, BFS, Shortest Paths and Spanning Trees.

Studying relative hardness of problems, NP-Hard and NP-complete Problems. Reduction Proofs. Coping with NP-Completeness, Approximation algorithms, Branch and Bound Algorithm for 0/1 Knapsack.

What the students need to bring to class?

Pen and Notebook.