3 ms·
I had a very good algorithms professor. He studied at UCLA. His classes about dynamic programming were superb. He started with a problem for which the naive sol
by marcodiego 3y ago
I had a very good algorithms professor. He studied at UCLA. His classes about dynamic programming were superb. He started with a problem for which the naive solution was simple and had exponential complexity. Then he broke the problem into smaller problems and reduced the complexity to something polynomial. Then he applied memoisation and the complexity dropped to linear.
I really would like to remember the problems he used.
- Horffupolde 3y ago1. *Fibonacci Sequence*: The classic example where the naive recursive solution has exponential complexity. By storing previously computed values (memoization), the complexity can be reduced to linear. 2. *Coin Change Problem*: Given different denominations of coins and a total amount, finding the number of ways to make the change. The naive approach is exponential, but dynamic programming reduces it to polynomial complexity. 3. *Knapsack Problem*: Particularly the 0/1 Knapsack problem, where items with given weights and values must be placed in a knapsack of a fixed capacity to maximize total value. The naive exponential solution can be optimized using dynamic programming. 4. *Matrix Chain Multiplication*: Determining the most efficient way to multiply a chain of matrices. The problem can be solved in exponential time using a naive approach but becomes much more efficient with dynamic programming. 5. *Longest Common Subsequence*: Finding the longest subsequence common to two sequences. A classic dynamic programming problem that can be solved in polynomial time. 6. *Longest Increasing Subsequence*: Finding the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. 7. *Shortest Path Problems*: Like the Floyd-Warshall algorithm for finding the shortest paths in a weighted graph with positive or negative edge weights. 8. *Edit Distance (Levenshtein Distance)*: Finding the minimum number of edits (insertions, deletions, substitutions) needed to change one word into another.
- JohnKemeny 3y agoI just want to add 9. Longest Path in DAGs: Find a longest path in a directed acyclic graph. 10. Weighted Independent Set on a Path: Given an array of integers, compute the maximum sum of numbers provided that you may not take two consecutive cells.
- manvillej 3y agoI am a big fan of the Knight Dialer. I wrote an article on it and how you can actually use graph theory to reduce it to an incredibly efficient 4x4 matrix. was super fun.
- qsantos 3y agoI have listed a few in the article. It's pretty common to see them in lectures and practical exercices. - longest common subsequence - longest common substring - line warp - subset sum - partition - knapsack You can also have a look at [1] for more ideas. [1] https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms_that_use_dynamic_programming https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms...
- jakeinspace 3y agoIn addition to the suggested problems others posted, perhaps it was a scheduling problem? Like, for example, scheduling N overlapping events in time, like course schedules or processes for a CPU. Generally this would be done to optimize something like throughput - I believe that when you start adding special requirements, like "These 2 courses must be taken together", then things get much more complicated and intractable compared to plain-old dynamic programming.
- colordrops 3y agoDid he study under Kang at UCLA?
- marcodiego 3y agoI don't know, but I know he studied there in late 90's or early 2000's.
- colordrops 3y agoI did as well in the 90s - I studied algorithms, which included dynamic programming, with Kang, who was recognized as an amazing algorithms teacher.
- LargeTomato 3y agoMaybe Eggert? He's also the chief maintainer of emacs and Linux tzdata.