5th Semester
3 PapersBCA
Select Paper / CourseCC-11
CC-114 CreditsMajor (MJC)
Data Structures
Single-tap topic to complete/uncomplete • Hold (long-press) for Ask AI
1
Unit 1: Introduction to Data Structures
Definition, Classification of Data Structures: Linear vs Non-Linear, Static vs Dynamic Data Structures
Abstract Data Types (ADTs)
Algorithm Complexity Analysis: Time Complexity, Space Complexity, Asymptotic Notations (Big-O, Big-Omega, Big-Theta)
2
Unit 2: Linear Data Structures - Arrays, Stacks, Queues, Linked Lists
Arrays: Memory Representation, Address Calculation (Row-Major and Column-Major Order), Sparse Matrices
Stacks: Stack ADT, Array and Linked Representation, Push and Pop Operations, Applications: Expression Evaluation, Infix to Postfix Conversion, Recursion
Queues: Queue ADT, Operations (Enqueue, Dequeue), Circular Queue, Priority Queue, Double-Ended Queue (Deque)
Linked Lists: Singly Linked List, Circular Linked List, Doubly Linked List
Operations: Insertion, Deletion, Searching, Reversing
3
Unit 3: Non-Linear Data Structures - Trees
Tree Terminology: Node, Root, Leaf, Depth, Height, Subtree, Degree
Binary Trees: Properties, Types (Full, Complete, Balanced Binary Trees), Memory Representation (Array vs Linked)
Binary Tree Traversals: In-order, Pre-order, Post-order, Level-order Traversals
Binary Search Trees (BST): Creation, Insertion, Deletion, Searching Algorithms
Balanced Trees: AVL Trees (Rotations and Balancing), B-Trees, B+ Trees overview
4
Unit 4: Non-Linear Data Structures - Graphs
Graph Terminology: Directed vs Undirected, Connected vs Disconnected, Weighted Graphs, Cyclic vs Acyclic Graphs
Graph Representations: Adjacency Matrix and Adjacency List Representations
Graph Traversal Algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS)
Minimum Spanning Trees: Prim's and Kruskal's Algorithms
Shortest Path: Dijkstra's Algorithm
5
Unit 5: Searching, Sorting & Hashing
Searching Techniques: Linear Search, Binary Search (Iterative & Recursive), Performance Comparison
Sorting Algorithms: Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort (Algorithms and Time Complexities)
Hashing: Hash Tables, Hash Functions (Division, Mid-Square, Folding), Collision Resolution Techniques (Chaining, Open Addressing - Linear Probing, Quadratic Probing, Double Hashing)
Recommended Textbooks:
Data Structures using C - Aaron M. Tenenbaum, Yedidyah Langsam, Moshe J. Augenstein, Pearson
Buy on AmazonData Structures: A Pseudocode Approach with C - Richard F. Gilberg & Behrouz A. Forouzan, Cengage
Buy on AmazonFundamentals of Data Structures in C - Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed, Silicon Press
Buy on Amazon