MCS-021 Data and File structures
(4 Credits)
Objectives
The learner should be well versed with the fundamentals of Algorithms, learn various data structures, should be able to use them appropriately as per need during development of programs. Also, the learner should know different sorting and searching techniques so that correct techniques can be used in different programs so that the complexity of the program does not increase due the sorting/ search technique employed. The learner should have the knowledge about file structures and finally, s/he should also know the concepts of advanced data structures.
Syllabus
BLOCK 1:
Introduction to Algorithms and Data Structures
Unit 1:
Analysis of Algorithms
·
Mathematical Background
·
Process of Analysis
·
Calculation of Storage Complexity
·
Calculation of Run Time Complexity
Unit 2
Arrays
·
Arrays and Pointers
·
Sparse Matrices
·
Polynomials
·
Representation of Arrays
o
Row Major Representation
o
Column Major Representation
·
Applications
Unit 3:
Lists
·
Abstract Data Type-List
·
Array Implementation of Lists
·
Linked Lists-Implementation
·
Doubly Linked Lists-Implementation
·
Circularly Linked Lists-Implementation
·
Applications
Block-2: Stacks, Queues and
Trees
Unit 4: Stacks
·
Abstract Data
Type-Stack
·
Implementation
of Stack
o
Implementation of Stack using Arrays
o
Implementation of Stack using Linked Lists
·
Algorithmic
Implementation of Multiple Stacks
·
Applications
Unit 5: Queues
·
Abstract Data
Type-Queue
·
Implementation
of Queue
o
Array Implementation
o
Linked List Implementation
·
Implementation
of Multiple Queues
·
Implementation
of Circular Queues
o
Array Implementation
o
Linked List Implementation of a circular queue
·
Implementation
of DEQUEUE
o
Array Implementation of a
dequeue
o
Linked List Implementation of
a dequeue
Unit 6: Trees
·
Abstract Data
Type-Tree
·
Implementation
of Tree
·
Tree Traversals
·
Binary Trees
·
Implementation
of Binary Tree
·
Binary Tree
Traversals
o
Recursive Implementation of Binary Tree Traversals
o
Non Recursive Implementations of Binary Tree
Traversals
·
Applications
BLOCK 3:
Graph Algorithms and Searching Techniques
Unit 7: Advanced Trees
·
Binary Search
Trees
o
Traversing a Binary Search Trees
o
Insertion of a node into a Binary Search Tree
o
Deletion of a node from a Binary Search Tree
·
AVL Trees
o
Insertion of a node into an AVL Tree
o
Deletion of a node from and AVL Tree
o
AVL tree rotations
o
Applications of AVL Trees
·
B-Trees
o
Operations on B-Trees
o
Applications of B-Trees
Unit 8: Graphs
·
Definitions
·
Shortest Path
Algorithms
o
Dijkstra’s Algorithm
o
Graphs with Negative Edge costs
o
Acyclic Graphs
o
All Pairs Shortest Paths Algorithm
·
Minimum cost
Spanning Trees
o
Kruskal’s Algorithm
o
Prims’s Algorithm
o
Applications
·
Breadth First
Search
·
Depth First
Search
·
Finding Strongly
Connected Components
Unit 9: Searching
·
Linear Search
·
Binary Search
·
Applications
BLOCK 4:
File Structures and Advanced Data
Structures
Unit 10: Sorting
·
Internal Sorting
o
Insertion Sort
o
Bubble Sort
o
Quick Sort
o
2-way Merge Sot
o
Heap Sort
·
Sorting on Several
Keys
Unit 11: Advanced Data Structures
·
Splay Trees
o
Splaying steps
o
Splaying Algorithm
·
Red-Black trees
o
Properties of a Red-Black tree
o
Insertion into a Red-Black tree
o
Deletion from a Red-Black tree
·
AA-Trees
Unit 12: File Structures
·
Terminology
·
File Organisation
·
Sequential Files
o
Structure
o
Operations
o
Disadvantages
o
Areas of use
·
Direct File
Organisation
·
Indexed Sequential
File Organisation