Skip to content
CampusPrep
AL-402 · Analysis & Design of Algorithms/Official Syllabus

Analysis & Design of Algorithms (AL-402) - 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
  • Code tuning techniques: Loop Optimization
  • Data Transfer Optimization
  • Logic Optimization
2
Unit 2

Study of Greedy strategy

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

Concept of dynamic programming

  • Concept of dynamic programming
  • 0/1 knapsack
  • multistage graph
  • reliability design
  • Floyd-Warshall algorithm
4
Unit 4

Backtracking concept and Branch & Bound

  • Backtracking concept
  • 8 queen’s problem
  • Hamiltonian cycle
  • Graph colouring problem
  • Introduction to branch & bound method
  • travelling salesman problem
  • 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

Laboratory Experiments

  • Write a program for Iterative and Recursive Binary Search.
  • Write a program for Merge Sort.
  • Write a program for Quick Sort.
  • Write a program for Strassen’s Matrix Multiplication.
  • Write a program for optimal merge patterns.
  • Write a program for Huffman coding.
  • Write a program for minimum spanning trees using Kruskal’s algorithm.
  • Write a program for minimum spanning trees using Prim’s algorithm.
  • Write a program for single sources shortest path algorithm.
  • Write a program for Floye-Warshal algorithm.
  • Write a program for traveling salesman problem.
  • Write a program for Hamiltonian cycle problem.

Reference Books

  • Introduction to Algorithms — Coremen Thomas, Leiserson CE, Rivest RL — PHI — Third edition
  • Analysis & Design of Algorithm — Horowitz, Sahani — Computer Science Press — Fourth Edition
  • algorithms — Dasgupta — TMH — Fifth Edition
  • Analysis & Design of Algorithm — Ullmann — Addison-wesley publishing company
  • Algorithm Design — Michael T Goodrich, RobartoTamassia — Wiely India
  • Analysis and Design of Algorithms: A Beginner's Approach — Rajesh K Shukla — Wiley
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