EXAMINATION QUESTIONS FOR CSC 411

EXCEPT QUESTION 2 WHICH IS FOR TEST

1a. Explain the concept of (not exceeding three sentences for each).
(10mrks)
 Recursive Relationship
 State
 Stage
 Alternative
 Optimal Policy
1b. State Bellman’s Principle of Optimality in Dynamic Programming and
give a mathematical formulation of a Dynamic Programming problem.
(5mks)

TEST QUESTIONS
2. Define the term Dynamic Programming? (21/2marks)
b. State the Principle of Dynamic Programming and Describe the basic
features which characterize a dynamic programming. (5marks)
c. Give a mathematical formulation of a Dynamic Programming problem
(21/2marks)

3a. A market executive located in a City A decided to travel to City B. He/she

knew the distances of alternative routes from City A to B, and then
he/she tabulated all the data as given below.
The city of origin A is city 1 and the destination city, B, is city 10. Other
cities through which the salesperson will have to pass are numbered
from 2 – 9. Construct the Network map for the Salesperson given the
following data below whose distance is in kilometer and the cities
labelled City 1 to City 10.
(10 marks)

A 2 3 4 8 9
FROM 1 4 6 3 5 4 8
6 3 7
5 6 7 7 8 4
2 7 10 5 10 B
3 3 8 4 8 7
4 6 10 5 9 9
3b. Clearly distinguish between Forward and Backward Computational
Procedure in Dynamic Programming. 5marks
4a. A sales Manager is planning to a business tour from Wukari to Jalingo.
He intends to cover one town from each of the Company’s different
marketing zones on the route. The network below shows the three
intermediate stages and three possible choices of route at all but the last
cities. The travel time between the two cities inclusive of working time is
given below the arrows between cities. Which intermediate cities should
he visit to minimize the time required to go from A to H.
Find the shortest route. (15marks)
Q1. STAGE:
Stage can be defined as the point at which decisions are called
for. Each stage can be thought of having beginning and an end.
Dynamic Programming is broken into sub – problems and each
problem is called Stage.
The point at which decisions called for, are referred to as
stages.

STATE:
State can be define as the information available at each stage
indicates the, value of state variables, which link up two stages.
State can be define as the variable that links up two stages is
called State Variables.

ALTERNATIVE:
At every stage, there may be more than one choice to take
decision, which is known as alternative.

OPTIMAL POLICY:
A policy, which optimize the value of a criterion objective or
return function is called Optimal Policy. Decision at any stage is
not dependent on the previous history of the system.

RECURSIVE RELATIONSHIP:
It represents mathematical expression connecting the optimal
solution of the earlier stage and the return function from the
current stage.
Q2A DYNAMIC PROGRAMMING
Dynamic Programming is a mathematical technique that deals
with the optimization of multistage decision tree.
Richard Bellman developed this technique. The technique is
called Recursive Function.

Q2B THE CHARACTERISTICS OF DYNAMIC PROGRAMMING

 The problem can be divided into stages with a policy
decision required at each stage.
 Every stage consists of number of states.
 Decision at each stage converts the current state with
state associated with the next stage
 Each stage has set of variables known as state variables.
 The decision of one stage is independent of another
stage.
 To find optimum policy recursive equation is developed.
 The backward recursive approach is used for taking
decision from the last stage to next previous stage. This is
followed till final solution is obtained.

Q2C BELLMAN’S PRINCIPLE OF OPTIMALITY

States that;
“An optimal policy (set of decisions) has the
property that, whenever the initial state and initial
decisions are, the remaining decision must
constitute Optimal Policy with respect to the state
resulting from the first decision.”

MATHEMATICAL REPRESENTATION
 Here:

( V(s_t)) is the value function, representing the

maximum
value that can be achieved starting from state
( s_t ).

( a_t ) is the action taken at time ( t ).

( R(s_t, a_t) ) is the immediate reward received after taking

action ( a_t ) in state ( s_t ).

( gamma ) is the discount factor, with

( 0 \leq \gamma \leq 1 ), which accounts for
the difference in importance between present
and future rewards.

( s_{t+1} ) is the state resulting from taking action ( a_t )

in state ( s_t ).

Q3A. The Constructed Network map for the Salesperson

7 4
10
8
5

3
4 3
6 8
4 7
3

6 8
10
5 4
Q3B. Clearly distinguish between Forward and Backward Computational
Procedure in Dynamic Programming.

Forward Computational Procedure in Dynamic Programming occurs

when the Dynamic Programming is solved using the recursive equation
starting from the first stage to last stage the computation involved is
called the Forward Computational Procedure.
While
Backward Computational Procedure in Dynamic Programming occurs
when the Dynamic Programming is solved using the recursive equation
starting from the last stage to first stage the computation involved is
called the Backward Computational Procedure.

Q4. SOLUTION TO QUESTION (4A).

STAGE 1
The Possible Alternatively is H.
The possible State Variables are nodes E F and G.
The recursive function is f1(x1) = d(x1, m1)

State Variable Alternative f1(x1) m1

x1 H
E 3 3 H
F 4 4 H
G 3 3 H
STAGE 2
The Possible Alternatives are E F G OUTPUT OF TABLE 1
The Possible State Variables are nodes B, C, and D. State Variable f1(x1)
The Recursive Function is x1
f2(x2) = d(x2, m2) + E 3
f1(x1=m2) F 4
G 3

State Variable Alternative m2 f2(x2) m2

x2 E F G
B 5+3=8 7 + 4 = 11 7 + 3 = 10 8 E
C 6+3=9 7 + 4 = 11 10 + 3 = 13 9 E
D 6+3=9 8 + 4 = 12 9 + 3 = 12 9 E

STAGE 3
The Possible Alternatives are B, C, D OUTPUT OF TABLE 2
The Possible State Variables is A. State Variable f2(x2)
The Recursive Function is x3
f3(x3) = d(x3, m3) + f2(x2=m3) B 8
C 9
D 9

State Variable Alternative m2 f3(x3) m3

x3 B C D
A 5 + 8 = 13 5 + 9 = 14 3 + 9 = 12 12 D

Therefore, the shortest path for this problem is 12

CONCLUSIVELY

3 6 3
A D E H = 12km, which is the shortest path.

the shortest path is from Node A – D – E – H