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

Digraphs and DAGs

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

Erik Demaine continues MIT's 6.1200J Mathematics for Computer Science with a lecture on directed graphs. He covers walks, cycles, and connectivity in digraphs before turning to Directed Acyclic Graphs, digraphs that contain no cycles. The session builds on earlier graph theory material in the course, formalizing definitions and working through the structural properties that distinguish DAGs from general digraphs, groundwork for later topics like topological sorting and scheduling problems. Demaine develops the ideas on the board in the standard MIT OCW lecture format, moving through definitions, examples, and proofs at a pace suited to students already familiar with basic graph terminology. Filmed as part of the Spring 2024 offering of 6.1200J, a core discrete mathematics course for MIT computer science students, the lecture runs just over an hour and is one installment in a full semester sequence available through MIT OpenCourseWare.

At a glance

Lecture facts

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

Mathematics for Computer Science

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 12 of 2214 h 45 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
State Machines

State Machines

MIT · 81 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
Relations and Counting

Relations and Counting

MIT · 79 MIN