DSA Full Course

Data Structures and Algorithms

Syllabus ( Only Java -Ignore c++ )

Module 1: Introduction

1. Analysis of Algorithm
2. Background analysis through a Program and its functions.
3. Order of Growth
4. A mathematical explanation of the growth analysis through limits and functions.
5. A direct way of calculating the order of growth
6. Asymptotic Notations
7. Best, Average and Worst case explanation through a program.
8. Big O Notation
9. Graphical and mathematical explanation.
10. Calculation
11. Applications at Linear Search
12. Omega Notation
13. Graphical and mathematical explanation.
14. Calculation.
15. Theta Notation
16. Graphical and mathematical explanation.
17. Calculation.
18. Analysis of common loops
19. Single, multiple and nested loops
20. Analysis of Recursion
21. Various calculations through Recursion Tree method
22. Space Complexity
23. Basic Programs
24. Auxiliary Space
25. Space Analysis of Recursion
26. Space Analysis of Fibonacci number

Module 2: Mathematics

1. Finding the number of digits in a number.
2. Arithmetic and Geometric Progressions.
3. Quadratic Equations.
4. Mean and Median.
5. Prime Numbers.
6. LCM and HCF
7. Factorials
8. Permutations and Combinations
9. Modular Arithmetic
10. Practice Problems

Module 3: Bitmagic

1. Bitwise Operators in C++
2. Operation of AND, OR, XOR operators
3. Operation of Left Shift, Right Shift and Bitwise Not
4. Bitwise Operators in Java
5. Operation of AND, OR
6. Operation of Bitwise Not, Left Shift
7. Operation of Right Shift and unsigned Right Shift
8. Problem(With Video Solutions): Check Kth bit is set or not
9. Using the left Shift.
10. Using the right shift
11. Problem(With Video Solutions): Count Set Bits
12. Simple method
13. Brian and Kerningham Algorithm
14. Using Lookup Table
15. Problems(With Video Solutions):
16. To check whether a number is a power of 2 or not
17. Odd occurrences in an array.
18. Two numbers having odd occurrences in an array.
19. Generate power set using bitwise operators.
20. Practice Problems

Module 4: Recursion

1. Writing base cases in Recursion
2. Factorial
3. N-th Fibonacci number
4. Various problems on Recursion(With Video Solutions)
5. Print n to 1
6. Tail Recursion
7. Checking Palindrome
8. Sum of digits
9. Rod cutting
10. Subsets of a set
11. Tower of Hanoi Problem
12. Josephus Problem

Module 5: Arrays

1. Introduction and Advantages
2. Types of Arrays
3. Fixed-sized array
4. Dynamic-sized array
5. Operations on Arrays
6. Searching
7. Insertions
8. Deletion
9. Arrays vs other DS
10. Reversing - Explanation with complexity
11. Left Rotation of the array by 1
12. Left Rotation of the array by D places
13. Leaders in an Array
14. Maximum Difference Problem
15. Stock Buy and Sell Problem
16. Trapping Rainwater Problem
17. Maximum subarray sum
18. Longest even-odd subarray
19. Maximum Circular sum subarray.
20. Majority Element
21. Minimum Consecutive Flips
22. Sliding Window Technique
23. Prefix sum technique
24. Practice Problems

Module 6: Searching

1. Binary Search and various associated problems(With Video Solutions)
2. Leftmost index of an element in an array
3. Count of occurrences of x in sorted element
4. Count of 1s in a binary sorted array
5. Find an element in sorted and rotated array
6. Peak element
7. Find an element in an infinite sized sorted array
8. The square root of an integer
9. Two Pointer Approach Problems(With Video Solutions)
10. Find pair in an unsorted array which gives sum X
11. Find pair in a sorted array which gives sum X
12. Find triplet in an array which gives sum X
13. Problems(With Video Solutions)
14. Median of two sorted arrays
15. Majority Element

Module 7: Sorting

