IT202

Course Name: 

Data Structures and Algorithms-I (IT202)

Programme: 

B.Tech (IT)

Semester: 

Third

Category: 

Programme Core (PC)

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

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.