Fundamentals
of Algorithms
CS502-Spring
2011
Assignment
#5
Uploading instructions
Please
view the assignment submission process
document provided to you by the Virtual
University
Rules for Marking
It should be clear that your
assignment will not get any credit if:
oThe assignment is submitted after due
date.
oThe submitted assignment does not
compile or run.
oThe
assignment is copied.
Objectives
This assignment will help you to
understand the concepts of Knapsack Problem and Chain matrix Multiplication
which results in efficient calculation time wise.
Guidelines
1. In order to attempt this assignment you should have full command on
Lecture # 39to Lecture # 45
2. In order to solve this assignment you have strong concepts about
following topics
ü Polynomial Time Algorithms
ü Non deterministic Polynomial time Algorithims
Recommended book
for solving assignment
Cormen, Leiserson, Rivest, and Stein (CLRS) 2001, Introduction to Algorithms, (2nd ed.) McGraw Hill.
Estimated Time 3
hours
You
can make justified search for the topic in One hour and 1.5 hour to understand
the whole themes you are asked and 0.5 hour to organize and type whole
material.
What to submit
You are
bound to submit word file only in the given format and given HEADLINES below.
Negative marking will be done in case of violating the format provided to you.
Question# 1
(9)
You are bound to answer the following queries relating to
Polynomial time/space algorithms:
Formal Definition 1.5
How the given problem is identified the Problem is in P
class
[You are only bound to
give some hints/theorems no detail proofs]
4
Are these problems Feasible to Solve in available memory
and time 2
[Why or why not give
constraints if any]
Examples 1.5
[General type examples
are preferable]
Question# 2
(9)
You are bound to answer the following queries relating to
Non Deterministic Polynomial time/space algorithms:
Formal Definition 1.5
How the given problem is identified the Problem is in NP class
4
[You are only bound to
give some hints/theorems no detail proofs, some more hints relating to NP
classes are preferable]
Are these problems Feasible to Solve in available memory
and time 2
[Why or why not give
constraints if any]
Examples 1.5
[General type examples
are preferable; Classes of NP can be given with single line explanation]
Q
3 Conclusions 2
[Here you have to write
two to three sentences relating to final comments on P and NP problems]
No comments:
Post a Comment
“You can't change the past, but you can ruin the present by worrying about the future”