Backtracking, Dynamic Programming & Randomization Algorithms

Backtracking, N-Queens Problem, Sum of Subsets, Floyd Warshall Algorithm, Randomization, Vertex Cover, Class P & NP

What you'll learn

Apply Backtracking Techniques to solve constraint-based problems using recursive exploration and pruning strategies.

Design and Implement Dynamic Programming Solutions for optimization problems involving overlapping subproblems

Understand and Utilize Randomized Algorithms to enhance algorithm performance and handle probabilistic problem-solving scenarios

Analyze Time and Space Complexity of algorithms, compare strategies, and choose the most efficient approach for given problem types in interviews

Requirements

No Prerequisites

Description

Unlock the logic behind some of the most fascinating and foundational problems in computer science through this comprehensive course on algorithms and computational theory. Whether you're a computer science student, a coding enthusiast, or a professional preparing for technical interviews or competitive programming, this course will guide you through both practical problem-solving techniques and essential theoretical insights.We begin with Backtracking, a systematic method for generating all possible solutions by exploring one option at a time and abandoning paths that don’t meet the criteria. Using intuitive explanations and hands-on coding, you'll learn how backtracking applies to real-world problems, including the classic N-Queens Problem, where the goal is to place N queens on an N×N chessboard so that no two queens attack each other, and the Sum of Subsets Problem, which involves finding subsets of numbers that sum to a specific value.Next, you’ll explore the Floyd-Warshall Algorithm, a key dynamic programming solution used to compute shortest paths between all pairs of vertices in a weighted graph. This technique is a fundamental part of graph theory and essential for applications involving network routing and path optimization.The course also covers Randomized Algorithms, which use randomness to improve performance or simplify solutions. You'll learn how they are used in sorting, testing, and optimization scenarios, and why they are often preferred in large-scale or uncertain environments.Delve into Vertex Cover, an important NP-complete problem in graph theory, where the objective is to find the smallest set of vertices that cover all edges in a graph. This introduces you to approximation algorithms and the challenges of computational hardness.Finally, we introduce P vs NP, one of the most profound questions in computer science. Understand the classification of problems, polynomial-time solvability, and the implications of NP-completeness.By the end of this course, you'll not only be able to implement these algorithms but also understand their underlying principles and applications in real-world scenarios.I am Dr. K.C. Prabu Shankar from SRM Institute of Science and Technology, the Course Instructor for Backtracking, Dynamic Programming & Randomization Algorithms Course.

Overview

Section 1: Introduction

Lecture 1 Introduction to Backtracking

Lecture 2 N Queens Problem

Lecture 3 Sum of Subsets

Section 2: Floyd Warshall Algorithm

Lecture 4 Floyd Warshall Algorithm

Section 3: Randomization and Approximation

Lecture 5 Introduction to Randomization and Approximation

Lecture 6 Rabin Carp Algorithm

Lecture 7 Vertex Cover Problem

Lecture 8 P Class and NP Class Demystified

This course is ideal for computer science students, coding enthusiasts, competitive programmers, and job seekers preparing for technical interviews. It also benefits software developers aiming to strengthen their problem-solving skills. Anyone with basic programming knowledge and a passion for algorithms will gain valuable insights and hands-on experience from this course.