Analysis and Design of Algorithms - Dynamic Programming-2
1 view 0 purchase
Course
Analysis and Design of Algorithms (MCA4040)
Institution
Sikkim Manipal University
Unit 11: Dynamic Programming-2
This unit defines the Principle of Optimality and analyzes binary search
trees using dynamic programming. It also introduces the Knapsack problem and solves an instance of it using dynamic programming and memory functions.
11.1 Introduction
Objectives
11.2 Principle of Optimality
11.3 Optimal Binary Search Trees
Solving binary search trees using
11.4 Knapsack Problem dynamic programming
Solving Knapsack problem using
11.5 Memory Functions
dynamic programming
Solving Knapsack problem using memory functions
11.6 Summary
11.7 Glossary
11.8 Terminal Questions
11.9 Answers
11.1 Introduction
In the previous unit we studied some concepts of dynamic programming. As
you know, dynamic programming is defined as an optimization technique
that is used for particular
classes of backtracking algorithms where the sub
problems are repeatedly solved.
The basic steps for dynamic programming are given below:
1) Develop a mathematical notation that is used to find a solution and sub
solutions for the problem.
2) Prove the solution using the Principle of Optimality.
3) Derive a recurrence relation that solves the sub solutions using the
mathematical notation in step 1.
4) Write an algorithm to compute the recurrence relation.
Sometimes, we have to solve problems optimally. At some other time a
non-optimal solution also gives a good solution. We cannot judge a problem
by a single criterion. Optimization of a problem is useful in any type of
problem we have to solve.
This unit defines the Principle of Optimality and analyzes binary search
e s using dynamic programming. It also introduces the Knapsack problem
,and solves an instance of it using dynamic programming and memory
functions.
Objectives:
After studying this unit you should be able to:
define Principle of Optimality'
analyze optimal binary search trees with an example
describe Knapsack problem with an example
explain memory functions with an example
11.2 Principle of Optimalityy
Principle of Optimality is defined as a basic dynamic programming principle
which helps us to view problems as a sequence of sub problems.
Richard Ernest Bellman, a mathematician, invented the Principle of
Optimality. This principle explains that an optimal path has the property that
whatever the initial conditions and choices over some initial period, the
decision variables chosen over the remaining period must be optimal for the
remaining problem. Therefore, we can say that the optimal solution to a
problem is a combination of optimal solutions of its sub problems.
We might face a difficulty in converting the Principle of Optimality into an
algorithm, as it is not very easy to identify the sub problems that are relevant
to the problem under consideration. Bellman developed an equation for the
Principle of Optimality. We can study this equation only with the help of
dynamic programming concepts.
All optimization problems tend to minimize space and time, and maximize
profits. There is a mathematical function defined for this namely,
optimization function. Every instance of a dynamic programming problem
should be tracked as it involves the use of various different sub problems to
solve it. This information about the current situation required to make a
correct decision is known as a state. The variables we choose for solving
the problem at any point of time are called control variables. At every state
we have to choose the control variable with the help of the previous state.
The rule that determines the controls as a function of states is known as
policy function. The best possible value of the problem objective, written as
a function of the state, is called the value function.
, Bellman formulated equation for the Principle of Optimality during the
an
early stages in technology development. The computers used during that
stage were not as powerful as we use now. This principle may help in
advanced dynamic programming applications which supportlarger
dimensions than that used today.
We can derive the Bellman
equation usingstep by step recursive process
a
of writing down the
relationship between the value function of one stage and
the value function of the next
stage.
The Bellman equation for
Principle of Optimality is given as:
V(xo) =maxpi(r|xo,ao)ri(ro, ao, x1)+Vw -1x1|
a
Eq: 11.1
In the equation Eq: 11.1,
Vn(Xo) is the value function where N is the number
of decision steps. We are aware that the
value function explains the best
possible value of the objective, as a function of the state Xo. Here
pi(xlxo, ao)[ri(xo, ao, xi) +Vw -(x)] are the policies with respect to
distribution.
Self Assessment Questions
1. Principle of is defined basic
as a
dynamic programming
principle which helps us to view problems as a sequence of sub
problems.
2. mathematician, invented the Principle of Optimality.
a
3. All optimization problems tend to minimizing cost, time and maximizing
11.3 Optimal Binary Search Trees
Now that we have discussed the basic Principle of
Optimality, let us
optimize a binary search tree. First, let us define a binary search tree.
Binary search tree Binary search tree is defined as a
binary tree with
-
the
following properties:
The values of elements in the left sub-tree of a node are lesser than the
node's value.
.
The values of elements in the rignt sub-tree of a node are greater than
the node's value.
The right and left sub-trees of a node are also binary search trees.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller nikhilcs. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.49. You're not tied to anything after your purchase.
