CMS-A-CC-2-3-TH: Data Structure Core Course-3: Theory, Credits - 04, Contact hours - 60.

 Introduction to Data Structure

Abstract Data Type.

Arrays

1D, 2D and Multi-dimensional Arrays, Sparse Matrices. Polynomial representation

Linked Lists

Singly, Circular and Doubly Lists, Polynomial representation.

Stacks

Array and linked representation of stack, Prefix, Infix and Postfix expressions, utility and

conversion of these expressions from one to another, evaluation of postfix and prefix

expression using stack, applications of stack, limitations of Array representation of stack.

Queues

Array and Linked representation of Queue, Circular Queue, De-queue, Priority Queues.

Recursion

Developing Recursive Definition of Simple Problems and their implementation; Advantages

and Limitations of Recursion; Understanding what goes behind Recursion (Internal Stack

Implementation), Tail recursion.

Trees

Introduction to Tree as a data structure: Binary Trees (Recursive and Iterative Traversals),

Binary Search Tree (Traversal, Insertion, Deletion and Searching), Threaded Binary Trees

(Traversal and advantages).

Searching and Sorting

Linear Search, Binary Search, Comparison of Linear and Binary Search with respect to time

complexity, Selection Sort, Bubble sort, Insertion Sort, Merge Sort, Quick sort, Heap sort,

Shell Sort, Radix sort, Comparison of Sorting Techniques with respect to time complexity.

Hashing

Introduction to Hashing, Different hashing Techniques, Collision and resolving collision by

Open Addressing, Closed Hashing, Separate Chaining, Choosing a Hash Function.