Skip to content
CampusPrep
IT-403 · Analysis and Design of Algorithm/Official Syllabus

Analysis and Design of Algorithm (IT-403) - Official Syllabus

1
Unit 1

Algorithms

  • Algorithms
  • Designing algorithms
  • analyzing algorithms
  • asymptotic notations
  • heap and heap sort
  • Introduction to divide and conquer technique
  • analysis, design and comparison of various algorithms based on this technique
  • example binary search
  • merge sort
  • quick sort
  • strassen’s matrix multiplication
2
Unit 2

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
3
Unit 3

Dynamic programming

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

Backtracking and Branch & Bound

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

Trees and NP-completeness

  • Binary search trees
  • height balanced trees
  • 2-3 trees
  • B-trees
  • basic search and traversal techniques for trees and graphs (In order, preorder, postorder, DFS, BFS)
  • NP-completeness

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
  • Analysis & Design of Algorithm — Horowitz, Sahani
  • algorithms — Dasgupta — TMH
  • Analysis & Design of Algorithm — Ullmann
  • Algorithm Design — Michael T Goodrich, Robarto Tamassia — Wiely India
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