1. Implementation of C++ STL sort() function in Arrays and Vector
2. Time Complexities
3. Sorting in Java
4. Arrays.sort() in Java
5. Collection.sort() in Java
6. Stability in Sorting Algorithms
7. Examples of Stable and Unstable Algos
8. Insertion Sort
9. Merge Sort
10. Intersection of 2 sorted arrays
11. Union of 2 sorted arrays
12. Count Inversions in arrays
13. Partitions (With Video Solutions)
14. Quick Sort
15. Using Lomuto and Hoare
16. Time and Space analysis
17. Choice of Pivot and Worst case
18. Tail call elimination
19. Problems (With Video Solutions)
20. Kth Smallest element
21. Chocolate Distribution Problem
22. Sorting arrays with 2 and 3 types of elements
23. Merge Overlapping Intervals
24. Meeting the Maximum Guests
25. Cycle Sort
26. Counting Sort
27. Radix Sort

Module 8: Matrix

1. Introduction to Matrix in C++ and Java
2. Printing matrix in a snake pattern
3. Transposing a matrix
4. Rotating a Matrix
5. Check if the element is present in a row and column-wise sorted matrix.
6. Boundary Traversal
7. Spiral Traversal
8. Matrix Multiplication

Module 9: Hashing

1. Introduction and Time complexity analysis
2. Application of Hashing
3. Discussion on Direct Address Table
4. Working and examples on various Hash Functions
5. Introduction and Various techniques on Collision Handling
6. Chaining and its implementation
7. Open Addressing and its Implementation
8. Chaining V/S Open Addressing
9. Double Hashing
10. C++
11. Unordered Set
12. Unordered Map
13. Java
14. HashSet
15. HashMap
16. Problems(With Video Solutions):
17. Count Distinct Elements
18. Count of the frequency of array elements
19. The intersection of two arrays
20. Union of two unsorted arrays
21. Pair with given sum in an unsorted array
22. Subarray with zero-sum
23. Subarray with given sum
24. Longest subarray with a given sum
25. Longest subarray with an equal number of 0’s and 1’s
26. Longest common span with the same sum in a binary array
27. Longest Consecutive Subsequence
28. Count Distinct elements in every window

Module 10: String

1. Discussion of String DS
2. Problems(With Video Solutions)
3. Given a string, check if they are an anagram of each other.
4. Given a string, find the leftmost character that repeats.
5. Given a string, find the leftmost character that does not repeat.
6. Given a string, find the lexicographic rank of it in O(n) time.
7. Implementation of the previously discussed lexicographic rank problem.
8. Given a text string and a pattern string, find if a permutation of the pattern exists in the text.
9. Given two strings, check if they are rotations of each other or not.
10. Various Pattern Searching Algorithms.
11. Rabin Karp Algorithm
12. KMP Algorithm

Module 11: Linked List

1. Introduction
2. Implementation in CPP
3. Implementation in Java
4. Comparison with Array DS
5. Doubly Linked List
6. Circular Linked List
7. Loop Problems
8. Detecting Loops
9. Detecting loops using Floyd cycle detection
10. Detecting and Removing Loops in Linked List
11. Problems(With Video Solutions):
12. Middle of Linked List
13. Nth node from the end of linked list
14. Deleting a Node without accessing Head pointer of Linked List
15. An iterative method to Reverse a linked list
16. Recursive method to reverse a linked list
17. Segregating even-odd nodes of linked list
18. The intersection of two linked list
19. Pairwise swap nodes of linked list
20. Clone a linked list using a random pointer
21. LRU Cache Design

Module 12: Arrays

1. Understanding the Stack data structure
2. Applications of Stack
3. Implementation of Stack in Array and Linked List
4. In C++
5. In Java
6. Problems(With Video Solutions):
7. Balanced Parenthesis
8. Two stacks in an array
9. K Stacks in an array
10. Stock span problem with variations
11. Previous Greater Element
12. Next Greater Element
13. Largest Rectangular Area in a Histogram  14. Understanding getMin() in Stack with O(1)

Module 13: Queue

1. Introduction and Application
2. Implementation of the queue using array and LinkedList
3. In C++ STL
4. In Java
5. Stack using queue
6. Problems(With Video Solutions)
7. Reversing a Queue
8. Generate numbers with given digits
9. Maximums of all subarrays of size k

Module 14: Tree

