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