SubsetSum

preview_player
Показать описание
Textbooks:
Computational Complexity: A Modern Approach by S. Arora and B. Barak.
Algorithm Design by J. Kleinberg and E. Tardos.

Lecture slides by K. Wayne accompanying the latter textbook:
  1. Computer Science Theory Explained
Рекомендации по теме
SubsetSum 0:21:57

SubsetSum

Subset Sum Problem 0:09:07

Subset Sum Problem Dynamic Programming

6.2 Sum Of 0:12:19

6.2 Sum Of Subsets Problem - Backtracking

3 CNF Subset 0:03:28

3 CNF Subset Sum - Georgia Tech - Computability, Complexity, Theory: Complexity

Subset Sum - 0:01:35

Subset Sum - Georgia Tech - Computability, Complexity, Theory: Complexity

Partition Equal Subset 0:14:12

Partition Equal Subset Sum - Dynamic Programming - Leetcode 416 - Python

L10. Subset Sum 0:24:25

L10. Subset Sum I | Recursion | C++ | Java

subset sum problem 0:25:42

subset sum problem dynamic programming | backtracking sum of subsets

Subset Sum Problem 0:28:54

Subset Sum Problem Dynamic programming

Komplexität #21 - 0:15:23

Komplexität #21 - SUBSET-SUM und RUCKSACK in NP

18. Dynamic Programming, 1:03:45

18. Dynamic Programming, Part 4: Rods, Subset Sum, Pseudopolynomial

Sum of Subset 0:09:29

Sum of Subset Problem | Backtracking Method | Design & Algorithms | Lec-54 | Bhanu Priya

DP 14. Subset 0:38:49

DP 14. Subset Sum Equals to Target | Identify DP on Subsequences and Ways to Solve them

7 Subset Sum 0:27:13

7 Subset Sum Problem

Partition equal subset 0:13:43

Partition equal subset sum | Equal sum partition | Dynamic Programming | Leetcode #416

Subset Sum Problem 0:29:56

Subset Sum Problem | O(Sum) with Solution Set | 🚀 Optimal Bottom Up way | DP Deep Dive 👨‍💻...

Reduction : 3-CNF 0:32:19

Reduction : 3-CNF SAT to Subset Sum

Minimum subset sum 0:16:34

Minimum subset sum difference | Minimum difference subsets | Dynamic Programming

Sum of Subset 0:07:37

Sum of Subset Problem Using Backtracking || Backtracking Algorithm || DAA

Subset Sum Problem: 0:14:36

Subset Sum Problem: Dynamic Programming | Data Structures And Algorithms

Subset Sum Problem 0:11:02

Subset Sum Problem using Memoization

Subset Sum Problem 0:17:21

Subset Sum Problem - Memoization | GeeksForGeeks

Subset Sum Problem 0:29:23

Subset Sum Problem (Dynamic Programming) Theory, Example and Implementation in Python

DP - 12: 0:25:15

DP - 12: Subset Sum Problem (If there exists a subset with sum equal to given sum)

Комментарии
Автор

Great video! Came to YouTube as my cs professor did not explain this 3 SAT -> subset sum reduction clearly. Your explanation was thorough and clear! Please continue to create great content like this, it would be greatly appreciated by CS students like me. Cheers!

xinrongwang
Автор

This was a very helpful explanation. The part after 13:00 was especially helpful explaining the purpose of the additional rows

welfarewagonrepairs
Автор

Very clear explanation - Thanks!
One Question:
What would we do, if we insist, that the numbers given as instance for the SUBST SUM problem are different to each other?

queenpost
Автор

The subset sum problem does not care about how the numbers are encoded.

The subset sum problem only cares that the numbers are in fact integers.

The encoding is completely irrelevant. It's the same problem regardless.

SmithnWesson
Автор

Also, what do you mean by there not being any carryovers?

confluenceking
Автор

when you say to read the numbers as decimal numbers, what do you mean by that?

confluenceking
Автор

you should get to the point faster in your vids, thanks.

AustinWang-ro
Автор

you really don't explain things well

liamtolkkinen