ADSA@IIIT Sri City

Indian Institute of Information Technology, Sri City (IIITS)

Advanced Data Structures and Algorithms (ADSA)

A CSE Program Core Course (UG2)

Instructor: Dr. Shiv Ram Dubey

Fall 2019

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 10% Quiz 10% Home Works

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.