Paper Title: Data Structures and Algorithms
Credits: 6
Total Contact Hours: 60 hours
Total Theory Exam Marks: 65
Assessment: One end-semester theory paper
Syllabus Breakdown
Module Topics Hours Marks Weightage
Module I Fundamental Data Structures 15 hrs 20 marks
Module II Advanced Data Structures and Trees 25 hrs 25 marks
Module III Algorithms and Analysis 20 hrs 20 marks
Total 60 hrs 65 marks
Module I: Fundamental Data Structures (15 hours, 20
marks)
1. Introduction to Data Structures (1 hr)
o Abstract Data Types (ADT)
o Use in algorithm design and problem-solving
2. Arrays and Strings (3 hrs)
o Static and dynamic arrays
o String operations and character arrays
o Pattern matching (brute-force)
3. Stacks and Queues (3 hrs)
o Stack: push, pop, postfix evaluation
o Queues: linear, circular, deque, and priority queues
o Applications in parsing and scheduling
4. Linked Lists (4 hrs)
o Singly, doubly, and circular linked lists
o Insertion, deletion, traversal
o Use in memory allocation
5. Hashing (4 hrs)
o Hash tables and hash functions
o Collision resolution: chaining, open addressing
o Load factor and rehashing
o Applications in sets, maps, and lookup tables
Module II: Advanced Data Structures and Trees (25
hours, 25 marks)
1. Binary Trees and Binary Search Trees (6 hrs)
o Tree terminology: nodes, depth, height, leaves
o Binary Tree traversals (preorder, inorder, postorder)
o Binary Search Trees (BST): insertion, deletion, search
2. Balanced Trees (5 hrs)
o AVL Trees: rotations, balancing
o Red-Black Trees: basic concepts
o Applications in memory and file systems
3. Heaps and Priority Queues (4 hrs)
o Binary Heap (Min-Heap and Max-Heap)
o Heap operations: insert, delete, heapify
o Heap Sort and priority queue implementation
4. Graphs and Disjoint Sets (8 hrs)
o Graph Basics
Definition: vertices and edges
Terminology: degree, path, cycle, connected components
o Types of Graphs
Directed and Undirected
Weighted and Unweighted
Cyclic and Acyclic
Connected and Disconnected
Simple, Multigraph, Complete graph
o Graph Representation
Adjacency list, adjacency matrix, edge list
Space-time trade-offs
o Graph Traversal Algorithms
Breadth-First Search (BFS), Depth-First Search (DFS)
Applications: reachability, shortest path, component counting
o Graph Coloring (Basics)
Vertex coloring and chromatic number
Applications: scheduling, register allocation, map coloring
Greedy coloring algorithm (overview)
5. Disjoint Set Data Structure (Union-Find) (2 hrs)
o Union by rank and path compression
o Applications: Kruskal’s Minimum Spanning Tree (MST), cycle detection
Module III: Algorithms and Analysis (20 hours, 20 marks)
1. Algorithm Analysis (5 hrs)
o Time and space complexity
o Asymptotic notations: Big-O, Big-Θ, Big-Ω
o Master’s Theorem for solving recurrence relations
o Application to divide-and-conquer algorithms
2. Sorting Algorithms (5 hrs)
oBubble, Selection, Insertion Sort
oMerge Sort, Quick Sort, Heap Sort
oTime and space complexity comparison
oStability and adaptiveness in sorting
3. Searching Algorithms (2 hrs)
o Linear Search and Binary Search
o Binary Search variations (e.g., rotated arrays)
4. Greedy Algorithms (4 hrs)
o Activity Selection
o Huffman Coding
o Fractional Knapsack
o Properties: greedy-choice, optimal substructure
5. Dynamic Programming (4 hrs)
o Tabulation and memoization techniques
o Classic problems: Longest Common Subsequence (LCS), 0/1 Knapsack,
Matrix Chain Multiplication
o Comparison with recursion and greedy techniques
Expected Learning Outcomes
Upon completing this course, students will:
Implement and apply core and advanced data structures for solving problems
efficiently
Analyze algorithmic performance using Big-O, Big-Θ, Big-Ω, and solve recurrences
using Master’s Theorem
Develop optimized algorithms using Divide & Conquer, Greedy, and Dynamic
Programming paradigms
Apply appropriate data structures and algorithmic strategies in real-world applications
and systems
Recommended Texts
Cormen, Leiserson, Rivest, Stein – Introduction to Algorithms
Horowitz & Sahni – Fundamentals of Data Structures
Mark Allen Weiss – Data Structures and Algorithm Analysis
Steven Skiena – The Algorithm Design Manual
Narasimha Karumanchi – Data Structures and Algorithms Made Easy
