IT251

Course Name: 

Data Structures and Algorithms-II (IT251) (2018 Curriculum)

Programme: 

B.Tech (IT)

Semester: 

Fourth

Category: 

Programme Core (PC)

Credits (L-T-P): 

(3-0-2) 4

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.

References: 

Jon Kleinberg and Eva Tardos, Algorithm Design, 1st Edition, Pearson Education India, 2013.
S Dasgupta, C Papadimitriou, U Vazirani, Algorithms, McGraw-Hill Education, 2006.
T H Cormen, C E Leiserson, R L Rivest, C Stein, Introduction to Algorithms, 3rd Edition, PHI Learning, 2010.
Horowitz and Sahni, Fundamentals of Computer Algorithms, Galgotia Publications, 2nd Ed., 2009.
Michael T. Goodrich and Roberto Tamassia. Algorithm Design, Wiley, 1st Edition, 2006.

Department: 

Information Technology
 

Contact us

Head of the Department,
Department of Information Technology,
National Institute of Technology Karnataka,
SurathkalP. O. Srinivasnagar, Mangalore - 575 025
Ph.:    +91-824-2474056
Email:  hodit [at] nitk [dot] edu [dot] in
 

Web Admin: Sowmya Kamath S

Connect with us

We're on Social Networks. Follow us & stay in touch.