Design and Analysis of Algorithms-Understand the Design and Analysis of Algorithms

Understand the Design and Analysis of Algorithms

Design and Analysis of Algorithms

Understand the Design and Analysis of Algorithms

A brief summary

Programming is a very complex task, and there are a number of aspects of programming that make it so complex. The first is that most programming projects are very large, requiring the coordinated efforts of many people.  The next is that many programming projects involve storing and accessing large quantities of data efficiently. The last is that many programming projects involve solving complex computational problems, for which simplistic or naive solutions may not be efficient enough. The complex problems may involve numerical data, but often they involve discrete data. This is where the topic of algorithm design and analysis is important.

Instructor:

NPTEL

What you will learn

  • 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


Course Fee: Free

Certification By: Not Certified

Understanding Algorithms

Understanding Algorithms, Searching and Sorting

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 pathsSingle source shortest paths: Dijkstras algorithm, Dijkstras algorithm: analysis, Negative edge weights: Bellman-Ford algorithm, All pairs shortest paths, Minimum Cost Spanning Trees, Prims Algorithm, Kruskals algorithm

Data Structures -Union- Find and Heaps,Divide and Conquer

Union-Find using arrays, Union-Find using pointers, Priority queues, Heaps, Heaps: Updating values, sorting, Counting inversions, Closest pair of points

Search Trees and Greedy Algorithms

Binary Search Trees, Balanced search trees, Interval scheduling, Scheduling with deadlines: minimizing lateness, Huffman codes

Dynamic Programming, Linear Programming and Network Flows, Intractability

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

Back to top