Y2HLYes to Happy Learning

Courses / AADS

23CS03HF · Python · Undergraduate, after a first data structures course

Advanced Algorithms and Data Structures

by Dr. Asesh Kumar Tripathy

Balanced trees, string matching, graphs, design techniques and NP-completeness. 34 topics, each with a picture-first explanation, a step-by-step trace, a short Python implementation, practice problems, a self-marking quiz and GATE-style questions with worked solutions.

  • 34topics
  • 34quizzes
  • 136GATE-style questions
  • 15lab programs
Start Topic 1 How to study this course

The 34 topics

CO1Advanced data structures and string matching

Topic 1 Binary search trees Topic 2 AVL trees Topic 3 Red-black trees Topic 4 Splay trees Topic 5 B-trees and B+ trees Topic 6 Segment trees and range trees Topic 7 Suffix trees and N-ary trees Topic 8 Tries and their types Topic 9 Knuth–Morris–Pratt string matching Topic 10 Boyer–Moore string matching Topic 11 Aho–Corasick multi-pattern matching CO1 test 20 questions from these topics

CO2Graph algorithms and network flow

Topic 12 Breadth-first and depth-first search Topic 13 Dijkstra's shortest paths Topic 14 Bellman–Ford Topic 15 Floyd–Warshall all-pairs shortest paths Topic 16 Prim's minimum spanning tree Topic 17 Kruskal's minimum spanning tree Topic 18 Ford–Fulkerson and Edmonds–Karp Topic 19 Max-flow min-cut theorem CO2 test 20 questions from these topics

CO3Divide and conquer, greedy and dynamic programming

Topic 20 Divide and conquer and merge sort Topic 21 Quicksort Topic 22 Closest pair of points Topic 23 Greedy method: coin change and activity selection Topic 24 Huffman coding and Borůvka's algorithm Topic 25 Dynamic programming and matrix-chain multiplication Topic 26 Longest common subsequence Topic 27 0/1 knapsack (dynamic programming) CO3 test 20 questions from these topics

CO4Backtracking, branch and bound, and NP-completeness

Topic 28 Backtracking and the N-Queens problem Topic 29 Sudoku and graph colouring Topic 30 Hamiltonian cycles Topic 31 Branch and bound: 0/1 knapsack Topic 32 Travelling salesperson: FIFO and LC branch and bound Topic 33 Deterministic and nondeterministic algorithms; P and NP Topic 34 NP-hard and NP-complete problems: 3-SAT, Cook–Levin, CDP and NCDP CO4 test 20 questions from these topics

See my marks →

How to study this courseThe study rhythm for each topic, setting up Python, how the quizzes and GATE-style questions work, and how your marks are kept. Lab programsA companion to the 15 lab sessions (CO5): what each Pre-Lab, In-Lab and Post-Lab task asks, the topic pages to read first, hints on the approach, test cases checked by program, and viva practice.

Course overview

Choose the right structure, and the right technique, and a hard problem becomes an easy one.

This course is about choosing and building the right tool for a computational problem:

Every topic page explains the idea with pictures first, then traces it step by step, then gives a short Python implementation you can run and change.

Course outcomes

CO You will be able to Level
CO1 Apply advanced data structures (balanced search trees, B-trees, segment and suffix trees, tries) and string-matching algorithms for efficient data organisation. Apply
CO2 Analyse real-world scenarios to choose and implement graph algorithms: traversal, shortest paths, spanning trees and network flow. Analyse
CO3 Examine problem requirements to choose between divide and conquer, greedy and dynamic programming, and implement the right one. Analyse
CO4 Analyse computational problems to decide whether backtracking, branch and bound or complexity-based arguments suit them. Analyse
CO5 Implement and analyse advanced algorithms and data structures in working programs (the lab programs). Analyse

Syllabus

Textbooks

Topic pages refer to these books by number.

  1. Textbook 1: Introduction to Algorithms, 3rd edition, The MIT Press, 2009.
  2. Textbook 2: Fundamentals of Computer Algorithms, 2nd edition, University Press, 2008.
  3. Textbook 3: Data Structures and Algorithm Analysis in C, 2nd edition, Pearson, 2010.
  4. Textbook 4: Fundamentals of Data Structures in C, 2nd edition, 2015.
  5. Textbook 5: Design and Analysis of Algorithms, Oxford University Press.

Reference books: 1. The Algorithm Design Manual, 2nd edition, Springer, 2008. 2. Data Structures and Algorithms in Python, Wiley, 2013. 3. The Art of Computer Programming, 3rd edition, Addison-Wesley, 1997. 4. Data Structures and Algorithms, Pearson Education, 2003.

Free online courses