The focus of the course is program design using data structures. After this course, the student will be able to analyze the difference between the choice of different data structures for a given programming task. The student will be able to write programs involving different data structures, and also appreciate the value of asymptotic analysis of data structure set-up times, maintenance
times and space used.
Week. No
Topics
1.
Introduction to Abstract Data Types and analysis of different algorithms
Review of elementary data types and structuresin C. The Array data
type and the importance of Random Access.
Searching an array:linear and Binary search. Sorting:Merge Sort, and analysis
2.
ADT Array -- searching and sorting on arrays.
Review of Pointers in C. The Linked list ADT.
Searching a linked list, inserting and deleting from a linked list. Application: representing a univariate polynomial, and adding two univariate polynomials
3.
ADT Linked Lists, Stacks, Queues.
List manipulation algorithms: reversal of a list, use of recursion to reverse/searc
h. Doubly linked lists, circular linked lists.
Stack and Queue ADT, comparison of implementation using arrays and linked lists
4.
Binary Trees
Tree ADTrepresentation, traversal, application of binary trees in Huffman coding.
Introduction to expression trees: Recursive traversaldepth, height, and number of nodes. post/pre/infix notation.
5.
Dictionary
Binary search treessearch, insertion and deletion
Balanced binary search trees.
6.
ADT Priority queues
Heap ADTimplementation and Heapsort, in place sorting.
Heaps for maintaining interval trees.
7.
Graphs
Representations or relations using matrices. The Graph ADT and applications
Transitive closure, Flyod Warshall's algorithm and applicatoinsconnectivity
and spanning trees.
8.
Advanced topics options for the teacher
Adj. List reprsentation of a Graph. Breadth First Search traversal and identification of shortest paths.
Depth First Search recursive specification and application to finding articulation points.
Qualitatively we assume that the B.Tech/BE student is exposed to Imperative programming language like C. He or she is comfortable with iterations, recursion, pointers, parameter passing by value and reference.
Important: Please enable javascript in your browser and download Adobe Flash player to view this site
Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in