DSA with Python

Duration: 3 Weeks | 24 Hours

Week 3: Linked Lists & Stack

Day 11-13: Singly Linked Lists

Topics:

• Linked list concept and structure
• Node representation
• Operations: creation, insertion, deletion, traversal
• Memory layout vs arrays
• Advantages and disadvantages

Subtopics:

• Node class design
• Head and tail pointers
• Insertion at different positions
• Deletion and memory cleanup
• Traversal techniques
• Circular linked lists
• Doubly linked lists

Learning Activities:

• Visual representation of linked lists
• Step-by-step operation tracing
• Compare with arrays
• Memory usage analysis

Hands-On Lab:

Implement from scratch:

1. Node class
2. LinkedList class
3. Insert at beginning
4. Insert at end
5. Insert at position
6. Delete node
7. Traversal (forward, backward)
8. Search
9. Display
10. Size calculation

Mini-Project 3: Linked List Implementation

Complete LinkedList with:

- Singly linked list

- Doubly linked list

- Circular linked list

- All operations

- Performance analysis

- Comparison with Python list
 

Day 14-15: Stack Data Structure

Topics:

• Stack concept (LIFO - Last In First Out)
• Stack operations: push, pop, peek, isEmpty
• Applications of stacks
• Implementation methods (array vs linked list)

Subtopics:

• Stack overflow and underflow
• Performance characteristics
• Stack frames in function calls
• Expression evaluation
• Backtracking problems

Learning Activities:

• Understand LIFO principle
• Trace stack operations
• Real-world applications
• Algorithm visualization

Hands-On Lab:

Implement Stack:

1. Using list (array-based)
2. Using linked list
3. Push operation
4. Pop operation
5. Peek operation
6. isEmpty check
7. Performance comparison
    

Week 4: Queue & Advanced Linear Structures

Day 16-17: Queue Data Structure

Topics:

• Queue concept (FIFO - First In First Out)
• Queue operations: enqueue, dequeue, peek
• Types: Simple queue, circular queue, deque
• Applications and use cases
• Implementation (array vs linked list)

Subtopics:

• Circular queue advantages
• Double-ended queue (deque)
• Queue overflow and underflow
• Performance analysis
• Priority queues

Learning Activities:

• Understand FIFO principle
• Visualize queue operations
• Compare with stack
• Real-world applications

Hands-On Lab:

Implement Queue:

1. .Simple queue (linked list)
2. Circular queue (array)
3. Deque (double-ended)
4. Priority queue basics
5.  Performance comparison
    

Day 18-19: Advanced Linear Structures

Topics:

• Skip lists
• Self-organizing lists
• Hash tables (introduction)
• Sparse vectors

Subtopics:

• Skip list levels and probability
• Move-to-front heuristic
• Hashing basics
• Collision handling preview

Learning Activities:

• Understand skip list operations
• Analyze performance
• Compare with balanced trees

Hands-On Lab:

Explore:

1. Skip list implementation
2. Skip list search
3. Self-organizing list
4. Performance comparison
    

Day 20: Module 2 Review & Assessment

Module 2 Assessment:

• Written test: 35 questions (1.5 hours)
• Practical: 4 coding problems (2 hours)
• Project presentations
• Code quality review

Module 2 Projects Submission:

1. Complete Linked List System
2. Stack Applications
3. Queue System
4. Real-world Linear DS problem

Duration: 4 Weeks | 32 Hours

Week 5: Binary Trees & Tree Basics

Day 21-23: Binary Trees Fundamentals

Topics:

• Tree terminology (root, leaf, height, depth)
• Binary tree concept
• Tree representations
• Binary tree properties
• Tree traversal methods

Subtopics:

• Tree node structure
• Complete and perfect trees
• Tree height and level
• In-order, Pre-order, Post-order, Level-order traversals
• Recursive vs iterative traversals

Learning Activities:

• Visual tree representation
• Trace traversals step-by-step
• Understand recursion in trees
• Practice drawing trees

Hands-On Lab:

Implement Binary Tree:

