DATA STRUCTURE & ALGORITHM
| L 3 | T 0 | P 4 | | Curri. Ref. No.: CSE406 |
| Total Contact hrs : 105 Theory: 45 Tutorial: 0 Practical: 60 Pre requisite: G205B, CSE402 Credit: 5 | Total marks: 150 | Theory: 100 End Term Exam: 70 P.A.: 30 Practical: 50 End Term Exam: 25 P.A. : 25 | ||
Theory
Total Periods : 45
Periods : 3 P/W
| UNIT | TOPIC/SUB-TOPIC | TOTAL HRS. |
1. Introduction and Overview 2
1.1 Introduction
1.2 Basic Terminology
1.3 Elementary Data Organization
1.4 Data Structures
1.5 Data Structure Operation
1.6 Algorithms; Complexity; Time- space Tradeoff
2. Preliminaries 3
2.1 Introduction
2.2 Mathematical notation and Functions
2.3 Algorithmic Notation
2.4 Control Structures
2.5 Complexity of Algorithms
2.6 Sub algorithms
2.7 Variables
2.8 Data Types
3. String Processing 5
1.1 Introduction
1.2 Basic Terminology
1.3 Storing Strings
1.4 Character Data Type
1.5 String Operation
1.6 Work Processing
1.7 Pattern matching Algorithms
4. Arrays, Records and Pointers 8
1.1 Introduction
1.2 Linear Arrays
1.3 Representation of Linear Arrays in Memory
1.4 Traversing Linear Arrays
1.5 Inserting and Deleting
1.6 Sorting; Bubble Sort
1.7 Search; Linear Search
1.8 Binary Search
1.9 Multidimensional Arrays
1.10 Pointers; Pointer Arrays
1.11 Records; Record Structures
1.12 Representation of Records in Memory; parallel Arrays
1.13 Matrices
1.14 Spares Matrices
5. Linked Lists 5
5.1 Introduction
5.2 Linked Lists
5.3 Representation of Linked Lists in Memory
5.4 Traversing a Linked List
5.5 Searching a Linked List
5.6 Memory Allocation Garbage Collection
5.7 Insertion into a linked list
5.8 Deletion from a Linked List
5.9 Header Linked Lists
5.10 Two –Ways Lists
6. Stacks, Queues, Recursion 6
6.1 Introduction
6.2 Stacks
6.3 Array Representation of Stacks
6.4 Arithmetic Expression; Polish Notation
6.5 Quicksort, an Application Stacks
6.6 Recursion
6.7 Towers of Hanoi
6.8 Implementation of Recursive Procedures by Stacks,
6.9 Queues
6.10 Defuse
6.11 Priority Queues
7. Trees 5
7.1 Introduction
7.2 Binary Trees
7.3 Representing Binary Trees in Memory
7.4 Traversing Binary Trees
7.5 Traversal Algorithms using Stacks
7.6 Header Nodes; Threads
7.7 Binary Search Trees,
7.8 Trees, Searching and Inserting in a Binary Search Tree
7.9 Deleting in a Binary Search Tree
7.10 Heap, Heapsort
7.11 Path Lengths; Huffman’s Algorithm
7.12 General Trees
8. Graphs and Their Application 4
8.1 Introduction
8.2 Graph Th. Terminology
8.3 Sequential Representation of Graphs; Adjacency matrix, path matrix
8.4 Warshall’s Algorithm, Shortest Paths
8.5 Linked Representation of a Graph
8.6 Operations on Graphs
8.7 Traversing a Graph
9. Sorting and Searching 5
9.1 Introduction
9.2 Sorting
9.3 Inserting Sort
9.4 Selection Sort
9.5 Merging
9.6 Merge-sort
9.7 Radix Sort
9.8 Linear searching
9.9 Binary searching
9.10 Interpolation searching
9.11 Hashing
10. Introduction to File Organization 2
Sequential, Index-Sequential and Direct file Organization
---------
45
Practical
Total Periods: 60
Classes : 4 P/W
Program Related to
1. Creation of singly & doubly linked list
2. Insertion, deletion and updation of (1) above
3. Creation of stack, queue and insertion/deletion operation on Stack/Queue
4. Conversion amongst infix, prefix & postfix expressions
5. Creation of tree and insertion/deletion of a node
6. Tree traversal problem
7. Graph search algorithms
8. Searching & Sorting Algorithm
REFERENCE BOOKS:
1. Data Structures - by Seymolur Lipschutz (Schaum Series)
2. Fundamentals of Computer Algorithms - by Horowitz,E & Sahani, S - Galgotia
3. Data Structures Theory Applications - by Trembly & Sorenson, TMH
4. Data Structure through C – by Mc Grew Hill
LIST OF EQUIPMENT
Hardware : Stand alone PC
(for detail, please refer Annex – I)
Software : C Compiler
