LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
State Machines
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

State Machines

81 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
MIT · Mathematics for Computer Science · LECTURE 4

Erik Demaine introduces state machines as a tool for modeling how algorithms behave, part of MIT's 6.1200J Mathematics for Computer Science. The lecture defines the components of a state machine (states, start states, and transitions) and shows how to represent stepwise processes abstractly. Demaine then connects this new abstraction to induction, demonstrating how to prove invariant properties that hold across every reachable state of a machine. Examples work through how an algorithm's behavior can be tracked state by state, and how inductive proofs establish that certain properties persist no matter how many transitions occur. The session builds on earlier proof techniques from the course and sets up state machines as a recurring tool for later topics in discrete mathematics and computer science. Eighty-one minutes of blackboard-style instruction aimed at students already familiar with basic induction and proof writing.

At a glance

Lecture facts

Runtime compared with the other 507 Mathematics lectures
Runtime1 h 21 m
Compared with MathematicsLonger than 81%
This series

Mathematics for Computer Science

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 3 of 222 h 39 m before this · 29 h 3 m in total

More from this course

12 LECTURES
Predicates, Sets, and Proofs

Predicates, Sets, and Proofs

MIT · 79 MIN
Contradiction and Induction

Contradiction and Induction

MIT · 80 MIN
Lecture 5: Sums

Lecture 5: Sums

MIT · 82 MIN
Lecture 6: Asymptotics

Lecture 6: Asymptotics

MIT · 78 MIN
Divisibility

Divisibility

MIT · 79 MIN
Modular Arithmetic

Modular Arithmetic

MIT · 80 MIN
Lecture 10: Cryptography

Lecture 10: Cryptography

MIT · 81 MIN
Graphs and Coloring

Graphs and Coloring

MIT · 81 MIN
Lecture 12: Matching

Lecture 12: Matching

MIT · 82 MIN
Lecture 13: Connectivity and Trees

Lecture 13: Connectivity and Trees

MIT · 82 MIN
Digraphs and DAGs

Digraphs and DAGs

MIT · 79 MIN
Relations and Counting

Relations and Counting

MIT · 79 MIN