Course Name
MSc IT (Master of Science in Information Technology)
Subject Code MT0033 (Data Structures Using ‘ C ‘)
Get Questions
PART  A
PART  B
PART  C
Data Structures Using ‘ C ‘ Syllabus.
Unit 1: Arrays, Pointers and Structures
Introduction, Definition and concept of an Array, Array Used in ‘C’
Language, Single – Dimensional Arrays (One Dimensional Array) , Two Dimensional
Arrays. [Matrix],
Pointers, Declaring a pointer variable, Pointer Operators, Pointers and Arrays ,
Pointers used in function, Pointers used in an Array, Structures, Declaration of
structure ,
Initialization of structure , Processing of Structure , Structure used with an
Array
Unit 2: Overview of Data Structures
Introduction, What is a Data Structure? , Definition of data structure , The
Abstract Level , The Application Level , Implementation Level, Data Types and
Structured Data
Type, Common Structures , Abstract Data Types , Properties of Abstract Data Type
Generic Abstract Data Types, Programming with Abstract Data Types, Pre and Post
Conditions, Preconditions, Postconditions, Checking Pre & Post Conditions ,
Implementation Checks Preconditions Linear Data Structure, The Array Data
Structure ,
Using an Array and Lists as a Data Structure , Elementary Data Structures , What
the application needs ?, Implementation methods, Non Linear , Data
Structures – Trees, Binary Tree, Hash Tables
Unit 3: Overview of Stack
Introduction, Operations of Stack, Insert / Push operation, Delete/pop
operation , Display , Stack implementation using arrays, Applications of stack.,
Stacks using structures. Sample
C programs to represents the Stack Implementation
Unit 4: Overview of Queues
Introduction, Queues and its Operations, Different types of queues, Ordinary
queue Disadvantage of ordinary queue, Double ended queue (Deque), Circular queue
Sample C
programs to represents the Queue Implementation:
Unit 5: Linked Lists
Introduction , Linear list, Linked list, Typical basic linkedlist
operations, SinglyLinked Lists, Circular singly linked list, Insert a node at
the front end , Insert a node at the rear end,
Delete a node from the front end , Delete a node from the rear end , Doubly
linked lists, Insert a node at the front end , Insert a node at the rear end,
Delete a node from the front end
Unit 6: Trees
Introduction , Overview of Tree Concept , Binary tree, Strictly binary tree,
Complete binary tree, Almost complete binary tree, Storage representation of a
binary tree, Various
operations on binary trees using linked representation, Insertion Operation
Traversals, Binary search tree (BST) , Insertion Operation, Searching , Other
operations , find maximum value in a tree BST, To find minimum value in a BST ,
Height of tree , Count nodes in a tree, Count leaves in a tree, Delete a node
from the tree
Unit 7: Graphs
Introduction, Overview of Graphs, Adjacency lists & Adjacency Matrix ,
Adjacency lists , Adjacency Matrix, Depth – First Traversal, Breadth – First
Traversal, Spanning Trees
Unit 8: Searching Methods
Introduction, Basics Searching Techniques, Self Assessment Questions ,
Algorithmic Notation Sequential Search [Linear search] , Binary Search ,
Illustration of C Programmes
Unit 9: Sorting Methods
Introduction, Overview of Sorting Methods , How do you sort? , Evaluating a
Sorting Algorithms , Stability on Sorting algorithm, Internal Sorting, Insertion
Sort , Bubble Sort ,
Selection Sort , Shell Sort, Quick Sort , Tree Sort External Sorts, Merge Sort,
2Way Merge Sort .
Unit 10: Advanced Topics in Trees and Their Applications
Introduction, Analyzing the BST Search Algorithm, Inserting Nodes into a BST,
The Order of Insertion Determines the BST's Topology, Deleting Nodes from a BST,
Traversing the
Nodes of a BST, Preorder Traversal, Inorder Traversal, Postorder Traversal,
Binary Search Trees in the RealWorld, BigO Notation, Application of BigO
notation to algorithm analysis , BigΩ and BigΘ ,Properties of the sets O(f(n))
and Θ(f(n)) , Other useful mathematical formulae, Height Balanced Trees, AVL
Trees, RedBlack Trees, Lemma , Insertion into a redblack tree, Deletions from
a RedBlack tree, The AA tree, AVL Trees, Definition, Worst case height of an
AVL tree with n Nodes ,The Binary Heap, Definition , Insertions into a Binary
Heap, Deletions from a Binary Heap, Analysis of Insertion Algorithm, Build Heap
 building a tree from a collection of forests
Unit 11: Minimum Spanning Trees and Algorithms
Introduction, Spanning Trees , Minimum spanning trees, Why minimum spanning
trees How to find minimum Spanning Tree?, Lemma , Kruskal's Algorithm, Prim's
algorithm Finding Shortest Paths using BFS, Relaxation , Dijkstra Algorithm,
BellmanFord Algorithm, Singlesource shortest paths in Directed Acyclic Graph (DAG),
Floyd Warshall and Variants, Transitive Hull, MiniMax Distance, MaxiMin
Distance, Safest Path, Other Graphs, Graph Transpose Problem, Euler Cycle, Euler
Path, Topological Sort Problem Strongly Connected Components problem
Unit 12: Graphs and their Applications – I
Introduction to Graphs, Representation, Examples of Graph Problems,
Telecommunication, Sample Problem: Riding The Fences, Knight moves, Overfencing
Terminology, Directed Graph, Paths, Graph Representation, Edge List, Adjacency
Matrix Adjacency List, Implicit Representation, Self Assessment Questions,
Connectedness, sub graphs, Special Graphs , Rooted tree, Forest, Complete Graph,
Bipartite Graph Uninformed Search, Breadthfirst search, Uniformcost search ,
Depthfirst search, Depthlimited search, Iterative deepening search
,Bidirectional search
Unit 13: Graphs and their Applications – II
Introduction, Depth First Search (DFS) Algorithm, Sample Problem: n Queens
[Traditional], Depth First Search (DFS) Implementation, Complexity, Breadth
First Search (BFS), Sample Problem: Knight Cover [Traditional], Breadth First
Search (BFS) Implementation, Complexity, Depth First with Iterative Deepening
(DFID), Complexity Comparison of DFS, BFS & DFS+ID, Sample Problems,
Superprime Rib, Betsy's Tour Udder Travel, Desert Crossing, Addition Chains,
Informed Search, Best First Search, A* Search, An Application of Graph ,
Amortized Analysis, Aggregate Analysis, The potential method, Properties of the
Potential Function, The Dynamic Hash Table, A Dynamic Hash Table that both
expands and contracts
Unit 14: Splay Trees (Selfadjusting Search Trees)
Introduction, Splay Trees, Access lemma , Balance Theorem, Strong Access
Lemma, Static Optimality Theorem , Static Finger Theorem, Other Theorems ,
Working Set Theorem, Sequential Access Theorem, Dynamic Finger Theorem, Dynamic
Optimality Conjecture,
Insertion, Join, Deletion.
Unit 15: File Structures
Introduction, Logical or Physical Organization and Data Independence , A
language for describing file structures , Basic terminology , Sequential files ,
Inverted files , Indexsequential files , Multilists , Cellular multilists ,
Ring structures , Threaded lists ,Trees Scatter storage or hash addressing ,
Clustered files , B  Tree File Organization, B Tree Index Files, Dynamic
Hashing, How does it work?
