VASIREDDY VENKATADRI INSTITUTE OF TECHNOLOGY

NAMBUR-522508 ANDHRA PRADESH, INDIA

YEAR : III [Link] SEMESTER:II

COURSE NAME: DESIGN AND ANALYSIS OF ALGORITHMS
COURSE CODE: XXXXXXXX
BRANCH: COMMON TO CSE & IT BRANCHES
PREREQUISITE: Knowledge of programming language(s) and basic Algorithms
COURSE OBJECTIVE: To provide an introduction to formalisms to understand,
analyze and denote time complexities of algorithms, to introduce the different
algorithmic approaches for problem solving through numerous example
problems, and to provide some theoretical grounding in terms of finding the
lower bounds of algorithms and the NP-completeness
COURSE OUTCOMES: Students will be able to:
Cognitive
Levels as
Weightag
SN OUTCOME per
e (%)
Bloom’s
Taxonomy
Infer the divide-and-conquer paradigm and its
context. Recite algorithms that employ this
CO paradigm. Apply this paradigm to design
L1,L2,L3, L4 20
1 algorithms for apt problems. Derive and solve
recurrences describing the performance of
divide-and-conquer algorithms.
Infer the greedy paradigm and its context.
CO Recite algorithms that employ this paradigm.
L1,L2,L3, L4 20
2 Apply this paradigm to design algorithms for
apt problems.
Infer the dynamic-programming paradigm and
CO its context. Recite algorithms that employ this
L1,L2,L3, L4 20
3 paradigm. Apply this paradigm to design
algorithms for apt problems.
Infer the backtracking paradigm and its
CO context. Recite algorithms that employ this
L1,L2,L3, L4 20
4 paradigm. Apply this paradigm to design
algorithms for apt problems.
Infer the branch and bound paradigm and its
CO context. Recite algorithms that employ this L1,L2,L3, L4 20
5 paradigm. Apply this paradigm to design
algorithms for apt problems.

WEIGHTAGE OF BLOOM’S LEGENDS & PERCENTAGEOF QUESTIONS IN

EXAMINATIONS:
L1 (Remembering) = 30- 40%, L2 (Understanding) = 30 - 40%,
L3 (Applying) = 10-20 %, L4 (Analysing) = 10 - 20%,
Easy (%) = 15%-20%, Average (%)= 60% - 70%, Difficult (%)= 15% - 20%
TOTAL = L1 + L2 + L3 + L4 = 100%(on an average about 2minutes per mark)
Note: This specification weightage in above shall be treated as a general
guideline for students, teachers and paper setters. The actual distribution of
marks in the question paper may vary slightly.
DETAILED SYLLABUS:
UNIT-1: INTRODUCTION: Algorithm Definition, Algorithm Specification,
Performance Analysis, Performance Measurement, Asymptotic notations.
DIVIDE AND CONQUER: General Method, Binary Search, Finding the Maximum
and Minimum, Quick Sort.
UNIT-II: THE GREEDY METHOD: The General Method, Knapsack Problem,
Single Source Shortest Path Problem, Optimal Storage on Tapes Problem,
Optimal Merge Patterns Problem
UNIT-III: DYNAMIC PROGRAMMING: The General Method, 0/1 Knapsack
Problem, Single Source Shortest Path – General Weights, All Pairs-Shortest Paths
Problem, Traveling Salesperson Problem, String Editing Problem.
UNIT-IV: BACKTRACKING: The General Method, The N-Queens Problem, Sum
of Subsets Problem, Graph Coloring Problem, Hamiltonian Cycles Problem.
UNIT-V: BRANCH AND BOUND: The General Method, FIFO Branch-and-Bound,
LC Branch-and-Bound, 0/1 Knapsack Problem, Travelling Salesperson Problem.
NP-HARD AND NP-COMPLETE PROBLEMS: Basic concepts, Cook’s Theorem.

TEXTBOOKS:
1. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, “Fundamentals of
Computer Al-gorithms”, 2nd Edition, Universities Press
REFERENCEBOOKS:
1. Harsh Bhasin, “Algorithms Design & Analysis”, Oxford University Press.
2. S. Sridhar, “Design and Analysis of Algorithms”, Oxford University Press.
ONLINE REFERENCES:
1. [Link]

MICRO-SYLLABUS:

Uni
Module Micro content
t
1 Definition and Algorithm Specification
Performance Analysis – time and space
complexity
Algorithm Analysis Performance Measurement – step count and
frequency count
Asymptotic Notations – Big Oh, Big Omega,
Big Theta
Divide and Conquer General Method
Binary Search – Procedure, Example,
Algorithm and Computing Time Complexity.
Finding the Maximum and Minimum -
Procedure, Example, Algorithm, and
 Computing Time Complexity.
