Data Structure

Unit

Topic

No. of Lectures

1

Basic Concept and Introduction to Data Structure

1.1 Pointers and Dynamic Memory Allocation

1.2 Algorithm-Definition and characteristics

1.3 Algorithm Analysis -Space Complexity -Time Complexity – Asymptotic Notation

      Introduction to Data structure

1.4 Types of Data structure

1.5 Abstract Data Types (ADT) Introduction to Arrays and Structure

1.6 Types of array and Representation of array

1.7 Polynomial - Polynomial Representation - Evaluation of  Polynomial - Addition of Polynomial

1.8 Self Referential Structure

5

2

Linear Data Structures

2.1 Introduction to Arrays – array representation

2.2 Sorting algorithms with efficiency-Bubble sort, Insertion sort,  Merge sort, Quick Sort,

     Selection Sort

2.3 Searching techniques –Linear Search, Binary search

6

3

Linked List

3.1 Introduction to Linked List

3.2 Implementation of Linked List–Static & Dynamic representation,

3.3 Types of Linked List

- Singly Linked list(All type of operation),

- Doubly Linked list (Create , Display)

- Circularly Singly Linked list (Create, Display)

- Circularly Doubly Linked list (Create, Display)

3.4 Generalized linked list – Concept and Representation

6

4

Stacks

4.1 Introduction

4.2 Representation- Static & Dynamic

4.3 Primitive Operations on stack

4.4 Application of Stack

4.5 Conversion of Infix, prefix, postfix , Evaluation of postfix and prefix

4.6 Simulating recursion using stack

8

5

Queues

5.1 Introduction

5.2 Representation - Static & Dynamic

5.3 Primitive Operations on Queue

5.4 Circular queue, priority queue

5.5 Concept of doubly ended queue

4

6

Trees

6.1  Concept & Terminologies

6.2 Binary tree, binary search tree

6.3 Representation – Static and Dynamic

6.4 Operations on BT and BST – create, Insert, delete, , counting leaf, non- leaf & total  

      nodes

6.5 Tree Traversals (preorder, inorder, postorder)

6.6 Application - Heap sort

6.7 Height balanced tree- AVL trees- Rotations, AVL tree examples.

12

7

Graph

7.1 Concept & Terminologies

7.2 Graph Representation – Adjacency matrix, adjacency list, inverse    Adjacency list,

      adjacency multilist, orthogonal list

7.3 Degree of Graph

7.4 Traversals – BFS and DFS

7.5 Applications – AOV network – topological sort, AOE network–criticalPath

7