Scribd
Upload
61 views8 pages

Week1 Module1 Introduction

This document provides an overview of an online course on algorithms offered in January-February 2015. It covers topics like asymptotic complexity, searching and sorting algorithms, graph algorithms, algorithm design techniques like divide-and-conquer and dynamic programming, and data structures like heaps and search trees. Students will be evaluated through weekly quizzes, programming assignments, and a certification exam. The course requires background in programming and basic data structures.

Uploaded by

Sandeep Mishra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
61 views8 pages

Week1 Module1 Introduction

This document provides an overview of an online course on algorithms offered in January-February 2015. It covers topics like asymptotic complexity, searching and sorting algorithms, graph algorithms, algorithm design techniques like divide-and-conquer and dynamic programming, and data structures like heaps and search trees. Students will be evaluated through weekly quizzes, programming assignments, and a certification exam. The course requires background in programming and basic data structures.

Uploaded by

Sandeep Mishra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

NPTEL MOOC,JAN-FEB 2015

Week 1, Module 1

DESIGN AND ANALYSIS


OF ALGORITHMS

MADHAVAN MUKUND, CHENNAI MATHEMATICAL INSTITUTE


http://www.cmi.ac.in/~madhavan
Understanding Algorithms
Correctness

Eciency

Asymptotic complexity, O( ) notation

Modelling

Graphs, data structures, decomposing the problem

Techniques

Divide and conquer, greedy, dynamic programming


Expectations

Background in programming

Any language (C, C++, Java)

Basic data structures

Arrays, lists
Topics to be covered
Asymptotic complexity

Searching and sorting in arrays

Binary search, insertion sort, selection sort, merge


sort, quick sort

Graphs and graph algorithms

Representations, reachability, connectedness

Directed acyclic graphs

Shortest paths, Spanning trees


Topics to be covered
Algorithmic design techniques

Divide and conquer, Greedy algorithms,


Dynamic programming

Data structures

Priority queues/heaps, Search trees,


Union of disjoint sets (union-find)

Miscellaneous topics

Intractability,
Tentative schedule January

Week 1: Motivation, asymptotic complexity


4 5 6 7 8 9 10

Week 2: Searching and sorting


11 12 13 14 15 16 17

18 19 20 21 22 23 24
Week 3: Graphs and basic graph algorithms

25 26 27 28 29 30 31
Week 4: More graph algorithms, disjoint set

February
Week 5: Divide and conquer, heaps
1 2 3 4 5 6 7

Week 6: Search trees, greedy algorithms


8 9 10 11 12 13 14

Week 7: Dynamic programming


15 16 17 18 19 20 21

Week 8: Miscellaneous topics 22 23 24 25 26 27 28


Evaluation
Continuous evaluation

8 Weekly quizzes

6 programming assignments

Certification exam

Requirement for successful course completion

60% in quizzes, certification exam

Submit at least 5 of 6 assignments

At least 4 with nonzero marks


Textbooks

Algorithm Design

Jon Kleinberg and Eva Tardos

Algorithms

Sanjoy Dasgupta, Christos Papadimitriou and


Umesh Vazirani

You might also like