Scribd
Upload
21 views1 page

Design and Analysis of Algorithms

The document outlines the course details for CSN-212: Design and Analysis of Algorithms at the Indian Institute of Technology Roorkee. It includes information on contact hours, examination duration, course objectives, prerequisites, and a detailed breakdown of course contents and topics covered. The course aims to familiarize students with various algorithm design strategies and performance analysis.

Uploaded by

singh.nitrr.ik
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
21 views1 page

Design and Analysis of Algorithms

The document outlines the course details for CSN-212: Design and Analysis of Algorithms at the Indian Institute of Technology Roorkee. It includes information on contact hours, examination duration, course objectives, prerequisites, and a detailed breakdown of course contents and topics covered. The course aims to familiarize students with various algorithm design strategies and performance analysis.

Uploaded by

singh.nitrr.ik
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

INDIAN INSTITUTE OF TECHNOLOGY ROORKEE

NAME OF DEPT./CENTRE: Department of Computer Science and Engineering

1. Subject Code: CSN-212 Course Title: Design and Analysis of Algorithms

2. Contact Hours: L: 3 T: 1 P: 0

3. Examination Duration (Hrs.): Theory:3 Practical:0

4. Relative Weight: CWS:25 PRS:0 MTE:25 ETE:5 PRE:0

5. Credits:4 6. Semester : Spring 7. Subject Area: DCC

8. Pre-requisite: CSn-102

9. Objective: To familiarize students with the design strategies and bounds on the performance of
different computer algorithms.

10. Details of the Course:

Sl. No. Contents Contact Hours


1. Review of Data Structures. 2
2. Program P erformance: T ime and space c omplexity, 4
asymptotic not ation, c omplexity a nalysis, r ecurrence e quations
and their solution.
3. Algorithmic T echniques: A lgorithm de sign strategies, divide 14
and c onquer, m erge s ort, qui ck s ort a nd i ts pe rformance
analysis, randomized qui ck s ort, S trassen’s m atrix
multiplication; G reedy method a nd i ts a pplications, kna psack
problem; D ynamic pr ogramming and i ts pe rformance a nalysis,
optimal bi nary s earch t rees, 0/ 1 kna psack pr oblem; T raveling
salesman problem; Back-tracking, n-queens pr oblem, gr aph
coloring, Hamiltonian c ycles, kna psack pr oblem; B ranch a nd
bound e xamples, 15 -puzzle pr oblem, 0/ 1 kna psack, t raveling
salesman.
4. Graph A lgorithms: D FS a nd B FS, s panning t rees, 6
biconnectivity; Minimum cost spanning trees: Kruskal’s, Prim’s
and S ollin’s a lgorithms; P ath f inding a nd shortest pa th
algorithms; Topological sorting; Bipartite graphs.
5. Infeasibility: P and NP-classes, NP-hard problems, reduction. 4
6. Parallel A lgorithms: D ata a nd c ontrol pa rallelism, e mbedding 6
of problem graphs into processor graphs, parallel algorithms for
matrix multiplication.
7. Other Algorithms: N umber the oretic a lgorithms, string 6
matching a lgorithms, a pproximation a lgorithms, r andomized
algorithms.
Total 42

You might also like