IT209

Course Name: 

Data Structures and Algorithms (IT209)

Programme: 

B.Tech (AI)

Semester: 

Third

Category: 

Programme Core (PC)

Credits (L-T-P): 

(3-0-2) 4

Content: 

Elementary Data Types and Abstract data types. Computational model and complexity of algorithms (running time and space metrics), Introduction to Asymptotic notation; Worst- case, Best -case, Average-case and amortized analysis. Arrays, Linear search and Binary search on sorted arrays. List ADT and its implementation using arrays and linked lists. Types of linked lists: Single, Double, circular linked lists and their applications. Stack ADT and Queue ADT implementations with applications. Dynamic set ADT and Dictionary ADT. Hash tables – collisions, open and closed hashing, choosing good hash functions. Trees: Definitions and Representations; Tree traversals and their applications. Binary Search Trees. AVL trees, Red-black trees, B-trees; Priority Queue ADT and its implementations using Binary heaps. Applications of Priority Queues. Sorting algorithms: Merge sort and Quicksort. Randomized Quick sort and its analysis. Linear-time sorting algorithms like Radix and Counting sort. Graphs: Definitions and representations. Depth first and breadth-first search and their applications. Basic Graph algorithms like Dijkstra's shortest path algorithm and Kruskal's MST algorithm.

References: 

T H Cormen, C E Leiserson, R L Rivest and C Stein, Introduction to Algorithms, 3rd Edition, PHI Learning, 2010.
S. Horowitz. Fundamentals of Data Structures in C, Universities Press, 2nd Edition, 2008.
Michael T. Goodrich and Roberto Tamassia. Algorithm Design, Wiley, 1st Edition, 2006.
Knuth D.E., The Art of Computer Programming, Vol. I: Fundamental Algorithms, Addison Wesley, 3rd Ed., 1997.

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.