1. Node class
2. Tree construction
3. In-order traversal (recursive)
4. Pre-order traversal (recursive)
5. Post-order traversal (recursive)
6. Level-order traversal (BFS with queue)
7. Height calculation
8. Size calculation
9. Display tree structure

Mini-Project 4: Binary Tree Implementation

Complete BinaryTree with:

- All traversal methods

- Tree properties

- Tree manipulation

- Performance analysis

- Visualization
 

Day 24-25: Binary Search Trees (BST)

Topics:

• BST properties and definition
• BST operations: search, insert, delete
• BST performance
• Advantages and disadvantages
• Applications

Subtopics:

• In-order traversal for sorted order
• Finding minimum and maximum
• Finding successor and predecessor
• Balanced vs unbalanced BSTs
• Time complexity analysis

Learning Activities:

• Understand BST property
• Trace insertions and deletions
• Visualize unbalanced trees
• Compare search performance

Hands-On Lab:

Implement Binary Search Tree:

1. Search operation
2. Insert operation
3. Delete operation (3 cases)
4. Find minimum/maximum
5. Find successor/predecessor
6. Validate BST
7.  Tree balancing visualization

Week 6: Advanced Trees & Balancing

Day 26-27: AVL Trees & Balancing

Topics:

• Balanced tree concept
• AVL tree properties
• Balance factor
• Rotations (single and double)
• AVL insertion and deletion

Subtopics:

• Left-left, left-right cases
• Right-right, right-left cases
• AVL rebalancing
• Height-balanced property
• Complexity analysis

Learning Activities:

• Understand rotations visually
• Trace rebalancing
• Compare with unbalanced BST
• Performance analysis

Hands-On Lab:

Implement AVL Tree:

1. Balance factor calculation

2. Single rotation (LL, RR)

3. Double rotation (LR, RL)

4. Insert with rebalancing

5. Delete with rebalancing

6. Validate AVL property

Day 28: Red-Black Trees (Introduction)

Topics:

• Red-Black tree properties
• Color rules
• Insertion and deletion basics
• Complexity guarantees
• Comparison with AVL

Subtopics:

• RB-tree color constraints
• Black height
• Fixing violations
• Use cases (Java TreeMap, C++ std::map)

Learning Activities:

• nderstand RB-tree rules
• Trace color fixing
• Compare with AVL

Hands-On Lab:

Study Red-Black Trees:

1. Understand properties

2. Trace insertions

3. Trace deletions

4. Study implementations

5. Compare performance

Day 29: Heaps & Priority Queues

Topics:

• Heap concept (min-heap, max-heap)
• Complete binary tree
• Heap property
• Heap operations: insert, delete, extract
• Heap sort
• Priority queues

Subtopics:

• Array representation of heap
• Heapify operation
• Up-bubble and down-bubble
• Heap construction
• Complexity analysis

Learning Activities:

• Visualize heap operations
• Trace bubble-up/down
• Understand array indexing
• Performance analysis

Hands-On Lab:

Implement Max Heap:

1.  Array-based representation
2. Insert (bubble-up)
3. Delete (bubble-down)
4. Extract max
5.  Heapify operation
6.  Heap sort algorithm

Day 30: Module 3 Review & Assessment

Module 3 Assessment:

• Written test: 40 questions (1.5 hours)
• Practical: 5 coding problems (2.5 hours)
• Project presentations
• Comparison analysis (BST vs AVL vs RB)

Module 3 Projects Submission:

1. Binary Tree System
2. BST with Analysis
3. AVL Tree Implementation
4. Heap & Priority Queue
5. Tree-based Application (Real-world)
    

Duration: 3 Weeks | 24 Hours

Week 7: Graph Fundamentals & Representations

Day 31-32: Graph Basics

Topics:

• Graph terminology (vertices, edges, paths)
• Directed vs undirected graphs
• Weighted vs unweighted graphs
• Graph representations (adjacency matrix, list)
• Graph density and sparsity

Subtopics:

• Degree of vertex
• Connected components
• Strongly connected graphs
• DAG (Directed Acyclic Graph)
• Multigraph and simple graph

Learning Activities:

• Draw various graphs
• Compare representations
• Analyze space complexity
• Understand use cases

Hands-On Lab:

Graph Implementation:

