Undergrad Complexity at CMU - Savitch's Theorem and NL
Offered By: Ryan O'Donnell via YouTube
Course Description
Overview
Explore Savitch's Theorem and NL in this undergraduate Computational Complexity Theory lecture from Carnegie Mellon University's Course 15-455. Delve into topics such as pseudocode, space complexity, recursion, and NL codecorrectness. Learn from Professor Ryan O'Donnell as he covers the remaining portions of Sipser Ch. 8.1 and 8.4. Gain valuable insights into this fundamental theorem and its implications for nondeterministic logarithmic space complexity.
Syllabus
Introduction
Savitchs Theorem
Pseudocode
Space Complexity
Recursion
NL
Code
correctness
Taught by
Ryan O'Donnell
Related Courses
数据结构与算法第二部分 | Data Structures and Algorithms Part 2Peking University via edX Computational Complexity Theory
Indian Institute of Technology Kanpur via Swayam The Complete Data Structures and Algorithms Course in Python
Udemy Computational Complexity
IIT Hyderabad via Swayam Introduction to Algorithms Course (How To)
Treehouse