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:
Evaluation Pattern: