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
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.