Learn · Design and Analysis of Algorithms
Lecture 34 of 34Design and Analysis of Algorithms
Approximation Algorithms for NP
Prof. Abhiram G Ranade, Prof. Ajit A Diwan and Prof. Sundar Viswanathan · IIT Bombay
Credits and licence
- From
- Design and Analysis of Algorithms, IIT Bombay (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Overview of the course
- Framework for Algorithms Analysis
- Algorithms Analysis Framework - II
- Asymptotic Notations
- Algorithm Design Techniques : Basics
- Divide And Conquer-I
- Divide And Conquer -II Median Finding
- Divide And Conquer -III Surfing Lower Bounds
- Divide And Conquer -IV Closest Pair
- Greedy Algorithms -I
- Greedy Algorithms - II
- Greedy Algorithms - III
- Greedy Algorithms - IV
- Pattern Matching - I
- Pattern Matching - II
- Combinational Search and Optimization I
- Combinational Search and Optimization II
- Dynamic Programming
- Longest Common Subsequences
- Matrix Chain Multiplication
- Scheduling with Startup and Holding Costs
- Average case Analysis of Quicksort
- Bipartite Maximum Matching
- Lower Bounds for Sorting
- Element Distinctness Lower Bounds
- NP-Completeness-I -Motivation
- NP - Completeness - II
- NP-Completeness - III
- NP-Completeness - IV
- NP-Completeness - V
- NP-Completeness - VI
- Approximation Algorithms
- Approximation Algorithms
- Approximation Algorithms for NP