Scribd
Upload
291 views3 pages

Analysis and Design of Algorithms1

This document outlines the objectives, syllabus, and resources for a course on Analysis and Design of Algorithms. The course is designed to teach students how to analyze the time complexity of algorithms, solve recurrence relations, and apply major algorithm design techniques like greedy algorithms, dynamic programming, and graph algorithms. The syllabus covers 8 units ranging from basic concepts like asymptotic analysis to advanced topics like approximation algorithms and branch and bound. Students will learn techniques like depth-first search, minimum spanning trees, and NP-completeness. The course is coordinated by Shashi Bhushan and provides reference books, lecture notes, videos, and assignments to support student learning.

Uploaded by

Harendra Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
291 views3 pages

Analysis and Design of Algorithms1

This document outlines the objectives, syllabus, and resources for a course on Analysis and Design of Algorithms. The course is designed to teach students how to analyze the time complexity of algorithms, solve recurrence relations, and apply major algorithm design techniques like greedy algorithms, dynamic programming, and graph algorithms. The syllabus covers 8 units ranging from basic concepts like asymptotic analysis to advanced topics like approximation algorithms and branch and bound. Students will learn techniques like depth-first search, minimum spanning trees, and NP-completeness. The course is coordinated by Shashi Bhushan and provides reference books, lecture notes, videos, and assignments to support student learning.

Uploaded by

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

Analysis and Design of Algorithm

Credits: 4 Credits

Course Coordinator: Shashi Bhushan

OBJECTIVES
Objectives of the course is to
Design time complexity (best case, worst case and average case) of
algorithm.
Solve recurrence relation through substitution method, Recursion tree and
Master methods
Discuss graph transal techniques such as DFS, BFS, and directed graph
concepts including strong connectivity and topological sorting

Cover major algorithm design techniques; greedy algorithm, divide and


conger dynamic programming and examine different kinds of application

SYLLABUS
(Basic Concepts)
Unit-1: Introduction

Algorithm
Analyzing an Algorithm
o Binary Search
o Insertion Sort
Asymptotic Notations (,, and )
Growth of function
o Example of Merge sort & Quick sort
Solving Recurrences
o Substitution Method
o Recursion Tree Method
o Master Method.

(Algorithm Design Techniques)


Unit-2 Graph Algorithms
o Representation of Graph
o Depth-First-Search and Breadth First Search (Directed & Undirected
Both)
o Topological Sorting
o Connected component & Strongly connected component
o Testing Bi-partite graph.
Unit-3 Divide & Conquer
o V Stressens Matrix Multiplication
o Closests pair of points
Unit- 4 Greedy Techniques
o Minimum spanning tree
Kruskals Algorithm
Prims Algorithm
o Implementation of Kruskals algorithm
Disjoint Set
o Implementation of Prims algorithm
Heaps
o Single Source Sorted path
Dijkstras Algorithm
o Scheduling Algorithms
An activity selection problem

Unit- 5 Dynaminc programming


o All pair shortest path problem
Floyed & Warshalls Algorithms
Solving 0/1 Knapsack problem
Weighted Interval Scheduling
Unit-6 NP Completeness
o Class of problems: P, NP
o Concept of problem reduction
o NP Hard, NP Complete
Vertex Cover to Independent set problem
Independent set to CLIQUE Problem
Three conjunctive normal form (satisfiability problems)
Sum-of-Subset to 0/1 Knapsack Problem

(Advanced Topics)
Unit-7 Approximation Algorithm
o Vertex cover
o Scaling Algorithm for Knapsack problem
Unit-8 Backtracking
o N-Queens Problem
o Sum of Subsets
Unit-9 Branch & Bound
o Graph Coloring problem
o Travelling salesman problem

REFERENCE BOOKS:
References:
1. Kleinberg and Tardos, Algorithm Design, Pearson.
2. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C.Stein, Introduction to
Algorithms
3. Sara Baase and Allen Van Gelder, Computer Algorithms Introduction to
Design and Analysis, Pearson Education.
4. A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of
Computer Algorithms, Pearson Education, 2003.
5. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Fundamental of
computer Algorithms, Orient Longman, 2006.

REFERENCE COURSE MATERIAL/Lectures Notes

WEBSITE REFERENCES

RELEVANT VIDEOS

ASSIGNMENTS

HANDOUTS / SLIDES USED FOR THE PRESENTATIONS

NEWS / ANNOUNCEMENTS

JOURNAL ARTICLES

EMAIL: [email protected]
137, School of Computer and Information
Sciences (SOCIS),
C-Block, First Floor, IGNOU Academic
Complex,IGNOU,
Maidangarhi, New Delhi 110068. Tel: +91-

You might also like