Quick Sort - Procedure, Example, Algorithm
and Computing Time Complexity.
Uni
Module Microcontent
t
General Method
Knapsack Problem - Description, Example,
Algorithm.
Optimal Storage on Tapes Problem -
Greedy Method
2 Description, Example, Algorithm.
Single Source Shortest Path Problem -
Description, Example, Algorithm.
Optimal Merge Patterns Problem -
Description, Example, Algorithm.
Uni
Module Microcontent
t
The General Method
0/1 Knapsack Problem - Description,
Example.
Single Source Shortest Path – General
Weights - Description, Example, Algorithm.
Dynamic Programming
3 All Pairs-Shortest Paths Problem -
Description, Example, Algorithm.
Travelling Salesperson Problem - Description,
Example.
String Editing Problem - Description,
Example.
Uni
Module Microcontent
t
The General Method
The 8-Queens Problem - Description, State
Space Tree, Algorithm.
Sum of Subsets Problem - Description,
Backtracking
4 Example, State Space Tree, Algorithm.
Graph Coloring Problem - Description,
Example, State Space Tree, Algorithm.
Hamiltonian Cycles Problem - Description,
Example, State Space Tree, Algorithm.
Uni
Module Microcontent
t
The General Method
FIFO Branch and Bound
LC Branch and Bound
Branch and Bound 0/1 Knapsack Problem - Description,
5 Example.
Travelling Salesperson Problem - Description,
Example.
NP-Hard and NP- Basics Concepts.
Complete problems Cook’s Theorem.
Code No : R20

III B. TECH II SEMESTER REGULAR EXAMINATION MODEL PAPER

MICROPROCESSORSANDMICROCONTROLLERS
(COMMON TO ECE & EEE BRANCHES)
Time : 3 Hours Max. Marks : 70
___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Note : Answer ONE question from each unit (5 × 14 = 70 Marks)

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~
UNIT-I CO BL
1. a Discuss various asymptotic notations used to [7M] CO L2
) represent complexity of algorithms with examples. 1
b Write algorithm for Min Max Problem. [7M] CO L3
) 1
(OR)
2. a Discuss Quick sort with an example and derive its [7M] CO L2
) time complexity in worst case. 1
b Write algorithm for calculating multiplication of [7M] CO L3
) matrices and derive its time complexity using step 1
count method.
UNIT-II
3. a Find an optimal solution to the knapsack instance [7M] CO L1
) n=5 objects and the capacity of knapsack m=10. 2
The profits and weights of the objects are (P1, P2,
P3, P4, P5) = (15, 7, 6, 18, 3), (W1, W2, W3, W4,
W5) = (5, 7, 1, 4, 1) respectively.
b Define optimal merge pattern? Find optimal merge [7M] CO L1
) pattern for ten files whose record lengths are 28, 2
32, 12, 5, 84, 53, 91, 35, 3, and 11.
(OR)
4. a Find shortest paths in the following graph using [14M CO L1
) Dijkstra’s algorithm. ] 2
 UNIT-III
5. a Define merging and purging rules in 0/1 knapsack [7M] CO L2
) problem and explain with an example.. 3
b Write and explain an algorithm to compute the all [7M] CO L3
) pairs shortest path using dynamic programming and 3
prove that it is optimal.
(OR)
6. a Explain the methodology of Dynamic programming. [7M] CO L2
) Mention the applications of Dynamic programming. 3
b Let X = a,a,b,a,a,b,a,b,a,a and Y = b,a,b,a,a,b,a,b. [7M] CO L1
) Find a minimum-cost edit sequence that transforms 3
X and Y.
UNIT-IV
7. a Explain the Graph–Coloring problem and draw the [7M] CO L2
) state space tree for m= 3 colors and n=4 vertices 4
graph.
b Write an algorithm to determine the Hamiltonian [7M] CO L3
) Cycle in a given graph using backtracking. 4
(OR)
8. a Find all possible subsets of w that sum to m. Let [7M] CO L3
) w={5,7,10,12,15,18,20}and m=35 and construct 4
the portion of the state space tree that is generated
using backtracking.
b Illustrate the process of backtracking on the 8 [7M] CO L2
) Queens problem. Explain with a suitable example. 4
UNIT-V
9. a State the concept of branch and bound method and [7M] CO L1
) mention its applications. 5
b Discuss 0/1 Knapsack problem with respect to [7M] CO L2
) branch and bound method. 5
(OR)
10 a Deduce an optimal tour of the following travelling [14M CO L4
. ) salesperson problem using LCBB. ] 5

*****
THE ABOVE MODEL PAPER ATTAINMENTS OF BLOOM’S TEXONOMY AS
FOLLOWS

L1: 4*7 + 1*14 = 42= 30%

L2: 7*7 = 49 = 35%
L3: 5*7 = 35 = 25%
L4: 1*14 = 14 = 10%
SIGNATURES OF

COURSE COORDINATER MODULE COORDINATER HOD