X
X
X

X
Courses » Design and Analysis of Algorithms

Design and Analysis of Algorithms

ABOUT THE COURSE

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

INTENDED AUDIENCE

Students in BE/BTech Computer Science, 2nd/3rd year

PRE-REQUISITES

Exposure to introductory courses on programming and data structures.

INDUSTRY SUPPORT – LIST OF COMPANIES/INDUSTRY THAT WILL RECOGNIZE/VALUE THIS ONLINE COURSE

This course should be of value to any company working in the area of software services and products.

INTERNSHIP/JOB OPPORTUNITIES FOR TOP 5% OF THIS COURSE AT VuNet:

VuNet Systems( www.vunetsystems.com ) brings in a big data approach to manage the complex IT infrastructure of enterprises. With its powerful analytics and intuitive visualisations, it helps connect the 1000s of dots in an IT infrastructure to keep it always on and secure. VuNet has customers across verticals, from banks, manufacturing, consumer care to IT/ITES, with some leading retail payment companies as well.  VuNet has also been recognised among the NASSCOM Emerge50 innovative product startups and is also part of the Cisco Launchpad program - Cisco’s partnership program with top emerging startups.

We are always on the lookout for talented programmers and will interview the course toppers( top 5% ), who are interested in an internship/job opportunity. Upon completion of this course, the toppers can submit their resumes and programming code samples. VuNet will interview the candidates and offer internships or job opportunities based on the interview.

COURSE INSTRUCTOR




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 is President of both the Indian Association for Research in Computing Science (IARCS) and the ACM India Council. 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 Council. He has contributed lectures on algorithms to the Massively Empowered Classroom (MEC) project of Microsoft Research and the QEEE programme of MHRD.


MORE DETAILS ABOUT THE COURSE

Course url: https://onlinecourses.nptel.ac.in/noc17_cs09
Course duration : 08 weeks
Start date and end date of course: 23 January 2017 
- 17 March 2017
Date of exam: 26 March 2017

Time of exam : Shift 1 -9.00a.m -12.00 p.m ;Shift 2 -2.00p.m - 5.00p.m
Any one shift can be chosen for course. 
Final List of exam cities will be available in exam registration form.
Registration url: Announcements will be made when the registration form is open for registrations.
Exam Fee: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 from is published.

CERTIFICATE
Final score will be calculated as: 25% of assignment score + 75% of Final Exam score
25% assignment score is calculated as 25% of average of Best 6 out of 8 Assignments.
E-Certificate will be given to those who register and write the exam and score greater than or equal to 40% final score.
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
COURSE LAYOUT

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