Design and analysis of algorithms

By Prof. Madhavan Mukund   |   Chennai Mathematical Institute
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

: Students in BE/BTech Computer Science, 2nd/3rd year.
PRE-REQUISITES: Exposure to introductory courses on programming and data structures.
INDUSTRY SUPPORT: This course should be of value to any company working in the area of software services and products.

Learners enrolled: 10069


Course Status : Ongoing
Course Type : Elective
Duration : 8 weeks
Start Date : 14 Sep 2020
End Date : 06 Nov 2020
Exam Date : 20 Dec 2020
Enrollment Ends : 25 Sep 2020
Category :
  • Computer Science and Engineering
  • Foundations of Computing
  • Level : Undergraduate
    This is an AICTE approved FDP course


    Week 1
    Module 1: Introduction
    Module 2: Examples and motivation
    Module 3: Examples and motivation

    Module 4: Asymptotic complexity: informal concepts
    Module 5: Asymptotic complexity: formal notation
    Module 6: Asymptotic complexity: examples
    Assignments MCQ/Fill in blanks (unique answer)

    Week 2
    Module 1: Searching in list: binary search
    Module 2: Sorting: insertion sort
    Module 3: Sorting: selection sort
    Module 4: Sorting: merge sort
    Module 5: Sorting: quicksort
    Module 6: Sorting: stability and other issues
    Assignments MCQ/Fill in blanks, programming assignment

    Week 3
    Module 1: Graphs: Motivation
    Module 2: Graph exploration: BFS
    Module 3: Graph exploration: DFS
    Module 4: DFS numbering and applications
    Module 5: Directed acyclic graphs
    Module 6: Directed acyclic graphs
    Assignments MCQ/Fill in blanks, programming assignment

    Week 4
    Module 1: Shortest paths: unweighted and weighted
    Module 2: Single source shortest paths: Dijkstra
    Module 3: Single source shortest paths: Dijkstra
    Module 4: Minimum cost spanning trees: Prim’s algorithm
    Module 5: Minimum cost spanning trees: Kruskal’s Algorithm
    Module 6: Union-Find data structure
    Assignments MCQ/Fill in blanks, programming assignment

    Week 5
    Module 1: Divide and conquer: counting inversions
    Module 2: Divide and conquer: nearest pair of points
    Module 3: Priority queues, heaps
    Module 4: Priority queues, heaps
    Module 5: Dijstra/Prims revisited using heaps
    Module 6: Search Trees: Introduction
    Assignments MCQ/Fill in blanks, programming assignment

    Week 6
    Module 1: Search Trees: Traversals, insertions, deletions
    Module 2: Search Trees: Balancing
    Module 3: Greedy : Interval scheduling
    Module 4: Greedy : Proof strategies
    Module 5: Greedy : Huffman coding
    Module 6: Dynamic Programming: weighted interval scheduling
    Assignments MCQ/Fill in blanks, programming assignment

    Week 7
    Module 1: Dynamic Programming: memoization
    Module 2: Dynamic Programming: edit distance
    Module 3: Dynamic Programming: longest ascending subsequence
    Module 4: Dynamic Programming: matrix multiplication
    Module 5: Dynamic Programming: shortest paths: Bellman Ford
    Module 6: Dynamic Programming: shortest paths: Floyd Warshall
    Assignments MCQ/Fill in blanks, programming assignment

    Week 8
    Module 1: Intractability: NP completeness
    Module 2: Intractability: reductions
    Module 3: Intractability: examples
    Module 4: Intractability: more examples
    Module 5: Misc topics
    Module 6: Misc topics
    Assignments MCQ/Fill in blanks




    Prof. Madhavan Mukund

    Chennai Mathematical Institute
    Madhavan Mukund studied at IIT Bombay (BTech) and Aarhus University (PhD). He has been a faculty member at Chennai Mathematical Institute since 1992, where he is presently Professor and Dean of Studies. His main research area is formal verification. He has active research collaborations within and outside India and serves on international conference programme committees and editorial boards of journals.

    He has served as President of both the Indian Association for Research in Computing Science (IARCS) (2011-2017) and the ACM India Council (2016-2018). He has been the National Coordinator of the Indian Computing Olympiad since 2002. He served as the Executive Director of the International Olympiad in Informatics from 2011-2014.

    In addition to the NPTEL MOOC programme, he has been involved in organizing IARCS Instructional Courses for college teachers. He is a member of ACM India's Education Committee. He has contributed lectures on algorithms to the Massively Empowered Classroom (MEC) project of Microsoft Research and the QEEE programme of MHRD.


    The course is free to enroll and learn from. But if you want a certificate, you have to register and write the proctored exam conducted by us in person at any of the designated exam centres.
    The exam is optional for a fee of Rs 1000/- (Rupees one thousand only).
    Date and Time of Exams: 20 December 2020 Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
    Registration url: Announcements will be made when the registration form is open for registrations.
    The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published. If there are any changes, it will be mentioned then.
    Please check the form for more details on the cities where the exams will be held, the conditions you agree to when you fill the form etc.


    Average assignment score = 25% of average of best 6 assignments out of the total 8 assignments given in the course.
    Exam score = 75% of the proctored certification exam score out of 100

    ( All assignments in a particular week will be counted towards final scoring - quizzes and programming assignments). 

    Final score = Average assignment score + Exam score

    YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.

    Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IIT Madras .It will be e-verifiable at nptel.ac.in/noc.

    Only the e-certificate will be made available. Hard copies will not be dispatched.

    Once again, thanks for your interest in our online courses and certification. Happy learning.

    - NPTEL team