Course Description: In this course, students deepen their knowledge of the design and analysis of computer algorithms. Advanced topics in algorithms and algorithm analysis covered in the course include balanced search trees, string matching and indexing, linear sorting, graphs and graph algorithms, dynamic programming, network flows, randomized algorithms, and NP-completeness.

Pre-requisite: C Programming, Data Structure and Algorithms

Course Outline (Topics): The following list of topics is tentative. Based on available time slots, some topics may be dropped or added or reordered.

Introduction:

Refresher: Abstract Data Types, Asymptotic Analysis, Stacks, Queues, Linked Lists, Trees, Searching and Sorting

Recurrence Relation: Recurrence Relation, Tree Method, Master Theorem, Substitution Method

Sorting: Radix and Bucket Sort

Balanced Search Trees: 2-3-4 Tree and Red Black Tree

String Matching and Indexing: Tries and Suffix Trees

Graph Algorithms:

Graphs: Graphs, Data Structures for Graphs

Breadth First Search: Breadth First Search, Applications of BFS

Depth First Search: Depth First Search, Applications of DFS, DFS in Directed Graphs, Applications of DFS in Directed Graphs,

Minimum Spanning Trees: Kruskal’s and Prim’s Algorithm

Shortest Paths: Single Source Shortest Paths- Dijkstra and Bellman Ford

All Pairs Shortest Paths- Floyd Warshall

Advanced algorithmic design techniques:

Dynamic Programming: Fibonacci Number, Bellman Ford, Floyd Warshall, Longest Common Subsequences, Knapsack, Independent Sets in Trees

Network Flows: Max flow, Min Cut and Applications

Randomized Algorithms: Introduction, Quicksort, Min Cut Problem - Karger and Karger-Stein Algorithms

NP-completeness: NP-completeness, Polytime reductions

Books/References:

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Third Edition, The MIT Press

Algorithms Design by Jon Kleinberg and Eva Tardos

Data Structures and Algorithm Analysis in C. Second Edition. - Mark Allen Weiss (DSAC)

Data structures and network algorithms, Robert Endre Tarjan, Society for Industrial and Applied Mathematics Philadelphia, PA, USA, 1983, ISBN:0-89871-187-8

Knapsack Problems - Algorithms and Computer Implementations, Silvano Martello and Paolo Toth, John Wiley & Sons, West Sussex, UK, 1990, ISBN: 0471924202

Evaluation Policy: Assignments should include explanatory/clear comments as well as a short report describing the approach, detailed analysis, and discussion/conclusion. It is expected to come up with most efficient answer in all assignments and exams.

15% Mid-Exam-1 15% Mid-Exam-2 30% End-Exam 20% Lab Exams 20% Quiz/Assignments

Course Ethics: Please note down the following activities leading to a fair academic honesty:

• • All class work is to be done independently.

  • It is best to try to solve problems on your own, since problem solving is an important component of the course, and exam problems are often based on the outcome of the assignment problems.

  • You are allowed to discuss class material, assignment problems, and general solution strategies with your classmates. But, when it comes to formulating or writing solutions or writing codes, you must work alone.

  • You are not allowed to take the codes from any source, including online, books, your classmate, etc. in the home works and exams.

  • You may use free and publicly available sources (at idea level only), such as books, journal and conference publications, and web pages, as research material for your answers. (You will not lose marks for using external sources.)

  • You may not use any paid service and you must clearly and explicitly cite all outside sources and materials that you made use of.

  • I consider the use of uncited external sources as portraying someone else's work as your own, and as such it is a violation of the Institute's policies on academic dishonesty.

  • Instances will be dealt with harshly and typically result in a failing course grade.

  • Cheating cases will attract severe penalties.

Lecture 1: Introduction, Insertion Sort, Merge Sort (Slide) - 10-Aug-2020

Lecture 2: Asymptotic Analysis (Slide) - 12-Aug-2020

Lecture 3: Recurrence Relation - Tree Method and Master Theorem (Slide) - 13-Aug-2020

Lecture 4: Recurrence Relation - Substitution Method (Slide) - 17-Aug-2020

Lecture 5: Randomized Algorithm - Quick Sort (Slide) - 18-Aug-2020

Lecture 6: Sorting - Linear Time (Slide) - 19-Aug-2020

Lecture 7: Binary Search Tree (Slide) - 25-Aug-2020

Lecture 8: Height Balance Tree (2-4 Tree) (Slide) - 26-Aug-2020

Lecture 9: Red Black Tree - Insertion (Slide) (Example) - 27-Aug-2020

Lecture 10: Red Black Tree - Deletion (Slide) - 01-Sept-2020

Lecture 11: AVL Tree (Slide) - 02-Sept-2020

Lecture 12: B+ Tree (Slide) - 03-Sept-2020

Lecture 13: Tries (Slide) - 08-Sept-2020

Lecture 14,15: Hashing (Slide) - 09,10-Sept-2020

Lecture 16,17: Graph (Slide) - 15,16-Sept-2020

Lecture 18,19: Depth First Search (Slide) - 17,22-Sept-2020

Lecture 20,21: Breadth First Search (Slide) - 23-Sept-2020, 12-Oct-2020

Lecture 22,23: Minimum Spanning Tree (Slide) - 12,14-Oct-2020

Lecture 24,25,26: Single Source Shortest Path - Dijkstra (Slide) - 19,21-Oct-2020

Lecture 27: Single Source Shortest Path - Bellman Ford (Slide) - 28-Oct-2020

Lecture 28,29: Dynamic Programming, Floyd Warshall (Slide) - 02-Nov-2020

Lecture 30: Dynamic Programming - Longest Common Subsequences (Slide) - 04-Nov-2020

Lecture 31,32: Dynamic Programming - Knapsack (Slide) - 09-Nov-2020

Lecture 33: Network Flow Algorithms (Slide) - 11-Nov-2020

Lecture 34,35,36: MinCut Karger Algorithm (Slide) - 16,18-Nov-2020

Lecture 37: Computational Complexity (Slide) - 23-Nov-2020