IT202

Course Name: 

Data Structures and Algorithms-I (IT202)

Programme: 

B.Tech (IT)

Credits (L-T-P): 

(3-0-0) 3

Content: 

Elementary Data Types and Abstract Data Types. Computational model and complexity of algorithms (running time and space metrics), Introduction to Asymptotic notation: Big-O, Big-Omega, Big-Theta notations. Worst-case, Best-case, Average-case and amortized analysis. Arrays, Linear search and Binary search on sorted arrays. List ADT, implementing List ADT using arrays. Pointers, implementing List ADT using Linked Lists. Types of Linked Lists: Single, Double, Circular linked lists and their applications for e.g. in garbage collection. Stack ADT and Queue ADT implementation, applications for parenthesis matching, expression evaluation, implementing recursion, etc. 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, Multi-way search trees, B-trees, splay trees; Priority Queue ADT and its implementations using Binary heaps. Applications of Priority Queues. Sorting algorithms: Bubble sort, Selection sort, Insertion sort, Merge sort and Quick sort. Randomized Quick sort and its analysis. Linear-time sorting algorithms like Radix and Counting sort. Lower bound for comparison based sorting.

References: 

T H Cormen et al., Introduction to Algorithms, 3rd Edition, PHI Learning Ltd., 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., Art of Computer Programming: Fundamental Algorithms, Addison Wesley, 3rd Ed., 1997.

Department: 

Information Technology
 

Contact us

Biju R Mohan

Head of the Department,
Department of Information Technology, NITK, Surathkal,
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.
Ph.:    +91-824-2474056
Email:  infotech[AT]nitk[DOT]ac[DOT]in
            infotech[AT]nitk[DOT]edu[DOT]in

Sowmya Kamath S (Web Admin)

Connect with us

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