28-b DMC: Fast vs. Slow Turing Machines 🚀
Explores how multi-tape TM speed compares to single-tape TM and discusses polynomial time problems in P, based on Prof. Malik Magdon-Ismail's lecture.
M MI
102 views • Feb 12, 2021
About this video
Foundations of Computer Science, Rensselaer Fall 2020.
Professor Malik Magdon-Ismail talks about efficiency and discusses the problems in P (polynomial time) and NP (nondeterministic polynomial time). We demonstrate how polynomial time is a robust definition of "fast" because it is architecture independent. This is the last lecture. Enjoy your next course: Algorithms! Always take the time and effort to prove your program works fully correctly all the time, others rely on it.
This is the twenty-eighth lecture in a "theory" course focusing on discrete math and the foundations of computing: what can we compute and what can't we compute.
Level of the course: Sophomore Computer Science or related major.
Material is from Chapter 28 of "Discrete Mathematics and Computing", dmc-book.com.
Professor Malik Magdon-Ismail talks about efficiency and discusses the problems in P (polynomial time) and NP (nondeterministic polynomial time). We demonstrate how polynomial time is a robust definition of "fast" because it is architecture independent. This is the last lecture. Enjoy your next course: Algorithms! Always take the time and effort to prove your program works fully correctly all the time, others rely on it.
This is the twenty-eighth lecture in a "theory" course focusing on discrete math and the foundations of computing: what can we compute and what can't we compute.
Level of the course: Sophomore Computer Science or related major.
Material is from Chapter 28 of "Discrete Mathematics and Computing", dmc-book.com.
Video Information
Views
102
Likes
3
Duration
16:36
Published
Feb 12, 2021
Related Trending Topics
LIVE TRENDSRelated trending topics. Click any trend to explore more videos.