IT251
Course Name:
Data Structures and Algorithms-II (IT251) (2018 Curriculum)
Programme:
Semester:
Category:
Credits (L-T-P):
Content:
Graphs: Definitions and representations. Adjacency List and Adjacency Matrix representations and their relative advantages and disadvantages. Graph Algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS). Applications of BFS and DFS. Topological Sorting and strongly connected components in directed graphs. Dijkstra's shortest path algorithm, and its analysis: runtime and correctness. Data Structure for Disjoint Sets: Union-by-rank and path-compression heuristics; applications to computing connected components and in Minimum Spanning Tree algorithms. Kruskal's and Prim's Minimal Spanning Tree algorithms. Network flows, max-flow min-cut theorem. Applications: network and internet examples. Tries, Suffix trees, Bloom filters and their applications. String Algorithms: Boyer-Moore, Rabin-Karp and Knuth-Morris-Pratt algorithms. Applications to Text Compression, Text similarity testing and Computational Biology. Topics in Computational Geometry: Range-trees, k-d trees, convex hull and other geometric algorithms.