1.  Vertex and Edge classes
2. Adjacency matrix representation
3.  Adjacency list representation
4.  Add/remove vertex and edge
5.  Get neighbors
6.  Display graph
7. Performance comparison

Day 33-34: Graph Traversal Algorithms

Topics:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Traversal applications
• Time and space complexity
• Connected components

Subtopics:

• BFS with queue
• DFS with stack/recursion
• Visited tracking
• Path reconstruction
• Cycle detection (undirected and directed)

Learning Activities:

• Trace BFS step-by-step
• Trace DFS step-by-step
• Visualize exploration order
• Compare approaches

Hands-On Lab:

Implement Traversals:

1.  BFS (iterative with queue)
2.  DFS (recursive)
3.  DFS (iterative with stack)
4.  Detect cycle (undirected)
5.  Detect cycle (directed)
6.  Find connected components
7.  Topological sort (DFS-based)
8.  Path finding

Day 35: Shortest Path Algorithms

Topics:

• Dijkstra's algorithm (weighted, non-negative)
• Bellman-Ford algorithm
• Floyd-Warshall algorithm
• A* algorithm basics

Subtopics:

• Priority queue optimization in Dijkstra
• Negative edge handling
• All-pairs shortest path
• Heuristics in A*

Learning Activities:

• Trace Dijkstra step-by-step
• Compare algorithms
• Analyze complexity
• Understand trade-offs

Hands-On Lab:

Implement Algorithms:

1.  Dijkstra's algorithm
2.  Bellman-Ford algorithm
3.  Floyd-Warshall algorithm
4.  Distance matrix generation

Week 8: Minimum Spanning Trees & Hashing

Day 36-37: Minimum Spanning Trees

Topics:

• MST concept and properties
• Kruskal's algorithm
• Prim's algorithm
• Applications and use cases
• Comparison of algorithms

Subtopics:

• Union-Find (Disjoint Set Union)
• Cut property of MST
• Cycle property
• Dense vs sparse graphs

Learning Activities:

• Understand MST property
• Trace Kruskal's algorithm
• Trace Prim's algorithm
• Visualize MST construction

Hands-On Lab:

Implement MST Algorithms:

1.  Union-Find data structure
2.  Kruskal's algorithm (sort + union-find)
3.  Prim's algorithm
4.  MST cost calculation
5.  Performance comparison
   
   Day 38: Hash Tables & Hashing

Topics:

• Hash function design
• Hash table concept
• Collision handling methods
• Load factor and rehashing
• Applications and use cases

Subtopics:

• Separate chaining
• Open addressing (linear, quadratic, double hashing)
• Hash function properties
• Universal hashing
• Perfect hashing

Learning Activities:

• Design hash functions
• Trace collision resolution
• Analyze performance
• Compare approaches

Hands-On Lab:

Implement Hash Table:

1.  Custom hash function
2.  Separate chaining collision handling
3.  Open addressing (linear probing)
4.  Rehashing when load factor > 0.75
5.  Insert, delete, search operations
6.  Performance analysis
   
   Day 39: Hash Map & Applications

Topics:

• Hash map vs hash table
• Dictionary implementation
• Applications of hashing
• Counting and grouping problems
• Substring problems

Subtopics:

• Hash map in different languages
• Iteration and ordering
• Two-sum and extension problems
• Frequency problems

Hands-On Lab:

Hash Map Applications:

1.  Word frequency counter
2.  Anagram grouping
3. Two-sum problem
4.  Duplicate detection
5.  Intersection of arrays
6.  Longest substring without repeating

Day 40: Module 4 Review & Assessment

Module 4 Assessment:

• Written test: 40 questions (1.5 hours)
• Practical: 5 coding problems (2.5 hours)
• Project presentations
• Algorithm comparison analysis

Module 4 Projects Submission:

1. Graph Implementation & Traversals
2. Shortest Path Solver
3. MST Implementation
4. Hash Table System
5. Graph-based Application (Real-world)

Duration: 2 Weeks | 16 Hours

Week 9: Advanced Data Structures

Day 41-42: Trie (Prefix Tree)

Topics:

