CS280: DATA STRUCTURES AND ALGORITHMS

Instructor: Dr. Sukhendu Das

Teaching Assistants: Vinod, Dyana, Manisha, Sunando.

 

L-T-P-C: 3 - 1 - 0 - 4

         

1. Problem Solving using Computers - Abstraction - Abstract data types;    Data Representation; Elementary data types; Basic concepts of data Structures; Mathematical preliminaries - big-Oh notation; efficiency of algorithms; notion of time and space complexity; performance measures for data structures.

 2.  ADT array - Computations on arrays - sorting and searching algorithms

 3. ADT Stack, Queue, list - array, linked list, cursor based implementations of linear structures.

 4. ADT Tree - tree representation, traversal of trees;

 5. ADT Binary tree - binary trees, threaded binary trees, application of binary trees - Huffmann coding; application of threaded binary trees - differentiation;

 6. Search Tree - Binary search tree; balanced binary search trees - AVL tree; Applications of Search Trees - TRIE; 2-3 tree, 2-3-4 tree; concept of B-Tree.

 7. ADT Dictionary - array based and tree based implementations; hashing - definition and application - LZW encoding.

 8. ADT Priority Queue - Heaps; heap-based implementations; applications of heaps - sorting;

 9. Graphs - shortest path, minimum spanning tree, DFS, BFS - an application of DFS and BFS.

 10. Algorithm Design Paradigms - greedy, divide and conquer, dynamic programming, backtracking

 References:

 1.       Mark Allen Weiss, "Data Structures and Algorithms in C++", Addison Wesley, 2003.

2.       Adam Drozdek, "Data Structures and Algorithms in C++, Brooks and Cole, 2001.

3.       Aho, Hopcroft and Ullmann, "Data structures and Algorithm, "Addison

Welsey, 1984.



 Makefile Link:

    http://vplab.cs.iitm.ernet.in/~vinod/makefiles.html


 Evaluation Pattern:

  1. Quiz 1 - 15-20
  2. Quiz 2 - 15-20
  3. Assign - 10-20 (from DAS Lab.)
  4. End Sem - 50