YoVDO

Catalytic Approaches to the Tree Evaluation Problem

Offered By: Association for Computing Machinery (ACM) via YouTube

Tags

Theoretical Computer Science Courses Algorithmic Problem Solving Courses

Course Description

Overview

Explore the Tree Evaluation Problem (TEP) and its catalytic approaches in this 26-minute ACM conference talk. Delve into the pebbling game introduced by Paterson and Hewitt in 1970, and understand the concept of catalytic space. Learn about a key lemma involving multiplication and discover a formula for TEP. Examine the first attempt at solving this problem and gain insights into computational complexity theory.

Syllabus

Intro
Outline
The Tree Evaluation Problem (TEP)
Pebbling game Paterson Hewitt 1970
Catalytic space
Lemma: Multiplication
A formula for TEP
First attempt


Taught by

Association for Computing Machinery (ACM)

Related Courses

Intro to Theoretical Computer Science
Udacity
Power and elegance of computational thinking
The University of Oklahoma via Janux
Comparing Genes, Proteins, and Genomes (Bioinformatics III)
University of California, San Diego via Coursera
Algoritmi quotidiani
University of Urbino via EMMA
Competitive Programmer's Core Skills
Saint Petersburg State University via Coursera