• Trie structure and nodes
• Prefix matching
• Applications (autocomplete, spell checker)
• Time and space complexity
• Optimization techniques

Subtopics:

• Trie construction
• Insertion and search
• Auto-complete implementation
• Space optimization (compressed trie)

Learning Activities:

• Understand trie structure
• Trace insertion and search
• Visualize prefix matching
• Compare with hash table

Hands-On Lab:

Implement Trie:

1. TrieNode class
2. Insert word
3. Search word
4.  Starts with prefix
5.  Auto-complete suggestions
6.  Spell checker
7.  Longest common prefix

Practical Trie Applications:

1. Auto-complete in search engines
2. Spell checking
3. IP routing (longest prefix match)
4. Dictionary implementation

Practical Problems:

1. Implement autocomplete
2. Word search (in grid)
3. Longest word in dictionary
4. Design search autocomplete

Day 43: Segment Trees & Fenwick Trees

Topics:

• Segment tree concept
• Range queries and updates
• Fenwick tree (Binary Indexed Tree)
• Applications
• Time complexity

Subtopics:

• Segment tree construction
• Lazy propagation
• BIT operations
• Sum query in range
• Update in range

Learning Activities:

• Understand segment tree structure
• Trace queries and updates
• Compare with naive approach
• Analyze complexity

Hands-On Lab:

Implement:

1. Segment tree (recursive)
2. Range sum query
3. Point update
4. Range update (with lazy propagation)
5. Fenwick tree
6. BIT range sum
7. BIT update

Practical Problems:

1. Range sum query
2. Update and query
3. Count elements in range

Day 44: Union-Find & DSU

Topics:

• Disjoint Set Union (DSU)
• Union and find operations
• Path compression
• Union by rank
• Applications

Subtopics:

• Path compression optimization
• Union by rank/size
• Connected components
• Cycle detection in graphs
• Kruskal's algorithm application

Learning Activities:

• Understand union-find operations
• Trace path compression
• Analyze amortized complexity
• Compare optimization techniques

Hands-On Lab:

implement Union-Find:

1. Basic union and find
2. Path compression
3. Union by rank
4. Find connected components
5. Detect cycle
6. Kruskal's algorithm

Practical Problems:

1. Connected components count
2. Detecting cycle in graph
3. Number of provinces
4. Redundant connections
5. Accounts merge

Day 45: Suffix Array & Pattern Matching

Topics:

• Suffix array concept
• Pattern matching in strings
• Applications (compression, bioinformatics)
• Time complexity
• Comparison with suffix trees

Subtopics:

• Suffix array construction
• Binary search on suffix array
• LCP (Longest Common Prefix) array
• Pattern matching

Learning Activities:

• Understand suffix array
• Trace construction
• Pattern matching practice
• Performance analysis

Hands-On Lab:

Implement:

1. Suffix array construction

2. LCP array

3. Pattern matching

4. Multiple pattern search

Week 10: Problem Solving & Complex Applications

Day 46-47: Complex Problem Solving

Topics:

• Combining multiple data structures
• Algorithm design techniques
• Trade-off analysis
• Optimization strategies
• Real-world problem modeling

Learning Activities:

• Solve complex problems from scratch
• Design solutions from requirements
• Optimize for different constraints
• Present design decisions
• Implement cache with O(1) operations

Complex Problems:

1. LRU Cache (HashMap + Doubly Linked List)

• Evict least recently used

1. Skyline Problem (Priority Queue + Tree)

• Merging city skylines
• Event-based approach

1. Median Finder (Two Heaps)

• Dynamic median finding
• Stream processing

1. Design Search Autocomplete (Trie + Heap)

• Fast prefix search
• Top k suggestions

1. Stock Span Problem (Monotonic Stack)

• Daily spans calculation
• Optimization

1. Closest Binary Search Tree Value (BST + Priority Queue)

• Find k closest elements

Mini-Project 5: System Design - In-Memory Database

Build database with:

- Hash table for data storage

- B-tree for range queries

- Indexing structures

- Query optimization

- Performance benchmarks

Day 48: Competitive Programming & Interview Prep

Topics:

