Skip to content
CampusPrep
CY-502 · Design& Analysis of Algorithms/Official Syllabus

Design& Analysis of Algorithms (CY-502) - Official Syllabus

1
Unit 1

Definitions of algorithms and complexity

  • Definitions of algorithms and complexity
  • Time and Space Complexity
  • Time space tradeoff
  • various bounds on complexity
  • Asymptotic notation
  • Recurrences and Recurrences solving techniques
  • Introduction to divide and conquer technique
  • binary search
  • merge sort
  • quick sort
  • heap sort
  • strassen’s matrix multiplication etc
  • Code tuning techniques: Loop Optimization
  • Data Transfer Optimization
  • Logic Optimization
2
Unit 2

Greedy Algorithms

  • Greedy Algorithms: strategy
  • optimal merge patterns
  • Huffman coding
  • minimum spanning trees
  • knapsack problem
  • job sequencing with deadlines
  • single source shortest path algorithm etc
  • Correctness proof of Greedy algorithms
3
Unit 3

Dynamic programming

  • Dynamic programming: characteristics
  • 0/1 knapsack
  • multistage graph
  • reliability design
  • Floyd-Warshall algorithm etc
4
Unit 4

Backtracking

  • Backtracking: concept and its examples like 8 queen’s problem
  • Hamiltonian cycle
  • Graph colouring problem etc
  • Introduction to branch & bound method
  • examples of branch and bound method like travelling salesman problem etc
  • Meaning of lower bound theory and its use in solving algebraic problem
  • introduction to parallel algorithms
5
Unit 5

Advanced tree and graph algorithms

  • Advanced tree and graph algorithms
  • NP-hard and NP-complete problems
  • Approximations Algorithms
  • Data Stream Algorithms
  • Introduction to design and complexity of Parallel Algorithms

Reference Books

  • Introduction to Algorithms — Cormen, Leiserson, Rivest, Stein — Prentice Hall of India — Second Edition
  • Design and Analysis of Computer Algorithms — Aho A.V., Hopcroft J.E., J. Ullman — Addison Wesley
  • Fundamentals of Computer Algorithms — Horowitz E., Sahani — Galgotia Publications
  • Fundamental algorithms: The Art of Computer programming, Volume – I — Knuth D. — Pearson Education
  • Sorting and Searching: The Art of Computer programming, Volume – III — Knuth D. — Pearson Education
  • Algorithm Design — John Kleinberg, Trades E. — Pearson Education
  • Probability, Random Variables and Stochastic Processes — A. Papoulis, S.U. Pillai — McGraw Hill
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in