This is an advanced course in design and analysis of algorithms covering topics typically not covered in undergraduate algorithms. In this course the students will learn how to : (i) design and implement ‘new’ algorithms in the real world. (ii) map problems to algorithmic problems. (iii) read and understand algorithms published in journals. (iv) develop writing skills to present your own algorithms (v) collaborate and work together with other people to design new algorithms

Course Syllabus:

Dynamic Programming, Greedy Algorithms, Amortized Analysis, Fibonacci Heaps, van Emde Boas Trees, Single-Source Shortest Paths, All-Pairs Shortest Paths, Maximum Flow, Multithreaded Algorithms, String Matching Algorithms, Approximation Algorithms, and Parallelism Parallel Graph Algorithms.

Course Outline:

1. Dynamic Programming:  Rod Cutting, Matrix-Chain Multiplication, Elements of Dynamic Programming, Longest Common Subsequence, Optimal Binary Search Trees. [TB1: Ch. 15]
2. Greedy Algorithms: An Activity-Selection Problem, Elements of the Greedy Strategy, Huffman Codes, Matroids and Greedy Methods, A Task-Scheduling Problem as A Matroid. [TB1: Ch. 16]
3. Amortized Analysis: Aggregate Analysis, The Accounting Method, The Potential Method, Dynamic Tables. [TB1: Ch. 17]
4. Fibonacci Heaps: Structure Of Fibonacci Heaps, Mergeable-Heap Operations, Decreasing a Key and Deleting a Node, Bounding the Maximum Degree. [TB1: Ch. 19]
5. vanEmde Boas Trees: Preliminary Approaches,  A Recursive Structure,  The Van Emde Boas Tree. [TB1: Ch. 20]
6. Single-Source Shortest Paths: The Bellman-Ford Algorithm, Single-Source Shortest Paths In Directed Acyclic Graphs,  Dijkstra’s Algorithm,  Difference Constraints and Shortest Paths, Proofs of Shortest-Paths Properties. [TB1: Ch. 24]
7. All-Pairs Shortest Paths: Shortest Paths and Matrix Multiplication, The Floyd-Warshall Algorithm, Johnson’s Algorithm for Sparse Graphs. [TB1: Ch. 25]
8. Maximum Flow: Flow Networks, The Ford-Fulkerson Method, Maximum Bipartite Matching, Push-Relabel Algorithms, The Relabel-To-Front Algorithm. [TB1: Ch. 26]