Engineering Tutorials

CSE -305 E Analysis and Design of Algorithms

Class Work: 50
Exam: 100

Unit-1: Brief Review of Graphs, Sets and disjoint sets, union, sorting and searching algorithms and their analysis in terms of space and time complexity.

Unit-2: Divide and Conquer: General method, binary search, merge sort, qick sort, selection sort, Strassen’s matrix multiplication algorithms and analysis of algorithms for these problems.

Unit-3: Greedy Method: General method, knapsack problem, job sequencing with dead lines, minimum spanning trees, single souce paths and analysis of these problems.

Unit-4: Dynamic Programming: General method, optimal binary search trees, O/I knapsack, the traveling salesperson problem.

Unit-5: Back Tracking: General method, 8 queen’s problem, graph colouring, Hamiltonian cycles, analysis of these problems.

Unit-6: Branch and Bound: Method, O/I knapsack and traveling salesperson problem, efficiency considerations. Techniques for algebraic problems, some lower bounds on parallel computations.

Unit-7: NP Hard and NP Complete Problems: Basic concepts, Cook’s theorem, NP hard graph and NP scheduling problems some simplified NP hard problems.

Text Books:

• Fundamental of Computer algorithms, Ellis Horowitz and Sartaj Sahni, 1978, Galgotia Publ.,
• Introduction To Algorithms, Thomas H Cormen, Charles E Leiserson And Ronald L Rivest: 1990, TMH

Reference Books:

• The Design and Analysis of Computer Algorithm, Aho A.V. Hopcroft J.E., 1974, Addison Wesley.
• Algorithms-The Construction, Proof and Analysis of Programs, Berlion, P.Bizard, P., 1986.

Johan Wiley & Sons,

• Writing Efficient Programs, Bentley, J.L., PHI
• Introduction to Design and Analysis of Algorithm, Goodman, S.E. & Hedetnieni, 1997, MGH.
• Introduction to Computers Science- An algorithms approach , Jean Paul Trembley, Richard B.Bunt, 2002, T.M.H.
• Fundamentals of Algorithms: The Art of Computer Programming Voll, Knuth, D.E.:

1985, Naresh Publ.

Note: Eight questions will be set in all by the examiners taking at least one question from each unit. Students will be required to attempt five questions in all.

Related posts:

1. PTU Syllabus | CS – 307 DESIGN AND ANALYSIS OF ALGORITHMS
2. CSE-201 E Data Structures & Algorithms
3. CSE-205 E Data Structures & Algorithms Lab.
4. EE– 462-E GENETIC ALGORITHMS & APPLICATIONS
5. MDU Syllabus | F-Scheme | CSE-201 F Data Structures Using ‘C’