Computational Complexity in Theory and in Practice by Richard M. Karp
Offered By: International Centre for Theoretical Sciences via YouTube
Course Description
Overview
Explore the contrasting approaches to algorithm efficiency in theoretical computer science and practical computing in this 1-hour 17-minute distinguished lecture by Professor Emeritus Richard M. Karp. Delve into theoretical concepts such as complexity classes P and NP, NP-completeness, approximation algorithms, and hardness of approximation. Examine practical applications including satisfiability solvers, linear and integer programming, the traveling salesman problem, deep learning algorithms, and game-playing programs based on reinforcement learning. Gain insights into the metrics used for evaluating algorithms in both theoretical and practical contexts, comparing worst-case performance analysis with empirical performance evaluation.
Syllabus
Computational Complexity in Theory and in Practice by Richard M. Karp
Taught by
International Centre for Theoretical Sciences
Related Courses
Algorithms: Design and Analysis, Part 2Stanford University via Coursera Intro to Theoretical Computer Science
Udacity 算法设计与分析(高级) | Advanced Design and Analysis of Algorithms
Peking University via edX Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Stanford University via Coursera Algorithm Design and Analysis
University of Pennsylvania via edX