Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

# Design and analysis of algorithms

### Overview

COURSE OUTLINE: This course will cover basic concepts in the design and analysis of algorithms.Asymptotic complexity, O() notation Sorting and search.Algorithms on graphs: exploration, connectivity, shortest paths, directed acyclic graphs, spanning trees. Design techniques: divide and conquer, greedy, dynamic programming. Data structures: heaps, union of disjoint sets, search trees Intractability.

### Syllabus

Course Outline.
Example: Air Travel.
Example: Xerox shop.
Example: Document similarity.
Introduction and motivation.
Input size, worst case, average case.
Quantifying efficiency: O( ), Omega( ), Theta( ).
Examples: Analysis of iterative and recursive algorithms.
Arrays and lists.
Searching in an array.
Selection Sort.
Insertion sort.
Merge sort.
Merge sort - analysis.
Quicksort.
Quicksort - analysis.
Sorting - Concluding remarks.
Introduction to graphs.
Representing graphs.
Depth first search (DFS).
Applications of BFS and DFS.
Directed acylic graphs: topological sort.
Directed acylic graphs: longest paths.
Dijkstras algorithm: analysis.
Negative edge weights: Bellman-Ford algorithm.
All pairs shortest paths.
Minimum Cost Spanning Trees.
Prims Algorithm.
Kruskals algorithm.
Union-Find using arrays.
Union-Find using pointers.
Priority queues.
Heaps.
Heaps: Updating values, sorting.
Counting inversions.
Closest pair of points.
Binary Search Trees.
Balanced search trees.
Interval scheduling.
Huffman codes.
Introduction to dynamic programming.
Memoization.
Grid paths.
Common subwords and subsequences.
Edit distance.
Matrix multiplication.
Linear Programming.
LP modelling: Production Planning.
LP modelling: Bandwidth allocation.
Network Flows.
Reductions.
Checking Algorithms.
P and NP.
Single source shortest paths: Dijkstras algorithm.

NPTEL-NOC IITM

## Reviews

5.0 rating, based on 1 Class Central review

Start your review of Design and analysis of algorithms

• Jnanesh Rm
Design and analysis of algorithms. Its really helped me to again my extra knowledge. I came to know that how to design algorithms.finally tq u for this online cousres

### Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.