Your cart is empty.
Keep shopping
Teach on Udemy
Turn what you know into an opportunity and reach millions around the world.
Learn MoreDeep Dive into Algorithms
Rating: 4.3 out of 54.3(46 ratings)
728 students
Deep Dive into Algorithms
Deep Dive into Algorithms
Created bySACHIN NANDHA SABARISH J
Last updated 9/2020
English
What you'll learn
- Students will learn various Backtracking Problems along with implementation using C language
- Students will learn various Dynamic Programming Problems along with implementation using C language
- Students will learn various Graph Algorithms along with implementation using C language
- Branch and Bound
- Divide and Conquer
- Greedy Algorithm
- Pattern Matching
- Searching and Sorting
Explore related topics
Course content
4 sections • 82 lectures • 32h 22m total length
- Introduction35:23
Explore backtracking and its cousins from recursion and recurrence relations to dynamic programming, with emphasis on state-space trees, bounding functions, branch-and-bound, and problem types like decision, optimization, and enumeration.
- Concept of N Queen Problem1:03:08
- Implementation of N Queen Problem38:14
- Time Complexity Analysis of N Queen Problem5:34
- Concept of Knight's Tour Problem25:48
- Implementation of Knight's Tour Problem41:23
Explore the knight's tour problem on a chessboard and implement a backtracking solution using eight knight moves, state space exploration, initialization, and a visited check to complete the tour.
- Time Complexity Analysis of Knight's Tour Problem8:44
- Concept Explanation of Rat in a Maze Problem23:36
- Implementation of Rat in a Maze35:49
- Time Complexity Analysis of Rat in a Maze4:55
- Concept Explanation of Subset Sum34:25
- Implementation of Subset Sum Problem28:34
- Time and Space Complexity Analysis of Subset Sum Problem13:24
- Concept Explanation of M-Coloring Problem43:04
Explore the m-coloring problem using backtracking to color a graph with given colors while enforcing that adjacent vertices have different colors; compare decision, optimization, and enumeration approaches.
- Implementation of M Coloring Problem36:39
- Time and Space Complexity Analysis of M Coloring Problem13:37
- Concept Explanation of Hamiltonian Cycle Problem34:16
- Implementation of Hamiltonian Cycle37:57
Explore implementing a Hamiltonian cycle via backtracking in C, building a graph with an adjacency matrix, and using a solve function and a display function to show all solutions.
- Time and Space Complexity Analysis of Hamiltonian Cycle9:58
- Concept Explanation of Sudoku Solver48:54
- Implementation of Sudoku Solver37:55
- Time and Space Complexity Analysis of Sudoku Solver24:05
Explain the time and space complexity of a sudoku solver using backtracking, showing nine possibilities per empty cell and a time complexity of nine to the n, with constant space.
- Sieve of Eratosthene18:56
Explore the Sieve of Eratosthenes to find all primes up to a given number by selecting a base and eliminating its multiples, stopping at the square root.
- Implementation of Sieve of Eratosthene19:02
Implement the sieve of Eratosthenes to generate primes by marking multiples up to the square root of n, starting at the square of each prime, and printing primes below n.
- Concept Explanation of Sieve of Sundaram24:13
- Implementation of Sieve of Sundaram21:46
Learn the implementation of the sieve of Sundaram to generate primes. Follow elimination steps, index-value mapping, and final prime construction.
- Time and Space Complexity Analysis of Sieve of Eratosthene and Sieve of Sundaram27:08
- Sieve of Eratosthene in O(N) Time Complexity31:01
- Implementation of Sieve of Eratosthene in O(N) Time Complexity33:36
- Prime Numbers after P with Sum S32:49
Use backtracking to find three prime numbers between two and S that sum to S, while generating prime numbers with the sieve of Eratosthenes and analyzing complexity.
- Implementation of Prime Numbers after P with Sum S42:02
Learn to implement a backtracking method that generates primes after a given prime and selects a subset whose sum matches the target, using linked lists, traversal, and recursive safety checks.
- Time and Space Complexity Analysis of Prime Numbers after P with Sum S20:46
Analyze the time and space complexity of a prime-selection algorithm using recursion and loops. Derive a recurrence, solve by substitution, and discuss activation records and space bounds.
- Introduction to Dynamic Programming - Part 143:25
- Introduction to Dynamic Programming - Part 216:30
- 0/1 Kanpsack Problem36:58
- Implementation of 0/1 Knapsack Problem19:39
Implement the 0/1 knapsack problem with dynamic programming using a (n+1) by (W+1) DP matrix. Read item values and weights, then apply the max transition to compute the optimal value.
- Printing items in 0/1 Knapsack Problem8:21
- Implementation of printing items in 0/1 Knapsack Problem9:19
Trace the dynamic programming matrix to print the selected items in the 0/1 knapsack problem, starting from the last column and moving upward to reveal chosen weights and values.
- Minimum Cost Path19:20
Uncover the minimum cost path using dynamic programming on a cost matrix, handling rectangular grids and moves only down or right from (0,0) to (m-1,n-1).
- Implementation of Minimum Cost Path15:59
- Tracing the path of Minimum Cost Path5:57
- Implementation of Tracing the Path of Minimum Cost Path12:12
- Subset Sum Problem33:24
Explore the subset sum problem for non-negative integers using dynamic programming, building a (n+1) by (sum+1) DP matrix to decide if a subset sums to the target.
- Implementation of Subset Sum Problem15:05
- Printing items in Subset Sum Problem5:52
Reconstruct a subset that sums to the target in the subset sum problem using a dynamic programming table, tracing from top to bottom.
- Implementation of printing items in Subset Sum6:41
- Maximum Size Square Sub Matrix with all 1s21:10
- Implementation of Maximum Size Square Sub Matrix with all 1s11:00
- Longest Increasing Subsequence22:24
- Implementation of Longest Increasing Subsequence7:22
Implement the longest increasing subsequence with dynamic programming. Initialize dp[i] to 1, read the input sequence, update dp[i] using dp[j]+1 when a[j] < a[i], and print dp.
- Printing items in Longest Increasing Subsequence9:07
- Implementation of Printing items in Longest Increasing Subsequence8:54
- Longest Common Subsequence26:01
- Implementation of Longest Common Subsequence10:59
Learn to implement the longest common subsequence by building a dp matrix, filling base zeros, and using max of top and left, with diagonal increment on character matches.
- Tracing the String in Longest Common Subsequence8:49
Trace the longest common subsequence from the dynamic programming matrix, matching diagonally on equal characters and taking the max of top or left on mismatches, with backtracking for enumeration.
- Implementation of Tracing the String in Longest Common Subsequence5:17
Implement tracing the longest common subsequence using a dynamic programming matrix, reconstruct the subsequence by following top, left, and diagonal moves, and reverse the result for correct order.
- Introduction and Brute Force Approach of Range Minimum Query10:22
- Implementation of Range Minimum Query ( Brute Force Approach )8:32
Explore the brute-force range minimum query by selecting a start and end index, iterating through the range, updating the minimum, and printing the result.
- Dynamic Programming Approach for Range Minimum Query16:40
- Implementation of Range Minimum Query ( Dynamic Programming Approach )11:51
- Introduction to Segment Tree19:44
- Constructing Segment Tree43:21
Learn how to construct a segment tree by recursively splitting an array into halves, building leaf nodes from input elements, and storing minimums at internal nodes.
- Implementation of Constructing Segment Tree17:04
- Range Minimum Query on the Constructed Segment Tree13:11
- Implementation of Range Minimum Query on Constructed Segment Tree22:09
- Range Minimum Query Using Sparse Table11:48
- Performing RMQ on Constructed Sparse Table20:46
- How to efficiently fill Sparse Table ?13:00
- Implementation of RMQ using Sparse Table34:00
Implement range minimum query using a sparse table, including preprocessing with logarithms and power-of-two intervals, then answer queries efficiently. Compare brute-force and dynamic programming approaches.
- How to represent a adjacency list for an directed and undirected graph ?23:19
Learn to represent graphs with adjacency lists for directed and undirected graphs, using an array of linked lists to store adjacent vertices, with proper memory management and source–destination concepts.
- Implementation of Adjacency List for Directed and Undirected Graph32:51
- HierHolzer's Algorithm25:44
This lecture covers Hierholzer's algorithm to find an Eulerian circuit in a directed graph, outlining conditions of strong connectivity and equal in and out degrees, and describing a stack-based process.
- Implementation of HierHolzer's Algorithm39:38
- Union Find Algorithm28:23
- Implementation of Union Find Algorithm36:02
- Topological Sorting16:55
- Dijkstra's Algorithm23:37
- Bellman Ford Algorithm48:28
Explore the Bellman-Ford algorithm for single-source shortest paths, including edge relaxation over B−1 iterations, handling negative weights, and detecting negative cycles with an extra pass.
- Ford Fulkerson Method Edmond Karg Maximum Flow Algorithm49:22
- Kargers Algorithm for Minimum Cut21:59
- Kruskal's Algorithm for Minimum Spanning Tree25:11
- Prim's Algorithm for Minimum Spanning Tree32:22
Learn how Prim's algorithm builds a minimum spanning tree using a binary heap, a hash map for vertex indexing, and priority queue, with insert, extract minimum, contains, and decrease operations.
Requirements
- Recursion
Description
An algorithmic paradigm or algorithm design paradigm is a generic model or framework which underlies the design of a class of algorithms. An algorithmic paradigm is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program.
How does one calculate the running time of an algorithm?
How can we compare two different algorithms?
How do we know if an algorithm is `optimal'?
Who this course is for:
- Programmers who are interested to learn algorithms