Syllabus  |   Lectures  |   Downloads  |   FAQ  |   Ask a question  |  
Course Co-ordinated by IIT Madras
Coordinators
 

 

Download Syllabus in PDF format



Untitled Document
 

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