• Interview preparation
• Common interview patterns
• Problem-solving strategies
• Time management
• Communication skills

Subtopics:

• Two-pointer technique
• Sliding window
• Divide and conquer
• Dynamic programming intro
• Backtracking

Learning Activities:

• Solve interview-style problems
• Practice communication
• Mock interview sessions
• Optimize solutions

Interview Problem Categories:

1. Array/String Problems (30%)
2. Tree Problems (20%)
3. Graph Problems (15%)
4. Linked List Problems (10%)
5. Hash Table Problems (10%)
6. Advanced Problems (15%)

Day 49-50: Module 5 Review & Final Projects

Module 5 Assessment:

• Written test: 30 questions (1 hour)
• Practical: 3 complex problems (1.5 hours)
• System design interview
• Code quality review

Module 5 Projects Submission:

1. Advanced Data Structures (Trie, Segment Tree, etc.)
2. Complex Problem Solutions
3. System Design Project
4. Performance Optimization Report

Duration: 2 Weeks | 16 Hours

Week 11: Real-World Applications

Day 51-52: Database Indexing & Query Optimization

Practical Application 1: Custom Database

Build simple database with:

- B-tree for indexed search

- Hash table for direct access

- Query optimization

- Explain plans

- Benchmark analysis

Components:

• File I/O for persistence
• Indexing strategies
• Query parser
• Optimizer
• Executor

Day 53: Social Network Analysis

Practical Application 2: Social Network

Model social network with:

- Graph for relationships

- Graph algorithms for recommendations

- Community detection

- Influence analysis

Features:

• User connections (graph)
• Recommendation algorithm
• Friend suggestions
• Feed ranking
• Viral spread simulation

Day 54-55: Capstone Project

Capstone Project Options:

Option 1: Search Engine

• Trie for auto-complete
• Graph for web crawling
• Hash tables for indexing
• Ranking algorithm

Option 2: File System

• Tree for directory structure
• Hash table for file lookup
• Allocation strategies
• Performance optimization

Option 3: Compiler/Interpreter

• Trie for symbol table
• Stack for expression evaluation
• Tree for AST
• Hash table for identifiers

Option 4: Game Development

• Spatial data structures for collision
• Priority queue for event handling
• Graph for pathfinding
• Optimization for performance

Option5: Machine Learning Pipeline

• Efficient data structures for model
• Feature indexing
• Caching strategies
• Performance optimization

Capstone Requirements:

• Design document
• Complete implementation
• Performance analysis
• Optimization report
• Presentation (20 minutes)

Week 12: Advanced Topics & Final Assessment

Day 56-57: Performance Optimization & Scalability

Topics:

• Memory optimization
• CPU cache awareness
• Parallelization opportunities
• Space-time tradeoffs
• Profiling and benchmarking

Learning Activities:

• Profile data structure operations
• Identify bottlenecks
• Implement optimizations
• Measure improvements
  • Reduce allocations

Optimization Techniques:

• Memory Optimization
  • Pool management
  • Compression
• Access Pattern Optimization
  • Cache locality
  • Prefetching
  • Memory alignment
• Algorithmic Optimization
  • Reduce complexity
  • Early termination
  • Approximation

Day 58: Emerging Data Structures

Topics:

• Bloom filters
• Skip lists
• Cuckoo hashing
• Radix trees
• Persistent data structures

Learning Activities:

• Study advanced structures
• Understand trade-offs
• Real-world usage
• Implementation studies

Day 59: Final Project Presentations

Capstone Project Presentations:

• 20-minute presentation per student
• Live demo
• Q&A and feedback
• Code walkthrough
• Performance analysis

Presentation Criteria:

• Design and architecture (20%)
• Implementation quality (20%)
• Performance optimization (20%)
• Presentation skills (20%)
• Q&A and technical depth (20%)

Day 60: Final Assessment & Course Wrap-up

Final Comprehensive Assessment:

Written Exam (2 hours):

• 50 questions covering all modules
• Mix of theory and practical
• Design and analysis problems
• Code review exercises

Practical Exam (2.5 hours):

• Implement data structure from scratch
• Optimize given algorithm
• Design solution to new problem

Debug and fix issues