Data Structures and Algorithm (CS-202)

Prerequisites

• Discrete Mathematics

• C Programming

Syllabus

Defining a Data Structure: Notion of DFA triplet, Types of Data Structures.

Linear Structures: Array, List, Stack, Queue, Applications of arrays, lists, stacks and queues.

Non-Linear Data Structures: Tree, Tree Traversals, Binary Tree, Applications of Trees, Binary Search Tree, Graph, Hashing and Collision Resolution Techniques.

Searching and Sorting: Linear Search, Binary Search, Selection Sort, Insertion Sort and Shell Sort.

Introduction to Algorithm Analysis and Design: Time Complexity Analysis, Asymptotic Notations, Introduction to Design Techniques such as Divide and Conquer, Dynamic Programming, Greedy algorithms Backtracking, Branch and Bound.

Suggested Readings:

1. T H Cormen, C E Leiserson, R L Rivest and C Stein, Introduction to Algorithms, MIT Press, 2001.

2. A. M .Tannenbaum, Y Langsam and M J Augenstein, Data Structures Using C++, Prentice Hall India, 1996.

3. J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.

4. A Aho, J E Hopcroft and J D Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.

5. S Sahni, Data Structures, Algorithms and Applications in C++, McGraw-Hill, 2001.

6. M T Goodrich and R Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley & Sons, 2001.

Weekly Office Hours

FRI : 15:10 - 16:00 Hours

SAT : 15:10 - 16:00 Hours

Reading Materials (On Graph)(Slides taken from Dr. PSM, IITG)

• Graph-BFS: .

• DFS, Spanning Tree.

• MST-KRUSKAL

• MST-PRIMS

• Shortest Paths in a Graph