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]
9. Multithreaded Algorithms: The Basics of Dynamic Multithreading, Multithreaded Matrix Multiplication, Multithreaded Merge Sort. [TB1: Ch. 27]
10. String Matching: The Naive String-Matching Algorithm, The Rabin-Karp Algorithm, String Matching With Finite Automata, The Knuth-Morris-Pratt Algorithm. [TB1: Ch. 32]
11. Approximation Algorithms: The Vertex-Cover Problem, The Traveling-Salesman Problem, The Set-Covering Problem, Randomization And Linear Programming, The Subset-Sum Problem. [TB1: Ch. 35]
12. Parallel Algorithms: Parallelism, The PRAM Model,   Simple Parallel Operations, Parallel Searching, Parallel Sorting, Parallel Numerical Algorithms, Parallel Graph Algorithms. [TB2: Ch. 9]