1. Introduction
2. Tree
3. Application
4. Binary Tree
5. Tree Traversal
6. Implementation of:
7. Inorder Traversal
8. Preorder Traversal
9. Postorder Traversal
10. Level Order Traversal (Line by Line)
11. Tree Traversal in Spiral Form
12. Problems(With Video Solutions):
13. Size of Binary Tree
14. Maximum in Binary Tree
15. Height of Binary Tree
16. Print Nodes at K distance
17. Print Left View of Binary Tree
18. Children Sum Property
19. Check for Balanced Binary Tree
20. Maximum Width of Binary Tree
21. Convert Binary Tree to Doubly Linked List
22. Construct Binary Tree from Inorder and Preorder
23. The diameter of a Binary Tree
24. LCA problem with an efficient solution

Module 15: Binary Search Tree

1. Background, Introduction and Application
2. Implementation of Search in BST
3. In CPP
4. In Java
5. Insertion in BST
6. In CPP
7. In Java
8. Deletion in BST
9. In CPP
10. In Java
11. Floor in BST
12. In CPP
13. In Java
14. Self Balancing BST
15. AVL Tree
16. Red Black Tree
17. Set in C++ STL
18. Map in C++ STL
19. TreeSet in java
20. TreeMap in Java
21. Problems(With Video Solutions):
22. The ceiling of a key in BST
23. Ceiling on the left side in an array
24. Find Kth Smallest in BST
25. Check for BST
26. Fix BST with Two Nodes Swapped
27. Pair Sum with given BST
28. Vertical Sum in a Binary Tree
29. Vertical Traversal of Binary Tree
30. Top View of Binary Tree
31. Bottom View of Binary Tree

Module 16: Heap

1. Introduction & Implementation
2. Binary Heap
3. Insertion
4. Heapify and Extract
5. Decrease Key, Delete and Build Heap
6. Heap Sort
7. Priority Queue in C++
8. PriorityQueue in Java
9. Problems(With Video Solutions):
10. Sort K-Sorted Array
11. Buy Maximum Items with Given Sum
12. K Largest Elements
13. Merge K Sorted Arrays
14. Median of a Stream

Module 17: Graph

1. Introduction to Graph
2. Graph Representation
3. Adjacency Matrix
4. Adjacency List in CPP and Java
5. Adjacency Matrix VS List
6. Breadth-First Search
7. Applications
8. Depth First Search
9. Applications
10. Problems(With Video Solutions):
11. Shortest Path in an Unweighted Graph
12. Detecting Cycle
13. In the Undirected Graph
14. In the Directed Graph
15. Topological Sorting
16. Kahn's BFS Based Algorithm
17. DFS Based Algorithm
18. Shortest Path in Directed Acyclic Graph

Module 18: Greedy

1. Introduction
2. Activity Selection Problem
3. Fractional Knapsack
4. Job Sequencing Problem

Module 19: Backtracking

1. Concepts of Backtracking
2. Rat In a Maze
3. N Queen Problem
4. Sudoku Problem

Module 20: Dynamic Programming

1. Introduction
2. Dynamic Programming
3. Memoization
4. Tabulation
5. Problems(With Video Solutions):
6. Longest Common Subsequence
7. Coin Change Count Combinations
8. Edit Distance Problem
9. Naive Approach
10. DP Approach
11. Longest Increasing Subsequence Problem
12. Naive Approach
13. Efficient Approach
14. Maximum Cuts
15. Minimum coins to make a value
16. Minimum Jumps to reach at the end
17. 0-1 knapsack problem
18. Naive Approach
19. Efficient Approach
20. Optimal Strategy for a Game
21. Variation of Longest Common Subsequence
22. Variation of Longest Increasing Subsequence
23. Egg Dropping Problem

Module 21: Graph Advance

1. Prim's Algorithm/Minimum Spanning Tree
2. Dijkstra's Shortest Path Algorithm
3. Bellman-Ford Shortest Path Algorithm
4. Kosaraju's Algorithm
5. Articulation Point
6. Bridges in Graph
7. Tarjan’s Algorithm

Module 22: Trie

1. Introduction
2. Representation
3. Search
4. Insert
5. Delete
6. Count Distinct Rows in a Binary Matrix

Module 23: Segment Tree

1. Introduction
2. Construction
3. Range Query
4. Update Query

Module 24: Disjoint Set

1. Introduction
2. Find and Union Operations
3. Union by Rank
4. Path Compression
5. Kruskal's Algorith