This video is part of Professor Frank Stajano’s lecture course on Algorithms at the University of Cambridge.
In a previous video we showed that the hall allocation problem exhibited optimal substructure and could be solved with dynamic programming. In this video we show how to solve it at a strictly lower asymptotic cost, using a greedy algorithm.
The greedy approach can be more economical but can also give incorrect results, unless we have developed a proof that the greedy choice will always take us to an optimal solution. We give another demonstration of this fact through variations on the knapsack problem.
If you find my lectures useful, give the videos a thumbs up. Subscribe and hit the notification bell for more of the same and to encourage me to publish more videos for budding computer scientists. Leave your comments below.
Course web page:
https://www.cl.cam.ac.uk/teaching/current/Algorithm1/
Course handout:
https://www.cl.cam.ac.uk/teaching/current/Algorithm1/2021-2022-stajano-algs1-handout.pdf
My home page:
http://frank.stajano.com
Add comment