DC08 DATA STRUCTURES

1.    Introduction                                                                                        3 hours

1.1 Abstract Data Type.

1.2 Frequency count.

1.3 Time complexity, Big O notation.     

I [1, 2, 4]; II [1, 4]

2.    Arrays                                                                                                    5 hours

2.1 Ordered lists and arrays.

2.2 Polynomial representation using arrays.             

2.3 Representation of arrays in contiguous memory using row major ordering.

I [2 (2.1, 2.2, 2.4, 2.6)]

3.    Linked Lists                                                                                          8 hours

3.1 Singly Linked List.                             

3.1.1 Implementation of Singly linked list in ‘C’.

3.1.2 Insertion.

3.1.3 Deletion.

3.1.4 Traversal.

3.2 Circular lists.                                 

3.3 Polynomial addition using linked lists.             

3.4 Sparse Matrices                           

I [3 (3.2, 3.4, 3.5), 4 (4.4, 4.7)]; II [4 (4.1, 4.4, 4.7)]

4. Stacks and Queue                                  11 hours

4.1    Linked list representation of stacks and queues.

4.2 Evaluation of arithmetic_expression.             

4.3 Simulation of queues.                           

I [4 (4.3, 4.4)]; II [4 (4.3, 4.4)]

5.    Searching and Sorting                                                                      13 hours

5.1 Searching Techniques.

5.1.1 Sequential Search.

5.1.2 Binary Search.                                 

5.2 Sorting Techniques.                             

5.2.1 Insertion Sort.

5.2.2 Selection Sort.

5.2.3 Bubble Sort.

5.2.4 Quick sort.

5.2.5 Merge Sort.

5.3 Hashing Schemes.                             

5.3.1 Collision Handling in Hashing.

 I [9 (9.1, 9.3-9.6, 9.9)]

6.    Trees        11 hours

6.1 Binary tree.

6.1.1 Height.

6.1.2 Representation using pointers.

6.1.3 Traversal – inorder, preorder, postorder.

6.2 Relationship between internal and external modes.

6.3 Non-recursive traversal of binary trees.             

6.4 Binary Search Tree.                           

6.5 Introduction to B-tree.                       

I [7 (7.2-7.4, 7.6, 7.7, 7.9), 8 (8.4)]

7.    Graphs                                                                9 hours

7.1 Graph Terminology.                           

7.1.1 Degree.

7.1.2 Incidence.

7.1.3 Path.

7.1.4 Cycle.

7.1.5 Connected Graph.

7.1.6 Minimal spanning Tree.

7.2 Graph Representation.                       

7.2.1 Adjacency Matrix.

7.2.2 Adjacency List.

7.3 Traversal Algorithm.                             

7.3.1 Depth first Traversal.

7.3.2 Breadth First Traversal.

7.4 Dijkstra’s Shortest Path Algorithm.     

I [10 (10.2, 10.5)]

Text Books

I. S. Chattopadhyay, D. G. Dastidar and M. Chattopadhyay, “Data Structures Through ‘C’ Language,” BPB Publications, 2002.

II. E. Horowitz and S. Sahni, “Fundamentals of Data Structures,” Galgotia Publications, 2003.