Theory of Computation Lectures | Computer Science and Computer Engineering

Lecture Link In this lecture, we introduce the Fractional Knapsack Problem, one of the most important applications of the Greedy Algorithm in optimization. You’ll learn why we use it, where it applies in the real world, and how to design the algorithm step by step. We’ll walk through the intuitive idea behind value-per-weight (density), explore practical examples like resource allocation and profit maximization, and write the pseudoalgorithm you’ll use to solve problems in the next lecture.

Lecture Link In this video, we break down regular expressions (regex) step by step — from the basic building blocks to how they form regular languages. You’ll learn: 1- The three core operations: Concatenation, Union, and Kleene Star 2- The difference between the empty string (ε) and the empty set (∅) 3- The distinction between Kleene Star (★) and the plus (+) operator 4- How regex compares to arithmetic operations with simple analogies 5- Solved examples to help you actually use these operations By the end, you’ll understand how regular expressions are built, how they define regular languages, and why they’re such a powerful tool in computer science. If you’re a student, developer, or just curious about how search patterns and compilers work, this video is for you!

  Lecture Link In this lecture, we introduce the Fractional Knapsack Problem, one of the most important applications of the Greedy Algorithm in optimization. You’ll learn why we use it, where it applies in the real world, and how to design the algorithm step by step. We’ll walk through the intuitive idea behind value-per-weight (density), explore practical examples like resource allocation and profit maximization, and write the pseudoalgorithm you’ll use to solve problems in the next lecture. ⚡️ In the next video, we’ll solve full examples step by step, so make sure you watch this one first to master the concept!

  Lecture Link In this video, we’ll write and explain the 0/1 Knapsack algorithm in Python line by line. You’ll learn how to: 1- Build a Dynamic Programming (DP) table to find the maximum profit 2- Understand each part of the nested loops that fill the table 3- Implement the backtrace function to recover the selected items 4- See how DP and backtracking work together in solving optimization problems

Lecture Link In this video, we solve the 0/1 Knapsack Problem step by step using Dynamic Programming . We cover two essential parts of the solution: 1️⃣ Building the DP table — to find the maximum profit achievable without exceeding the knapsack’s capacity. 2️⃣ Backtracking the table — to trace which items were actually chosen to reach that maximum profit. By the end of the lecture, you’ll not only know the optimal profit but also exactly which items to select , making this one of the clearest walkthroughs of the knapsack problem you’ll find.

Lecture Link In this lesson, we tackle the 0/1 Knapsack Problem , a classic optimization problem in computer science and interview prep. We’ll motivate the problem, define it clearly, and then solve it using dynamic programming . You’ll see the pseudoalgorithm , learn why we use a table (columns = capacities 0…W, rows = items), and walk through a concrete example step by step. In the next video, we’ll implement it in Python . What you’ll learn: What the 0/1 Knapsack Problem is used for (budgeting, scheduling, resource allocation, portfolios) The DP intuition: solve small capacities first, reuse results How to build the DP table: rows = items, columns = capacities The key choice at each cell: take or skip the item How to trace back selected items from the final table Clean pseudoalgorithm you can convert to code