ConceptTheory & Algos
Approximation algorithm
Algorithms that run in polynomial time and find solutions that are guaranteed to be close to the optimal or satisfy a large fraction of constraints rather than being exact.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
NP-hardness3Optimization3Polynomial time3Guess and check2Optimization problems2While loop2Algorithm complexity1Constraint satisfaction problem1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
6Each in their own terms, from the easiest level.
Ana Bell
An algorithm that finds an acceptable solution within a certain tolerance (epsilon) rather than an exact equality.Ryan O'Donnell
An efficient algorithm that guarantees finding an assignment of at least a certain value when the optimal assignment meets a threshold.Erik Demaine & Srini Devadas
Algorithms that can get us within a certain fraction of optimal and run in polynomial time for optimization problems.Brian Yu
Algorithms that try to find a good solution even if they cannot guarantee finding the globally best solution in a feasible amount of time.Srini Devadas
An algorithm for a problem of size n that finds near-optimal solutions when finding exact optimal solutions is intractable.Amartya Shankha Biswas
An algorithm that guarantees a solution within a constant factor of the optimal value.
Lectures that assume it
4Connections
22The lectures that define it or assume it, and the concepts next to it.