Srini Devadas
Edwin Sibley Webster Professor of Electrical Engineering… · MIT · Distinguished
Srini Devadas is the Edwin Sibley Webster Professor of Electrical Engineering and Computer Science at MIT, known for physical unclonable functions.
- lectures
- 25
- series
- 2
- hours
- 28
Start here
Series and courses
MIT 6.046J: Design and Analysis of Algorithms
Open the course
- 1Course Overview, Interval Scheduling
- 2Divide & Conquer: Convex Hull, Median Finding
- 3Divide & Conquer: FFT
- 4R2. 2-3 Trees and B-Trees
Show 11 moreShow fewer
- 5Divide & Conquer: Van Emde Boas Trees
- 6Amortization: Amortized Analysis
- 7Randomization: Matrix Multiply, Quicksort
- 8Randomization: Skip Lists
- 11Dynamic Programming: Advanced DP
- 15Incremental Improvement: Max Flow, Min Cut
- 16Incremental Improvement: Matching
- 17Linear Programming: LP, Reductions, Simplex
- 19Complexity: Approximation Algorithms
- 24Cryptography: Hash Functions
- 25Cryptography: Encryption
MIT 6.006: Introduction to Algorithms
In these lectures
- Small changes in problem constraints can shift an algorithm from polynomial-time tractability to NP-completeness.Course Overview, Interval Scheduling
- Polynomial multiplication is equivalent to vector convolution and can be solved in time using the Fast Fourier Transform.Divide & Conquer: FFT
- Asymptotic complexity provides a way to evaluate how algorithms scale with large inputs compared to naive linear approaches.Algorithmic Thinking & Peak Finding in 1D and 2D
Draws on
People cited in the lectures, at the moment of the citation.
- Eric DemaineCo-lecturer for 6.006
- Mick DavisA student who provided a counterexample to the lecturer's greedy algorithm hypothesis.
- Alexander MadryResearcher who developed a variant max flow algorithm.
- William PughInventor of the skiplist in 1989.
- Peter van Emde BoasInventor of the data structure discussed in the 1970s.
- Arnold SchönhageSchönhage-Strassen algorithm co-author.
Playlists
1About
Srini Devadas is the Edwin Sibley Webster Professor of Electrical Engineering and Computer Science at MIT, known for physical unclonable functions. His MIT 6.006 and 6.046J algorithms lectures prove the Max-Flow Min-Cut Theorem and analyze Dijkstra, Bellman-Ford, skip lists and Karatsuba multiplication.
Taught with
Same subject, Algorithms & Theoretical CS
Connections
32Their places, courses, books and lectures.
Scholar1
Institutions2
Concept1
Lectures25
- Course Overview, Interval Scheduling
- Divide & Conquer: FFT
- Algorithmic Thinking & Peak Finding in 1D and 2D
- Randomization: Matrix Multiply, Quicksort
- Amortization: Amortized Analysis
- Dynamic Programming: Advanced DP
Show 19 moreShow fewer
- Linear Programming: LP, Reductions, Simplex
- Incremental Improvement: Matching
- Incremental Improvement: Max Flow, Min Cut
- Divide & Conquer: Convex Hull, Median Finding
- Randomization: Skip Lists
- Divide & Conquer: Van Emde Boas Trees
- Integer Arithmetic, Karatsuba Multiplication
- R2. 2-3 Trees and B-Trees
- Open Addressing, Cryptographic Hashing
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- Square Roots, Newton's Method
- Priority Queues, Binary Heaps & O(n) Build-Max-Heap
- Bellman-Ford
- Complexity: Approximation Algorithms
- Cryptography: Encryption
- Cryptography: Hash Functions
- Single-Source Shortest Paths Problem
- Insertion Sort, Binary Insertion & Merge Sort Recurrences
- Speeding up Dijkstra





