Sinhgad Technical Education Society’s
SINHGAD COLLEGE OF ENGINEERING, PUNE
Department of Information Technology
Assignments
Class: T.E. I. T. Subject: Design and Analysis of Algorithm
ASSIGNMENT NO: - 01
Unit I: INTRODUCTION
Question Course
Question
No. Outcome
1 What is contradiction?
Explain following terms in detail.
2 a. Mathematical Induction
b. Masters Theorem and substitution method CO1
3 Explain different asymptotic notations?
4 Explain Brute force method in detail.
5 Explain term “Analysis of Algorithm” in detail.
Sinhgad Technical Education Society’s
SINHGAD COLLEGE OF ENGINEERING, PUNE
Department of Information Technology
Assignments
Class: T.E. I. T. Subject: Design and Analysis of Algorithm
ASSIGNMENT NO: - 02
Unit II: DIVIDE AND CONQUER AND GREEDY METHOD
Question Course
Question
No. Outcome
1 Explain Divide & Conquer method in detail with example.
2 Explain Greedy method and its characteristics.
3 Explain terms Quick sort with example. CO1,
CO2
4 What is Binary search? Explain with example.
Explain following terms with example
5
i) Worst case ii) Best Case iii) Average case
6 Explain Kruskal’s method for MST and Dijkstra’s Algorithm.
Sinhgad Technical Education Society’s
SINHGAD COLLEGE OF ENGINEERING, PUNE
Department of Information Technology
Assignments
Class: T.E. I. T. Subject: Design and Analysis of Algorithm
ASSIGNMENT NO: - 03
Unit III: DYNAMIC PROGRAMMING
Question Course
Question
No. Outcome
1 Explain term Principle of Optimality
2 Explain Bellman- Ford Algorithm with example.
CO1,
3 CO3
Explain 0/1 knapsack Problem with example.
4 What is Travelling Salesman Problem? Explain with example.
5
What is Multistage Graph ? Explain Multistage Graph problem
with example.
Sinhgad Technical Education Society’s
SINHGAD COLLEGE OF ENGINEERING, PUNE
Department of Information Technology
Assignments
Class: T.E. I. T. Subject: Design and Analysis of Algorithm
ASSIGNMENT NO: - 04
Unit IV: BACKTRACKING
Question Course
Question
No. Outcome
1 What is backtracking? Explain general backtracking method.
2 Explain Recursive backtracking algorithm in detail.
3 Explain Iterative backtracking method in detail. CO1,
CO4
4 What is n-Queen problem? Explain with suitable example.
5 Explain term Graph Coloring in detail.
6 What is 0/1 Knapsack Problem ? Explain with example.
Sinhgad Technical Education Society’s
SINHGAD COLLEGE OF ENGINEERING, PUNE
Department of Information Technology
Assignments
Class: T.E. I. T. Subject: Design and Analysis of Algorithm
ASSIGNMENT NO: - 05
Unit V: BRANCH AND BOUND
Question Course
Question
No. Outcome
1 What is branch and bound? Explain General Method.
2 Explain FIFO branch and bound in detail. CO1,
CO5
3 What is LC branch and bound ? Explain in detail.
4 What is Traveling salesperson problem- LC branch and bound.
Sinhgad Technical Education Society’s
SINHGAD COLLEGE OF ENGINEERING, PUNE
Department of Information Technology
Assignments
Class: T.E. I. T. Subject: Design and Analysis of Algorithm
ASSIGNMENT NO: - 06
Unit VI: COMPUTATIONAL COMPLEXITY
Question Course
Question
No. Outcome
1 Explain NP problem in detail.
CO1,
2 Differentiate between NP complete & NP hard. CO6
3 What is Satisfiability problem? Explain in detail.
