CS 231 No. of Hrs/week : 03+03 hrs
No. of credits :04
Course objectives : This course covers data organizations and the algorithms which act on them. Stacks, Queues, trees, Graphs and sets are introduced. Different searching and sorting algorithms are included. The laboratory exercises will focus on the implementation and application of the different data structures using C++ language with necessary documentation and reports.
1. Over view of C++ including Templates. 3 Hrs
2. Algorithm Analysis
ö Space Complexity
3. Recursion
ö Definition & Examples
ö Complexity analysis of Recursive algorithms 3 Hrs
4. Stacks
ö Definitions & implementation
ö Representation
ö Operations on Stacks
ö Applications of Stacks 3 Hrs
5. Queues
ö Definition
ö Representation
ö Operations on Queues 3 Hrs
6. Linked lists
ö Singly Linked lists
ö Doubly Linked lists 3 Hrs
7. Standard Template Library
1. Introduction
Introduction to Container and Iterators
2. Sequence Container , Associative Container
Container Adapters 3 Hrs
3. Trees
ö Definition
ö Representation
ö Binary Trees
- Operations
- Recursive and Iterative Traversal
ö Binary Search Trees
ö Height Balanced Trees
ö Time Complexity Analysis of BST, HBT 8 Hrs
4. Searching
ö Linear Search
ö Binary Search
ö Time Complexity Analysis of the above Search methods.
ö Comparative Performance of Searching Algorithms 3 Hrs
5 Sorting
ö Bubble Sort
ö Quick Sort
ö Merge Sort
ö Heap Sort
ö Time Complexity Analysis of the above Sorting Methods. 6 Hrs
Hashing
ö Abstract Data Type
ö Static Hashing
- Hash Tables
- Hashing Functions
- Overflow Handling 3 Hrs
Sets
ö Representation
ö Union and Find Operations. 3 Hrs
Graphs
ö Types of Graphs
ö Representation
- Adjacency Matrix
- Adjacency Lists
ö Depth-First Search and Breadth-First Search
ö Shortest paths and Transitive Closure. 6 Hrs
TEXT BOOK:
“Fundamentals of Data Structures in C ++” by Ell’s Horowitz, Sartaj Sahni, Dinesh Mehta Galgotia Publications Pvt. Ltd.
C++ How to Program by Deitel and Deitel 3rd Edition, Pearson Education
REFERENCES:
1) Mark Allen Weiss- Algorithms, Data Structures and Problem solving with C++, Addison Wesley
2) Tannenbaum and Augustine – Data Structures using C and C++. Prentice Hall.
DATA STRUCTURES LAB
1) Review of C++ including Templates.
2) Recursive programs.
3) Implementation of Stacks and queues.
4) Linked lists
5) Implementation of simple programs in standard template library.
6) Binary trees – traversal, insertion, deletion.
7) Binary Search trees.
8) Linear Search, Binary Search
9) Sorting Programs.