Live Training on data structure and algorithms

Course Content

 Introduction

• Analysis of Algorithm 
• Background analysis through a Program and its functions.
• Order of Growth 
• A mathematical explanation of the growth analysis through limits and functions.
• A direct way of calculating the order of growth
• Asymptotic Notations
• Best, Average and Worst case explanation through a program.
• Big O Notation
• Graphical and mathematical explanation.
• Calculation
• Applications at Linear Search
• Omega Notation
• Graphical and mathematical explanation.
• Calculation.
• Theta Notation
• Graphical and mathematical explanation.
• Calculation.
• Analysis of common loops
• Single, multiple and nested loops
• Analysis of Recursion
• Various calculations through Recursion Tree method
• Space Complexity 
• Basic Programs
• Auxiliary Space
• Space Analysis of Recursion
• Space Analysis of Fibonacci number

 Mathematics

• Finding the number of digits in a number.
• Arithmetic and Geometric Progressions.
• Quadratic Equations.
• Mean and Median.
• Prime Numbers.
• LCM and HCF
• Factorials
• Permutations and Combinations
• Modular Arithmetic
• Problems(With Video Solutions):
• Count Digits
• Palindrome Numbers
• Factorial of Numbers
• GCD of Two Numbers
• LCM of Two Numbers
• Check for Prime
• Prime Factors
• Sieve of Eratosthenes
• Computing Power

 Bit Magic

• Bitwise Operators
• Operation of AND, OR, XOR operators
• Operation of Left Shift, Right Shift and Bitwise Not
• Method 1: Simple method
• Method 2: Brian and Kerningham Algorithm
• Method 3: Using Lookup Table
• To check whether a number is a power of 2 or not
• Odd occurrences in an array.
• Two numbers having odd occurrences in an array.
• Generate power set using bitwise operators.

 Recursion

• Introduction to Recursion
• Applications of Recursion
• Writing base cases in Recursion
• Factorial
• N-th Fibonacci number
• Various problems on Recursion(With Video Solutions)
• Print n to 1
• Print 1 to n
• Tail Recursion
• Checking Palindrome
• Sum of digits
• Rod cutting
• Subsets of a set
• Tower of Hanoi Problem
• Josephus Problem

 Arrays

• Types of Arrays
• Fixed-sized array
• Dynamic-sized array
• Operations on Arrays
• Searching
• Insertions
• Deletion
• Arrays vs other DS
• Reversing - Explanation with complexity
• Problems(With Video Solutions)
• Left Rotation of the array by 1
• Check if Sorted
• Left Rotation of the array by D places
• Leaders in an Array
• Maximum Difference Problem
• Frequencies in Sorted Array
• Stock Buy and Sell Problem
• Trapping Rainwater Problem
• Maximum Consecutive 1s
• Maximum Subarray Sum
• Longest Even-Odd Subarray
• Maximum Circular sum subarray.
• Majority Element
• Minimum Consecutive Flips
• Sliding Window Technique
• Prefix Sum Technique

 Searching

• Binary Search Iterative and Recursive
• Binary Search and various associated problems
• Index of First Occurence in Sorted Array
• Index of Last Occurence in Sorted Array
• Count of occurrences of x in sorted element
• Count of 1s in a binary sorted array
• Find an element in sorted and rotated array
• Peak element
• Find an element in an infinite sized sorted array
• The square root of an integer
• Find pair in an unsorted array which gives sum X
• Find pair in a sorted array which gives sum X
• Find triplet in an array which gives sum X
• Median of two sorted arrays 
• Majority Element 

 Sorting

• Overview of Sorting Algorithms
• Insertion Sort
• Merge Sort
• Problems(With Video Solutions)
• Intersection of 2 sorted arrays
• Union of 2 sorted arrays
• Count Inversions in arrays
• Partitions(With Video Solutions)
• Naive
• Lomuto
• Hoare
• Quick Sort
• Using Lomuto and Hoare
• Time and Space analysis
• Choice of Pivot and Worst case
• Tail call elimination
• Problems(With Video Solutions)
• Kth Smallest element
• Chocolate Distribution Problem
• Sorting arrays with 2 and3 types of elements
• Merge Overlapping Intervals
• Meeting the Maximum Guests
• Cycle Sort
• Counting Sort
• Radix Sort
• Bucket Sort

 Matrix

• Introduction to Matrix
• Multidimensional Matrix
• Pass Matrix as Argument
• Printing matrix in a snake pattern
• Transposing a matrix
• Rotating a Matrix
• Check if the element is present in a row and column-wise sorted matrix.
• Boundary Traversal
• Spiral Traversal
• Matrix Multiplication
• Search in row-wise and column-wise Sorted Matrix

 Hashing

• Introduction and Time complexity analysis
• Application of Hashing
• Discussion on Direct Address Table
• Working and examples on various Hash Functions
• Introduction and Various techniques on Collision Handling
• Chaining and its implementation
• Open Addressing and its Implementation
• Chaining V/S Open Addressing
• Double Hashing

 Strings

