This course covers the learning outcomes and goals of understanding time complexity in algorithms. Students will learn how to analyze algorithms based on their running time and input size, as well as measure and compare the efficiency of different algorithms. The course teaches skills such as analyzing running time, scaling run time, and understanding intrinsic complexity. The teaching method includes theoretical explanations, problem-solving sessions, and practical examples. The intended audience for this course includes computer science students, software developers, and anyone interested in algorithm analysis and efficiency.
Overview
Syllabus
Intro
Dammit I'm mad, by Demetri Martin
Suppose you are the proofreader. How would you check if there's a mistake?
Problems
Algorithms
Instance/input size
When instances are integers
When instances are lists/strings
When instances are graphs
Measuring running time
Running time example
Why worst case?
On input I, algorithm A takes 2718 steps
Run time scaling
Let's do a log-log plot Say 1 step = 1 us
Intrinsic complexity
PALINDROMES: We know an O(n) algorithm, TwoFingers. Could there be a faster one? E.g., O(n)?
MULTIPLICATION
Common progress paradigm for a problem
Does "polynomial time" imply "efficient"?
Definition recall(?)
Taught by
Ryan O'Donnell
