Play all

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

Breadth first search (BFS)

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

Scheduling with deadlines: minimizing lateness

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

Description:

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.

Design and Analysis of Algorithms

NPTEL

Add to list

#Computer Science #Algorithms and Data Structures #Mathematics #Linear Programming #Graph Theory #Algorithm Design #Algorithms #Sorting Algorithms #Searching Algorithms #Algorithm Analysis #Dynamic programming #Big O Notation

0:00 / 0:00