• Given a string, check if they are an anagram of each other.
• Given a string, find the leftmost character that repeats.
• Given a string, find the leftmost character that does not repeat.
• Given a string, find the lexicographic rank of it in O(n) time.
• Implementation of the previously discussed lexicographic rank problem.
• Given a text string and a pattern string, find if a permutation of the pattern exists in the text.
• Given two strings, check if they are rotations of each other or not.
• Various Pattern Searching Algorithms.
• Rabin Karp Algorithm
• KMP Algorithm

 Linked List

• Introduction
• Doubly Linked List
• Circular Linked List
• Loop Problems
• Detecting Loops
• Detecting loops using Floyd cycle detection
• Detecting and Removing Loops in Linked List
• Middle of Linked List
• Nth node from the end of linked list
• Deleting a Node without accessing Head pointer of Linked List
• An iterative method to Reverse a linked list 
• Recursive method to reverse a linked list
• Reverse in group of size k
• Segregating even-odd nodes of linked list
• The intersection of two linked list
• Pairwise swap nodes of linked list
• Clone a linked list using a random pointer
• LRU Cache Design
• Merge two Sorted Linked Lists
• Palindrome Linked List

 Stack

• Understanding the Stack data structure 
• Applications of Stack
• Implementation of Stack in Array and Linked List
• Balanced Parenthesis 
• Two stacks in an array 
• K Stacks in an array 
• Stock span problem with variations
• Previous Greater Element 
• Next Greater Element 
• Largest Rectangular Area in a Histogram
• Understanding getMin() in Stack with O(1)

 Queue

• Implementation of the queue using array and LinkedList
• Stack using queue
• Problems
• Reversing a Queue
• Generate numbers with given digits
• First Circular Tour

 Deque

 Tree

• Introduction
• Tree
• Application
• Binary Tree
• Tree Traversal
• Implementation of:
• Inorder Traversal 
• Preorder Traversal 
• Postorder Traversal 
• Level Order Traversal (Line by Line)
• Tree Traversal in Spiral Form 
• Problems
• Size of Binary Tree 
• Maximum in Binary Tree 
• Height of Binary Tree 
• Print Nodes at K distance 
• Print Left View of Binary Tree 
• Children Sum Property 
• Check for Balanced Binary Tree 
• Maximum Width of Binary Tree 
• Convert Binary Tree to Doubly Linked List 
• Construct Binary Tree from Inorder and Preorder 
• Tree Traversal Spiral Form
• The diameter of a Binary Tree 
• LCA problem with an efficient solution
• Burn A Binary Tree from a Leaf
• Count Nodes in a complete Binary Tree
• Serialize and Deserialize a Binary tree

 Binary Search Tree

 Heap

• Introduction & Implementation
• Binary Heap 
• Insertion
• Heapify and Extract
• Decrease Key, Delete and Build Heap
• Heap Sort 
• Problems
• Sort K-Sorted Array 
• Buy Maximum Items with Given Sum 
• K Largest Elements 
• Merge K Sorted Arrays 
• Median of a Stream

 Graph

• Introduction to Graph 
• Graph Representation 
• Adjacency Matrix
• Adjacency List
• Adjacency Matrix VS List
• Breadth-First Search 
• Applications
• Depth First Search 
• Applications
• Problems
• Shortest Path in an Unweighted Graph 
• Detecting Cycle
• In the Undirected Graph 
• In the Directed Graph
• Topological Sorting 
• Kahn's BFS Based Algorithm
• DFS Based Algorithm
• Shortest Path in Directed Acyclic Graph 
• Prim's Algorithm/Minimum Spanning Tree
• Dijkstra's Shortest Path Algorithm
• Bellman-Ford Shortest Path Algorithm
• Kosaraju's Algorithm
• Articulation Point
• Bridges in Graph
• Tarjan’s Algorithm

 Greedy

 Backtracking

 Dynamic Programming

• Introduction 
• Dynamic Programming
• Memoization 
• Tabulation
• Problems(With Video Solutions):
• Longest Common Subsequence
• Coin Change Count Combinations 
• Edit Distance Problem
• Naive Approach
• DP Approach
• Longest Increasing Subsequence Problem
• Naive Approach
• Efficient Approach
• Maximum Cuts 
• Minimum coins to make a value 
• Minimum Jumps to reach at the end 
• 0-1 knapsack problem 
• Naive Approach
• Efficient Approach
• Optimal Strategy for a Game 
• Variation of Longest Common Subsequence 
• Variation of Longest Increasing Subsequence 
• Egg Dropping Problem 
• Count BST with nkeys
• Maximum Sum with No Consecutive
• Subset Sum Problem
• Matrix Chain Multiplication
• Palindrome Parititioning

 Trie

• Introduction
• Representation
• Search
• Insert
• Delete
• Count Distinct Rows in a Binary Matrix

 Segment Tree

• Introduction
• Construction
• Range Query 
• Update Query

 Disjoint Set

• Introduction
• Find and Union Operations
• Union by Rank
• Path Compression
• Kruskal's Algorithm