08(UoB)

2008
2009
09(UoB)
10(UoB)
2010
 2011
11(UoB)
 A23926
12(UoB)
2012
Any Calculator

SECTION A

1. (a) Is the following matrix totally unimodular (TU)? Briefly justify your answer. [5]
 
−1 0 1 0 −1 0 0 0
 

 0 1 0 1 1 0 1 0 

A= 0 1 0 0 0 −1 0 1  .
 
 

 0 0 1 0 0 0 1 0 

−1 0 0 1 0 1 0 0

(b) Solve the following integer programming problem by using dynamic programming:

max 12x1 + 7x2 + 13x3

s.t. x1 + 2x2 + 2x3 ≤ 4,
x1 , x2 , x3 ≥ 0 and integer.

What are the optimal objective value and optimal solution to this integer programming
problem? [10]

(c) A factory produces a single type of product in periods 1, ..., n. Production in period t incurs
a fixed cost ft > 0, and each unit produced in period t costs pt . Earlier production can
be kept in storage for later sale at a unit storage cost of ht during period t . Initial storage
is empty. Client demand in period t is dt . How to plan production so as to satisfy all
demands and minimize total costs? Formulate this problem as an integer programming
problem. (You are NOT required to solve this integer programming problem.) [10]

2. (a) Consider the IP problem:

max{cT x : Ax ≤ b, x ∈ X ⊂ Z n }

where c ∈ Rn , A is an m×n matrix, and b ∈ Rm . The symbol Z n denotes the n-dimensional

integer space. Define the Lagrangian dual of this IP problem. [3]

(b) Consider the following knapsack problem:

z∗ = max 23x1 + 35x2 + 7x3 + 14x4 + 2x5 + 21x6

s.t. 5x1 + 7x2 + 4x3 + 7x4 + x5 + 5x6 ≤ 41,
xi ≥ 0 and integer, i = 1, ..., 6.

(i) Find a lower bound for z∗ by the greedy heuristic method.

Page 2 Turn over

A23926 Any Calculator

(ii) Find an upper bound for z∗ by solving the linear programming relaxation of the above
knapsack problem. [10]

(c) Solve the following integer programming problem by the Branch and Bound method: [12]

z∗ = max 5x1 + 7x2

s.t. 2x1 + x2 ≤ 13,
5x1 + 9x2 ≤ 41,
x1 , x2 ≥ 0 and integer.

Page 3 Turn over

 A23926 Any Calculator

3. (a) Prove that y2 + 2y3 + 3y4 ≤ 7 is a valid inequality for the set

4
X = {y ∈ Z+ : 4y1 + 5y2 + 11y3 + 16y4 ≤ 37},

4 denotes the 4-dimensional nonnegative integer space, i.e.,

where Z+

4
Z+ = {x ∈ R4 : x ≥ 0 and integer}.

[5]

(b) Solve the following integer programming problem by using logical inequalities: [8]

(IP) z∗ = min 4x1 + 5x2 + 2x3

s.t. 7x1 + 3x2 − 4x3 − 2x4 ≤ 1,
−4x1 + 14x2 + 6x3 + 2x4 ≤ 12,
−3x1 + 2x2 ≤ −1,
2 3 6
− x1 − x3 − x4 ≤ −1
5 5 5
xi ∈ {0, 1}, i = 1, 2, 3, 4.

(c) Consider the following Integer programming problem: [12]

(IP) z∗ = min −7x1 − 9x2

s.t. −x1 + 3x2 ≤ 6,
7x1 + x2 ≤ 35,
x1 , x2 ≥ 0 and integer.

The linear programming relaxation of (IP) is solved by the simplex method, and the optimal
simplex tableau is given as follows, where s1 and s2 are slack variables

x1 x2 s1 s2 RHS
28 15
z 0 0 − 11 − 11 −63
.
7 1 7
x2 0 1 22 22 2
1 3 9
x1 1 0 − 22 22 2

Solve the problem (IP) by the cutting plane method.

Page 4 Turn over

 A23926 Any Calculator

SECTION B

4. (a) Give a detailed account and justification of the individual steps of the primal-dual algo-
rithm. Include the definition of the set of admissible indices, formulation of the restricted
primal problem and its dual and the optimality criterion. Derive the formula for updating a
dual feasible solution. Formulate and prove the infeasibility criterion. [13]

(b) For the linear programming problem below find its dual and solve the dual. Then use
duality of linear programming, including the complementary slackness, to find an optimal
solution to the primal problem (if there is any):

x1 + 2x2 − x3 + 3x4 −→ min

subject to

x1 − x4 ≥ −5,
−2x1 + x2 ≥ 3,
x2 + x3 + 2x4 = 7,
x1 , x4 ≥ 0.

Show your working. [6]

T
(c) Use the primal-dual algorithm, starting from π = (−1, 1) , to decide whether the following
linear program has an optimal solution and in the positive case find one:

6x1 − 3x2 + x3 + 2x4 −→ min

subject to

−5x1 + 2x2 + 3x3 + 4x4 = 3,

x1 − x2 − 4x3 − 5x4 = −1,
x1 , x2 , x3 , x4 ≥ 0.

Show your working. [6]

Page 5 Turn over

 A23926 Any Calculator

5. (a) Define the transportation problem and find its dual, restricted primal and the dual to the
restricted primal. [8]
 
(b) What are the values of the individual components of the optimal solution α, β to the
dual of the restricted primal problem used in the algorithm ALPHABETA? Prove that this
vector is feasible (you are not required to prove optimality). [8]

(c) Algorithm ALPHABETA has been applied to the transportation problem below:

70 30 60 20 αi
60 13 20 15 18 .
80 7 23 14 9 8
40 6 12 8 11 .
βj . . 5 .

The current network and maximum flow found by the algorithm are shown in Figure 1. Use
this figure to find the missing values of αi and β j and then carry out the remaining work
of ALPHABETA. Write down the optimal solution found by ALPHABETA and calculate the
minimal total transportation cost. [9]

Page 6 Turn over

 A23926 Any Calculator

6. (a) Give a definition of a spanning tree and of a maximal acyclic subgraph of a connected
graph. Then prove the statement: Every maximal acyclic subgraph of a connected graph
G is a spanning tree of G. [10]

(b) Define a Hamilton cycle in a digraph. How many Hamilton cycles are there in the complete
digraph with n nodes? Justify your answer. [4]

(c) Define the Travelling Salesman Problem (TSP) in a complete arc-weighted digraph. [3]

(d) For the direct-distances matrix A below (where p is a real parameter) write all TSP tours
and their lengths. Is there any value of the real parameter p for which GREEDY finds an
optimal tour? If there is any then find all such values. Justify your statement.
 
∞ 7 4 9
 
 5 ∞ 3 4 
A=
 p 4 ∞ 8
.

 
5 4 4 ∞

[8]

Page 8 End of paper

 A23926 Any Calculator
13(UoB)
2013
Section A

1. (a) Is the following matrix totally unimodular (TU)? Justify your answer. [5]
 
−1 0 0 0 −1
 
 0 1 1 0 0 
 
 
 1 0 0 1 0 
 
A=
 0 1 0 0 1 
.
 
 −1 1 0 0 0 
 
 0 −1 0 1 
 0 
0 1 0 1 0

(b) I have been approached by three telephone companies to subscribe to their long distance
service. MaBell will charge a flat £16 per month plus £0.25 a minute. PaBell will charge
a flat £25 a month but will reduce the per-minute cost to £0.21. As for BabyBell, the flat
monthly charge is £18, and the cost per minute is £0.22. I usually make an average of
200 minutes of long-distance calls a month. Assuming that I do not pay the flat monthly
fee unless I make calls and that I can apportion my calls among all three companies as I
please, how should I use the three companies to minimise my monthly telephone bill?

Formulate this problem as an integer programming problem. Clearly define your variables,
objective and constraints. (You are NOT required to solve this integer programming
problem.) [8]

(c) Use the dynamic programming method to solve the integer programming problem

max 13.2x1 + 9.5x2 + 11.7x3

s.t. x1 + 2x2 + 2x3 ≤ 4,
x1 , x2 , x3 ≥ 0 and integer.

What are the optimal solution and objective value to this integer programming problem? [12]

Page 2 Turn over

 A23926 Any Calculator

2. (a) Let X ⊆ B4 denote the feasible set of an integer programming problem, where B4 =
{(x1 , x2 , x3 , x4 ) : xi = 0 or 1, i = 1, ..., 4} is the set of 4-dimensional binary vectors. As-
sume that the following two polyhedra are formulations of X :

P1 = {x ∈ R4 : 84x1 + 62x2 + 52x3 + 20x4 ≤ 101, 0 ≤ xi ≤ 1, i = 1, ..., 4},

P2 = {x ∈ R4 : 4x1 + 3x2 + 2x3 + x4 ≤ 4, 0 ≤ xi ≤ 1, i = 1, ..., 4}.

That is, X = P1 ∩ B4 = P2 ∩ B4 . Prove that the formulation P2 is better than P1 . [5]

(b) Consider the following integer programming problem:

z∗ = max 20x1 + 34x2 + 7x3 + 16x4 + 1.95x5 + 23x6

s.t. 5x1 + 7x2 + 5x3 + 8x4 + x5 + 6x6 ≤ 45,
xi ≥ 0 and integer, i = 1, ..., 6.

(i) Find a lower bound for z∗ by using greedy heuristic method. [3]

(ii) Find an upper bound for z∗ by solving the (dual of) linear programming relaxation of
the above integer programming problem. [5]

(c) Consider the integer programming problem [12]

(IP) z∗ = max x1 + x2
s.t. 5x1 + 8x2 ≤ 40,
2x1 + x2 ≤ 12,
x1 , x2 ≥ 0 and integer.

It is known that (x1 , x2 ) = ( 56 20

11 , 11 ) is the optimal solution to the linear programming re-
laxation of the problem (IP). Use Branch and Bound method to solve the problem (IP) by
branching the problem according to x1 = 56
11 .

Page 3 Turn over

 A23926 Any Calculator

3. (a) Consider the integer programming problem

(IP) max{cT x : Ax ≤ b, x ≥ 0 and integer}

and the linear programming problem

(D) min{bT y : AT y ≥ c, y ≥ 0}.

Assume that both (IP) and (D) are feasible. Prove that (D) is a weak dual of (IP). [5]

(b) Consider the 0-1 integer programming problem

max 8x1 − 6x2 − 6x3 + 5x4

s.t. 7x1 + 3x2 − 4x3 − 2x4 ≤ 1,
−2x1 + 7x2 + 3x3 + x4 ≤ 6,
−2x2 − 3x3 − 6x4 ≤ −5,
3x1 − 2x3 ≥ −1,
xi ∈ {0, 1}, i = 1, ..., 4.

Solve this problem by using logical inequalities. [8]

(c) Use the cutting-plane method to solve the following integer programming problem: [12]

max 5x1 + 2x2

s.t. 5x1 + 4x2 ≤ 21,
x1 , x2 ≥ 0 and integer.

Page 4 Turn over

 A23926 Any Calculator

Section B

4. (a) Define the dual to a general linear program (that includes both equations and inequalities
and both nonnegative and free variables).

[5]

(b) Formulate the weak duality theorem (its proof is not required) and deduce a corollary that
guarantees optimality of feasible solutions.

[5]

(c) State and prove the complementary slackness theorem.

[8]

(d) For the linear program below find its dual. Then solve the dual without using the simplex
method and use the complementary slackness theorem to find an optimal solution and
the optimal objective function value of the primal problem.

12x1 − 9x2 + 4x3 −→ min

x1 + 2x3 ≥ 7
2x1 − 3x2 = 10
x1 ≥ 0
x3 ≥ 0

[7]

5. (a) Define a network, flow in a network and a cut.

Page 5 Turn over

A23926 Any Calculator

[7]

(b) Let N = (V, E, s,t, b) be a network. Prove that the following relation holds for any cut
( )
W,W and any flow f in N :

v( f ) = ∑ f (x, y) − ∑ f (x, y) .
x∈W,y∈W x∈W ,y∈W
(x,y)∈E (x,y)∈E

[9]

(c) In the network of Figure 1, where the numbers in squares indicate the capacities of in-
dividual arcs, find a maximal flow without using the Ford and Fulkerson algorithm if it is
( )
given that W,W is a minimal cut where W = {s, a, b, e} .

[5]

6
a d
11 30

8 34

s c t
10 12

30 3
16
b e

Figure 1

(d) It is required that the network of Figure 1 is modified so that the max-flow is increased
by 6 units subject to the restriction that only the capacities of two arcs can be changed
(by any value) but the capacities of the arcs leaving the source must remain unchanged.
Suggest a change of arcs satisfying these conditions, find a maximal flow and minimal
cut. Show your working.

[4]

Page 6 Turn over

 A23926 Any Calculator

6. (a) What is the relative error of an algorithm with respect to an instance of a combinatorial
optimisation problem? What is an ε - approximate algorithm?

[5]

(b) Formulate Christofides’ algorithm for solving ∆TSP and prove that it is 12 - approximate.
You may assume that the following statement has already been proved: Let (Kn , (ai j ))
be an instance of ∆TSP for a symmetric matrix A = (ai j ). If G = (V, E) is an Eulerian
spanning graph for A then every tour in Kn embedded in an Eulerian walk in G has length
not exceeding the cost of G.

[10]

(c) Use Christofides’ algorithm to find a tour for the ∆TSP where the cities are: a = (0, 0) , b =
(5, 0) , c = (8, 2) , d = (3, 3) , e = (2, 5) . Describe the tour as a sequence of cities starting
from a and find also the length of the tour. You may leave the length in the form of a sum
of radicals. For the application of the algorithm you may find the following approximations
√ √ √ √ √
of radicals helpful: 2 ≈ 1.414, 5 ≈ 2.236, 17 ≈ 4.123, 26 ≈ 5.099, 29 ≈ 5.385.
[5]

(d) Use your results in question (c) to find a lower bound for the minimal length of a tour for
the ∆TSP in that question.

[5]

Page 7 End of paper

 A23926
14(UoB)
2014
Any Calculator

Section A

1. (a) Consider the set

X = {y ∈ Z+
4
: 48y1 + 15y2 + 32y3 + 20y4 ≤ 85},

4 denotes the 4-dimensional nonnegative integer space, i.e., Z 4 = {y ∈ R4 : y ≥

where Z+ + i
0 and integer, i = 1, 2, 3, 4}. Prove that 3y1 + y2 + 2y3 + y4 ≤ 5 is a valid inequality for
the set X. [5]

(b) There are six cities in region R. The region must determine where to build fire stations.
The region wants to build the minimum number of fire stations and ensures that at least
one fire station is within 16 minutes of each city. The times (in minutes) required to drive
between cities are:
 
From to
 
 City1 City2 City3 City4 City5 City6 
 
 
 City1 0 10 20 30 30 20 
 
 10 
 City2 10 0 25 35 20 
 
 City3 20 25 0 15 30 20 
 
 
 City4 30 35 15 0 15 25 
 
 City5 30 20 30 15 0 14 
 
City6 20 10 20 25 14 0

Formulate this problem as an integer programming problem. Clearly define your variables,
objective and constraints. (You are NOT required to solve this integer programming
problem.) [8]

(c) Use the dynamic programming method to solve the integer programming problem

max 14.1x1 + 13.9x2 + 7.2x3

s.t. 2x1 + 2x2 + x3 ≤ 4,
x1 , x2 , x3 ≥ 0 and integer.

What are the optimal solution and objective value of this integer programming problem? [12]

Page 2 Turn over

 A23926 Any Calculator

2. (a) Consider the integer programming problem

z∗ = max 23x1 + 40x2 + 14x3 + 20x4 + 3.5x5 + 36x6

s.t. 4x1 + 7x2 + 3x3 + 4x4 + 0.8x5 + 6x6 ≤ 65,
xi ≥ 0 and integer, i = 1, ..., 6.

(i) Find a lower bound for z∗ by using the greedy heuristic method. [4]

(ii) Find an upper bound for z∗ by solving the (dual of) linear programming relaxation of
the above integer programming problem. [4]

(b) Let Z n be the set of n-dimensional integer vectors and Rm be the set of m-dimensional
vectors. Let X ⊆ Z n and U ⊆ Rm be two given sets. Let the problem

(D) min{w(u) : u ∈ U ⊆ Rm }

be the weak dual of the integer programming problem

(IP) max{ f (x) : x ∈ X ⊆ Z n },

where w(·) and f (·) are two continuous functions. Suppose that x∗ ∈ X and u∗ ∈ U
satisfy that f (x∗ ) = w(u∗ ). Prove that x∗ is an optimal solution of (IP) and u∗ is an optimal
solution of (D). [5]

(c) Consider the following integer programming problem (IP):

(IP) z∗ = max 5x1 + 7x2

s.t. 5x1 + 9x2 ≤ 41,
2x1 + x2 ≤ 13,
x1 , x2 ≥ 0 and integer.

It is known that (x1∗ , x2∗ ) = ( 76 17

13 , 13 ) is the optimal solution to the linear programming re-
laxation of the problem (IP). Use Branch and Bound method to solve the problem (IP) by
branching the problem according to the component x2∗ = 17
13 . [12]

Page 3 Turn over

 A23926 Any Calculator

3. (a) Is the following matrix totally unimodular (TU)? Justify your answer. [5]
 
−1 0 0 0 −1 1
 
 0 1 −1 00  0
 
 
 0 0 0 1 1 0 
 
A=
 1 0 −1 0 0 0 .
 
 0 0 −1 0 −1 0 
 
 −1 0 0 0 0 
 1 
0 0 −1 1 0 0

(b) Solve the following 0-1 integer programming problem by using logical inequalities. [8]

max 10x1 − 8x2 − 7x3 + 9x4

s.t. 6x1 + 7x2 − 5x3 − 3x4 ≤ 2,
−3x1 + 6x2 + 3x3 + 2x4 ≤ 5,
−4x2 − 7x3 − 3x4 ≤ −8,
−4x1 + 3x3 − x4 ≤ −1,
xi ∈ {0, 1}, i = 1, ..., 4.

(c) Use the cutting-plane method to solve the following integer programming problem: [12]

max 10x1 + 4x2

s.t. 15x1 + 12x2 ≤ 63,
x1 , x2 ≥ 0 and integer.

Page 4 Turn over

 A23926 Any Calculator

Section B

4. (a) Define the transportation problem and find its dual, restricted primal and the dual to the
restricted primal. [5]

(b) When is a transportation problem called balanced? Prove that a transportation problem
is balanced if and only if it has a feasible solution. Then prove that every transportation
problem has an optimal solution if it has a feasible solution. Deduce a criterion for the exis-
tence of an optimal solution to the transportation problem based on these two statements.
[12]

(c) Algorithm ALPHABETA has been applied to the transportation problem

10 8 15 7
16 6 13 8 4
.
15 2 1 5 6
9 10 7 12 9

At a certain iteration the vectors α = (0, −3, 3)T and β = (5, 4, 8, 4)T have been obtained
as a dual feasible solution. Use these vectors to continue in the work of ALPHABETA until
an optimal solution is found. Then calculate the optimal transportation cost and compare
it with that of the transportation plan obtained by GREEDY. [8]

5. (a) Define the concept of an independence system and that of a matroid. [6]

(b) Prove that if GREEDY correctly solves every combinatorial optimisation problem associ-
ated with an independence system S then the Exchange Proposition holds in S. [9]

(c) Let m, n ≥ 2 be integers and M = {1, 2, . . . , m}, N = {1, 2, . . . , n}.

(i) Show that the system S = (E, J) is a matroid where E = M × N (the set of all cells of a
rectangular matrix) and I ∈ J if and only if I is a set of cells where no three belong to the
same column. [Hint: Use the Exchange Proposition.]

(ii) Formulate the combinatorial optimisation problem (COP) associated with S.

Page 5 Turn over

 A23926 Any Calculator

(iii) Using GREEDY, solve the COP formulated in (ii) for the matrix
 
9 13 3 12 2
 
A=
 10 11 0 13 1 
.
12 7 1 9 3

Clearly indicate which cells will be accepted and which will be rejected in the order they
are processed by GREEDY and calculate the optimal cost. [10]

6. (a) Define an Eulerian walk in a multigraph and an Eulerian spanning graph of a symmetric
matrix. Define also the cost of an Eulerian spanning graph. [6]

(b) State and prove the generalised triangle inequality for a square matrix given that a triangle
inequality holds and then prove the statement:
( )
”Let A = ai j ∈ Rn×n be a symmetric matrix with zero diagonal satisfying the triangle
( )
inequality. If G = (V, E) is an Eulerian spanning graph for A = ai j then every tour (of
the travelling salesman) embedded in an Eulerian walk in G has length not exceeding the
cost of G”. [13]

(c) Use algorithm TREE to find two approximate solutions to the ∆TSP where the cities are
placed at the points

a = (0, 1) , b = (1, 2) , c = (3, 0) , d = (1, 5) , e = (0, −3) .

In your construction of the Eulerian walks start at point d. Find also the lengths of the
tours produced by this algorithm and use them to find a lower bound of the length of an
optimal tour (you may leave your results in the form of radicals). [6]

Page 6 End of paper

 A25086
2015
15(UoB) Any Calculator

1. (a) Consider the integer programming problem

z∗ = max 22x1 + 36x2 + 3.3x3 + 20x4 + 3.2x5 + 48x6

s.t. 4x1 + 7x2 + 1.1x3 + 4x4 + 0.8x5 + 8x6 ≤ 79,
xi ≥ 0 and integer, i = 1, ..., 6.

(i) Find a lower bound for z∗ by using the greedy heuristic method. [4]

(ii) Find an upper bound for z∗ by solving the dual of the linear programming relaxation of
the above integer programming problem. [4]

(b) Prove that the polyhedron

P = {(x1 , x2 , ..., xm , xm+1 ) : 0 ≤ xm+1 ≤ 1, 0 ≤ xi ≤ xm+1 for i = 1, ..., m}

has an integer extreme point. [8]

(c) Use the dynamic programming to solve the following 0-1 knapsack problem:

max 7x1 + 8x2 + 3x3

s.t. x1 + 2x2 + x3 ≤ 3,
x1 , x2 , x3 ∈ {0, 1}.

[9]

Page 2 Turn over

 A25086 Any Calculator

2. (a) Consider the set

4
X = {y ∈ Z+ : 50y1 + 25y2 + 65y3 + 21y4 ≤ 150},

4 denotes the 4-dimensional nonnegative integer space, i.e., Z 4 = {y ∈ R4 : y ≥

where Z+ + i
0 and integer, i = 1, 2, 3, 4}. Prove that 2y1 + y2 + 3y3 + y4 ≤ 7 is a valid inequality for
the set X. [5]

(b) Use logical inequalities to solve the following 0-1 integer programming problem:

max 30x1 − 24x2 − 21x3 + 27x4

s.t. 12x1 + 14x2 − 10x3 − 6x4 ≤ 4,
−1.5x1 + 3x2 + 1.5x3 + x4 ≤ 2.5,
− 2x2 − 3.5x3 − 1.5x4 ≤ −4,
−8x1 + 6x3 − 2x4 ≤ −2,
x1 , x2 , x3 , x4 ∈ {0, 1}.

[8]

(c) Use the Branch and Bound method to solve the following integer programming problem:

z∗ = max 5x1 + 4x2

s.t. x1 + x2 ≤ 5,
10x1 + 6x2 ≤ 45,
x1 , x2 ≥ 0 and integer.

[12]

Page 3 Turn over

 A25086 Any Calculator

3. (a) Let X ⊆ Z n and Y ⊆ Rm be two given sets, where Z n denotes the set of n-dimensional
integer vectors and Rm denotes the set of m-dimensional real vectors. Let the problem

(WD) min{g(y) : y ∈ Y ⊆ Rm }

be the weak dual of the integer programming problem

(IP) max{ f (x) : x ∈ X ⊆ Z n },

where g(·) and f (·) are two continuous functions. Suppose that x∗ ∈ X and y∗ ∈ Y satisfy
the condition f (x∗ ) = g(y∗ ). Prove that x∗ is an optimal solution of (IP) and y∗ is an optimal
solution of (WD). [5]

(b) The Record-a-Song Company has contracted with a rising star to record eight songs. The
durations of the songs are 8, 3, 5, 5, 9, 6, 7, and 12 minutes, respectively. Record-a-Song
uses a two-sided cassette tape for the recording. Each side has a capacity of 30 minutes.
The company would like to distribute the songs between the two sides so that the total
length of the songs on each side is about the same. Formulate this problem as an integer
programming problem. Clearly define your variables, objective and constraints. (You are
NOT required to solve this integer programming problem.) [8]

(c) Use the cutting-plane method to solve the following integer programming problem:

max 30x1 + 12x2

s.t. 30x1 + 24x2 ≤ 126,
x1 , x2 ≥ 0 and integer.

[12]

Page 4 Turn over

 A25086 Any Calculator

4. (a) Give a detailed account and justification of the individual steps of the primal-dual algo-
rithm. Include the definition of the set of admissible indices, formulation of the restricted
primal problem and its dual and the optimality criterion. Derive the formula for updating a
dual feasible solution. [14]

(b) Without finding the dual decide with reasoning whether the dual to the linear program
below has an optimal solution. (Hint: add up all equations.)

2x1 − 4x2 − 5x3 + 7x4 → min

3x1 − 2x2 + 4x3 − 8x4 = 7,
−5x1 − x2 − 7x3 + 3x4 = −4,
x1 + x2 − x3 + 2x4 = 5,
x1−4 ≥ 0.

[4]

T
(c) Use the dual feasible solution π = (−2, 1) to run one iteration of the primal-dual algo-
rithm applied to the following linear program:

8x1 + 11x2 + 3x3 + x4 → min

2x1 + x2 − x3 − x4 = 2,
−x1 + 3x2 + x3 − x4 = 1,
x1−4 ≥ 0.

[7]

Page 5 Turn over

 A25086 Any Calculator

5. (a) Define a network, a flow in a network, the value of a flow and the max-flow problem. [6]

(b) Formulate the Ford and Fulkerson algorithm (FFA) for solving the max-flow problem. For-
mulate and prove the Max-Flow Min-Cut Theorem and deduce then the correctness of the
FFA (that is state and prove also the Ford and Fulkerson Theorem). You may assume


that the following lemma has already been proved: For any cut W,W and flow f in the
network N = (V, E, s,t, b) the value of the flow is equal to

∑ f (x, y) − ∑ f (x, y) .
x∈W,y∈W x∈W ,y∈W
(x,y)∈E (x,y)∈E

[10]


(c) Given is the network N of Figure 1 and the cut W,W , where W = {s, a, b, c, d} .


(i) Find the capacity of W,W .


(ii) Find a max-flow in N if it is given that W,W is the unique minimal cut in N . Note
that there are more than one flow of maximal value in N .

(iii) Among all max-flows find one for which the flow on arc (s, b) is minimal. Justify your
answer.

[9]

25
a d
13
20
15 6
s c t
10
9
18 26
12
b e
Figure 1

Page 6 Turn over

 A25086 Any Calculator

6. (a) What is the relative error of an algorithm with respect to an instance of a combinatorial
optimisation problem? What is an ε - approximate algorithm? [5]

(b) Formulate the algorithm TREE for the ∆TSP (the Travelling Salesman Problem satisfy-
ing the triangle inequality) and prove that it is 1-approximate. You may assume that the
following theorem has already been proved:




”Let Kn , ai j be an instance of the ∆TSP for a symmetric matrix A = ai j . If G =


(V, E) is an Eulerian spanning graph for A = ai j then every tour embedded in an Eule-
rian walk in G has length not exceeding the cost of G”. [8]

(c) Use Christofides’ algorithm to find two tours for the ∆TSP when the cities are: a =
(0, 0) , b = (2, 2) , c = (4, 3) , d = (8, 1) , e = (3, 6) . Describe each tour as a sequence
of cities starting from a and find also its length. Compare the two tours. You may
√ √ √
find the following approximations of radicals helpful: 5 ≈ 2.236, 10 ≈ 3.162, 37 ≈
√
6.083, 50 ≈ 7.071. You may leave your results in the form of a sum of radicals. [7]

(d) Use your results in question (c) to find an upper and lower bound for the minimal length
of a tour for the ∆TSP in that question. [5]

Page 7 End of paper

 A25086
2016
16(UoB) Any Calculator

1. (a) Let Z5+ denote the 5-dimensional nonnegative integer space, i.e., Z5+ = {x ∈ R5 : xi ≥
0 and integer, i = 1, . . . , 5}. Let X be the set

X = {x ∈ Z5+ : 9x1 + 12x2 + 8x3 + 17x4 + 13x5 ≥ 50}.

Find a valid inequality for X cutting off the point xe = (0, 25

6 , 0, 0, 0). [5]

(b) Let P be the set of x = (x11 , x12 , x13 , x21 , x22 , x23 , x31 , x32 , x33 ) ∈ R9 , where xi j satisfy the
following system:
3
∑ xi j = 1 for j = 1, 2, 3
i=1
3
∑ xi j = 1 for i = 1, 2, 3
j=1

0 ≤ xi j ≤ 1 for i, j = 1, 2, 3.

Use total unimodularity (TU) theory to show that any extreme point of the set P is integral.
[8]

(c) Use Branch and Bound Method to solve the following integer programming problem:

(IP) z∗ = max 2x1 − x2

s.t. 2x1 − 2x2 ≤ 3
x2 ≤ 4
x1 , x2 ≥ 0 and integer.

(You may solve all linear programming relaxation problems graphically.) [12]

Page 2 Turn over

 A25086 Any Calculator

2. (a) Let Zn denote the set of n-dimensional integer vectors. Let c ∈ Rn and b ∈ Rm be given
vectors and A be a given m × n matrix. Show that the integer programming problem

(P1) max{cT x : Ax ≤ b, x ≥ 0, x ∈ Zn }

and the linear programming problem

(P2) min{bT y : AT y ≥ c, y ≥ 0, y ∈ Rm }

form a weak dual pair. [5]

(b) Use the preprocessing techniques (tightening bounds, checking redundancy, and variable
fixing) to solve the following integer programming problem:

max 4x1 + 3x2 − 2x3

s.t. 4x1 − 3x2 + 6x3 ≤ 12
2x1 + 2x2 + 2x3 ≤ 15
3x1 + 2x3 ≤ 13
0 ≤ x1 ≤ 4
0 ≤ x2 ≤ 1
0 ≤ x3
x1 , x2 , x3 ≥ 0 and integer.

[8]

(c) Use Dynamic Programming Method to solve the following integer programming problem

max 28.2x1 + 27.8x2 + 14.4x3

s.t. 2x1 + 2x2 + x3 ≤ 4
x1 , x2 , x3 ≥ 0 and integer.

[12]

Page 3 Turn over

 A25086 Any Calculator

3. (a) Consider the following problem:

(P) max x1 + x2 + x3
3
[
s.t. x∈ Sj
j=1
0 ≤ xi ≤ 10, i = 1, 2, 3,
 
x
 1  3
 ∈ R and
where x =  x2 

x3

S1 = {x ∈ R3 : x1 + 2x2 + 3x3 ≤ 8},

S2 = {x ∈ R3 : 3x1 − 2x2 + 4x3 ≤ 10},
S3 = {x ∈ R3 : −5x1 − 2x2 − 7x3 ≤ −5}.

Formulate the problem (P) as an integer programming problem. (You are NOT required
to solve this integer programming problem.) [5]

(b) Solve the following 0-1 integer programming problem by using logical inequalities.

max 5x1 − 8x2 + 6x3 − 2x4

s.t. 7x1 + 3x2 − 4x3 − 2x4 ≤ 1
−2x1 + 7x2 + 3x3 + x4 ≤ 6
− 2x2 − 3x3 − 6x4 ≤ −5
3x1 − 2x3 ≥ −1
xi ∈ {0, 1}, i = 1, ..., 4.

[8]

(c) Use Cutting-Plane Method to solve the following integer programming problem:

max 15x1 + 6x2

s.t. 10x1 + 8x2 ≤ 42
x1 , x2 ≥ 0 and integer.

[12]

Page 4 Turn over

 A25086 Any Calculator

4. (a) Define the dual to a general linear program (which includes both equations and inequali-
ties and both nonnegative and free variables). [5]

(b) Formulate the weak and strong duality theorems (their proofs are not required). [4]

(c) State and prove the complementary slackness theorem. [8]

(d) For the linear program below find its dual. Then solve the dual problem without needing
to resort to the simplex method and use the complementary slackness theorem to find an
optimal solution and the optimal objective function value of the primal problem.

3x1 + x2 + 7x3 − x4 −→ min

x1 + 2x3 + x4 ≥ 4
2x1 − x2 + 3x4 = 10
x1 ≥ 0
x3 ≥ 0

[8]

Page 5 Turn over

 A25086 Any Calculator

5. (a) Define the max-flow problem in a network (MFP) and all concepts you use in this defini-
tion. [7]

(b) Define the node-arc incidence matrix of a digraph and then use it to prove that every MFP
can be formulated as a linear program. [7]

(c) Prove that a max-flow exists in every network with finite capacities of arcs leaving the
source. [3]

(d) In the network of Figure 1, where the encircled numbers indicate the capacities of indi-
vidual arcs, run exactly one iteration of the Ford and Fulkerson algorithm starting from
the flow given by the free-standing numbers. Write down a full record of the run of this
iteration. When scanning the labels use the first-in first-out principle. Use your record to
determine an augmenting path and the value by which the value of the current flow can
be increased using this path. [8]

Page 6 Turn over

 A25086 Any Calculator

6. (a) Define an independence system and the term combinatorial optimisation problem asso-
ciated with an independence system. [4]

(b) Give a precise formulation of the greedy algorithm for solving combinatorial optimisation
problems associated with independence systems. What is a matroid? [6]

(c) State the Exchange Proposition and Rank Proposition in independence systems. Prove
that in every independence system the Rank Proposition holds if the Exchange Proposi-
tion holds. [6]

(d) Consider the system of seven points a, b, c, d, e, f , g and seven lines (line segments ab,
ac, ad , bc, be, c f and the circle) shown in Figure 2. Note that point g is the intersection
of the lines ad , be and c f . Let S = (E, F ), where E = {a, b, c, d, e, f , g} and a subset M
of E is in F if and only if one of the following is true: |M| < 3 or (|M| = 3 and none of the
seven lines passes through all three points in M ). [9]

(i) Show that S is a matroid.

(ii) Formulate a combinatorial optimisation problem associated with this matroid.

(iii) Suppose that the weights of the elements of E are w1 ≥ w2 ≥ ... ≥ w7 > 0. Show
that the optimal value in the combinatorial optimisation problem in (ii) is either w1 +
w2 + w3 or w1 + w2 + w4 .

f e
g

b c
d

Figure 2
Page 8 End of paper
 A25086
17(UoB)
2017
Any Calculator

1. (a) Let P be the set of x = (x11 , x12 , x13 , x21 , x22 , x23 , x31 , x32 , x33 ) ∈ R9 , where xi j satisfy the
following system:
3
∑ xi j = 1 for j = 1, 2, 3
i=1
3
∑ xi j = 1 for i = 1, 2, 3
j=1
0 ≤ xi j ≤ 1 for i, j = 1, 2, 3.

Use total unimodularity (TU) theory to show that any extreme point of the set P is an
integer vector. [7]

(b) Consider the integer programming problem

z∗ = max 23x1 + 40x2 + 14x3 + 20x4 + 3.5x5 + 36x6

s.t. 4x1 + 7x2 + 3x3 + 4x4 + 0.8x5 + 6x6 ≤ 65,
xi ≥ 0 and integer, i = 1, ..., 6.

Find a lower bound for z∗ by using the greedy heuristic method, and an upper bound for z∗
by solving the (dual of) linear programming relaxation of the above integer programming
problem. [9]

(c) There are six cities in region R. The regional council must determine in which cities to build
fire stations. The region wants to build the minimum number of fire stations and ensures
that at least one fire station is within 16 minutes of each city. The times (in minutes)
required to drive between cities are:
 
From to
 

 City1 City2 City3 City4 City5 City6 

 
 City1 0 10 20 30 30 20 
 

 City2 10 0 25 35 20 10  
 

 City3 20 25 0 15 30 20  
City4 30 35 15 0 15 25 
 

 

 City5 30 20 30 15 0 14  
City6 20 10 20 25 14 0

Formulate this problem as an integer programming problem. Clearly define your variables,
objective and constraints. (You are NOT required to solve this problem.) [9]

Page 2 Turn over

 A25086 Any Calculator

2. (a) Prove that y2 + y3 + 2y4 ≤ 6 is a valid inequality for

4
X = {y ∈ Z+ : 4y1 + 5y2 + 9y3 + 12y4 ≤ 34},

4 denotes the 4-dimensional nonnegative integer space, i.e., Z 4 = {x ∈ R4 : x ≥

where Z+ +
0 and integer}. [7]

(b) Let r ≥ 1 and λ ≥ 0 be two integer numbers. Consider the following problem:
r
(Pr (λ )) fr (λ ) = max ∑ c jx j
j=1
r
s.t. ∑ a jx j ≤ λ ,
j=1
x j ∈ {0, 1}, j = 1, ..., r

where c j and a j , j = 1, . . . , r are given nonnegative numbers, and a j , j = 1, . . . , r are

integer numbers. Prove that

(i) if λ < ar , then

fr (λ ) = fr−1 (λ );

(ii) if λ ≥ ar , then
fr (λ ) = max{ fr−1 (λ ), cr + fr−1 (λ − ar )}.

[9]

(c) Use Branch and Bound Method to solve the following integer programming problem:

(IP) z∗ = max 2x1 − x2

s.t. 2x1 − 2x2 ≤ 3
x2 ≤ 4
x1 , x2 ≥ 0 and integer.

(You may solve all linear programming relaxation problems graphically.) [9]

Page 3 Turn over

 A25086 Any Calculator

3. (a) Solve the following 0-1 integer programming problem by using logical inequalities.

max 10x1 − 8x2 − 7x3 + 9x4

s.t. 6x1 + 7x2 − 5x3 − 3x4 ≤ 2,
−3x1 + 6x2 + 3x3 + 2x4 ≤ 5,
− 4x2 − 7x3 − 3x4 ≤ −8,
−4x1 + 3x3 − x4 ≤ −1,
xi ∈ {0, 1}, i = 1, ..., 4.

[7]

(b) A set of n jobs must be carried out on a single machine that can do only one job at a time.
Each job j takes p j hours to complete. Given job weights w j for j = 1, ..., n, in what order
should the jobs be carried out so as to minimise the weighted sum of their starting times?

Formulate this scheduling problem as a mixed integer programme. Clearly define your
variables, objective and constraints. (You are NOT required to solve this integer pro-
gramming problem.) [9]

(c) Use the cutting-plane method to solve the following integer programming problem:

max 10x1 + 4x2

s.t. 15x1 + 12x2 ≤ 63,
x1 , x2 ≥ 0 and integer.

[9]

Page 4 Turn over

 A25086 Any Calculator

4. (a) Give a definition of a linear program in standard form (SLP). Then state the dual to the
SLP. Describe the meaning of all symbols you use in your answer. [5]

(b) State the individual steps of the primal-dual algorithm (PDA), including the input and out-
put, and prove the infeasibility criterion in the PDA. [9]

(c) Use duality theory to solve the linear program

3x1 − αx2 + 2x3 −→ min

x1 + 4x2 − x3 = 1
2x1 + x3 = 7
x2 ≥ 0

where α is a real parameter. For every real value of α either find an optimal solution and
optimal function value or show that this LP is unbounded or that is infeasible. [6]

(d) Apply the PDA to solve the linear program

3x1 + 4x2 + x3 −→ min

2x1 − 4x2 + 4x3 = 3
−5x1 + 5x2 − 7x3 = 4
x1−3 ≥ 0

T
starting from the dual feasible solution π = (−1, 0) . Solutions found by other methods
will not be credited. [5]

Page 5 Turn over

 A25086 Any Calculator

5. (a) Define the transportation problem (describe all symbols you use). Then prove that every
transportation problem has an optimal solution whenever it has a feasible solution. [8]

(b) The algorithm obtained by an application of the primal-dual algorithm to the transportation
problem is called ALPHABETA. State this algorithm (no proofs are required here). [5]

(c) Algorithm ALPHABETA has been applied to the transportation problem below.

70 100 100 αi
80 6 7 12 .
40 3 2 8 .
50 4 1 3 .
100 6 7 8 .
βj 2 . 5

The current network and maximum flow found by the algorithm are shown in Figure 1. Use
this figure to find the missing values of αi and β j and then carry out the remaining work
of ALPHABETA. Write down the optimal solution found by ALPHABETA and calculate the
minimal total transportation cost. [7]

(d) Given is the transportation problem

25 80 85 15
45 8 1 4 4
70 2 3 0 3
90 9 3 5 8

and the transportation plan

Page 6 Turn over

A25086 Any Calculator

25 80 85 15
45 30 15
.
70 25 45
90 50 40
Using the complementary slackness theorem or otherwise, decide whether this plan is
optimal. If it is not optimal then find a cheaper plan. Show your working. [5]

70
70
80 0 70
70
40
40 40 40
100
t
50
s
50
50
100

100 50 100

50

Figure 1

Page 7 Turn over

 A25086 Any Calculator

6. (a) What is the relative error of an algorithm with respect to an instance of a combinatorial
optimisation problem (minimisation)? What is an ε - approximate algorithm? [5]

(b) In this question ∆TSP stands for the travelling salesman problem satisfying the triangle
inequality. Formulate Christofides’ algorithm for solving ∆TSP, including the input and out-
put, and prove that it is 21 - approximate. You may assume that the following statement
has already been proved: Let (Kn , (ai j )) be an instance of ∆TSP for a symmetric ma-
trix A = (ai j ). If G = (V, E) is an Eulerian spanning graph for A then every tour in Kn
embedded in an Eulerian walk in G has length not exceeding the cost of G. [10]

(c) Draw separately (sketches are sufficient) all Hamilton cycles in the graph of Figure 2. [4]

(d) Use Christofides’ algorithm to find a tour for the ∆TSP when the cities are: a = (2, 6) , b =
(0, 1) , c = (5, 0) , d = (4, 5) , e = (3, 3) . Describe the tour as a sequence of cities starting
from a and find also the length of the tour. You may leave the length in the form of a sum
of radicals. Then use your result to find a lower and an upper bound for the length of an
optimal tour.

[6]

Page 8 Turn over

 18(UoB)
2018
Any Calculator

1. (a) Let A be a given m × n matrix, and let b ∈ Rm and c ∈ Rn be given vectors. Consider the
integer programming problem

(IP) max{cT x : Ax ≤ b, x ∈ Z+
n
},

n denotes the n-dimensional nonnegative integer space, i.e., Z n = {y ∈ Rn : y ≥

where Z+ +
0 and integer}. Prove that the following linear programming problem is a weak dual to the
problem (IP)
(LP) min{bT y : AT y ≥ c, y ≥ 0}.

[7]

(b) Consider the following two 0-1 integer programming problems: max{cT x : x ∈ X1 } and
max{cT x : x ∈ X2 } where X1 and X2 are given as

X1 = {x ∈ R4 : 97x1 + 32x2 + 25x3 + 20x4 ≤ 139, xi = 0 or 1 for i = 1, 2, 3, 4},

X2 = {x ∈ R4 : x1 +x2 +x3 ≤ 2, x1 +x2 +x4 ≤ 2, x1 +x3 +x4 ≤ 2, xi = 0 or 1 for i = 1, 2, 3, 4}.

Prove that these two integer programming problems have the same feasible sets, i.e.,
X1 = X2 . [8]

(c) Solve the following problem by using the preprocessing techniques (tightening bounds,
checking redundancy and variable fixing):

Maximise 4x1 + 3x2 − 2x3

subject to 4x1 − 3x2 + 6x3 ≤ 12,
2x1 + 2x2 + 2x3 ≤ 15,
3x1 + 2x3 ≤ 13,
x1 ≤ 4,
x2 ≤ 1,
x1 , x2 , x3 ≥ 0 and integer.

[10]

A25086 Page 2 Turn over

 Any Calculator

2. (a) Consider the following set:

4
X = {y ∈ Z+ : 24y1 + 5y2 + 9y3 + 12y4 ≤ 44},

4 denotes the 4-dimensional nonnegative integer space, i.e., Z 4 = {y ∈ R4 : y ≥

where Z+ +
0 and integer}. Prove that
4y1 + y2 + y3 + 2y4 ≤ 8

is a valid inequality for X. [7]

(b) Use total unimodularity theory to show that the following linear programming problem has
an integer optimal solution:

Maximise x1 + x2 + x3 + x4 + x5 + x6 + x7
subject to x1 + x3 − x5 ≤ 24,
− x2 − x3 + x4 ≤ 20,
x1 − x2 + x6 ≤ 20,
x4 − x5 + x7 ≤ 10,
0 ≤ xi ≤ 10, i = 1, ..., 7.

[9]

(c) Solve the LP relaxation (by geometric method) of the following integer programming prob-
lem:

z∗ = max 2x1 − x2
s.t. x2 ≤ 4,
2x1 − 2x2 ≤ 3,
x1 , x2 ≥ 0 and integer.

Based on a fractional component of the optimal solution of the LP relaxation, perform only
one step of the Branch & Bound Algorithm: Split the integer programming problem into
two branch problems, solve these two branch problems, and find the upper bound for z∗ . [9]

A25086 Page 3 Turn over

 Any Calculator

3. (a) Consider the following 0-1 integer programming problem:

z = max 10x1 + 20x2 + 5x3 + 12x4 + 4x5 + 30x6

s.t. 4x1 + 3x2 + 5x3 + 8x4 + 2x5 + 3x6 ≤ 12,
xi ∈ {0, 1}, i = 1, ..., 6.

Find the primal bound (i.e. the lower bound) for this problem by the greedy heuristic
method. [7]

(b) Solve the following integer programming problem by Dynamic Programming

max 11x1 + 6x2 + 12x3

s.t. 2x1 + x2 + 2x3 ≤ 4,
x1 , x2 , x3 ≥ 0 and integer.

Is the optimal solution to this integer programming problem unique? [9]

(c) Consider the following Integer programming problem:

(P) z∗ = min −7x1 − 9x2

s.t. −x1 + 3x2 ≤ 6,
7x1 + x2 ≤ 35,
x1 , x2 ≥ 0 and integer.

The linear programming relaxation of (P) is solved by simplex method, and the optimal
simplex tableau is given as follows, where s1 and s2 are slack variables

x1 x2 s1 s2 RHS
28 15
z 0 0 − 11 − 11 −63
.
7 1 7
x2 0 1 22 22 2
1 3 9
x1 1 0 − 22 22 2

Solve the problem (P) by the cutting plane method. [9]

4. (a) Without finding the dual to the following primal linear program, decide if the dual has an
optimal solution or not. (Hint: sum the constraints). [4]

A25086 Page 4 Turn over

 Any Calculator

x1 + x2 + x3 → min
2x1 + x2 − x3 = 1
−x1 − 2x2 + 2x3 = 2
−x1 + x2 − x3 = 3
x1−3 ≥ 0

(b) Give the definition of a linear program in standard form (SLP), then give the dual to the
SLP. Describe the meaning of all symbols you use in your answer. [5]

(c) Construct the dual to the following primal linear program and solve the dual without using
simplex (by the graphical method or otherwise). Then, use complementary slackness to
find an optimal solution to the primal and the optimal objective function value to the primal.
[8]

2x1 + 6x2 − 2x3 → min

−1/3x1 + 3x2 + x3 = 1
x1 − x2 − x3 = 1
x1−3 ≥ 0

(d) State the steps of the primal-dual algorithm including input and output. Prove the infeasi-
bility criterion. [8]

5. (a) Define the node-arc incidence matrix of a digraph. Use it to prove every max-flow problem
can be formulated as a linear program. [8]

(b) Do two runs of the Ford and Fulkerson algorithm for the network given, starting from
the zero flow. Write down a full record of the runs and record the updated flows on the
question sheet. Use the “first-in first-out” principle when scanning nodes. Determine an
augmenting path in each iteration and calculate by how much the current flow value can
be increased. [8]

A25086 Page 5 Turn over

 Any Calculator

a 40 d

20 10 10 15 50

s 20 e 10 t
b 15

30 20
20 15 10

c 10
f

(c) Given is a network N and a cut W,W where W = {s, a, b, c, d}.

a 15 d

18 15 20 20

s c t

20 15 25 20

b 10 e

(i) Find the capacity of W,W . [3]


(ii) Is W,W a minimal cut? Justify your answer. If not, propose a cut with a smaller
capacity. [6]

A25086 Page 6 Turn over

 Any Calculator

6. (a) (i) What is the relative error of an algorithm with respect to an instance of a combina-
torial optimisation problem (minimisation)? [2]

(ii) What is an ε -approximate algorithm? [3]

(b) Use Christofides’ algorithm to find a tour of the 4-TSP for cities a = (6, 2) , b = (1, 0) , c =
(0, 5) , d = (5, 4) and e = (3, 3). Describe the tour as a sequence of cities and give the
length of the tour as a sum of radicals. Use your results to give upper and lower bounds
on the length of an optimal tour. [6]

(c) Define an “independence system” and a “combinatorial optimisation problem associated

with an independence system”. [4]

(d) Give a precise formulation of “GREEDY” for solving combinatorial optimisation problems
associated with an independence system. What is a matroid? [5]

(e) State the Exchange Proposition and Rank Proposition in an independence system. Prove
that in every independence system, the exchange proposition implies the rank proposition.
[5]

A25086 Page 7 End of paper

 21(UoB)
1. (a) Are the following matrices totally unimodular? Explain.
 
−1 1 0
 
(i) 
 1 0 −1 
,
1 −1 1
 
1 −1 0 0 1 −1
 
 −1 0 1 −1 0 1 
 
(ii)  0 −1 0 0 1 0 .
 
 
 0 0 1 0 0 0 
 
1 −1 0 0 1 −1

[10]

(b) Given the following IP in the standard form,

max c̄T x̄
s.t. Ax̄ = b̄
x̄ ∈ Zn+ ,

we transform it into an equivalent program

max c̄T x̄
s.t. A0 x̄ ≤ b̄0
x̄ ∈ Zn+

by replacing each equality constraint ai1 x1 + ai2 x2 + . . . + ain xn = bi with two opposite
inequality constraints ai1 x1 + ai2 x2 + . . . + ain xn ≤ bi and −ai1 x1 − ai2 x2 − . . . − ain xn ≤
−bi . If the matrix A is known to be totally unimodular, explain why A0 is also totally
unimodular. [5]

(c) Solve the following BIP using logical inequalities:

max 11x1 + 3x3 − 5x4

s.t. −2x1 + 5x2 + x3 − x4 ≤ 2
2x1 − 3x2 + x3 − 2x4 = 0
x1 , x2 , x3 , x4 ∈ {0, 1}.

[10]

A34323alt Page 2 Turn over

2. (a) Consider the network with nodes N = {s, 1, 2, 3, 4,t} and arcs

A = {(s, 1), (s, 2), (1, 2), (1, 3), (2, 4), (3, 4), (4, 3), (3,t)}.

The arc lengths are given in the following table:

ds1 ds2 d12 d13 d24 d34 d43 d3t

5 10 4 12 3 5 7 2

Formulate a BIP that finds the shortest path from s to t . (Do not solve the program.) [7]

(b) For the following nonlinear binary integer program, formulate an equivalent (linear) BIP.
You need to provide an explanation why the new program is equivalent to the initial one.

max 6x1 − x2 + 2x1 x2 + x1 x2 x3 − 2x32

s.t. 3x1 + 2x2 + x1 x2 + 4x3 ≤ 7
−x1 + 5x2 − x3 ≤ 4
x1 , x2 , x3 ∈ {0, 1}

[8]

(c) Solve the following IP using the cutting plane algorithm with Gomory cuts. Provide details
how pivots are chosen and how cuts are generated.

max 3x1 + x2 + 7x3

s.t. 2x1 + x2 + 2x3 ≤ 7
−x1 + 2x2 − x3 ≤ 4
x1 , x2 , x3 ∈ Z+

[10]

A34323alt Page 3 Turn over

3. (a) Consider the following linear programming problem: [8]

min 6x1 + 2x2 + 5x3 + 15x4 + 3x5

s.t. 3x1 − x2 + x3 + 8x4 − x5 = 3

− x1 − x2 + x3 + 2x4 = 1
x1 , x2 , x3 , x4 , x5 ≥ 0

Solve this problem by the primal-dual algorithm using the dual feasible solution π =
(1.5, 1.5)> . Write a full record of each iteration.

(b) Consider a network without directed cycles, where the capacity of any arc (including the
arcs leaving the source) can be either +∞ or a positive integer. Prove that if such network
does not contain a directed path from the source to the sink along which all capacities are
+∞, then the Ford-Fulkerson algorithm stops after a finite number of iterations. [8]

(c) Consider the following network, where the capacities of the arcs are given in rectangles,
and the initial flows through the arcs are given by free-standing numbers. [9]
5
a d
35

0 5 10
0 5 5 5
21 5 +∞

20 20 35
s b e t
20 20 35

35 12 10
5 0 13 15
100 12 10

23
c f
28

(i) Run the Ford-Fulkerson algorithm for this network, starting with the given initial flow,
until it stops. For each iteration, record the work of the labelling algorithm, the re-
sulting augmenting path and the changes of flows through the arcs (drawing whole
networks is not necessary). What is the value of the resulting maximal flow?

(ii) Using your working in (i), find a minimal cut for this network. Justify.

A34323alt Page 4 Turn over

4. (a) Formally define the network, which is used at each iteration of the ALPHABETA algo-
rithm to decide about the optimality of the current dual feasible solution (α, β ). Explain
all notation that you use, and state the condition of optimality of (α, β ) in terms of this
network. [5]

(b) Consider the transportation problem with 3 producers and 4 customers, where the capac-
ities of the producers are a1 = 3, a2 = 4 and a3 = 6, the demands of the customers are
b1 = 5, b2 = 3, b3 = 2 and b4 = 3 and the cost matrix is [14]
 
4 1 5 8
 
C=
 2 5 3 1.

7 3 4 5

(i) Let the following transportation plan be given:

 
0 3 0 0
 
X =
1 0 0 3 .

4 0 2 0

Using the complementary slackness and dual feasibility conditions, decide if this
plan is optimal.

(ii) Perform one iteration of the ALPHABETA algorithm starting from the dual feasible
solution (α, β ) where α = (−1, −1, 1)> and β = (3, 2, 3, 2)T . Show your work-
ing: draw the network used in the update (with a maximal flow), and explain how
α and β are updated. Check the optimality of the resulting dual feasible solution.
Justify.

(c) Consider a metric travelling salesman problem and let c(τ ∗ ) be the cost of the optimal
travelling salesman tour τ ∗ . Suppose that T is a minimal spanning tree of the complete
graph on which τ ∗ is sought, and that M is a perfect matching of minimum cost on the set
of all nodes of T that have odd degrees with respect to T . Prove that c(τ ∗ ) ≥ 23 (c(T ) +
c(M)), where c(T ) is the cost of T and c(M) is the cost of M . [6]

A34323alt Page 5 End of paper

 Any Calculator
22(UoB)
1. (a) Consider the following binary integer program (BIP).

max 2x1 + 2x2 + 3x3 − 7x4

s.t. 2x1 + x2 + 2x3 + 3x4 ≤ 6
3x1 + 2x2 + 4x3 + 2x4 ≤ 7
x1 , x2 , x3 , x4 ∈ {0, 1}

(i) Show that in the optimal solution we must have x4 = 0.

(ii) Setting x4 = 0, explain why the first constraint becomes redundant and hence can
be removed.

(iii) Solve the remaining Binary Knapsack Problem using the dynamic programming
method. [10]

(b) Decide whether the following matrices are totally unimodular (TU). Explain!
 
1 0 −1 0 0
 
 −1 1 0 0 −1 
(i)  
 0
 1 0 1 −1  
0 −1 1 0 1
 
1 0 0 1 −1
 
 −1 1 0 0 1 
(ii) 
 0 −1 0 1
 [8]
 0 

1 −1 1 0 −1

(c) (i) Consider the following road network connecting four cities V = {s, a, b,t} with one-
way roads. The roads and their lengths are shown in the following table

road sb as at ba bt ts
length 150 30 350 100 730 550

Formulate a binary integer program (BIP) determining the shortest path from s to t .
Clearly explain the meaning of variables, objective function, and constraints. Do not
solve the resulting BIP.

(ii) Explain why this BIP can be solved by the simplex method. [7]

A34323 Page 2 Turn over

 Any Calculator

2. (a) Transform the following non-linear binary integer program (BIP) into an equivalent linear
BIP. Explain the meaning of new variables and constraints. Do not solve the resulting
linear BIP.
max 2x12 + 2x1 x2 − x33
s.t. 3x1 − x1 x2 + x1 x2 x3 ≤ 3
x2 x3 + x32 ≤ 2
x1 , x2 , x3 ∈ {0, 1}

[6]

(b) Solve the following binary integer program (BIP) using logical inequalities.

max 11x1 − 3x2 + 5x3 + x4

s.t. 2x1 + 8x2 − 2x3 − 5x4 ≤ 2
3x1 − x2 + 2x3 − 4x4 ≥ 0
2x1 − 2x2 + x4 ≤ 1
x1 , x2 , x3 , x4 ∈ {0, 1}

Provide an explanation how you derive logical inequalities and how you combine them. [6]

(c) Consider the following integer program (IP).

max 5x1 + 3x2 + 2x3

s.t. −x1 + 2x2 + x3 ≤ 6
2x1 + x2 + 2x3 ≤ 5
x1 , x2 , x3 ∈ Z+

Do one iteration of the cutting plane algorithm. Namely,

(i) find the optimal solution of the linear relaxation of this IP using the simplex method;

(ii) write down all available Gomory cuts;

(iii) add the Gomory cut corresponding to the first fractional variable to the tableau;

(iv) renormalise the tableau using the dual simplex method (i.e., bring the tableau into a
state where all right sides are positive).

Have you achieved the optimal solution of the IP? If you have, state the optimal solution
and the optimal value of the objective function. In either case, don’t continue beyond the
first iteration. [13]

A34323 Page 3 Turn over

 Any Calculator

3. (a) Consider a general linear programming problem

min cT x
s.t. Ax = b,
x ≥ 0,
with given real-valued m × n matrix A = (ai j ), n-component vector c and m-component
vector b ≥ 0, and let π be a dual feasible solution. For this problem and the dual feasible
solution π , formulate the dual to restricted primal (DRP) and write down the formula that is
used in the primal-dual algorithm for updating a dual feasible solution. Then prove that this
formula, when applied to a dual feasible solution, results in another dual feasible solution.
Explain any notation that you use. [7]

(b) Consider the following network, where all capacities are equal to 10 (as are the numbers
in rectangles) and the initial flows are given in loose numbers at every arc. Apply the
Ford-Fulkerson algorithm to find a maximal flow through this network starting with the
given initial flow. Write a record of each iteration including the labelling process, the
augmenting paths and the change of flows through arcs (but there is no need to draw the
network in your script). State the value of the maximal flow which you find. [8]
a 10 c
8
10 5 10 5
6
s 10 10 10 t
3 3
10 10 10
10
b 10 d
4

(c) Consider a general transportation problem with m producers and n customers. Let non-
negative m × n matrix X be a feasible transportation plan of this problem and (α, β ),
where α is an m-dimensional real vector and β is an n-dimensional real vector, be an
arbitrary dual feasible solution of this problem. Write out the complementary slackness
conditions for X and (α, β ). For a given feasible transportation plan X , how can these
complementary slackness conditions be used to check whether X is optimal? Justify. [6]

(d) Consider an arbitrary directed graph G . Let V be the set of all nodes of that graph and
F be a collection of sets F ⊆ V such that F = 0/ , or F consists of a single node of G , or
for each a, b ∈ F there is no directed path from a to b and no directed path from b to a.
Prove that (V, F ) is an independence system, but not a matroid. [4]
A34323 Page 4 Turn over
 Any Calculator

4. (a) Suppose that we are given a general transportation problem with m producers and n
customers, and that the producers’ capacities are a1 , . . . , am and the customers’ demands
are b1 , . . . , bn . Prove that a feasible transportation plan for this problem exists if and only
if ∑m n
i=1 ai = ∑ j=1 b j . [6]

(b) Suppose that S = (E, F ), where E is a finite set and F is a collection of subsets of
E , is a matroid, and w : E 7−→ R+ is a function defined on E and taking nonnegative
values. Prove that the greedy algorithm applied to the combinatorial optimisation problem
(S, w) constructs (as its output) a maximal independent set of E for which the function
M(F) = min{w(e) : e ∈ F} has the greatest value among all maximal independent sets
F ⊆ E. [7]

(c) Suppose that the location of the sites a, b, c, d, e, f is given by the following coordinates
on the plane: a = (2, 2), b = (3, 2), c = (3, 5), d = (5, 4), e = (7, 2), f = (7, 7). For your
convenience the following table of distances between these sites {a, b, c, d, e, f } is also
given: [12]

a b c d e f
√ √ √
a 0 1 10 13 5 50
√ √
b 1 0 3 8 4 41
√ √ √
c 10 3 0 5 5 20
√ √ √ √ √
d 13 8 5 0 8 13
√
e 5 4 5 8 0 5
√ √ √ √
f 50 41 20 13 5 0
√ √ √ √
You may also find it useful that: 5 ≈ 2.24, 8 ≈ 2.83, 10 ≈ 3.16, 13 ≈ 3.61,
√ √ √
20 ≈ 4.47, 41 ≈ 6.40, 50 ≈ 7.07. Using this data perform the following tasks:

(i) Apply the Christofides algorithm to find 4 essentially different travelling salesman
tours around these 6 sites. Write a detailed description of your application. Compute
the approximate costs of all tours which you find (round to one decimal place).

(ii) Which tightest possible upper and lower bounds on the optimal cost of a travel-
ling salesman tour can you derive under the condition that you can use only the
costs of the 4 tours found in (i) and the fact that the Christofides algorithm is 1/2-
approximate? State the bounds (giving their approximate numerical values). Explain
which tours you use.

A34323 Page 5 End of paper

 Any Calculator
19(JBJI)
1. (a) Solve the following 0-1 integer programming problem by using logical inequalities.

max 8x1 − 6x2 − 6x3 + 5x4

s.t. 7x1 + 3x2 − 4x3 − 2x4 ≤ 1,
−2x1 + 7x2 + 3x3 + x4 ≤ 6,
−2x2 − 3x3 − 6x4 ≤ −5,
3x1 − 2x3 ≥ −1,
[8]
x1 , x2 , x3 , x4 ∈ {0, 1}.
(b) (i) Give the definition of a totally unimodular matrix. [2]

(ii) Is the following matrix totally unimodular?

 
−1 1 1 −1
 
0 −1 0 1
A=
0

0 0 1
[3]
 
0 1 0 0
(c) Consider the integer programming problem

(IP) z∗ = max x1 + x2
s.t. 5x1 + 8x2 ≤ 40,
2x1 + x2 ≤ 12,
x1 , x2 ≥ 0 and integer.

It is known that (x1 , x2 )T = ( 56 20 T

11 , 11 ) is the optimal solution to the linear programming
relaxation of the problem (IP). Use the Branch and Bound method to solve the problem
(IP) by branching the problem according to x1 = 56
11 . [12]

AUoBM321 Page 2 Turn over

 Any Calculator

2. (a) Consider the integer programming problem

z∗ = max 20x1 + 35x2 + 5x3 + 16x4 + 1.95x5 + 18x6

s.t. 5x1 + 7x2 + 5x3 + 8x4 + x5 + 6x6 ≤ 45,
xi ≥ 0 and integer, i ∈ {1, . . . , 6}.

(i) Find a lower bound for z∗ by using the greedy heuristic method. [4]

(ii) Find an upper bound for z∗ by solving the (dual of the) associated linear program-
ming relaxation. [4]

(b) Prove that y2 + y3 + 2y4 ≤ 6 is a valid inequality for

X = {y ∈ Z4+ | 4y1 + 5y2 + 9y3 + 12y4 ≤ 34},

where Z4+ denotes the 4-dimensional nonnegative integer space, i.e.,

Z4+ = {x ∈ R4 | x ≥ 0 and integer}. [5]

(c) Use the dynamic programming method to solve the following integer knapsack problem:

max 6x1 + 9x2 + 19x3

s.t. x1 + 2x2 + 3x3 ≤ 4,
x1 , x2 , x3 ≥ 0 and integer.

Find an optimal solution and corresponding optimal objective value of this integer pro-
gramming problem. [12]

Note: Full marks will only be awarded to question 2(c) if you show your working and in
particular evaluate all variables which the relevant algorithm initializes.

AUoBM321 Page 3 Turn over

 Any Calculator

3. (a) The Record-a-Song Company has contracted with a rising star to record eight songs.
The durations of the different songs are 8, 3, 5, 5, 9, 6, 7, and 12 minutes, respectively.
Record-a-Song uses a two-sided cassette tape for the recording. Each side has a capacity
of 30 minutes. The company would like to distribute the songs between the two sides such
that the length of the songs on each side is about the same. Formulate this problem as
an integer programming problem. Clearly define your variables, objective and constraints.
(You are NOT required to solve this integer programming problem.) [8]

(b) Let A denote an m × n matrix, let c ∈ Rn and b ∈ Rm . Consider the integer programming
problem
(IP) max{cT x | Ax ≤ b, x ∈ Zn+ }

and the linear programming problem

(D) min{bT y | AT y ≥ c, y ≥ 0, y ∈ Rm },

where
Zn+ = {x ∈ Rn | x ≥ 0 and integer}.

Assume that both (IP) and (D) are feasible. Prove that (D) is a weak dual of (IP). Provide
reasoning for every step of your proof. [5]

(c) Use the cutting-plane method to solve the following integer programming problem:

max 5x1 + 2x2

s.t. 5x1 + 4x2 ≤ 21,
x1 , x2 ≥ 0 and integer. [12]

AUoBM321 Page 4 Turn over

 Any Calculator

4. (a) The restricted primal (RP) within the primal-dual algorithm is given below:

m
(RP) min ξ = ∑ xia
i=1
s.t. ∑ ai j x j + xia = bi, i = 1, . . . , m,
j∈J
xia ≥ 0, j ∈ J.

The infeasibility criterion states:

If ξ min > 0 and (∀ j 6∈ J) π T A j < 0, then MP = 0/ , where ξ min is the optimal objective
function value to the restricted primal and π is an optimal solution to the dual to the
restricted primal. You may assume that π is a known feasible solution to the dual (D)
given below:

(D) max w = π T b
s.t. π T A ≤ cT .

Prove the infeasibility criterion. [5]

(b) Find an optimal solution to the following linear program using the primal-dual algorithm,
T
starting with the dual feasible solution π = (−2, 2) . [15]

min 6x1 + 7x2 − 3x3

s.t. x1 − x2 + 2x3 = 1,
4x1 + 2x2 − x3 = 2,
x1 , x2 , x3 ≥ 0.

Question 4 continued overleaf.

AUoBM321 Page 5 Turn over

 Any Calculator

(c) Find an optimal solution to the following linear program using the primal-dual algorithm,
starting with the dual feasible solution π1 = 5/2. [5]

min 3x1 − 2x2

s.t. x1 − x2 = 1,
x1 , x2 , ≥ 0.

5. (a) Let N = (V, E, s,t, b) be a network. Prove that the value of a max-flow is equal to the


capacity of any min-cut. You may assume the relation v ( f ) ≤ c W,W holds for every


flow and every cut in N . You may also assume the following holds for any cut W,W and
flow f :

v( f ) = f (x, y) − f (x, y) . [5]

∑ ∑
x∈W,y∈W :(x,y)∈E x∈W ,y∈W :(x,y)∈E

(b) Starting from the given flow, find a max-flow in the network below using the Ford and
Fulkerson algorithm. [15]

4
a c
(6) 6
2
(8)
(5)
s 2 (2) 2 (3) t
5 1
(6)
3 (3)
b d
(8)

(c) Try to apply the Ford and Fulkerson algorithm to the figure below starting from the given
flow. What problem do you encounter? Can you give a reason for the problem? [5]

a
(1) 0
1 1 0 (1)
s (1) (1) s
0( 1
1)
(1)
b

AUoBM321 Page 6 Turn over

 Any Calculator

6. (a) Prove that the transportation problem given below has a feasible solution if and only if it
is balanced, that is if ∑m n
i=1 ai = ∑ j=1 b j . [5]

m n
∑ ∑ ci j xi j −→ min
i=1 j=1
n
∑ xi j = ai; i = 1, . . . , m
j=1
m
∑ xi j = b j ; j = 1, . . . , n
i=1

xi j ≥ 0; i = 1, . . . , m; j = 1, . . . , n

(b) Solve the following transportation problem using ALPHABETA. [15]

40 50 50
20 8 9 14
30 6 12 9
40 10 13 16
50 9 7 5

(c) The transportation problem below is not balanced. Convert it to an equivalent balanced
transportation problem and solve it using ALPHABETA. Give your answer in terms of the
original transportation problem. [5]

20 10
40 5 6
30 4 3

AUoBM321 Page 7 End of paper

 Any Calculator
20(JBJI)
1. (a) Solve the following integer programming problem by branch and bound.

max x1 + 2x2
s.t. 2x1 + 3x2 ≤ 6
2x1 + 5x2 ≤ 8
[11]
x1 , x2 ∈ Z≥0

(b) (i) Give the definition of a totally unimodular matrix. [2]

(ii) Is the following matrix totally unimodular?

 
−1 11 −1
 
0 −1 0 1 
A=
0

0 0 1
[2]
 
0 1 0 0

(c) Prove that the difference between the optimal objective value of an integer program-
ming problem and the optimal objective value of its LP-relaxation may be arbitrarily large.
Please do not use the graphical method in your proof.

Hint: For n ∈ N consider

max x1
s.t. x1 − nx2 ≤ 0
x1 + nx2 ≤ n
[5]
x1 , x2 ∈ Z≥0

(d) Solve the following integer programming problem by making use of dynamic programming.

max 6x1 + 5x2 + 7x3

s.t. x1 + x2 + 2x3 ≤ 5
x1 ∈ {0, 1}
x2 , x3 ∈ Z≥0 .

Clearly explain your solution method.

Hint: Note that dynamic programming cannot be applied directly, as x1 is binary but x2 , x3
are integer. [5]

AUoBM321 Page 2 Turn over

 Any Calculator

2. (a) The direct distances (ai j ) between the cities A, B, C, D, and E are shown in the table
below.
A B C D E
A 10 5 3 7
B 10 7 6 4
C 5 7 2 8
D 3 6 2 9
E 7 4 8 9
Find an approximate solution to the symmetric Travelling Salesman Problem (TSP) with
the above direct-distances matrix using CHRISTOFIDES’ algorithm.
Clearly state the main steps of the algorithm and show all your working. [11]

(b) (i) Give the precise definition of a Combinatorial Optimisation Problem (COP) of min-
imisation type. You do not need to define an independence system. [4]

(ii) Given is the complete arc-weighted graph Km = (V, E) with m = |V | ≥ 4 nodes and
arc-weights given by w : E → R≥0 . Let s,t ∈ V denote two designated nodes. In
the shortest path problem the aim is to find an s-t path of minimal total weight.

Find an independence system S = (X, F ) such that the shortest path problem
is the Combinatorial Optimisation Problem of minimisation type associated with S .
Prove that the system you state indeed is an independence system. [5]

(c) Let fe be a flow in the network Nf= (V, E, s,t, e

b). Suppose there esists an arc e∗ ∈ E
that is incoming for the sink t (i.e. e∗ = (x,t) for some x ∈ V ), for which fe(e∗ ) > 0. Due
to construction works the transportation link e∗ cannot be used anymore. Thus, consider
the network N = (V, E, s,t, b), where

0 : e = e∗
b(e) =
b(e) : e ∈ E \ {e∗ }.
e

Determine a solution method to find a feasible flow in the new network N starting from
the flow fe. Describe your solution method in detail and justify why it provides a feasible
flow.

Note: It is important that you start with the given flow fe. Do not solve this question without
using fe. [5]

AUoBM321 Page 3 End of paper

 Any Calculator
21(JBJI)
1. (a) Solve the following Integer Program by Branch and Bound.

(IP) max 3x1 +x2

s.t. −2x1 +2x2 ≤ 5
2x1 ≤ 7
x1,2 ∈ Z≥0

Please do not use pre-processing techniques in your solution. [11]

(b) Given is a set of potential depots N = {1, . . . , n}, and a set of clients M = {1, . . . , m} all of
whom make orders. A fixed cost f j is incurred if depot j is in use. If all of client i’s orders
are delivered from depot j the transportation cost is ci j . If only a portion x ∈ [0, 1] of
client i’s order is delivered from depot j, then proportional transportation costs of xci j are
incurred. The task is to decide which depots to open and what proportion of the demand
of client i to satisfy from depot j so as to minimise the total costs.

State a Mixed Integer Program which models the above-stated Uncapacitated Facility
Location problem and give an interpretation of the variables in terms of the Uncapacitated
Facility Location problem. [6]

(c) Consider the following Integer Program.

(IP) max x1 +3x2

s.t. 2x1 −2x2 ≤ 5
−5x1 +x2 ≤ 1
2x2 ≤ 7
x1,2 ∈ Z≥0

(i) Provide the ideal formulation of the above problem. You may use a graph to justify
how you arrived at the solution and are not required to provide an algebraic proof
that the formulation you provide is ideal.

(ii) Why are ideal formulations beneficial when solving Integer Programs? [8]

AUoBM321 Page 2 Turn over

 Any Calculator

2. (a) Given is the following Knapsack problem.

max 2x1 +7x2 +9x3

s.t. x1 +3x2 +4x3 ≤ 8
x1−3 ∈ Z≥0

Find two different optimal solutions to this problem by applying dynamic programming.
Clearly state all variables that the algorithm initialises. You may present your answer in
form of a table and should apply back-tracking to arrive at your solutions. [11]

(b) Suppose that

(IP) max{c⊤ x | x ∈ X ⊆ Zn } and (D) min{w(u) | u ∈ U ⊆ Rm }

form a weak dual pair. Prove the following statement.

If x∗ ∈ X and u∗ ∈ U are such that c⊤ x∗ = w(u∗ ) then x∗ is optimal for (IP) and u∗ is
optimal for (D). [4]

(c) The company TRex seeks to take out loans from banks, and has approached three banks,
A, B, and C. The charges and terms of these banks are summarised in the following table.

Bank Account fees Interest charges on the Maximum amount that the
per year borrowed amount per year bank offers to lend
A £160 2.5% £150 000
B £250 2.1% £100 000
C £180 2.2% £120 000

TRex wishes to take out £200 000 in total and can apportion the amount among the three
banks as it pleases, as long as TRex borrows an integer amount from each bank. The
account fee is only charged by a bank if money is borrowed from that bank. How much
should TRex borrow from each bank, so as to minimise its yearly charges?

Formulate this problem as an integer programming problem. Clearly define your vari-
ables, objective and constraints. (You are not required to solve this integer programming
problem.) [10]

AUoBM321 Page 3 Turn over

 Any Calculator

3. (a) The direct distances between the cities Birmingham (BH), Amsterdam (A), Bangkog (BK),
Dubai (D) and Guangzhou (G) are displayed in the following table (approximate distances
in 100 km).

BH A BK D G
BH 4 96 56 95
A 4 92 52 91
BK 96 92 49 17
D 56 52 49 58
G 95 91 17 58

(i) Find an approximate solution to the metric Travelling Salesman problem with the
above direct-distances matrix using CHRISTOFIDES’ algorithm. Clearly state the
main steps of the algorithm and show all your working.

(ii) Using your result from (i) and a result on the approximation quality of CHRISTOFIDES’
algorithm covered in lectures, find an upper and a lower bound on the total length of
a minimal tour.
(Note: If you did not solve (i) then assume that the length of a tour found by CHRISTO-
FIDES is 210.) [11]

(b) Prove or disprove the following statement. A max-flow in a network is always unique. [6]

(c) Let N = (V, E, s,t, b) denote a network and let n := |V | denote the number of nodes in
N.

(i) Determine the number of different cuts in the network N . Justify your answer.

(ii) Suppose that f is a max-flow in N found by the Ford and Fulkerson algorithm.
Let (W ∗ ,W ∗ ) denote the minimal cut determined by the labelling algorithm at non-
breakthrough. Let x ∈ W ∗ , y ∈ W ∗ be such that (y, x) ∈ E . Determine f (y, x). [8]

AUoBM321 Page 4 Turn over

 Any Calculator

4. (a) Consider the transportation problem with three producers and four customers which is
given by the following transportation table:

10 5 30 15
30 8 6 10 9
20 9 12 13 7
10 14 9 16 5.

Suppose that in the second iteration of the Alpha-Beta algorithm we obtain the vectors
α = (−1, 1, −1)⊤ and β = (8, 7, 11, 6)⊤ . Starting with these α and β , carry out the
Alpha-Beta algorithm to find an optimal solution and the optimal transportation costs to
the given transportation problem.
(Note: You may solve the max-flow problems by inspection, and do not need to justify that
the stated flows are maximal.) [15]

(b) Let G = (V, E) denote a digraph with at least three nodes. Let x, y ∈ V denote two distict
nodes in G . A set of paths in G is called arc-disjoint if each arc in G appears in at most
one of the paths; several arc-disjoint paths may pass through the same vertex, however.
The aim is to find the maximum number of arc-disjoint paths from x to y in G .

Convert the given problem into a max-flow problem in an associated network N .

(i) Provide a complete description of the associated network N .

(ii) Describe how to find the maximum number of arc-disjoint paths from x to y when
knowing a max-flow in the network N . Provide a justification that the method that
you describe indeed solves the stated problem. [10]

AUoBM321 Page 5 End of paper

 22(JBJI)
Any Calculator

1. (a) Find a primal (lower) bound for the following IP by the greedy heuristic method.

z = max 2x1 + 11x2 + 6x3 + 2x4 + 12x5 + 8x6 + 17x7

s.t. 7x1 + 3x2 + 4x3 + 2x4 + 3x5 + 5x6 + 3x7 ≤ 13
x ∈ {0, 1}7 [5]

(b) Let r ≥ 1 and λ ≥ 0 be two integer numbers. Consider the following problem
r
(Pr (λ )) fr (λ ) = max ∑ c jx j
j=1
r
s.t. ∑ a jx j ≤ λ
j=1
x ∈ {0, 1}r

where a j ∈ R≥0 and c j ∈ R for j ∈ {1, . . . , r}. Prove that if 0 ≤ λ < ar , then fr (λ ) =
fr−1 (λ ). [5]

(c) Use Dynamic Programming to find all optimal solutions to the following IP problem. Use
the table-form and back-tracking to arrive at your solutions.

z = max 17x1 + 8x2 + 12x3 + 2x4 + 6x5

s.t. 7x1 + 3x2 + 4x3 + 2x4 + 3x5 ≤ 5
x ∈ {0, 1}5 [5]

(d) The company Hornitex produces wooden boards of the same size and three different
thicknesses. The production costs and the customer demand of the different type of
boards are summarised in the below table. Boards can be replaced by thicker boards
(e. g. to satisfy the demand of 6000 Type 1 boards, Hornitex could e. g. produce additional
4000 boards of Type 2 and 2000 boards of Type 3). Hornitex wishes to minimise their
total costs while satisfying all demand. Formulate this problem as an IP problem. Clearly
define your variables, objective and constraints. (You are not required to solve this IP.)

Type 1 2 3
Thickness (in mm) 16 20 22
Demand (number of boards) 6000 5000 4000
Variable costs (£/board) 1.6 2.0 2.2
[10]
Fixed costs (£ if boards of this type are produced) 1000 1000 1000

AUoBM321 Page 2 Turn over

 Any Calculator

2. (a) Is the following matrix totally unimodular? Justify your answer.

 
−1 0 0 0 −1
 
0 1 1 0 0
 
1 0 0 1 0
 
 
A=
0 1 0 0 1
−1
 
1 0 0 0
 
0 0 −1 0 1
[5]
 
0 1 0 1 0
(b) Write down the Basic Cutting Plane algorithm for the IP

max{c⊤ x | x ∈ X = P ∩ Zm } (IP)

with formulation P ⊂ Rm , c ∈ Rm and m ∈ N. In particular, write down the initialisation

step as well as the procedure in the k-th iteration step. [5]

(c) Consider the following Integer Programming Problem.

max x1 + x2
s.t. x1 − x2 ≤ 2
2x1 + 8x2 ≤ 19
x1 , x2 ∈ Z≥0

Carry out two iterations of the Gomory cutting plane algorithm. Did you arrive at an
optimal solution to the above Integer Programming Problem (give a short reasoning)? [15]

AUoBM321 Page 3 Turn over

 Any Calculator

3. (a) Does the greedy algorithm correctly solve every instance of the transportation problem?
Either give a proof or provide a counterexample. [6]

(b) Consider the transportation problem with two producers A1 and A2 and two consumers
B1 and B2 given by the following transportation table, where ci j is the cost of sending one
unit from Ai to B j for 1 ≤ i, j ≤ 2.

B1 B2
30 10
A1 20 c11 = 6 c12 = 8
A2 20 c21 = 4 c22 = 8

Solve the transportation problem using the ALPHABETA algorithm. Clearly explain each
step. For the optimal solution, write down the amount xi j transported from Ai to B j for
1 ≤ i, j ≤ 2. Determine the cost of the transportation plan. [10]

(c) For a set V and two subsets V1 ,V2 ⊆ V , we use the notation V = V1 ⊔V2 to denote that
V is the disjoint union of V1 and V2 , i.e. that V = V1 ∪V2 and V1 ∩V2 = 0/ .
An undirected graph G = (V, E) with finite non-empty vertex set V and edge-set

E ⊆ {{u, v} : u, v ∈ V, u ̸= v}

is said to be bipartite if V can be decomposed into the disjoint union of two sets V =
V1 ⊔ V2 and such that for all u, v ∈ V1 , we have {u, v} ̸∈ E and similarly, for all u, v ∈ V2 ,
we have {u, v} ̸∈ E .

(i) Determine whether the following graph is bipartite. Either find decomposition V =
V1 ⊔V2 as above or explain why the graph is not bipartite.
v6

v2 v4

v1 v3 v5

(ii) Let G = (V, E) be an undirected graph. Assume that G admits a 2-colouring. This
is an assignment of two colours, blue or red, to each v ∈ V such that if {u, v} ∈ E ,
then u and v have different colours. Prove that G is bipartite. [9]

AUoBM321 Page 4 Turn over

 Any Calculator

4. (a) The direct distances between the five cities A, B, C, D and E are displayed in the following
table.
A B C D E
A 33 54 71 82
B 33 21 58 89
C 54 21 55 96
D 71 58 55 50
E 82 89 96 50

(i) Find an approximate solution to the metric Travelling Salesman problem with the
above direct distances matrix using CHRISTOFIDES’ algorithm. Clearly state the
main steps of the algorithm and show all your working.

(ii) Using that CHRISTOFIDES’ algorithm is a 1/2-approximate algorithm for the sym-
metric travelling salesman problem and your result from (i), find a lower bound on
the total length of a minimal tour. [12]

(b) Five girls and five boys are interested in pairs ice-skating. The trainer has checked for
each pair girl-boy whether their heights and weights make them suitable to form an ice-
skating pair. The result of these measurements is given in the table below (empty cells
mean ”no”). Find an assignment between boys and girls, which

(i) satisfies the suitability condition and

(ii) creates the maximum number of such pairs,

by transforming the problem into a max-flow problem on a suitable network.

B1 B2 B3 B4
G1 yes yes
G2 yes
G3 yes yes yes
[5]
G4 yes

Question 4 continued overleaf.

AUoBM321 Page 5 Turn over

 Any Calculator

(c) Consider the network N given in the figure below with arc-capacities displayed in shaded
boxes along the arcs. Let fe denote the flow which is given by the free-standing values
along the arcs, where fe(v1 , v2 ) shall be 0 if no value is displayed along the arc (v1 , v2 ).
You may use without a proof that fe is a max-flow on the network N .

4 2 g
a d
4 2

3 4 4 3
1 1 5 4 3 5
3 2 4 3

6 4
s b e h t
8 3 7 4

3 3 5
3 3 5 2 2
7 5 4 6

6 3
c f i
6 3

Suppose that due to roadworks the transportation link (e, g) can no longer be used. De-
scribe a method how to determine a max-flow in this new situation by starting from the
flow fe. Using the method you described, find a max-flow in this new situation and prove
that it is indeed maximal. [8]

AUoBM321 Page 6 End of paper

 23(JBJI) Any Calculator

1. (a) Solve the following 0-1 knapsack problem by dynamic programming

max 7x1 + 9x2 + 3x3

s.t. x1 + 3x2 + 2x3 ≤ 5

x1 , x2 , x3 ∈ {0, 1}.

Clearly state all variables that the algorithm initialises. You may present your answer in
form of a table and should apply back-tracking to arrive at your solution. [7]

(b) (i) Give the definition of a totally unimodular matrix.

(ii) Let A = [ai j ] be a matrix such that

(1) ai j ∈ {+1, −1, 0} for all i, j.

(2) Each column contains at most two nonzero coefficients, i.e. ∑m
i=1 |ai j | ≤ 2 for
j ∈ {1, . . . , n}.
(3) The set M of rows can be partitioned into (M1 , M2 ) such that each column j
containing two nonzero coefficients satisfies ∑i∈M1 ai j − ∑i∈M2 ai j = 0.

Prove that A is totally unimodular.

[8]

(c) Consider the following integer programming problem

max x1 + x2
s.t. x1 + 8x2 ≤ 40

2x1 ≤ 12
x1 , x2 ∈ Z≥0 .

Use branch and bound method to solve the problem without using any pre-processing
techniques. Use the most fractional variable branching option, i.e., branch at the variable
that corresponds to the index

j = arg max min{ fi , 1 − fi },

i∈C

where fi = xi∗ − ⌊xi∗ ⌋ and C is the set of indices of fractional variables of the solution x∗ .
In each step, update the bounds and prune branches when possible. Use the graphical
method to find dual (upper) bounds. [10]

AUoBM321 Page 2 Turn over

 Any Calculator

2. (a) Five projects are being evaluated over a 3-year planning horizon. The following table
gives the expected returns for each project and the associated yearly expenditures.

Expenditures (million $)/yr

Project 1 2 3 Returns (million $)
1 5 1 8 20
2 3 9 2 20
3 4 7 10 40
4 8 6 10 30
5 7 4 1 15
Available funds (million $) 25 25 25

Formulate an integer programming problem for project selection to maximize total return
while respecting budget constraints. Clearly define your variables, objectives and con-
straints. (You are not required to solve the problem). [5]

(b) Formulate the constraints you would add to the integer programming problem from 2(a) to
satisfy the following requirements:

(i) Projects 2 and 3 are mutually exclusive.

(ii) Project 4 must be selected if either project 1 or project 2 is selected.

(iii) Project 5 is selected if and only if at least one of the projects 1 and 3 is selected.

(iv) Project 5 is selected if and only if both the projects 1 and 3 are selected.

(v) Project 5 is selected if and only if exactly one of the projects 1 and 3 is selected. You
are allowed to introduce an auxiliary variable in this case.

[5]

(c) Consider the following integer programming problem.

max 4x1 − x2
s.t. 7x1 − 2x2 ≤ 14

x2 ≤ 3
x1 , x2 ∈ Z≥0 .

Solve the problem using the Gomory cutting plane algorithm. [15]

AUoBM321 Page 3 Turn over

 Any Calculator

3. (a) Let

V = {s, A, B,C, D,t},

E = {(s, A), (s,C), (A, B), (B, D), (B,t), (C, A), (C, D), (D, A), (D,t)} and

b(s, A) = 4, b(s,C) = 2, b(A, B) = 3, b(B, D) = 1, b(B,t) = 3, b(C, A) = 1,

b(C, D) = 3, b(D, A) = 3, b(D,t) = 4.

(i) Draw the network N = (V, E, s,t, b).

(ii) Starting from the flow f given by f (s,C) = f (C, A) = f (A, B) = f (B,t) = 1 and
f (i, j) = 0 for all other arcs (i, j) ∈ E carry out at most three iterations of the Ford
and Fulkerson Algorithm. Provide all details (in particular, clearly state the labels
and the augmenting paths in each iteration step).

(iii) Is the flow that you obtained in (ii) maximal? Justify your answer. [11]

(b) Let N = (V, E, s,t, b) denote a network. Determine whether the following statements
are correct. Justify your answers by providing a proof or a counterexample.

(i) The following inequality holds for all s-t cuts (W,W ) and all flows f in N :

c(W,W ) ≤ v( f ),

where c(W,W ) is the capacity of the s-t cut (W,W ) and v( f ) is the value of the
flow f .

(ii) If |V | = n then there are 2n different cuts in N . [6]

(c) Let A1 , . . . , Am denote producers with capacities a1 , . . . , am . Let B1 , . . . , Bn denote cus-

tomers with demands b1 , . . . , bn . Further, let ci j denote unit transportation costs from Ai
to B j for every i ∈ {1, . . . , m} and j ∈ {1, . . . , n}, and let xi j denote the initially unknown
amount of units transported between Ai and B j .

(i) Write the associated transportation problem as an LP.

(ii) Prove the following statement: If a transportation problem has a feasible solution
then it also has an optimal solution. [8]

AUoBM321 Page 4 Turn over

 Any Calculator

4. (a) The direct distances between the five cities A, B, C, D and E are displayed in the following
table.
A B C D E
A 66 108 142 164
B 66 42 116 178
C 108 42 110 192
D 142 116 110 100
E 164 178 192 100

(i) Find an approximate solution to the metric Travelling Salesman problem with the
above direct distances matrix using CHRISTOFIDES’ algorithm. Clearly state the
main steps of the algorithm and show all your working.

(ii) Using your result from (i), find an upper bound on the total length of a minimal tour.

(iii) Using that CHRISTOFIDES’ algorithm is a 1/2-approximate algorithm for the sym-
metric travelling salesman problem and your result from (i), find a lower bound on
the total length of a minimal tour. [14]

(b) Let A ∈ Nn×4 denote an n × 4 matrix with entries from N, where n ∈ N and n ≥ 2. The
value of a row of this matrix is the sum of all entries of this row. The aim is to find a
collection of linearly independent rows, such that the sum of their values is maximal.

(i) State an independence system S = (X, F ) and a combinatorial optimisation prob-

lem (S , w) associated with S that models the above problem.

(ii) Does GREEDY correctly solve the combinatorial optimisation problem (S , w) for
every w : X → R≥0 ? Provide a proof or a counterexample. [11]

AUoBM321 Page 5 End of paper

10(UoB)
2010
2011
11(UoB)
 A28242
2012
12(UoB) Any Calculator, Statistical tables

1. (a) A sample of 200 Chicago households was taken to investigate how far American house-
holds tend to travel when they take vacation. The interested variables are listed as follows:

MILES measures the distance in miles per year, INCOME measures the annual income
of the household in $1000, AGE measures the average age of the adult members of the
household and KIDS measures the number of children in household.

The following model was estimated

MILES = β1 + β2 INCOME + β3 AGE + β4 KIDS + e, Eqn(1)

where β ’s are parameters and e is the random error term.

residual against income

ehat
2000

1000

-1000

-2000

10 20 30 40 50 60 70 80 90 100 110 120

income

residual against age

ehat
2000

1000

-1000

-2000

20 30 40 50 60

age

Figure 1

Page 2 Turn over

A28242 Any Calculator, Statistical tables

(i) Equation (1) was estimated by least squares and residuals are plotted against AGE
and INCOME in Figure 1. What do these graphs suggest to you in terms of model
fit? [3]

(ii) Ordering the observations according to descending values of INCOME , and ap-
plying least squares to the first 100 observations, and again to the second 100
observations, yields the sums of squared errors of SSE1 and SSE2, respectively
where
SSE1 = 2.9471 × 107 , SSE2 = 1.0479 × 107 .

Use the Goldfeld-Quandt test to test for heteroskedasticity of errors. Include specifi-
cation of the null and alternative hypotheses. [5]

(iii) Table 1 (overleaf) contains three sets of estimates: those from least squares, those
from least squares with White’s standard errors, and those from generalized least
squares under the assumption of σi2 = σ 2 × INCOME 2 .

(1) How do vacation miles travelled depend on INCOME , AGE and KIDS? [3]
(2) How do White’s standard errors compare with the least squares standard er-
rors? Do they change your assessment of the precision of estimation? [3]
(3) Is there evidence to suggest that the generalised least squares estimates are
better estimates? Justify your answer. [3]

(b) Suppose you are estimating a simple linear regression model of y1 = β1 +β2 x1 +u, where
y is the dependent variable and x is the independent variable, u is the random error term,
and i is the ith number of observations. Answer the following questions.

(i) If you multiply all the x values by 20, but not the y values, show mathematically what
happens to the parameter values of β1 and β2 and explain your results. What will
happen to the least squares estimates, b1 and b2 ? What happens to the variance of
the error term? [4]

(ii) If you multiply all the y values by 50, but not the x values, show mathematically what
happens to the parameter values of β1 and β2 and explain your results. What will
happen to the least squares estimates, b1 and b2 ? What happens to the variance of
the error term? [4]

Page 3 Turn over

A28242 Any Calculator, Statistical tables

Least squares estimate

Parameter Standard
Variable DF Estimate Error t value Pr > |t|
Intercept 1 -391.55 169.78 -2.31 0.022
INCOME 1 14.20 1.80 7.89 0.000
AGE 1 15.74 3.76 4.19 0.000
KIDS 1 -81.83 27.13 -3.02 0.003

Least squares estimates with White standard errors

Parameter Standard
Variable DF Estimate Error t value Pr > |t|
Intercept 1 -391.55 142.65 -2.74 0.007
INCOME 1 14.20 1.94 7.32 0.000
AGE 1 15.74 3.96 3.97 0.000
KIDS 1 -81.83 29.15 -2.81 0.006

Generalised least squares estimates

Parameter Standard
Variable DF Estimate Error t value Pr > |t|
Intercept 1 -425.00 121.44 -3.50 0.001
INCOME 1 13.95 1.48 9.42 0.000
AGE 1 16.72 3.02 5.53 0.000
KIDS 1 -76.81 21.85 -3.52 0.001
Table 1 Output for 1 (a) (iii)

Page 4 Turn over

 A28242 Any Calculator, Statistical tables

2. (a) Consider the wage equation

ln(WAGE) = β1 + β2 EDUC + β3 EDUC2 + β4 EXPER + β5 EXPER2

+ β6 (EDUC × EXPER) + β7 HRSW K + e. (2)

WAGE = earnings per hour in dollars, EDUC = years of education, EXPER = years of
post education experience and HRSW K = usual hours worked per week.

The mean values of each variable are reported in Table 2, and estimation results for model
(2) and its modified versions are displayed in Table 3 (overleaf).

Variable N Mean Std Dev Minimum Maximum

WAGE 1000 20.201 12.104 2.030 72.130
EDUC 1000 10.689 2.440 1.000 16.000
EXPER 1000 26.501 12.990 3.000 64.000
HRW KS 1000 39.240 11.446 0.000 99.000
Table 2: The MEANS Procedure

(i) Write out the equation based on SAS output results from Table 3 for Eqn (B) only. [2]

(ii) Using an approximate 5 percent critical value of t = 2, which coefficients are not
significantly different from zero? [1]

(iii) What restrictions on the coefficients of Eqn (A) would produce Eqn(C)? Use an
F-test to test these restrictions. What equation would you be trying to answer by
performing this test? [4]

(iv) Consider all of these models from Eqn (A) to Eqn (E) carefully, which model would
you prefer? Why? Explain and demonstrate your answer in details. [8]

(v) Compute the missing AIC value for Eqn (D) and the missing SC value for Eqn (A).
Which model is favored by the AIC? Which model is favored by the SC? [4]

(b) The estimated/fitted simple least squares line is ŷi = b1 + b2 xi , here ŷ is the fitted de-
pendent variable and x is the independent variable, i is the i-th observation. Algebraically
show that the average value of ŷi s equals the sample average of yi s, where N is the total
number of observations. That is, show that
N
ŷ¯i = ȳ, where ŷ¯i = ∑ ŷi /N. [6]
i=1

Page 5 Turn over

A28242 Any Calculator, Statistical tables

Variables Eqn (A) Eqn (B) Eqn (C) Eqn (D) Eqn (E)
Intercept 1.055 1.252 1.573 1.917 0.904
(0.266) (0.190) (0.188) (0.080) (0.096)
EDUC 0.0498 0.0289 0.0366 0.1006
(0.0397) (0.0344) (0.0350) (0.0063)
EDUC2 0.00319 0.00352 0.00293
(0.00169) (0.00166) (0.00170)
EXPER 0.0373 0.0303 0.0279 0.0295
(0.0081) (0.0048) (0.0054) (0.0048)
EXPER2 0.000485 0.000456 -0.00047 -0.000440
(0.00009) (0.000086) (0.000096) (0.000086)
EDUC × EXPER -0.00051
(0.000482)
HRSW K 0.01145 0.01156 0.01345 0.01524 0.01188
(0.00137) (0.00137) (0.00136) (0.00151) (0.00136)
SSE 222.4166 222.6674 233.8317 280.5061 223.6716
AIC -1.489 -1.490 -1.445 -1.488
SC -1.461 -1.426 -1.244 -1.463
Table 3: Estimation Results with Standard Errors in the Parentheses

Page 6 Turn over

 A28242 Any Calculator, Statistical tables

3. Table 4 contains computer output after estimating the following two models to the same 35
observations. The models are

y = β1 + β2 x + β3 w + e, (3)

y = β1 + β2 x + e. (4)

Implementing the regression specification error test (RESET) suggests augmenting an existing
model with the squares of its predictions, or with their squares and cubes. RESET applied to the
second model yields F-value of 17.98 (for ŷ2 ) and 8.72 (for ŷ2 and ŷ3 ). The correlation between
x and w is 0.975. Answer the following questions.

(a) Should w be included in the model? [5]

(b) What can you say about omitted variable bias? [6]

(c) What can you say about the existence of collinearity and its possible effect? [5]

(d) What would happen if we use RESET augmenting the model with the predictor, ŷ? [9]

Variables Model (3) Model (4)

Intercept 3.6356 -5.8382
(2.763) (2.000)
x -0.99845 4.1072
(1.235) (0.3383)
w 0.49785
(0.1174)
Table 4 Estimation results with Standard Errors in the Parentheses

Page 7 Turn over

 A28242 Any Calculator, Statistical tables

4. (a) We analyze the pattern of GDP growth using 250 quarterly observations in the United
States, the data starts from quarter two of 1947 to quarter three of 2009. G denotes GDP
growth rate, and t refers to the quarterly observation, and the average GDP growth during
this period is Ḡ. The following quantities are calculated from the data:
250

∑ Gt − Ḡ = 333.8558,
t=1
250


∑ Gt − Ḡ Gt−1 − Ḡ = 162.9753,
t=2
250


∑ Gt − Ḡ Gt−2 − Ḡ = 112.4882,
t=3
250


∑ Gt − Ḡ Gt−3 − Ḡ = 30.5802.
t=4

(i) Compute the first three autocorrelations for G, denoting them as r1 , r2 and r3 respectively. [3]

(ii) From the results you have computed in (i), test whether r2 is significantly different
from zero at a 5% significance level. [2]

(iii) From the results you have obtained in (i) and (ii), sketch the first three bars of the
correlogram which should include the significant bounds. [6]

(b) Consider the following AR(1) model, where Gt = δ + θ Gt−1 + et , and

250
Ḡ1 = ∑ Gt /249 = 1.662249,
t=2
250
Ḡ−1 = ∑ Gt−1/249 = 1.664257,
t=2
250
2
∑ Gt−1 − Ḡ−1 = 333.1119,
t=2
250


∑ Gt − Ḡ1 Gt−1 − Ḡ−1 = 162.974.
t=2

(i) Find the least squares estimates of δ and θ1 . [2]

(ii) Compare and explain the difference between the estimate θ̂1 and the estimate r1
obtained in (a)(i). [4]

Page 8 Turn over

A28242 Any Calculator, Statistical tables

(c) Consider a random walk model

yt = yt−1 + νt .

(i) Rewrite y as a function of lagged errors. [2]

(ii) What is the mean and variance of y? [4]

(iii) What is the covariance between yt and yt−2 ? [2]

Page 9 Turn over

 A28242 Any Calculator, Statistical tables

5. (a) Explain with a brief reason whether the following statements are true, false, or uncertain.

(i) When autocorrelation is present, ordinary least squares (OLS) estimators are biased
as well as inefficient.

(ii) A significant Durbin-Watson d test does not necessarily mean there is autocorrela-
tion of the first order.

(iii) The Durbin h test is valid in both large and small samples.

(iv) There is no general test of heteroscedasticity that is free of any assumption with
which variable the error term is correlated.

(v) If residuals estimated from an OLS regression exhibit a systematic pattern, it means
heteroscedasticity is present in the data. [10]

(b) Fix the errors in the following program, assuming there are no statements split across
multiple lines. The actual data starts with the second row of the file with three variables
named as ”airlines”, ”cost” and ”traveler” in the data of ”travel.csv”. You can only earn the
full marks if you can correct all the errors. [5]

data holiday
infile ”c:\travel.csv”
input air lines cost traveler;
procprint;
run;

Page 10 Turn over

A28242 Any Calculator, Statistical tables

(c) David used SAS to check whether the model yi = β1 +β2 xi +ei has the heteroscedasticity
issue, where y is the dependent variable, x is the only explanatory variable, e is the error
term and i stands for the i-th number of the observations. He read in the data into SAS,
checked the descriptions of the variables carefully, and he was sure that the data was
imported correctly.

(i) Now David wants to use the graphical method first, plotting the least squares resid-
uals against x. He made the program run, however, he accidentally deleted some
words and letters which made the program look like the one listed below. How can
you help him fix this program so that he can make a plot of the least squares resid-
uals against x? [3]

proc reg ndata=question5;

model y = x;
output out=foodout
title ’OLS and outputs’;
run;

symbol1 value=dot color=blue; * symbol for plots;

proc gplot data= * plot using output data;
plot ehat * ; * residuals vs. x-variable;
title ’Residual plots for variable x’;
run;

Page 11 Turn over

A28242 Any Calculator, Statistical tables

(ii) The second step that David plans to do is to confirm the result obtained in (i) with
the Breusch-Pagan test. The SAS output is given below. What program would
you suggest David to write so that he can obtain such output? Write down the
appropriate SAS procedure code in full. [7]

proc model heteroskedasticity tests

The MODEL Procedure
Nonlinear OLS Summary of Residual Errors
DF DF Adj
Equation Model Error SSE MSE Root MSE R- Square R-sq
Y 2 38 304505 8013.3 89.5170 0.3850 0.3688
Nonlinear OLS Parameter Estimates
Approx Approx
Parameter Estimate Std Err t Value Pr > |t| Label

b1 83.41601 43.4102 1.92 0.0622 intercept

b2 10.20964 2.0933 4.88 <0.0001 income
Number of Observations Statistics for System
Used 40 Objective 7613
Missing 0 Objective*N 304505

Heteroscedasticity Test
Equation Test Statistics DF Pr > ChiSq Variables
Y White’s Test 7.56 2 0.0229 Cros of all vars
Breusch-Pagan 7.38 1 0.0066 1, x

Page 12 Turn over

 A28242 Any Calculator, Statistical tables

6. (a) A multiple linear regression model with two explanatory variables can be written as:

y = β1 + β2 x2 + β3 x3 + ε

where the β ’s are the parameters and ε is the random error term ∼ (0, σ 2 ). Complete
the following questions, giving as much detail as possible:

(i) Derive the least squares estimates b1 , b2 , and b3 of β1 , β2 and β3 , respectively. [15]

(ii) Let γ12 denote the sample correlation coefficient between y and x2 , γ13 denote the
sample correlation coefficient between y and x3 , and γ13 denote the sample correla-
tion coefficient between x2 and x3 . Is it possible to obtain the following results from
a set of data? Why?

(i) γ23 = 0.9, γ13 = −0.2, γ12 = 0.8

(ii) γ12 = 0.6, γ23 = −0.9, γ31 = −0.5.

[4]

(b) Let β̂Y X and β̂XY represent the slopes in the simple regression of Y on X and X on Y ,
respectively. Show that
β̂Y X β̂XY = γ 2

where γ is the coefficient of correlation between X and Y . [6]

Page 13 Turn over

 A28242
13(UoB)
2013
Any Calculator, Statistical tables

1. (a) A multiple linear regression model with two explanatory variables can be written as:

y = β1 + β2 x2 + β3 x3 + ε

where the β ’s are the parameters and ε is the random error term ∼ (0, σ 2 ). Complete
the following questions, giving as much detail as possible:

(i) Let γ12 denote the sample correlation coefficient between y and x2 , γ13 denote the
sample correlation coefficient between y and x3 , and γ23 denote the sample correla-
tion coefficient between x2 and x3 . Is it possible to obtain the following results from
a set of data? Why?

(a) γ23 = 0.9, γ13 = −0.2, γ12 = 0.8

(b) γ12 = 0.6, γ23 = −0.9, γ31 = −0.5.

[8]

(ii) Related to (i), let γ12.3 denote the partial correlation coefficient between y and x2
while holding x3 constant, γ13.2 denote the partial correlation coefficient between y
and x3 while holding x2 constant, and γ23.1 denote the sample partial correlation
coefficient between x2 and x3 while holding y constant. Are the following statements
true or false? Explain and correct any false statements.

(a) γ12.3 and γ12 (and similar comparisons) have the same sign.
(b) If y is uncorrelated with x3 , and x2 is not correlated with x3 either, then y is not
correlated with x2 .
(c) From the relationship between R2 , simple correlation coefficients, and partial
correlation coefficient, we can conclude that R2 will not decrease if an additional
explanatory variable is introduced into the model.

[9]

(iii) Write down an appropriate procedure step using SAS to find out partial correlation
coefficients among y, x2 and x3 . You can start with “proc” directly. [3]

(b) Let β̂Y X and β̂XY represent the slopes in the simple regression of Y on X and X on Y ,
respectively. Show that
β̂Y X β̂XY = γ 2

where γ is the coefficient of correlation between X and Y . [5]

Page 2 Turn over

 A28242 Any Calculator, Statistical tables

2. (a) Consider the following regression model:

( )
1 1
= β1 + β2 + ei
Yi Xi
where Y and X assume non-zero values and the β ’s are the parameters, ei is the random
error term, and i denotes the number of individuals. Complete the following questions,
giving as much detail as possible:

(i) Explain whether or not it is a linear regression model. [2]

(ii) How would you fit this model? [2]

(iii) What will Yi tend to be as Xi goes to infinity? [2]

(iv) Please give an example where such a model may be appropriate. [2]

(b) Consider a simple regression in which the dependent variable MIM =mean income of
males who are 18 years of age or older, in thousands of dollars. The explanatory variable
PMHS=percent of males 18 or older who are high school graduates. The data consist of
51 observations on the 50 states in USA plus the District of Columbia. Thus MIM and
PMHS are ”state averages.” The fitted regression, along with standard errors (se) and
t-statistics, is
[ =
MIM (A) + 0.180PMHS
(se) (2.174) (B)
(t) (1.257) (5.754)

(i) What is the estimated intercept term (A) in the equation? Show your calculation. [3]

(ii) What is the standard error of the estimated slope coefficient (B)? Show your calcu-
lation. [3]

(iii) Interpret the meaning of the slope coefficient. Is the sign expected? [3]

(iv) Test the hypothesis that the slope parameter is 0.2 against the alternative that is not.
[4]

(v) Suppose the data for this model is saved as maleincome.csv, and it is under the path
of D:\maleincome.csv. The first line of this data file consists of variable names,and
the numeric values start from line 2. Write down a short SAS program to obtain
the above fitted regression. Your code should have at least one data step and one
procedure step. [4]

Page 3 Turn over

 A28242 Any Calculator, Statistical tables

3. (a) Consider the wage equation

ln(WAGE) = β1 + β2 EDUC + β3 EDUC2 + β4 EXPER + β5 EXPER2

+ β6 (EDUC × EXPER) + β7 HRSW K + e.

WAGE = earnings per hour in dollars, EDUC = years of education, EXPER = years of
post education experience and HRSW K = usual hours worked per week.

The mean values of each variable are reported in Table 1, and estimation results for the
above and its modified versions are displayed in Table 2. Please note that two of the
values of the model selection criteria have been omitted from Table 2. Both tables are
displayed overleaf.

(i) What restrictions on the coefficients of Eqn (A) would produce Eqn(C)? Use an
appropriate statistic to test if these restrictions are appropriate. [5]

(ii) Consider the model selection criterions shown in Table 2 and apply them to all of
these models from from Eqn (A) to Eqn (E). Based on your results, which model
would you prefer? Explain and demonstrate your answer in details. [12]

(b) Explain with a brief reason whether the following statements are true or false.

(i) If residuals estimated from an OLS regression exhibit a systematic pattern, it means
heteroscedasticity is present in the data. [2]

(ii) The Durbin h test is valid in both large and small samples. [2]

(iii) Unfortunately, dummy variables cannot be used to estimate the seasonal effects on
a regression model applied to time-series data. [2]

(iv) A linear regression model means the dependent variable is a linear function of all
the explanatory variables. [2]

Question 3 continued overleaf.

Page 4 Turn over

A28242 Any Calculator, Statistical tables

Table 1: The MEANS Procedure

Variable N (sample size) Mean Std Dev Minimum Maximum
WAGE 1000 20.201 12.104 2.030 72.130
EDUC 1000 10.689 2.440 1.000 16.000
EXPER 1000 26.501 12.990 3.000 64.000
HRW KS 1000 39.240 11.446 0.000 99.000

Table 2: Estimation Results with Standard Errors in the Parentheses

Variables Eqn (A) Eqn (B) Eqn (C) Eqn (D) Eqn (E)
Intercept 1.055 1.252 1.573 1.917 0.904
(0.266) (0.190) (0.188) (0.080) (0.096)
EDUC 0.0498 0.0289 0.0366 0.1006
(0.0397) (0.0344) (0.0350) (0.0063)
EDUC2 0.00319 0.00352 0.00293
(0.00169) (0.00166) (0.00170)
EXPER 0.0373 0.0303 0.0279 0.0295
(0.0081) (0.0048) (0.0054) (0.0048)
EXPER2 0.000485 0.000456 -0.00047 -0.000440
(0.00009) (0.000086) (0.000096) (0.000086)
EDUC × EXPER -0.00051
(0.000482)
HRSW K 0.01145 0.01156 0.01345 0.01524 0.01188
(0.00137) (0.00137) (0.00136) (0.00151) (0.00136)
SSE 222.4166 222.6674 233.8317 280.5061 223.6716
AIC -1.489 -1.490 -1.445 -1.488
SC -1.461 -1.426 -1.244 -1.463

Page 5 Turn over

 A28242 Any Calculator, Statistical tables

4. (a) Table 3 contains computer output after estimating the following two models to the same
35 observations. The first model (Model 1) is: y = β1 + β2 x + β3 w + e, and the second
model (Model 2) is: y = β1 + β2 x + e. The β s are parameters and e is the random error.

Table 3 Estimation results with Standard Errors in the Parentheses

Coefficients Model 1 Model 2
Intercept 3.6356 -5.8382
(2.763) (2.000)
x -0.99845 4.1072
(1.235) (0.3383)
w 0.49785
(0.1174)

Implementing the regression specification error test (RESET) suggests augmenting an

existing model with the squares of its predictions, or with their squares and cubes. RESET
applied to the second model yields an F-value of 17.98 (for ŷ2 ) and 8.72 (for ŷ2 and ŷ3 ).
The correlation between x and w is 0.975. Answer the following questions.

(i) Should w be included in the above model? [4]

(ii) What can you say about the existence of collinearity in the above model and its
possible effect on model results? [6]

(iii) What would happen if we use RESET augmenting the second model with the pre-
dictor, ŷ? [6]

(b) Suppose a true model is

Yi = β Xi + ui ,

where β is parameter and u is the random error, and i denotes the number of obser-
vations. But instead of fitting this regression through the origin, it is fitted by the usual
intercept-present model:
Yi = α0 + α1 Xi + vi

where the α s are parameters, v is the random error, and i denotes the number of obser-
vations. Explain the consequences of this specification error on the model. [9]

Page 6 Turn over

 A28242 Any Calculator, Statistical tables

5. (a) Consider the following model, where the error term, vt is assumed to follow a first-order
autoregressive model or AR(1),

y = β1 + β2 x2t + β3 x3t + vt .

The β ’s are the parameters, v is the random error term, and t stands for the number of
observations in time series data. Complete the following questions, giving as much detail
as possible:

(i) What are the consequences of ignoring true existence of serially correlated errors
and proceeding with least squares estimation? [3]

(ii) Describe the process of how you carry out an appropriate Lagrange multiplier (LM)
test for whether the first order autoregression is correct. [7]

(iii) Describe mathematically how to transform the above model so that there is no auto-
correlation in the transformed model. [8]

(b) Consider a random walk model

yt = yt−1 + vt .

(i) Rewrite yt as a function of lagged errors. [2]

(ii) What is the mean and variance of yt ? [3]

(iii) What is the covariance between yt and yt−2 ? [2]

Page 7 Turn over

 A28242 Any Calculator, Statistical tables

6. (a) Suppose we wish to explain a dependent variable y and that the number of possible ex-
planatory variables (x1 , x2 , ..., xK ) is so large that it is tempting to take a subset of explana-
tory variables. In such a situation, some researchers apply the so-called Theil criterion
and maximize the adjusted R2 , and it is defined by

(n − 1)
R̄2 = 1 − (1 − R2 ),
n − (K − 1)

where n is the number of observations, K is the number of parameters, and (K − 1) is the

number of explanatory variables.

(i) Show that the Theil criterion is equivalent to minimizing the sum of the squared
residuals. [6]

(ii) For the null hypothesis of β j = 0, where β j is the parameter for an explanatory
variable x j , show that the Theil criterion implies that x j will be maintained if and only
if the F-test statistic > 1. [7]

(b) Fix the errors in the following SAS program, assuming there are no statements split across
multiple lines. The actual data is in comma separated variable format with the name of
travel.csv in the C: drive. The data starts with the second row of the file, with three
variables named as ”airlines”, ”cost” and ”traveler”. You can only earn the full marks if you
can correct all the errors. [6]

data holiday
infile "c:\travel.csv";
in put air-lines cost traveler;
procprint;
run;

(c) David used SAS to check whether the model yi = β1 + β2 xi +ei has the heteroscedasticity
issue, where y is the dependent variable, x is the only explanatory variable, e is the error
term and i stands for the i-th number of the observations. He read in the data into SAS,
checked the descriptions of the variables carefully, and he was sure that the data was
imported correctly.

Question 6 continued overleaf.

Page 8 Turn over

A28242 Any Calculator, Statistical tables

Now David wants to use the graphical method first, plotting the least squares residuals
against x. He made the program run, however, he accidentally deleted some words and
letters which made the program look like the one listed below. How can you help him fix
this program so that he can make a plot of the least squares residuals against x? [6]

proc reg data=question6;

model y = x;
output out=foodout ;
title ’OLS and outputs’;
run;

proc gplot data= ; * plot using output data;

plot ehat * ; * residuals vs. x-variable;
title ’Residual plots for variable x’;
run;

Page 9 Turn over

 A28242
2014
14(UoB)
Any Calculator, Statistical tables

1. (a) Consider a linear regression model can be written as:

yi = β1 + β2 x2i + εi

where the β ’s are the parameters and ε is IID the random error term ∼ (0, σ 2), and i
denotes the number of observations. Let b1 and b2 be the least squares estimators of β1
and β2 respectively. Complete the following questions, giving as much detail as possible:

(i) State the Gauss-Markov Theorem about the least squares estimators b1 and b2 ? [5]

(ii) Prove the Gauss-Markov theorem for the least squares estimator b2 of β2 . [11]

(b) Answer the following questions.

(i) Explain, with at least one example, how the effects of qualitative independent vari-
ables (such as race) can be included in a regression analysis. Illustrate the use of
incorporating this type of variable, and how it affects the intercept and the slope. [3]

(ii) We impose assumptions on the dependent variable and the random error term in
linear regression models using least squares method. We do not need to impose
assumptions on the explanatory variables since they are random variables. Is this
statement true or false? Make your judgement and provide brief explanations to your
answer. [2]

(iii) For linear models, it is always appropriate to use R2 as a measure of how well the
estimated regression equation fits the data because it shows the proportion of total
variation that is explained by the regression. Is this statement true or false? Make
your judgement and provide brief explanations to your answer. [2]

(iv) Interval estimates based on the least squares method incorporate both the point
estimate and the standard error of the estimate, and the sample size as well, so
a true parameter is actually certain to be included in an interval like that. Is this
statement true or false? Make your judgement and provide brief explanations to
your answer. [2]

Page 2 Turn over

 A28242 Any Calculator, Statistical tables

2. (a) Dr. Stats EZ has decided that writing the least squares estimator is too much trouble.
Noting that two points determine a line, Dr. EZ chooses two points from a sample of size
N and draws a line between them, calling the slope of this line the EZ estimator of β2 in the
simple regression model of Yi = β1 + β2 Xi + ei , where Y and X assume non-zero values
and the β ’s are the parameters, ei is the random error term, and i denotes the number of
individuals. Algebraically, if the two points are x1 , y1 and x2 , y2 , the EZ estimation rule is
y2 − y1
bEZ = .
x2 − x1
Assuming all the assumptions of a regression model hold, answer the following questions:

(i) Show that bEZ is a linear and unbiased estimator of β2 . [4]

(ii) Find the variance of bEZ . [2]

(iii) Find the probability distribution of bEZ . [2]

(iv) Convince Dr. EZ that the EZ estimator is not as good as the least squares estimator.
No proof is required here. [4]

(b) A multiple linear regression model with two explanatory variables can be written as y =
β1 + β2 x2 + β3 x3 + ε , where the β ’s are the parameters and ε is the random error term
∼ (0, σ 2 ). Let γ12 denote the sample correlation coefficient between y and x2 , γ13 denote
the sample correlation coefficient between y and x3 , and γ23 denote the sample correlation
coefficient between x2 and x3 . Also we further let γ12.3 denote the partial correlation
coefficient between y and x2 while holding x3 constant, γ13.2 denote the partial correlation
coefficient between y and x3 while holding x2 constant, and γ23.1 denote the sample partial
correlation coefficient between x2 and x3 while holding y constant.

(i) Are the following statements true or false? Explain your answer and correct any
false statements.

(1) γ12.3 and γ12 (and similar comparisons) have the same sign. [3]
(2) If y is uncorrelated with x3 , and x2 is not correlated with x3 either, then y is not
correlated with x2 . [3]
(3) From the relationship between R2 , simple correlation coefficients, and partial
correlation coefficients, we can conclude that R2 will not decrease if an addi-
tional explanatory variable is introduced into the model. [3]

(ii) Write down an appropriate and complete SAS procedure statement to find out the
partial correlation coefficients among y, x2 and x3 . You can start with “proc” directly.
[4]
Page 3 Turn over
 A28242 Any Calculator, Statistical tables

3. (a) Consider the following regression model:

 
1 1
= β1 + β2 + ei
Yi Xi
where Y and X assume non-zero values and the β ’s are the parameters, ei is the random
error term, and i denotes the number of individuals. Complete the following questions,
giving as much detail as possible:

(i) Explain whether or not it is a linear regression model. [2]

(ii) How would you fit this model? [2]

(iii) What will Yi tend to be as Xi goes to infinity? [2]

(iv) Please give an example where such a model may be appropriate. [2]

(b) Consider a simple linear regression model in which the dependent variable MIM =mean
income of males who are 18 years of age or older, in thousands of dollars. The explana-
tory variable PMHS=percent of males 18 or older who are high school graduates. The
data consist of 51 observations on the 50 states in USA plus the District of Columbia.
Thus MIM and PMHS are ”state averages.” The fitted regression, along with standard
errors (se) and t-statistics, is

[ =
MIM (A) + 0.180PMHS
(se) (2.174) (B)
(t) (1.257) (5.754)

(i) What is the estimated intercept term (A) in the equation? Show your calculation. [3]

(ii) What is the standard error (B) of the estimated slope coefficient? Show your calcu-
lation. [3]

(iii) Interpret the meaning of the slope coefficient. Is the sign expected? [3]

(iv) Test the hypothesis that the slope parameter is 0.2 against the alternative that it is
not, using the significance level of 5 percent. [4]

(v) Suppose the data for this model is saved as maleincome.csv, and it is under the path
of D:\maleincome.csv. The first line of this data file consists of variable names,and
the numeric values start from line 3. Write down a short SAS program to obtain
the above fitted regression. Your code should have at least one data step and one
procedure step. [4]

Page 4 Turn over

 A28242 Any Calculator, Statistical tables

4. (a) A simple linear regression model with one explanatory variable can be written as:

yi = β1 + β2 x2i + ei for i = 1, ..., N.

Where the β ’s are the parameters, i denotes the number of observations, N stands for
the sample size, and e is the normally distributed random error term ∼ (0, σ 2 ). Let X̄ be
the sample mean of x, êi denote the sample counterparts of the true random errors, b1
and b2 be the least squares estimator of β1 and β2 , respectively. b2 is normally distributed
∼ (β2 , σ 2 /∑N 2
i=1 (xi − x̄) ). You can use the following established facts directly in your

i=1 êi /σ is statistically independent of b1 and b2 and only N − 2 of the

proof that ∑N 2 2

2 2 b −β
least squares residuals are independent in the simple regression model. Show that se(b
2)

follows the t distribution with N − 2 degrees of freedom. [8]

(b) Consider a model of log(WAGE)i = β1 + β2 IQi + β3 EDUi + β4 T ENU REi + ui , i =

1, ..., N, where WAGE is the logarithmic term of the real wage for a staff member, i,in
a university, IQ represents the score of the intelligence quotient, EDU stands for the
years of education, and TENURE is an indicator variable denoting whether a staff mem-
ber, i, has tenured or not, and u is the random error term, i stands for the number of staff
members in the data, and N stands for the sample size.

(i) Describe how you would examine the joint significance of β2 = 0, β3 = 0 and β4 = 0
at 5% significance level. Describe the steps, state the null and alternative hypothe-
sis, test statistics and the rejection rule. [5]

(ii) If EDU and IQ are positively correlated, and we omit EDU from the model, what
would be the likely sign of the bias of the coefficient? [2]

(iii) If EDU and IQ are positively correlated, and we omit EDU from the model, what
would you expect the effect of increasing the sample size on the estimated errors on
the parameters? [2]

(iv) If EDU and IQ are positively correlated, and we omit EDU from the model, what
would you expect the effect of increasing the sample size on the bias of the coeffi-
cient? [2]

(c) Consider the following model, y = β1 + β2 x2 + β3 x3 + u. The β ’s are the parameters,

u is the random error term. Describe how you would test for heteroskedasticity using
the special case of the White test. Describe each step, state the null and alternative
hypothesis, test statistics and the rejection rule. [6]

Page 5 Turn over

 A28242 Any Calculator, Statistical tables

5. (a) Consider the following model yt = 0.5yt−1 + xt + v1t , and xt = 0.5xt−1 + v2t , where both
v1t and v2t follow IID normal distribution ∼ (0, 1). Examine the following statements, state
whether they are true or false first, and then explain why they are true or false.

(i) The time series yt is weakly stationary. [2]

(ii) The unconditional variance of yt is larger than the conditional one-step ahead variance. [2]

(iii) The path of forecasts for yt+i conditional on the information available at time t will
be oscillatory but it will eventually converge to 0.1. [2]

(iv) If a sample of 1000 observations were simulated from this model for yt , then at least
five values will be expected to be larger than 6. [3]

(v) The upper bound for the 95 percent conditional 1-step ahead confidence interval for
yt is 2. [2]

(vi) The series yt and xt share a common stochastic trend. [2]

(vii) The series yt and xt have the same unconditional mean. [2]

(viii) If yt = 1 and xt = 1, then E[yt+1 |yt , xt ] = 1. [2]

(ix) If yt = 1, xt = 1, v1t = 1, and v2t = 1, then E[yt+1 |yt , xt ] 6= 1. [2]

(x) If yt = 0 and xt = −0.8, then E[yt+1 |yt , xt ] = −0.8. [2]

(b) Answer the following questions with brief explanations.

(i) What is the consequence of specifying a model with a variable in logarithm form, if
in the true population model of the variable is in level form? [2]

(ii) Is a regression with a low R2 useless? Explain your answer. [2]

Page 6 Turn over

 A28242 Any Calculator, Statistical tables

6. (a) Suppose that you fit a simple linear regression model of y = β1 + β2 xi + ε , where the β ’s
are the parameters and ε is the random error term ∼ (0, σ 2 ). You get the estimates as
β̂1 = 2, β̂2 = 0.8, the correlation between y and x, ρxy = 0.6, and σb 2 = 4. The model
uses 100 observations. Using the level of significance of 5 percent, test the hypothesis
that β2 = 0. [6]

(b) Consider a random walk model

yt = yt−1 + vt .

(i) Rewrite yt as a function of lagged errors. [2]

(ii) What is the mean and variance of yt ? [2]

(iii) What is the covariance between yt and yt−2 ? [2]

(c) Suppose we wish to explain a dependent variable y and that the number of possible ex-
planatory variables (x1 , x2 , ..., xK ) is so large that it is tempting to take a subset of explana-
tory variables. In such a situation, some researchers apply the so-called Theil criterion
and maximize the adjusted R2 , and it is defined by

(n − 1)
R̄2 = 1 − (1 − R2 ),
n − (K − 1)

where n is the number of observations, K is the number of parameters, and (K − 1) is

the number of explanatory variables. For the null hypothesis of β j = 0, where β j is the
parameter for an explanatory variable x j , show that the Theil criterion implies that x j will
be maintained if and only if the F-test statistic > 1. [7]

(d) David used SAS to check whether the model yi = β1 + β2 xi +ei has the heteroscedasticity
issue, where y is the dependent variable, x is the only explanatory variable, e is the error
term and i stands for the i-th number of the observations. He read in the data into SAS,
checked the descriptions of the variables carefully, and he was sure that the data was
imported correctly.

Question 6 continued overleaf.

Page 7 Turn over

A28242 Any Calculator, Statistical tables

Now David wants to use the graphical method first, plotting the least squares residuals
against x. He made the program run, however, he accidentally deleted some words and
letters which made the program look like the one listed below. How can you help him fix
this program so that he can make a plot of the least squares residuals against x? [6]

proc reg data=question6;

model y = x;
output out=foodout ;
title ’OLS and outputs’;
run;

proc gplot data= ; * plot using output data;

plot ehat * ; * residuals vs. x-variable;
title ’Residual plots for variable x’;
run;

Page 8 Turn over

 2015
15(UoB)
A28242 Any Calculator, Statistical tables

1. (a) Consider the following estimated regression equation (standard errors in parentheses)and
answer the following questions:

yb = 5.83 + 0.869x R2 = 0.756.

(se) (1.23) (0.117)

(i) Rewrite the estimated equation including the standard errors and R2 that would re-
sult if all values of x were divided by 20 before estimation. [2]

(ii) Rewrite the estimated equation including the standard errors and R2 that would re-
sult if all values of x and y were divided by 20 before estimation. [2]

(b) Consider a simple linear regression model that can be written as:

yi = β1 + β2 x2i + ei , i = 1, 2, ..., N,

where the β s are the parameters, and ei is the IID random error term ∼ (0, σ 2 ), and i
denotes the number of observations, and N is the sample size. Let ȳ be the mean value
of y, and ês be the least square residuals. R2 is the coefficient of determination, and SSR
denotes the sum of squares due to regression and SST denotes the total sum of squares.

(i) Given that sample size is N = 20, Σyi 2 = 5930.94, ȳ = 16.035, and SSR = 666.72,
find R2 . [3]

(ii) Given that R2 =0.7911, SST = 552.36, ȳ = 16.035, and N = 20, find the unbiased
estimator of σ 2 . [3]

(c) Consider a linear regression model written as:

yi = β1 + β2 x2i + ei ,

where the β s are the parameters and ei is the IID random error term ∼ (0, σ 2 ), and i
denotes the number of observations. Let b1 and b2 be the least squares estimators of β1
and β2 , respectively. Complete the following questions, giving as much detail as possible.

(i) State the Gauss-Markov Theorem about the least squares estimators b1 and b2 . [4]

(ii) Prove the Gauss-Markov theorem for the least squares estimator b2 of β2 . [12]

Page 2 Turn over

 A28242 Any Calculator, Statistical tables

2. (a) Consider a random walk model

yt = yt−1 + vt .

(i) Rewrite yt as a function of lagged errors. [1]

(ii) What is the mean and variance of yt ? [4]

(iii) What is the covariance between yt and yt−2 ? [2]

(b) The monthly data sets on industrial production and the Standard & Poor’s 500 Index are
collected to fit the following model:

pcipt =
[ 1.54+ 0.344pcipt−1 +0.074pcipt−2 +0.073pcipt−3 +0.031pcspt−1 ,
(se) (0.56) (0.042) (0.045) (0.042) (0.013)
n = 554, R2 = 0.174, R̄2 = 0.168,

where pcip is the percentage change in monthly industrial production, at an annualized

rate, and pcsp is the percentage change in the Standard & Poor’s 500 Index, also at an
annualized rate.

(i) If the past three months of pcip are zero and pcspt−1 = 0, what is the predicted
growth in industrial production for this month? Is it statistically different from zero? [3]

(ii) If the past three months of pcip are zero and pcspt−1 = 10, what is the predicted
growth in industrial production for this month? Is it statistically different from zero? [3]

(iii) What can you conclude about the effects of the stock market on real economic ac-
tivity? [3]

(c) David used SAS to check whether the model yi = β1 +β2 xi +ei has the heteroskedasticity
issue, where y is the dependent variable, x is the only explanatory variable, e is the error
term and i stands for the i-th number of the observations. He read in the data into SAS,
checked the descriptions of the variables carefully, and he was sure that the data was
imported correctly.

Question 2 continued overleaf.

Page 3 Turn over

A28242 Any Calculator, Statistical tables

Now David wants to use the graphical method first, plotting the least squares residuals
against x. He made the program run, however, he accidentally deleted some words and
letters which made the program look like the one listed below. How can you help him fix
this program so that he can make a plot of the least squares residuals against x? [3]

proc reg data=question6;

model y = x;
output out=foodout ;
title ’OLS and outputs’;

run;

proc gplot data= ; * plot using output data;

plot ehat * ; * residuals vs. x-variable;
title ’Residual plots for variable x’;
run;

(d) Suppose that a time series process yt is generated by yt = z + et , for all t = 1, 2, ...,
where et is an IID sequence with mean zero and variance σe2 . The random error z does
not change over time, and it has mean zero and variance σz2 . Assume that each et is
uncorrelated with z. Answer the following questions, giving as much detail as possible.

(i) Find the expected value and the variance of yt . [3]

(ii) Find Cov(yt , yt+h ) for any t and h. Is yt covariance stationary? [3]

Page 4 Turn over

 A28242 Any Calculator, Statistical tables

3. (a) A statistician studied a sample of data from 935 working men, and he fitted the following
equation:
[ = 10.36 − 0.094sib + 0.131meduc + 0.210 f educ,
educ

and
n = 722, R2 = 0.214,

where educ is years of schooling, sibs is number of siblings, meduc is mother’s years of
schooling, and f educ is father’s years of schooling. Use his results to answer the following
questions.

(i) Holding meduc and f educ fixed, by how much does sibs have to increase to reduce
predicted years of education by one year? Show your calculation.(A non-integer
answer is acceptable here.) [3]

(ii) Interpret the coefficient on meduc. [3]

(iii) Suppose Mr. A has no siblings, and his mother and father each have 12 years of
education. While Mr. B has no siblings, and his mother and father each have 16
years of education. What is the predicted difference in years of education between
Mr. B and Mr. A? [3]

(b) Sam hopes to investigate the football players’ salary on major leagues. He collected data
on 353 players, and fitted the following two models:

\ =
lsalary 12.373 +0.177years,
(se) (0.098) (0.0132)
n = 353 SSR = 326.196 R2 = 0.337 σb = 0.964,

\ =
lsalary 11.861 +0.0904years +0.030scoreyr
(se) (0.084) (0.0118) (0.0020)
n = 353 SSR = 198.475 R2 = 0.597 b = 0.753
σ
where the dependent variable, lsalary, is the log of salary. The two explanatory variables
are years in the major leagues (years), and scores achieved per year (scoreyr).

Question 3 continued overleaf.

Page 5 Turn over

A28242 Any Calculator, Statistical tables

(i) How many degrees of freedom are there in each regression model? Why is the σ
b
smaller in the second regression model than in the first one? Explain your argument
clearly. [4]

(ii) If the sample correlation between years and scoreyr is about 0.487, would you be
concerned about the collinearity? Explain your argument clearly. [3]

(iii) Explain in detail why the standard error for the coefficient on years in the multiple
regression model is lower than its counterpart in the simple regression model. [3]

(c) A multiple linear regression model with two explanatory variables can be written as:

y = β1 + β2 x2 + β3 x3 + ε

where the β s are the parameters and ε is the random error term ∼ (0, σ 2 ). You are
interested in estimating the sum of the parameters on x1 and x2 , which is denoted as
θ = β2 + β3 . Complete the following questions, giving as much detail as possible.

(i) Show that θb = βb2 + βb3 is an unbiased estimator of θ . [3]

(ii) Find the variance of θb in terms of Var(βb2 ), Var(βb3 ), and the correlation between βb2
and βb3 . [2]

Page 6 Turn over

 A28242 Any Calculator, Statistical tables

4. (a) Consider the following model yt = 0.5yt−1 + xt + v1t , and xt = 0.5xt−1 + v2t , where both
v1t and v2t follow IID normal distribution ∼ (0, 1). Examine the following statements, state
whether they are true or false first, and then explain why they are true or false.

(i) The time series yt is weakly stationary. [2]

(ii) The unconditional variance of yt is larger than the conditional one-step ahead variance. [3]

(iii) The upper bound for the 95 percent conditional 1-step ahead confidence interval for
yt is 2. [3]

(iv) The series yt and xt share a common stochastic trend. [2]

(v) The series yt and xt have the same unconditional mean. [2]

(vi) If yt = 1 and xt = 1, then E[yt+1 |yt , xt ] = 1. [3]

(vii) If yt = 1, xt = 1, v1t = 1, and v2t = 1, then E[yt+1 |yt , xt ] 6= 1. [2]

(viii) If yt = 0 and xt = −0.8, then E[yt+1 |yt , xt ] = −0.8. [2]

(b) Suppose that yt and zt are I(1) series, but yt − β zt is I(0) for some β 6= 0. Show that for
any δ 6= β , yt − δ zt must be I(1). [6]

Page 7 Turn over

 A28242 Any Calculator, Statistical tables

5. (a) Discuss which of the following three cases can cause OLS estimators to be biased. [4]

(i) Heteroskedasticity.

(ii) Omitting an important variable.

(iii) A sample correlation coefficient of 0.95 between two independent variables both
included in the model.

(b) Suppose you have estimated the following model of fertility and the amount of personal
tax exemption for the years 1913 through 1984 in the United States:

f rt =
gd 92.05+ 0.089pet −0.004pet−1 +0.0074pet−2 −21.34ww2t −31.08pillt
(se) (3.33) (0.126) (0.153) (0.165) (11.51) (3.90)
n = 68, R2 = 0.537,

where the variable g f r is the general fertility rate which is the number of children birth
to every 1,000 women of childbearing age, and pe is the average real dollar value of the
personal tax exemption. The variable ww2 takes on the value unity during the years 1941
through 1945, when the United States was involved in World War II. The variable pill is
unity from 1963 onward, when the birth control pill was made available for contraception.
t stands for the number of observations in the time series data.

(i) Interpret the coefficient on pet . Be specific. [2]

(ii) Interpret the coefficient on ww2t . Be specific. [2]

(iii) What is the long-run effect of pe on g f r? [2]

(iv) How would you test whether the long-run effect is statistically significant? [4]

(v) How would you modify the model if you suspect that some of the variables exhibit a
linear time trend? [4]

(vi) Suppose that g f r and pe both have upward time trends. What would be a potential
consequence of not including a time trend in the regression model? What is this
phenomenon called? [2]

(vii) Suppose that g f r and pe both have upward time trends. How would you obtain a
goodness-of-fit measure which is not affected by the presence of time trend? Explain
your arguments in details. [5]

Page 8 Turn over

 A28242 Any Calculator, Statistical tables

6. (a) Discuss which of the following three cases that can cause the usual OLS t-statistics to be
invalid (that is, not to have t distributions under the null hypothesis). [4]

(i) Heteroskedasticity.

(ii) A sample correlation coefficient of 0.95 between two independent variables that are
in the model.

(iii) Omitting an important variable.

(b) True or False? Explain your decision for the following statements.

(i) When the errors in a regression model have AR(1) serial correlation, the OLS stan-
dard errors are still the best among other linear estimators. [3]

(ii) The weighted least squares method is preferred to OLS when an important variable
has been omitted from the model. [3]

(iii) The OLS estimators are no longer BLUE (best linear unbiased estimators) under the
situation of the heteroskedasticity. [2]

(c) Let math10 denote the percentage of students at Michigan high schools in the U.S. re-
ceiving a passing score on a standardized math test. We are interested in estimating
the effect of per-student spending on maths performance. A model is developed for 428
schools:

math10 = β1 + β2 log(expend) + β3 log(enroll) + β4 poverty + e,

where poverty is the percentage of students living in poverty which is measured by a

proxy variable, lnchprg. The variable lnchprg is the percentage of students eligible for
the government funded school meal programme for low-income household. log(enroll)
is the logarithmic form of student enrollment for each school, the β s are parameters and
e is the random error.

Question 6 continued overleaf.

Page 9 Turn over

A28242 Any Calculator, Statistical tables

The table that follows contains OLS estimates, with and without lnchprg as an explanatory
variable.

Estimation results with Standard Errors in the Parentheses

Coefficients Model 1 Model 2

Intercept −69.24 −23.14
(26.72) (24.99)
log(expend) 11.13 7.75
(3.30) (3.04)
log(enroll) 0.022 −1.26
(0.615) (0.58)
lnchprg −0.324
(0.036)
R − squared 0.0297 0.1893

(i) Explain why the effect of expenditures on math10 is lower in Model (2) than in Model
(1)? Is its effect in model (2) still statistically greater than zero? [3]

(ii) Does it appear that pass rates are lower at larger schools, other factors being equal?
Explain your arguments. [3]

(iii) Interpret the coefficient on lnchprg in Model (2). [2]

(iv) How can you explain the substantial increase in R2 from Model (1) to Model (2)? [4]

Page 10 Turn over

 2016
16(UoB)
A28242 Any Calculator, Statistical tables

1. (a) Briefly discuss the following questions.

(i) What is the consequence of specifying a model with a variable in logarithmic form,
if in the true population model, the variable is actually in its level form? [2]

(ii) Is a regression with a low R2 useless? Explain. What does a low R2 imply about the
specified regression model? [2]

(iii) Suppose you have N observations on a variable with constant mean µ but a he-
teroskedastic variance. What is the heteroskedasticity-consistent (White corrected)
estimate of the variance? How does it compare to the usual estimate of this variance
that ignores heteroskedasticity? [4]

(b) True or False? Explain your decision for the following statements.

(i) By including one more independent variable in the regression, you will eliminate the
possibility of omitted variable bias from excluding that variable. [2]

(ii) The central limit theorem states that sums of random variables, properly standardi-
zed, converge in distribution to standard normal. [2]

(iii) The OLS estimators are no longer BLUE (best linear unbiased estimators) under the
situation of the heteroskedasticity. [2]

(c) Suppose you estimate the consumption function of Yi = α1 + α2 Xi + ei and the savings
function of Zi = β1 + β2 Xi + ui , where Y denotes for consumption, Z denotes for savings,
X denotes for income, α ’s and β ’s are parameters and e and u are the random error
terms. Furthermore, X = Y + Z , that is, income is equal to consumption plus savings,
and variables are all in numerical terms.

(i) What is the relationship, if any, between the OLS estimators of α

c2 and βb2 ? Show
your calculations. [4]

(ii) Will the residual (error) sum of squares be the same for the two models of Yi =
α1 + α2 Xi + ei and Zi = β1 + β2 Xi + ui ? Explain your answer. [4]

(iii) Can you compare the R2 terms of the two models? Explain your answer. [3]

Page 2 Turn over

 A28242 Any Calculator, Statistical tables

2. (a) (i) Supposing that a simple linear regression has quantities N = 20, ∑N 2
i=1 yi = 5930.94,
ȳ = 16.035, and regression sum of the squares SSR = 666.72, show your calculati-
ons and find R2 . [3]

(ii) Supposing that a simple linear regression has quantities N = 20, total sum of squa-
res SST = 552.36, and R2 = 0.7911, show your calculations and find σ̂ 2 . [3]

(b) A sample of 300 Chicago households was taken to investigate how far American house-
holds tend to travel when they take vacation. The interested variables are listed as follows:
MILES measures the distance in miles per year, INCOME measures the annual income
of the household in $1000, AGE measures the average age of the adult members of the
household and KIDS measures the number of children in household. The following model
was estimated

MILES = β1 + β2 INCOME + β3 AGE + β4 KIDS + e,

where β ’s are parameters and e is the random error term.

(i) Ordering the observations according to descending values of INCOME , and ap-
plying least squares to the first 150 observations, and again to the second 150
observations, yields the sums of squared errors of SSE1 and SSE2, respectively
where
SSE1 = 2.9471 × 107 , SSE2 = 1.0479 × 107 .
Use the Goldfeld-Quandt test to test for heteroskedasticity of errors. Include speci-
fication of the null and alternative hypotheses. You may use an approximate critical
value as the distribution table may not provide the threshold values for the exact
degrees of freedom that you look for. [7]

(ii) Table 1 (overleaf) contains three sets of estimates: those from least squares, those
from least squares with White’s standard errors, and those from generalized least
squares under the assumption of σi2 = σ 2 × INCOME 2 .

(1) How do vacation miles travelled depend on INCOME , AGE and KIDS? [3]
(2) How do White’s standard errors compare with the least squares standard er-
rors? Do they change your assessment of the precision of estimation? [4]
(3) Is there evidence to suggest that the generalised least squares estimates are
better estimates? Justify your answer. [5]

Page 3 Turn over

A28242 Any Calculator, Statistical tables

Least squares estimate

Parameter Standard
Variable DF Estimate Error t value Pr > |t|
Intercept 1 -391.55 169.78 -2.31 0.022
INCOME 1 14.20 1.80 7.89 0.000
AGE 1 15.74 3.76 4.19 0.000
KIDS 1 -81.83 27.13 -3.02 0.003

Least squares estimates with White standard errors

Parameter Standard
Variable DF Estimate Error t value Pr > |t|
Intercept 1 -391.55 142.65 -2.74 0.007
INCOME 1 14.20 1.94 7.32 0.000
AGE 1 15.74 3.96 3.97 0.000
KIDS 1 -81.83 29.15 -2.81 0.006

Generalised least squares estimates

Parameter Standard
Variable DF Estimate Error t value Pr > |t|
Intercept 1 -425.00 121.44 -3.50 0.001
INCOME 1 13.95 1.48 9.42 0.000
AGE 1 16.72 3.02 5.53 0.000
KIDS 1 -76.81 21.85 -3.52 0.001
Table 1 Output for 1 (a) (iii)

Page 4 Turn over

 A28242 Any Calculator, Statistical tables

3. (a) Researchers at the Boston College wished to investigate individuals’ earning by using
a random sample of 935 respondents throughout the United States. Let ln(wage) be
the logarithmic transformation of an individual’s weekly earning in dollars, IQ denotes an
individual’s IQ score, educ denotes the number of years of an individual’s education, and
tenure denotes the number of years with current employer.

(i) What would be the likely sign of the bias of the coefficient on IQ if we omit educ
from the true model: ln(wage) = β1 + β2 IQ + β3 educ + β4tenure + u, where u is
the random error term and β s are the parameters? Explain your answer. [4]

(ii) What is the effect of increasing the sample size on the standard errors of the partial
coefficients? [3]

(iii) What is the effect of increasing the sample size on the bias of the partial coefficients?
[2]

(b) Table 2 contains computer output after estimating the following two models to the same
35 observations. The models are

y = β1 + β2 x + β3 w + e, (1)

y = β1 + β2 x + e. (2)

Implementing the regression specification error test (RESET) yields F-value of 17.98 (for
ŷ2 ) and 8.72 (for ŷ2 and ŷ3 ). The correlation between x and w is 0.975. Answer the
following questions.

Variables Model (3) Model (4)

Intercept 3.6356 -5.8382
(2.763) (2.000)
x -0.99845 4.1072
(1.235) (0.3383)
w 0.49785
(0.1174)
Table 2 Estimation results with Standard Errors in the Parentheses

Page 5 Turn over

A28242 Any Calculator, Statistical tables

(i) Should w be included in the model? Justify your answer. [4]

(ii) What can you say about omitted variable bias? [4]

(iii) What can you say about the existence of collinearity and its possible effect? List and
explain two methods to detect collinearity. [4]

(iv) What would happen if we use RESET augmenting the model with the predictor, ŷ? [4]

Page 6 Turn over

 A28242 Any Calculator, Statistical tables

4. (a) Hanushek and Jackson (1977) estimate the following model to study the effect of defense
expenditures on other expenditures in the economy:

Ct = β1 + β2 GNPt + β3 Dt + ut , (1)

where Ct is the aggregate private consumption expenditure in year t , GNPt refers to the
gross national product in year t , and Dt is the national defense expenditures in year t , u
is the random error term, and β s are the parameters. Postulating that the variance could
be σt2 = σt2 (GNPt )2 , they transform equation (1) and estimate

Ct /GNPt = β1 (1/GNPt ) + β2 + β3 (Dt /GNPt ) + ut /GNPt . (2)

The empirical results based on the data from 1946 to 1975 given as follows(standard
errors in the parentheses):

Cbt = 26.190+ 0.6248GNPt −0.4398Dt

(se) (2.760) (0.0060) (0.0736) R2 = 0.999,
Ct\
/GNPt = 25.920(1/GNPt )+ 0.6246 −0.4315(Dt /GNPt )
(se) (2.220) (0.0068) (0.0597) R2 = 0.875.

(i) What assumption(s) are(is) made by the authors? What is the statistical terminology
for this postulation? How to justify it? [4]

(ii) Compare the results of the two models, comment on your findings. [3]

(iii) Can you compare R2 values for the two models? Explain your answer. [3]

(iv) What are its implications? Provide two formal statistical tests to examine the non-
constant variance. [8]

(v) What is the method used in Model (2) to correct for the non-constant variance? If
the variance function is known, how can you correct the problem of the non-constant
variance? [5]

(b) State whether the following statement is true or false. Briefly justify your answer. ”When
autocorrelation is present, OLS estimators are biased as well as inefficient”. [2]

Page 7 Turn over

 A28242 Any Calculator, Statistical tables

5. (a) (i) Explain trend-stationary process and difference-stationary process, respectively. [2]

(ii) What is the error correction mechanism? What is its relationship with cointegration?
[2]

(iii) State whether the following statement is true or false. Briefly justify your answer.
”The Durbin-Watson test assumes that the variance of the error term is homosce-
dastic”. [2]

(b) The following model examines how the return to education and the gender gap have
changed from 1978 to 1985 using the US data. The results are presented as follows
(standard errors in the parentheses):

\ =
ln(wage) 0.459 +0.118y85 +0.0747educ +0.0185y85 × educ
(s.e. =) (0.093) (0.124) (0.0067) (0.0094)
+0.0296exper −0.0004exper2 +0.202union
(s.e. =) (0.0036) (0.00008) (0.030)
−0.317 f emale +0.085y85 × f emale
(s.e. =) (0.037) (0.051)
2
n = 1084, R2 = 0.426, R = 0.422

where ln(wage) is the logarithmic term of hourly nominal wage, educ is the years of
education, exper refers to the years of experience and exper2 is its squared term. The
variable y85 is a dummy variable equal to 1 if the observation comes from 1985 and 0 if it
comes from 1978, union is a dummy variable equal to 1 if the person belongs to a union,
and 0 otherwise, f emale is the gender dummy variable equal to 1 if the person is female
otherwise equal to 0. Both y85 × educ and y85 × f emale are interaction variables.

(i) Interpret the return to education in 1985 and 1978, and comment on your findings. [3]

(ii) Interpret the gender gap, report both the approximate and exact changes. Does the
gender gap increase over years? [3]

(iii) Suppose you suspect that there exists a structural change across the time periods
of 1978 and 1985. What type of test do you plan to implement for the structural
change? Explain clearly how you will carry out the test. [5]

(iv) Interpret the coefficient on y85? (Be careful here; you must account for the inte-
raction terms y85 × educ and y85 × f emale.) [2]

Page 8 Turn over

A28242 Any Calculator, Statistical tables

(v) Now we refit the above equation and let all wages be measured in 1978 dollars. In
particular, define the real wage as rwage which equals to the wage for 1978 and
rwage equals to wage/1.65 for 1985. Then use ln(rwage) in place of ln(wage)
in estimating the model. Which coefficient(s) will differ from those in the above
equation? Will the R2 from the new regression be the same as 0.426? Explain
your answer. [2]

(vi) There was a notable fall in union membership from 1978 to 1985. Describe and
discuss how you will test union participation changed from 1978 to 1985 over time. [4]

Page 9 Turn over

 A28242 Any Calculator, Statistical tables

6. (a) From the data for the period of the first quarter in 1971 to the fourth quarter in 1988 for
Canada, the following results were obtained:

\t =
lnM1 −10.2571 +1.5975lnGDPt model(1)
(t − value =) (−12.9422) (25.8865) R2 = 0.9463, d = 0.3254
\t =
∆lnM1 0.0095 +0.5833∆lnGDPt model(2)
(t − value =) (2.4957) (1.8958) R2 = 0.0885, d = 1.7399
∆ût = −0.1958ût−1 model(3)
(τvalue) (−2.2521) R2 = 0.1118, d = 1.4767.

where M1 is the most liquid part of money supply including paper and coins, checking
account and etc., GDP refers to the gross domestic product measured in billions of Cana-
dian dollars, ln is the natural logarithmic term and ût represents the residuals from model
(1).

(i) Interpret fitted regression results for model (1). [3]

(ii) Based on the results from models (1) and (2), do you suspect that model (1) is
spurious? Explain your answer. [3]

(iii) From the above results, comment on cointegration. You need to explain your answer
clearly. [4]

(iv) Now use the same notation and consider the following model:

\t =
∆lnM1 0.0084 +0.7340∆lnGDPt −0.0811ût−1 (4)
(t − value =) (2.0496) (2.0636) (−0.8537)
R2 = 0.1066, d = 1.6697

Comment on this model. Is Model (1) spurious? Explain your answer. [5]

(b) What is the difference between the tests of unit roots and the tests of cointegration? [2]

(c) The first-difference transformation to eliminate autocorrelation assumes that the parame-
ter of autocorrelation ρ is −1. Is the statement true or false? Briefly justify your answer.
[2]

Page 10 Turn over

A28242 Any Calculator, Statistical tables

(d) Suppose we wish to explain a dependent variable y and that the number of possible expla-
natory variables (x1 , x2 , ..., xK ) is so large that it is tempting to take a subset of explanatory
variables. In such a situation, some researchers apply the so-called Theil criterion and
maximize the adjusted R2 , which is defined by

(n − 1)
R̄2 = 1 − (1 − R2 ),
n − (K − 1)

where n is the number of observations, K is the number of parameters, and (K − 1) is

the number of explanatory variables. For the null hypothesis of β j = 0, where β j is the
parameter for an explanatory variable x j , show that the Theil criterion implies that x j will
be maintained if and only if the F-test statistic > 1. [6]

Page 11 Turn over

 A28242
17(UoB)
2017
Any Calculator, Statistical tables

1. (a) Sam hopes to investigate the football players’ salary on major leagues. He collected data
on football players, and fitted the following two models:

\ =
lsalary 12.373 +0.177years,
(se) (0.098) (0.01325)
SSE = 326.196 R2 = 0.337,

\ =
lsalary 11.861 +0.0904years +0.030scoreyr
(se) (0.084) (0.0118) (0.0020)
SSE = 198.475 R2 = 0.597.
where the dependent variable, lsalary, is the log of salary. The two explanatory variables
are years in the major leagues (years), and scores achieved per year (scoreyr). SSE is
the error sum of squares.

(i) Find the sample size in Sam’s data. Keep five decimal places in the calculation but
round to the nearest integer for the result. [6]

(ii) How many degrees of freedom are there in each regression model? Why is the σ
b
smaller in the second regression model than in the first one? Explain your argument
clearly. [4]

(iii) If the sample correlation between years and scoreyr is about 0.697, and Sam also
fitted the following model, would you be concerned about the collinearity? Explain
your argument. [4]

[=
years 3.25 +0.217scoreyr,
(se) (1.18) (0.0132)
R2 = 0.50

(iv) Explain in detail why the standard error for the coefficient on years in the multiple
regression model is lower than its counterpart in the simple regression model. [4]

Question 1 continued overleaf.

Page 2 Turn over

A28242 Any Calculator, Statistical tables

Question 1 continued.

(b) Consider a linear regression model that can be written as:

yi = β1 + β2 x2i + ... + βk xki + ei , i = 1, 2, ..., N,

where the β s are the parameters, ei is the IID random error term ∼ (0, σ 2 ), and i denotes
the number of observations, and N is the sample size. When you fit the model, you can
find the values of R2 and F -statistic in the ANOVA table. Show that

R2 /(k − 1)
F= ,
(1 − R2 )/(N − k)

where is k refers to the number of parameters in the model. [4]

(c) A multiple linear regression model with two explanatory variables can be written as:

y = β1 + β2 x2 + β3 x3 + ε,

where the β s are the parameters and ε is the random error term ∼ (0, σ 2 ). You are
interested in estimating the sum of the parameters on x2 and x3 , which is denoted as
θ = β2 + β3 . Complete the following questions, giving as much detail as possible.

(i) Show that θb = βb2 + βb3 is an unbiased estimator of θ . [1.5]

(ii) Find the variance of θb in terms of Var(βb2 ), Var(βb3 ), and the correlation between βb2
and βb3 . [1.5]

Page 3 Turn over

 A28242 Any Calculator, Statistical tables

2. (a) Consider a simple linear regression model that can be written as:

yi = β1 + β2 x2i + ei , i = 1, 2, ..., N,

where the β s are the parameters, ei is the IID random error term ∼ (0, σ 2 ), and i denotes
the number of observations, and N is the sample size. Let ȳ be the sample mean of y, R2
is the coefficient of determination, SSR denotes the sum of squares due to regression and
SST denotes the total sum of squares.

(i) Find R2 , given that the sample size is N = 20, Σyi 2 = 5930.94, ȳ = 16.035, and
SSR = 666.72. [3]

(ii) Find the unbiased estimator of σ 2 , given that R2 =0.7911, SST = 552.36, ȳ = 16.035,
and N = 20. [2]

(b) Consider a linear regression model written as:

yi = β1 + β2 x2i + ei ,

where the β s are the parameters, ei is the IID random error term ∼ (0, σ 2 ), and i denotes
the number of observations. Let b1 and b2 be the least squares estimators of β1 and β2 ,
respectively. Complete the following questions, giving as much detail as possible.

(i) State the Gauss-Markov Theorem about the least squares estimators b1 and b2 . [3]

(ii) Prove the Gauss-Markov theorem for the least squares estimator b2 of β2 . [8]

(iii) Let SST, SSR and SSE denote the total sum of squares, the regression sum of
squares, and the error sum of squares, respectively. Prove that SST = SSR + SSE . [8]

Page 4 Turn over

 A28242 Any Calculator, Statistical tables

3. (a) Prof. Stats EZ has decided that writing the least squares estimator is too much trouble.
Noting that two points determine a line, Dr. EZ chooses two points from a sample of size
N and draws a line between them, calling the slope of this line the EZ estimator of β2
in the simple regression model of Yi = β1 + β2 Xi + ei , where Y and X assume non-zero
values, β s are the parameters, ei is the random error term, and i denotes the number of
observations. Algebraically, if the two points are (x1 , y1 ) and (x2 , y2 ), the EZ estimation
rule is
y2 − y1
bEZ = .
x2 − x1
Assuming all the assumptions of a simple regression model hold, answer the following
questions:

(i) Show that bEZ is a linear and unbiased estimator of β2 . [4]

(ii) Find the variance of bEZ . [2]

(iii) Find the probability distribution of bEZ . [2]

(iv) Convince Dr. EZ that the EZ estimator is not as good as the least squares estimator.
No proof is required here. [4]

Question 3 continued overleaf.

Page 5 Turn over

A28242 Any Calculator, Statistical tables

Question 3 continued.

(b) The table below contains computer output after estimating the following two models for
the same 35 observations. The models are

y = β1 + β2 x + β3 w + e, (1)

y = β1 + β2 x + e. (2)

Implementing the regression specification error test (RESET) suggests augmenting an

existing model with the squares of its predictions, or with their squares and cubes. RESET
applied to the second model yields F-values of 17.98 (for ŷ2 ) and 8.72 (for ŷ2 and ŷ3 ).
The correlation between x and w is 0.975. Answer the following questions.

(i) Should w be included in the model? [4]

(ii) What can you say about the omitted variable bias? [3]

(iii) What can you say about the existence of collinearity and its possible effect? [3]

(iv) What would happen if we use RESET augmenting the model with the predictor, ŷ? [3]

Variables Model (1) Model (2)

Intercept 3.6356 -5.8382
(2.763) (2.000)
x -0.99845 4.1072
(1.235) (0.3383)
w 0.49785
(0.1174)
Table Estimation results with Standard Errors in the Parentheses

Page 6 Turn over

 A28242 Any Calculator, Statistical tables

4. (a) Consider the following model yt = 0.5yt−1 + xt + v1t , and xt = 0.5xt−1 + v2t , where both
v1t and v2t follow an IID normal distribution ∼ (0, 1). Examine the following statements,
state whether they are true or false first, and then explain why they are true or false.

(i) The time series yt is weakly stationary. [2]

(ii) The unconditional variance of yt is larger than the conditional one-step ahead vari-
ance. [2]

(iii) The path of forecasts for yt+i conditional on the information available at time t will
be oscillatory but it will eventually converge to 0.1. [2]

(iv) If a sample of 1000 observations were simulated from this model for yt , then at least
five values will be expected to be larger than 6. [2]

(v) The upper bound for the 95 percent conditional 1-step ahead confidence interval for
yt is 2. [2]

(b) A sample of 500 Birmingham households was taken to investigate how far British house-
holds tend to travel when they take vacation. The interested variables are listed as follows:

MILES measures the distance in miles per year, INCOME measures the annual income
of the household in $1000, AGE measures the average age of the adult members of the
household and KIDS measures the number of children in household.

Question 4 continued overleaf.

Page 7 Turn over

A28242 Any Calculator, Statistical tables

Question 4 continued.

The following model was estimated

MILES = β1 + β2 INCOME + β3 AGE + β4 KIDS + e,

where β s are parameters and e is the random error term.

(i) Suppose that you fit the model by the least squares method and the residuals are
plotted against INCOME . You found out that the residuals increase with income.
What does this suggest to you in terms of variance? What misleading inferences
are there likely to be? [3]

(ii) Ordering the observations according to descending values of INCOME , and apply-
ing least squares to the first 250 observations, and again to the second 250 observa-
tions separately, yields the sums of squared errors of SSE1 and SSE2, respectively
where,
SSE1 = 8.9471 × 108 , SSE2 = 4.0479 × 108 .

Use the Goldfeld-Quandt test to test for heteroskedasticity of errors. Include specifi-
cation of the null and alternative hypotheses. [6]

(iii) Table 1 contains three sets of estimates: those from least squares, those from least
squares with White’s standard errors, and those from generalized least squares un-
der the assumption of σi2 = σ 2 × INCOME 2 .

(1) How do vacation miles travelled depend on INCOME, AGE and KIDS? [2]
(2) How do White’s standard errors compare with the least squares standard er-
rors? Do they change your assessment of the precision of estimation? [2]
(3) Is there evidence to suggest that the generalised least squares estimates are
better estimates? Justify your answer. [2]

Question 4 continued overleaf.

Page 8 Turn over

A28242 Any Calculator, Statistical tables

Question 4 continued.

Least squares estimate

Parameter Standard
Variable DF Estimate Error t value Pr > |t|
Intercept 1 -391.55 169.78 -2.31 0.022
INCOME 1 14.20 1.80 7.89 0.000
AGE 1 15.74 3.76 4.19 0.000
KIDS 1 -81.83 27.13 -3.02 0.003

Least squares estimates with White standard errors

Parameter Standard
Variable DF Estimate Error t value Pr > |t|
Intercept 1 -391.55 142.65 -2.74 0.007
INCOME 1 14.20 1.94 7.32 0.000
AGE 1 15.74 3.96 3.97 0.000
KIDS 1 -81.83 29.15 -2.81 0.006

Generalised least squares estimates

Parameter Standard
Variable DF Estimate Error t value Pr > |t|
Intercept 1 -425.00 121.44 -3.50 0.001
INCOME 1 13.95 1.48 9.42 0.000
AGE 1 16.72 3.02 5.53 0.000
KIDS 1 -76.81 21.85 -3.52 0.001
Table 1 Regression results

Page 9 Turn over

 A28242 Any Calculator, Statistical tables

5. (a) Suppose that yt and zt are I(1) series, but yt − β zt is I(0) for some β 6= 0. Show that for
any δ 6= β , yt − δ zt must be I(1). [6]

(b) Consider the wage equation

ln(WAGE) = β1 + β2 EDUC + β3 EDUC2 + β4 EXPER + β5 EXPER2

+ β6 (EDUC × EXPER) + β7 HRSW K + β8 FEMALE + e, (3)

where WAGE = earnings per hour in dollars, EDUC = years of education, EXPER = years
of post education experience, HRSWK = usual hours worked per week, and FEMALE is
an indicator variable, FEMALE=1 if an individual is female, 0 otherwise.

The summary statistics of each variable are reported in Table 2, and estimation results for
the above model and its modified versions are displayed in Table 3 (overleaf).

Variable N Mean Std Dev Minimum Maximum

WAGE 1000 20.201 12.104 2.030 72.130
EDUC 1000 10.689 2.440 1.000 16.000
EXPER 1000 26.501 12.990 3.000 64.000
HRW KS 1000 39.240 11.446 0.000 99.000
FEMALE 1000 0.501 0.47 0.000 1.000
Table 2: The MEANS Procedure

(i) Write out the equation based on SAS output results from Table 3 for Model (D) only.
[2]

(ii) What is the wage difference between women and men using Model (A)? Report both
an approximate calculation and an exact calculation. Perform an appropriate statisti-
cal test to examine whether women had lower wage than men using the results from
Model (A). [6]

(iii) What restrictions on the coefficients of Model (A) would produce Model (C)? Use an
F-test to test these restrictions. What question(s) can you answer by performing this
test? [6]

(iv) Consider all of these models from Model (A) to Model (E) carefully. Which model
would you prefer? Why? Explain and demonstrate your answer in detail. [5]

Question 5 continued overleaf.

Page 10 Turn over

A28242 Any Calculator, Statistical tables

Question 5 continued.

Variables Model (A) Model (B) Model (C) Model (D) Model (E)
Intercept 0.576 0.378 0.744 0.927 0.325
(0.266) (0.190) (0.188) (0.080) (0.096)
EDUC 0.0498 0.0289 0.0366 0.1006
(0.0397) (0.0344) (0.0350) (0.0063)
EDUC2 0.00319 0.00352 0.00293
(0.00169) (0.00166) (0.00170)
EXPER 0.0373 0.0303 0.0279 0.0295
(0.0081) (0.0048) (0.0054) (0.0048)
EXPER2 0.000485 0.000456 -0.00047 -0.000440
(0.00009) (0.000086) (0.000096) (0.000086)
EDUC × EXPER -0.00051
(0.000482)
HRSW K 0.01145 0.01156 0.01345 0.01524 0.01188
(0.00137) (0.00137) (0.00136) (0.00151) (0.00136)
FEMALE -0.150 -0.164 -0.161
(0.132) (0.145) (0.141)
SSE 222.4166 222.6674 233.8317 280.5061 223.6716
AIC -1.494 -1.490 -1.445 -1.488
SC -1.461 -1.426 -1.244 -1.463
Table 3: Estimation Results with Standard Errors in the Parentheses

Page 11 Turn over

 A28242 Any Calculator, Statistical tables

6. (a) Consider an ARDL(1, 1) model which can be written as:

yt = δ + θ1 yt−1 + δ0 xt + δ1 xt−1 + vt

where δ and θ are the parameters and vt is the random error term. Complete the following
questions, giving as much detail as possible:

(i) Derive its error correction model. [7]

(ii) What is the cointegrating relationship embedded in the error correction model? [1]

(iii) What is the error correction term? [1]

(iv) Does the error correction model only allow us to study the long-run relationship
between yt and xt ? Why the error correction model is popular? Justify your answer. [3]

(v) What problem will occur if you add another lag of the error correction term into the
model? Show your derivation. [7]

(b) Consider the following model

yi = β1 + β2 xi∗ + ei

where the β s are the parameters and ei is the random error term. In practice we can only
measure xi∗ by xi . Answer the following questions, giving as much detail as possible.

(i) What is the effect of measurement error on estimates of true β1 and β2 if xi = xi∗ +5?
[2]

(ii) What is the effect of measurement error on estimates of true β1 and β2 if xi = 3xi∗ ? [2]

(iii) What is the effect of measurement error on estimates of true β1 and β2 if xi = xi∗ +ui ,
where ui is a white noise random error term? [2]

Page 12 Turn over

 2018
18(UoB) Any Calculator, Statistical tables

1. (a) Consider a linear regression model which can be written as:

yi = β1 + β2 x2i + εi

where the β s are the parameters, ε is the IID random error term ∼ (0, σ 2 ) and i denotes
the number of observation, i = 1, ..., N . Let b1 and b2 be the ordinary least squares (OLS)
estimators of β1 and β2 respectively. The model satisfies the assumptions of OLS. The
usual OLS estimators b1 and b2 are unbiased for their respective parameters. Let β˜2
be the estimator of β2 by assuming the intercept term is zero. Complete the following
questions, giving as much detail as possible:

(i) List the assumptions of the OLS, and explain them briefly. [3]

(ii) What is the Gauss-Markov Theorem about the least squares estimators b1 and b2 ? [3]

(iii) Find E(β˜2 ). [6]

(iv) Verify that β˜2 is unbiased for β2 when the intercept parameter β1 is zero. Are there
any other cases where β˜2 is unbiased? [3]

(v) Find the variance of β˜2 , i.e., Var(β˜2 ). [4]

(b) Consider a linear regression model which can be written as:

yi = β1 + ei

where the β1 is the intercept parameter and e is the IID random error term. Let β˜1 be the
OLS estimator of β1 , and let i denote the number of observation, i = 1, ..., N .

(i) Show that β˜1 = ȳ, that is, the sample average is the estimator. [4]

(ii) Show that the residual terms always sum to zero. [2]

A28242 Page 2 Turn over

 Any Calculator, Statistical tables

2. (a) We are interested in the effect of per-student spending on maths performance for 428
schools in Michigan, U.S. Let math10 denote the percentage of Year-Ten students receiv-
ing a passing score on a standardised maths test, expend denote the school expenditure
per student in dollars, enroll denote the school enrollments, and poverty denote the per-
centage of students living in poverty. A model for each school is presented as follows:

math10i = β1 + β2 log(expendi ) + β3 log(enrolli ) + β4 log(povertyi ) + ei

where the β s are the parameters, ei is the random error term, and i denotes the ob-
servation of schools in the data, i = 1, ..., N . Assuming all the assumptions of a linear
regression model hold, using the estimation results in the table below answer the follow-
ing questions:

(i) The variable lnchprg is the percentage of students eligible for the government funded
school lunch programme. Do you think it is a sensible proxy variable for poverty?
Explain your answer briefly. Interpret the coefficient of lnchprg in Model (2). [3]

(ii) The table below contains OLS estimates. Explain the effect of expenditures on
math10. Why is the effect lower in Model (2)? [3]

(iii) Explain the effect of school size on pass rates. [2]

(iv) Comment on the change of R2 in the models. [2]

Variables Model (1) Model (2)

Intercept -69.24 -23.14
(26.72) (24.99)
log(expend) 11.13 7.75
(3.30) (3.04)
log(enroll) 0.022 -1.26
(0.615) (0.580)
lnchprg – -0.324
– (0.036)
R − squared 0.03 0.189
Estimation results of math10 with Standard Errors in the Parentheses

A28242 Page 3 Turn over

 Any Calculator, Statistical tables

(b) Consider a multiple liner model to explain salaries of CEO (salary) in terms of several fac-
tors listed in the following table. The variable mktval is market value of the firm, pro f marg
is profit as a percentage of sales, ceoten is years as CEO with the current company, and
comten is total years with the company. The log denotes the variable is converted to its
natural logarithm. The sample size is 177. Results are presented in the table below.

(i) Explain the effect of pro f marg on CEO salary. [2]

(ii) Does the market value have a significant effect? Explain the result. [2]

(iii) Explain the effects of ceoten and comten on CEO salary. [2]

(iv) Comment on the result that longer tenure with the company is associated with a
lower salary, holding other factors constant. [2]

(v) Now when the squared terms of ceoten and comten are added to Model (3), the
R2 value increases to 0.375. Is there any evidence of misspecification of Model
(3)? Describe a test which can help examine misspecificationn. You need to include
the general model(s), the null and alternative hypothesis, the test statistic and the
rejection rule. [7]

Variables Model (1) Model (2) Model (3)

Intercept 4.94 4.62 4.57
(0.20) (0.25) (0.25)
log(sales) 0.224 0.158 0.188
(0.027) (0.40) (0.40)
log(mktval) – 0.112 0.100
– (0.050) (0.049)
pro f marg – -0.0023 -0.0022
– (0.0022) (0.0022)
ceoten – – 0.0171
– (0.0055)
comten – – -0.0092
– (0.0033)
R − squared 0.281 0.304 0.353
Estimation results of log(salary) with Standard Errors in the Parentheses

A28242 Page 4 Turn over

 Any Calculator, Statistical tables

3. (a) Consider the model log(WAGE)i = β1 +β2 IQi +β3 EDUi +β4 T ENUREi +ui , i = 1, ..., N,
where WAGE is the logarithmic term of the real wage for a staff member in a university,
IQ represents the score of the intelligence quotient, EDU stands for the years of educa-
tion, and TENURE is an indicator variable denoting whether a staff member has tenured
or not, and u is the random error term, i stands for the index of an individual staff member
in the data, and N stands for the sample size.

(i) Describe how you would examine the joint significance of β3 = 0 and β4 = 0 at 5%
significance level. Describe the steps, state the null and alternative hypotheses, test
statistics and the rejection rule. [5]

(ii) If EDU and IQ are positively correlated and we omit EDU from the model, what
would be the likely sign of the bias of the coefficient? [2]

(iii) If EDU and IQ are positively correlated and we omit EDU from the model, what
would you expect to be the effect of increasing the sample size on the estimated
errors on the parameters? [2]

(iv) If EDU and IQ are positively correlated and we omit EDU from the model, what
would you expect to be the effect of increasing the sample size on the bias of the
coefficient? [2]

(b) True or false: The weighted least squares (WLS) method is preferred to OLS when an
important variable has been omitted from a model. Justify your answer. [4]

(c) Consider a linear model to explain students’ mark in their final year of study. The results
are listed in the following table. Model (1) is for male students, Model (2) is for female stu-
dents, Model (3) and (4) combine all male and female students. The variable f inalmark
is the average mark of in the final year, marksecond is the average mark of the second-
year of study in the university, mark f irst is the average mark of the first-year of study and
male is an indicator variable with being a male equals 1, else 0. There are two interaction
variables, male − marksecond and male − mark f irst , which measure the association be-
tween male and marksecond and mark f irst , respectively. The data is collected based
upon 814 students who have studied statistics in the STATSFUN university.

(i) Interpret the fitted coefficients in Model (3) . [4]

(ii) Perform the Chow test to examine the null hypothesis that the regression models
are the same for male and female students. [6]

A28242 Page 5 Turn over

 Any Calculator, Statistical tables

Variables Model (1) Model (2) Model (3) Model (4)

Intercept 20.52 13.79 15.60 13.79
(3.72) (4.11) (2.80) (3.91)
marksecond 13.60 11.89 12.82 11.89
(0.94) (1.09) (0.72) (1.04)
mark f irst 0.670 1.03 0.838 1.03
(0.150) (0.18) (0.116) (0.17)
male – – 3.17 6.73
– – (0.73) (5.55)
male − marksecond – – – 1.72
– – (1.44)
male − mark f irst – – – -0.364
– – (0.232)
observations 406 408 814 814
R − squared 0.4025 0.3666 0.3946 0.3968
ResidualSumSquares 38781.38 48029.82 87128.96 86811.20
Table Estimation results of f inalmark with Standard Errors in the Parentheses

A28242 Page 6 Turn over

 Any Calculator, Statistical tables

4. (a) Hanushek and Jackson (1977) estimate the following model to study the effect of defense
expenditures on other expenditures in the economy:

Ct = β1 + β2 GNPt + β3 Dt + ut , (1)

where Ct is the aggregate private consumption expenditure in year t , GNPt refers to the
gross national product in year t , and Dt is the national defense expenditures in year t , u
is the random error term, and β s are the parameters. Postulating that the variance could
be σt2 = σt2 (GNPt )2 , they transform equation (1) and obtain

Ct /GNPt = β1 (1/GNPt ) + β2 + β3 (Dt /GNPt ) + ut /GNPt . (2)

The empirical results based on the data from 1946 to 1975 are given as follows (standard
errors in the parentheses),

Cbt = 26.190+ 0.6248GNPt −0.4398Dt

(se) (2.760) (0.0060) (0.0736) R2 = 0.999,
Ct\
/GNPt = 25.920(1/GNPt )+ 0.6246 −0.4315(Dt /GNPt )
(se) (2.220) (0.0068) (0.0597) R2 = 0.875.

(i) What assumption(s) are(is) made by the authors? What is the statistical terminology
for this postulation? How would you justify it? [4]

(ii) Compare the results of the two models, are they largely different from each other?
Comment on your findings. [2]

(iii) Can you compare the R2 values for the two models? Explain your answer. [2]

(iv) What are the consequences of non-constant variance in a model? Provide TWO
formal statistical tests to diagnose the non-constant variance. You need to include
the model, hypotheses, procedures, test-statistic and decision rules. [9]

(v) What is the method used in Model (2) to correct for the non-constant variance? If the
variance function is unknown, how can you correct the problem of the non-constant
variance? [6]

(b) True or false: When autocorrelation is present, OLS estimators are biased as well as
inefficient. Justify your answer. [2]

A28242 Page 7 Turn over

 Any Calculator, Statistical tables

5. (a) The following model examines how the return to education (profits from schooling) and
the gender pay gap have changed from 1978 to 1985 using the US data. The results are
presented as follows (standard errors in the parentheses):
\ =
ln(wage) 0.459 +0.118y85 +0.0747educ +0.0185y85 × educ
(s.e. =) (0.093) (0.124) (0.0067) (0.0094)
+0.0296exper −0.0004exper2 +0.202union
(s.e. =) (0.0036) (0.00008) (0.030)
−0.317 f emale +0.085y85 × f emale
(s.e. =) (0.037) (0.051)
2
n = 1084, R2 = 0.426, R = 0.422
where ln(wage) is the logarithmic term of hourly nominal wage, educ is the years of
education, exper refers to the years of experience and exper2 is its squared term. The
variable y85 is a dummy variable equal to 1 if the observation comes from 1985 and 0 if it
comes from 1978, union is a dummy variable equal to 1 if the person belongs to a union,
and 0 otherwise, f emale is the gender dummy variable equal to 1 if the person is female
otherwise equal to 0. Both y85 × educ and y85 × f emale are interaction variables.

(i) Interpret the return to education in 1985 and 1978, and comment on your findings. [3]

(ii) Interpret the gender gap, report both the approximate and exact changes. Does the
gender gap increase over years? [3]

(iii) Suppose you suspect that there exists a structural change across the time periods
of 1978 and 1985. What type of test do you plan to implement for the structural
change? Explain clearly how you will carry out the test. [5]

(iv) Interpret the coefficient on y85? (Be careful here: you must account for the interac-
tion terms y85 × educ and y85 × f emale.) [2]

(v) Let us assume that we refit the above equation and let all wages be measured in
1978 dollars. In particular, define the real wage as rwage which equals to the wage
for 1978 and rwage equals to wage/1.65 for 1985. Then use ln(rwage) in place of
ln(wage) in fitting the model. Which coefficient(s) will differ from those in the above
equation? Will the R2 from the new regression be the same as 0.426? Explain your
answer. [4]

(vi) There was a notable fall in union membership from 1978 to 1985. Describe and
discuss how you will test whether union participation changed from 1978 to 1985. [2]

A28242 Page 8 Turn over

 Any Calculator, Statistical tables

(b) (i) Explain trend-stationary process and difference-stationary process, respectively. [2]

(ii) What is the error correction mechanism? What is its relationship with cointegration?
[2]

(iii) True or false: The Durbin-Watson test assumes that the variance of the error term is
homoscedastic. Justify your answer. [2]

A28242 Page 9 Turn over

 Any Calculator, Statistical tables

6. (a) From the data for the period of the first quarter in 1971 to the fourth quarter in 1988 for
Canada, the following results were obtained:

\t =
lnM1 −10.2571 +1.5975lnGDPt model(1)
(t − value =) (−12.9422) (25.8865) R2 = 0.9463, d = 0.3254

\t =
∆lnM1 0.0095 +0.5833∆lnGDPt model(2)
(t − value =) (2.4957) (1.8958) R2 = 0.0885, d = 1.7399

ût =
∆c −0.1958ût−1 model(3)
(τ − value) (−2.2521) R2 = 0.1118, d = 1.4767.

where M1 is the most liquid part of money supply including paper, checking account and
etc., GDP refers to the gross domestic product measured in billions of Canadian dollars,
ln is the natural logarithmic function, ∆lnM1t = lnM1t − lnM1t−1 , ∆ût = ût − ût−1 and
ût represents the residuals from model (1).

(i) Interpret the fitted regression results for model (1). [3]

(ii) Based on the results from models (1) and (2), would you suspect that model (1) is
spurious? Explain your answer. [3]

(iii) From the above results, comment on cointegration. [4]

(iv) Using the same notation, consider the following model:

\t =
∆lnM1 0.0084 +0.7340∆lnGDPt −0.0811ût−1 model(4)
(t − value =) (2.0496) (2.0636) (−0.8537)
R2 = 0.1066, d = 1.6697

Comment on this model. Consider again whether Model (1) is spurious or not.
Explain your answer. [5]

(b) State and derive the error correction model. Suppose we add another lag of the error
correction term, can we fit the ”‘new”’ error correction model? Why? Prove your answer. [10]

A28242 Page 10 Turn over

 21(UoB) Any Calculator, Statistical tables

1. (a) Consider an ARDL(1, 1) model which can be written as:

yt = δ + θ1 yt−1 + δ0 xt + δ1 xt−1 + vt

where θ and δ ’s are the parameters and vt is the random error term. Answer the following
questions, giving as much detail as possible:

(i) Derive its error correction model. You need to show its cointegration term and the
error correction term. [5]

(ii) Does the error correction model only allow us to study the long-run relationship
between yt and xt ? What are the advantages of using the error correction model? [2]

(iii) What problem will occur if you add another lag of the error correction term into the
model? Show your derivation. [2]

(b) Consider the following model yi = β1 + β2 xi∗ + ei where the β ’s are the parameters and ei
is the random error term. In practice we can only measure xi∗ by xi . Answer the following
questions, giving as much detail as possible.

(i) What is the effect of measurement error on estimates of true β1 and β2 if xi = 2xi∗ ? [2]

(ii) What is the effect of measurement error on estimates of true β1 and β2 if xi = xi∗ +ui ,
where ui is a white noise random error term? [2]

(c) Consider a random walk model yt = yt−1 + vt .

(i) What is the mean and variance of yt ? [2]

(ii) What is the covariance between yt and yt−2 ? [1]

(d) Suppose we wish to explain a dependent variable y and that the number of possible
explanatory variables (x1 , x2 , ..., xK ) is so large that it is tempting to take a subset of ex-
planatory variables. In such a situation, some researchers apply the Theil criterion and
maximize the adjusted R2 . It is defined by
(n − 1)
R̄2 = 1 − (1 − R2 ),
n − (K − 1)
where n is the number of observations, K is the number of parameters, and (K − 1) is the
number of explanatory variables. Is the Theil criterion equivalent to minimising the sum of
the squared residuals? Show your reasoning. [5]

Question 1 continued overleaf.

A36779 Page 2 Turn over

 Any Calculator, Statistical tables

(e) Is the following judgment correct? Clearly explain your decision. Consider a linear model
y = β1 + β2 x2 + β3 x3 + β4 x4 + e which satisfies the classical assumptions of OLS. After
fitting the model to 24 observations, we have obtained the R2 = 0.34. We can conclude
that although the R2 is not high, it is still a good model and is significant at 1% level.

[4]

A36779 Page 3 Turn over

 Any Calculator, Statistical tables

2. (a) Given an initial condition for y0 , answer the following questions, where yt is the random
variable at time t , ε is the error, t is also the time trend in (iii):

(i) find the solution for yt , where yt = yt−1 + εt + 0.3εt−1 . [2]

(ii) find the solution for yt , and the s-step-ahead forecast Et [yt+s ] for yt = 1.2yt−1 + εt
and explain how to make this model stationary. [4]

(iii) find the solution for yt , and the s-step-ahead forecast Et [yt+s ] for yt = yt−1 + t + εt
and explain how to make this model stationary. [4]

(b) The following analysis is based upon the the UK lending-deposit interest rate. The spread,
yt , is the difference between the lending rate lendr and the deposit rate depr from January
1990 to January 2020. dlendr is the first order difference term of lendr. ddepr is the first
order difference term of depr. dy is the first order difference term of the spread, yt , and
the spread is very persistent at lag 1 and lag 2.

(i) Consider results from the lag length of 7. Is the spread stationary? Perform an
appropriate analysis and make your decision, using 5% of significance level.
b =
dyt 0.534+ 0.204 yt−1 + ∑7i=1 β̂i dyt−i
(t − val) (3.56) (−4.25)

[3]

(ii) Consider results from the lag length of 7. Is the lending rate stationary? Perform an
appropriate analysis and make your decision, using 5% significance level.
\ t = 0.214+
dlendr 0.04 lendrt−1 + ∑7i=1 β̂i dlendrt−i
(t − val) (3.56) (−2.32)

[3]

(iii) Consider results from the lag length of 7. Is the deposit rate stationary? Perform an
appropriate analysis and make your decision, using 5% significance level.
\ t = 0.461+
ddepr 0.03 deprt−1 + ∑7i=1 β̂i ddeprt−i
(t − val) (2.78) (−2.15)

[3]

(iv) Now study the results from the above, comments on the rates and the spread. [3]

(v) Suppose that you found out that the lending rate is stationary using four lags, can
you use 4-lag of lending rate to model the spread instead? Explain your decision. [3]

A36779 Page 4 Turn over

 Any Calculator, Statistical tables

3.

The following model examines the houses sold at H area in B city.

LPi = β1 + β2 SQFTi + β3 SQFT 2i + β4 AGEi + β5 BEDSi + β6VACANTi + ei

where y is the dependent variable, the β ’s are the parameters, e is the error term and i stands for
the i-th number of the observations. The descriptions of the variables are given below. Answer
the following questions (Round your answer to keep two significant figures after the decimal
point).

LP: house price in logarithmic term

SQFT: total square feet of the living area, in 100 square feet scale
QFT2: the square term of SQFT
BEDS: number of bedrooms
AGE: age of the house in years
VACANT: whether the house is vacant while for sale: Yes = 1, No = 0

Estimation results

Variables Parameter Estimate Std. Error t value Pr(> |t|)

Intercept 10.686555 0.0973817 109.739 < 2e − 16 ∗ ∗∗
SQFT 0.0870278 8.406 6.14e − 16 ∗ ∗∗
SQFT2 −0.0005264 0.000269 −1.956 0.0511.
AGE −0.024407 0.004818 −5.066 6.03e − 07 ∗ ∗∗
BEDS −0.0852105 0.0176343 -4.832 1.88e − 06 ∗ ∗∗
VACANT −0.0832782 0.0191199 -4.356 1.66e − 05 ∗ ∗∗

Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Question 3 continued overleaf.

A36779 Page 5 Turn over

 Any Calculator, Statistical tables

Variance-Covariance Table

Variables Intercept SQFT SQFT2 AGE BEDS VACANT

Intercept 0.00948 −0.0848 0.2252 −0.0000151 −0.0004 −0.00038
SQFT −0.0848 1.07185 −2.7082 0.0000411 −0.0039 0.000015
SQFT2 0.22252 −2.7082 7.2448 0.0000959 0.00328 −0.00159
AGE −0.00002 0.00004 −0.00009 0.0000232 0.00002 0.00001
BEDS −0.00048 −0.00393 0.003275 0.0000016 0.00031 −0.00001
VACANT −0.00038 0.00147 −0.00159 0.0000014 −0.00001 0.00037

(a) Calculate the sample size, SSR (due to regression), R2 , adjusted R2 and the standard
error of the model. [4]

(b) Report the fitted model. You need to include the standard errors, significant level, sample
size, R square and adjusted R square. [2]

(c) Find the marginal effects of SQFT on logged value of house price for a house with 700
square feet and 3400 square feet, respectively. What does it suggest? [3]

(d) Interpret the fitted model for all the explanatory variables. [3]

(e) Is this a good model? Perform an appropriate test on the overall significance of the model
using α = 5%. [3]

(f) Calculate the corrected predictor of price for a 40-year-old and vacant house of 1, 600
square feet, having three bedrooms. [2]

(g) Find the 95% interval estimate for a nonlinear function: λ = exp(βAGE /10). [4]

(h) You suspect the variability of house price for the vacant houses are larger than that of
non-vacant ones. Propose an appropriate method to test this type of heteroscedasticity. [4]

A36779 Page 6 Turn over

 Any Calculator, Statistical tables

4. (a) Explain with a brief reason whether the following statements are true or false.

(i) The Durbin-Watson test is valid in large samples, but Durbin h test is valid in both
large and small samples. [2]

(ii) If you fit two models, one is yi = β1 + β2 x2i + β3 x3i + β4 x4i + ei , and the other is
yi = α1 + α2 z2i + α3 z3i + α4 z4i + ui by OLS, where zki = (xki − x̄k ) for k = 2, 3, 4,
then the fitted regression functions should be the same. [2]

(iii) A linear regression model means the dependent variable is a linear function of all
the explanatory variables. [2]

(iv) The Lagrange Multiplier test for heteroscedasticity generates a test statistic N × R2
which follows the Chi-square distribution. The degrees of freedom in the Chi-square
distribution refers to the number of explanatory variables in the initial model. [2]

(v) To implement RESET, we add the squared and cubed terms of the OLS fitted values
(ŷ) into the initial model to test functional form misspecification. We can also include
the fitted value term (ŷ) into the expanded equation. [2]

(b) Suppose that you fit a simple linear regression model of y = β1 + β2 xi + ε , where the β ’s
are the parameters and ε is the random error term ∼ (0, σ 2 ). You get the estimates as
b 2 = 4. The model
β̂1 = 2, β̂2 = 0.8, the correlation between y and x, ρbxy = 0.6, and σ
uses 100 observations.

(i) What is SSR (Sum Squares of Regression) for this model? [3]

(ii) Using the level of significance of 5%, perform a two-sided t-test on β2 = 0.5. [3]

(c) Let mathscore denote the percentage of students at primary schools in England receiving
a passing score on a standardized maths test. We are interested in estimating the effect
of per-student spending on maths performance. A model is developed for 428 schools:

mathscore = β1 + β2 log(expend) + β3 log(enroll) + β4 poverty + β5 ratio + e,

where poverty is the percentage of students living in poverty which is measured by a

proxy variable, lnchprg. The variable lnchprg is the percentage of students eligible for
the government funded school meal programme for low-income household. log(enroll)
is the logarithmic form of student enrollment for each school, ratio is the female and male
students ratio, and the β ’s are parameters and e is the random error.

Question 4 continued overleaf.

A36779 Page 7 Turn over

 Any Calculator, Statistical tables

Estimation results with Standard Errors in the Parentheses

Coefficients Model (1) Model (2)

Intercept −69.24 −23.14
(26.72) (24.99)
log(expend) 11.13 7.75
(3.30) (3.04)
log(enroll) 0.022 −1.26
(0.615) (0.58)
lnchprg −0.324
(0.036)
ratio 0.541
(0.627)
R − squared 0.0297 0.1893
SSE 5781.4 4362.1

(i) Interpret the effect of expenditures on mathscore in both models. Explain why the
effect of expenditures on mathscore is lower in Model (2) than in Model (1)? Is its
effect in model (2) still statistically greater than zero using α = 5%? [2]

(ii) Does it appear that pass rates are lower at larger schools, while holding other factors
constant? Explain your arguments. [2]

(iii) How can you explain the substantial increase in R2 from Model (1) to Model (2)?
Find out the adjusted R2 for both models, which model do you think is better? [2]

(iv) Set up hypotheses and perform a suitable test that both lnchprg and ratio have no
effect on mathscore. Use α = 5%. [3]

A36779 Page 8 Turn over

 22(UoB) Any Calculator, Statistical tables

1. (a) Consider a linear regression model written as:

yi = β1 + β2 x2i + ei ,

where the β s are the parameters and ei is the IID random error term ∼ (0, σ 2 ), and i
denotes the number of observations. Let b1 and b2 be the least squares estimators of β1
and β2 , respectively. Complete the following questions, giving as much detail as possible.

(i) State the classical assumptions of regression model, including both simple and mul-
tiple regression.

(ii) State the Gauss-Markov Theorem about the least squares estimators b1 and b2 .

(iii) Prove the Gauss-Markov theorem for the least squares estimator b2 of β2 in the
case of simple regression model.

[9]

(b) Is the following judgment correct? Show your calculation and explain your finding. Con-
sider a linear model yi = β1 + β2 x2i + β3 x3i + β4 x4i + ei which satisfies the classical
assumptions of OLS. After fitting the model to 24 observations, we have obtained the
R2 = 0.34. We can conclude that although the R2 is not high, this model is still significant
at 5% level. [4]

(c) Briefly explain whether the following statements are true or false.

(i) By including one more independent variable in the regression model, you will elimi-
nate the possibility of omitted variable bias from excluding that variable.

(ii) The central limit theorem states that sums of random variables, properly standard-
ized, converge in distribution to standard normal.

(iii) The OLS estimators are no longer BLUE (best linear unbiased estimators) under the
situation of the heteroskedasticity and autocorrelation.

[3]

Question 1 continued overleaf.

A36779 Page 2 Turn over

 Any Calculator, Statistical tables

(d) Suppose you estimate the consumption function of Yi = α1 + α2 Xi + ei and the savings
function of Zi = β1 + β2 Xi + ui , where Y denotes for consumption, Z denotes for savings,
X denotes for income, α ’s and β ’s are parameters and e and u are the random error
terms. Furthermore, X = Y + Z , that is, income is equal to consumption plus savings,
and variables are all in numerical terms.

(i) What is the relationship, if any, between the OLS estimators of α

b2 and βb2 ? Show
your calculations.

(ii) Will the residual (error) sum of squares be the same for the two models of Yi =
α1 + α2 Xi + ei and Zi = β1 + β2 Xi + ui ? Verify your answer.
(iii) Can you compare the R2 terms of the two models? Explain your answer.

[9]

A36779 Page 3 Turn over

 Any Calculator, Statistical tables

3. (a) Consider an AR(1) model which can be written as:

yt = δ + θ yt−1 + et ,

where δ and θ are the parameters with |θ | < 1, and et is the random error term with
E(et |It−1 ) = 0 and var(et |It−1 ) = σ 2 . All the current and past observations on y at time
T
t − 1 are denoted by the information set It−1 . Let ȳ−1 = ∑t=2 yt /(T − 1) (the average of
T
the observations on y with the first one missing) and ȳ−T = ∑t=2 yt−1 /(T − 1) (the aver-
age of the observations on y with the last one missing). Complete the following questions,
giving as much detail as possible: [17]

(i) Show that the least squares estimator for θ can be written as
T
∑t=2 et (yt−1 − ȳ−T )
θ̂ = θ + T
.
∑t=2 et (yt−1 − ȳ−T )2

(ii) Show and explain why θ̂ is a biased estimator of θ .

(iii) Show and explain why θ̂ is a consistent estimator of θ .

(b) Consider a time series of observations, It = (y1 , x1 ), (y2 , x2 ), · · · , (yT , xT ). Given that
T = 29, yT = 10, yT −1 = 12, xT +2 = xT +1 = xT = 5, and xT −1 = 6, forecast the best
one-period and two-period for yT +1 and yT +2 , respectively for the following models. In
each case, vt are assumed to be independent random errors distributed as vt ∼ N(0, 4). [8]

(i) The random walk ln(yt ) = ln(yt−1 ) + vt .

(ii) The first difference model ∆yt = 0.6∆yt−1 + 0.3∆xt + vt .

A36779 Page 6 Turn over

 Any Calculator, Statistical tables

4. (a) Consider the following stock market data which comprise the monthly price ( price) and
dividends of S &P Index (div, in logarithmic terms) for the sample period between January
1871 to September 2015 (1871M1– 2015M9). Answer the following questions. Use a 1%
level of significance for all hypothesis tests. [20]

(i) In Figure 1, the top line represents the price and the bottom dotted line represents
the dividends. Do they appear to be stationary? What else can you observe?

(ii) Using the following R output to carry out an appropriate analysis (variables are de-
fined at the end of the output). You need to perform the appropriate tests, specify
the corresponding models and draw your final conclusion.

(iii) Based upon the conclusion you draw from the above, describe an alternative ap-
proach which can lead to the same conclusion.

> lm(Dprice ˜ Lprice1 + LDprice1 + trend )

Estimate Std. Error t value Pr(>|t|)
(Intercept) 2.819e-02 1.060e-02 2.659 0.00791 **
Lprice1 -6.216e-03 2.354e-03 -2.640 0.00836 **
LDprice1 2.748e-01 2.314e-02 11.878 < 2e-16 ***
trend 9.956e-06 3.959e-06 2.515 0.01201 *
---
Signif. codes: 0 ’***’ 0.001 ’**’ 0.01 ’*’ 0.05 ’.’ 0.1

Question 4 continued overleaf.

A36779 Page 7 Turn over

 Any Calculator, Statistical tables

Residual standard error: 0.03943 on 1731 degrees of freedom

Multiple R-squared: 0.07742,Adjusted R-squared: 0.07582
F-statistic: 48.42 on 3 and 1731 DF, p-value: < 2.2e-16
--------------------------------
>lm(Ddiv ˜ Ldiv1+ trend+ LDdiv1+ LDdiv2+ LDdiv3+ LDdiv4)
Estimate Std. Error t value Pr(>|t|)
(Intercept) 9.853e-03 2.734e-03 3.604 0.000323 ***
Ldiv1 -5.606e-03 1.546e-03 -3.625 0.000297 ***
trend 5.291e-06 1.498e-06 3.533 0.000421 ***
LDdiv1 4.262e-01 2.393e-02 17.811 < 2e-16 ***
LDdiv2 1.442e-01 2.594e-02 5.559 3.13e-08 ***
LDdiv3 3.215e-02 2.596e-02 1.239 0.215687
LDdiv4 7.750e-02 2.389e-02 3.244 0.001203 **
---
Residual standard error: 0.01192 on 1725 degrees of freedom
Multiple R-squared: 0.3232, Adjusted R-squared: 0.3209
F-statistic: 137.3 on 6 and 1725 DF, p-value: < 2.2e-16
--------------------------------
>reg.out <- lm(div ˜ price + trend)
>ehat <- resid(reg.out)
Estimate Std. Error t value Pr(>|t|)
(Intercept) 3.810e-01 3.833e-02 9.94 <2e-16 ***
price 3.041e-01 8.512e-03 35.72 <2e-16 ***
trend 4.483e-04 1.433e-05 31.29 <2e-16 ***
----
Residual standard error: 0.1429 on 1734 degrees of freedom
Multiple R-squared: 0.9145, Adjusted R-squared: 0.9144
F-statistic: 9269 on 2 and 1734 DF, p-value: < 2.2e-16
--------------------------------

Question 4 continued overleaf.

A36779 Page 8 Turn over

 Any Calculator, Statistical tables

>ur.df(ehat, type = c("none", "drift", "trend"), lags = 5,

selectlags = c("Fixed", "AIC", "BIC"))
Call:
lm(z.diff ˜ z.lag.1 - 1 + z.diff.lag)
Estimate Std. Error t value Pr(>|t|)
z.lag.1 -0.014780 0.002768 -5.340 1.05e-07 ***
z.diff.lag1 0.446186 0.023844 18.713 < 2e-16 ***
z.diff.lag2 -0.001253 0.026134 -0.048 0.96177
z.diff.lag3 0.026592 0.026116 1.018 0.30873
z.diff.lag4 0.056006 0.026114 2.145 0.03212 *
z.diff.lag5 0.073036 0.024008 3.042 0.00238 **
---
Residual standard error: 0.01595 on 1725 degrees of freedom
Multiple R-squared: 0.236, Adjusted R-squared: 0.2333
F-statistic: 88.79 on 6 and 1725 DF, p-value: < 2.2e-16
--------------------------------
L denotes a lagged version of a time series;
D denotes the first(1st)-differenced version of a time series;
Lprice1 denotes one-period lag of "price";
LDprice1 denotes one-period lag of first-differenced "price";
Ddiv is the first-differenced term of "div";
Ldiv1 denotes one-period lag of "div";
LDdiv[i] denotes the i-th lag of 1st-differnced term of "div";
"trend" is a variable indicating the trend.
--------------------------------

(b) Suppose that yt and zt are I(1) series, but yt − β zt is I(0) for some β ̸= 0. Show that for
any δ ̸= β , yt − δ zt must be I(1). [5]

A36779 Page 9 Turn over

 19(JBJI) Any Calculator, Statistical tables

1. (a) Consider a simple linear regression model that can be written as

yi = β1 + β2 xi + εi , i = 1, 2, . . . , n ,

where β1 and β2 are unknown parameters, εi ∼ N(0, σ 2 ) are the random error terms, i
denotes the number of observations, and n is the sample size. Let x̄ and ȳ be the sample
means of x and y, respectively. ŷi is the predicted value of yi . R2 is the coefficient of
determination.

(i) Let b1 and b2 be the least squares estimators of β1 and β2 , respectively. State the
Gauss–Markov Theorem about the least squares estimators, b1 and b2 . [3]

(ii) Let SST , SSR, and SSE denote the total sum of squares, the regression sum of
squares, and the error sum of squares, respectively. Defining the residual as ei =
yi − ŷ, we have
yi − ȳ = (ŷi − ȳ) + ei .

By squaring both sides of the equation above, prove that SST = SSR + SSE . [12]

(iii) Why does the equality, SST = SSR + SSE , hold only if the model contains an inter-
cept? [2]

(b) Consider a simple linear regression model that can be written as

yi = β1 + β2 xi + εi , i = 1, 2, . . . , n ,

where β1 and β2 are unknown parameters, εi ∼ N(0, σ 2 ) are the random error terms, i
denotes the number of observations, and n is the sample size.

(i) If you multiply all the x values by 20, but not the y values, show mathematically
what happens to the parameter values of β1 and β2 and explain your results. What
happens to the least squares estimates, b1 and b2 ? What happens to the variance
of the error term? [4]

(ii) If you multiply all the y values by 20, but not the x values, show mathematically
what happens to the parameter values of β1 and β2 and explain your results. What
happens to the least squares estimates, b1 and b2 ? What happens to the variance
of the error term? [4]

AUoBM321 Page 2 Turn over

 Any Calculator, Statistical tables

2. Suppose that you are interested in the relationship between the return rate on a stock in 2005,
compared to the return rate in 2004. You believe that the return rates in both years are positively
correlated in a standard setting of simple linear regression models. A sample of 15 stocks
yields the following regression results: b1 = 5.3, b2 = 1.04, se(b1 ) = 1.79, se(b2 ) = 0.2163,
R2 = 0.64, and MSE = 35.4.

(i) Interpret the intercept coefficient b1 and the slope coefficient b2 , respectively. [4]

(ii) Compute the predicted return rate on a stock in 2005 when the return rate in 2004 was
five. [1]

(iii) Compute the regression sum of squares. [3]

(iv) Compute the sample correlation coefficient for the stock returns of the two years. What
sign does it have? Why? [3]

(v) Apply the t -test on H0 : β2 = 0 against H1 : β2 > 0 at α = 0.025. [5]

(vi) Apply the F -test on H0 : β2 = 0 against H1 : β2 6= 0 at α = 0.05. [7]

(vii) Have you noticed any relationship between the Student’s t -statistic computed for the slope
coefficient, b2 , in (v) at α = 0.025 and the F -statistic computed in (vi) at α = 0.05? What
is the relationship in general? [2]

AUoBM321 Page 3 Turn over

 Any Calculator, Statistical tables

3. (a) Let byx and bxy represent the slopes in simple linear regression models of y on x and x on
y, respectively. Show that
2
byx bxy = rxy ,

where rxy is the sample correlation coefficient between x and y. [4]

(b) True or False? Explain your answer for the following statements.

(i) When the errors in a regression model have AR(1) serial correlation, the ordinary
least squares (OLS) standard errors tend to correctly estimate the sampling variation
in the estimators. [3]

(ii) The weighted least squares method is preferred to OLS when an important variable
is omitted from the model. [3]

(iii) The OLS estimators are no longer BLUE (best linear unbiased estimators) under the
situation of the heteroskedasticity. [3]

(iv) The adjusted R2 will not decrease if an additional explanatory variable is introduced
into the model. [3]

(v) We impose assumptions on the dependent variable and the random error term in lin-
ear regression models using the least squares principle. We do not need to impose
assumptions on the explanatory variables since they are random variables. [3]

(vi) For linear models, it is always appropriate to use R2 as a measure of how well the
estimated regression equation fits the data because it shows the proportion of total
variation that is explained by the regression. [3]

(vii) Interval estimates based on the least squares principle incorporate both the point
estimate and the standard error of the estimate, and the sample size as well, so a
true parameter is actually certain to be included in such an interval. [3]

AUoBM321 Page 4 Turn over

 Any Calculator, Statistical tables

4. (a) The following table contains computer output after estimating the following two models to
the same 20 observations. The first model (Model 1) is y = β1 + β2 x + β3 w + ε and the
second model (Model 2) is y = β1 + β2 x + ε . β1 , β2 , and β3 are unknown parameters and
ε is the random error term.

Coefficients Model 1 Model 2

Intercept 3.636 −5.838
(2.763) (2.000)
x −0.998 4.107
(1.235) (0.338)
w 0.498
(0.117)
Estimation results with standard errors in the parentheses.

The regression specification error test (RESET) suggests augmenting an existing model
with the squares of its predictions, or with their squares and cubes. Applying RESET to the
second model yields F -values of 17.98 (for ŷ2 ) and 8.72 (for ŷ2 and ŷ3 ). The correlation
between x and w is 0.975. Answer the following questions.

(i) Should w be included in the above model? [5]

(ii) What can you say about the existence of collinearity in the above model and its
possible effect on model results? [4]

(iii) What would happen if we use RESET to augment the second model with the pre-
dicted value of y, i.e., ŷ? [4]

Question 4 continued overleaf.

AUoBM321 Page 5 Turn over

 Any Calculator, Statistical tables

Question 4 continued.

(b) Suppose a true model is the usual intercept-present model

yi = α1 + α2 xi + νi , i = 1, 2, . . . , n ,

where α1 and α2 are unknown parameters, νi ∼ N(0, σν2 ) are the random error terms, i
denotes the number of observations, and n is the sample size. Instead, it is fitted by

yi = β xi + µi , i = 1, 2, . . . , n ,

where β is a unknown parameter, µi ∼ N(0, σµ2 ) are the random error terms.

(i) Let b be the least squares estimator of β . What are the expected value and the
variance of b? [7]

(ii) Explain the consequences of this specification error on the model. [5]

AUoBM321 Page 6 Turn over

 Any Calculator, Statistical tables

5. (a) Consider the following model yt = 0.5yt−1 + xt + ν1t and xt = 0.5xt−1 + ν2t , where both
ν1t ∼ N(0, 1) and ν2t ∼ N(0, 1) follow normal distributions. Examine the following state-
ments, state whether they are true or false first, and then explain why they are true or
false.

(i) The time series yt is weakly stationary. [2]

(ii) The unconditional variance of yt is larger than the conditional one-step ahead vari-
ance. [2]

(iii) The path of forecasts for yt+i conditional on the information available at time t will
be oscillatory but it will eventually converge to 0.1. [2]

(iv) The upper bound for the 95% conditional one-step ahead confidence interval for yt
is 2. [2]

(v) The series yt and xt share a common stochastic trend. [2]

(vi) The series yt and xt have the same unconditional mean. [2]

(vii) If yt = 1 and xt = 1, then E(yt+1 |yt , xt ) = 1. [2]

(viii) If yt = 1, xt = 1, ν1t = 1, and ν2t = 1, then E(yt+1 |yt , xt ) 6= 1. [2]

(ix) If yt = 0 and xt = −0.8, then E(yt+1 |yt , xt ) = −0.8. [2]

(b) Suppose that yt and zt are I(1) series, but yt − β zt is I(0) for some β 6= 0. Show that for
any δ 6= β , yt − δ zt must be I(1). [7]

AUoBM321 Page 7 Turn over

 Any Calculator, Statistical tables

6. (a) Dr. Stats XS has decided that writing the least squares estimator is too much trouble.
Noting that two points determine a line, Dr. Stats XS chooses two points from a sample
of size n and draws a line between them, calling the slope of this line the XS estimator of
β2 in the simple regression model of yi = β1 + β2 xi + εi , where y and x assume non-zero
values, β1 and β2 are unknown parameters, εi ∼ N(0, σ 2 ) are the random error terms,
i denotes the number of observations, and n is the sample size. Algebraically, if the two
points are (x1 , y1 ) and (x2 , y2 ), the XS estimation rule is

y2 − y1
bXS = .
x2 − x1
Assuming all the assumptions of a simple linear regression model hold, answer the fol-
lowing questions:

(i) Show that bXS is a linear and unbiased estimator of β2 . [3]

(ii) Find the variance of bXS . [2]

(iii) Find the probability distribution of bXS . [2]

(iv) Convince Dr. Stats XS that the XS estimator is not as good as the least squares
estimator. [4]

(b) Consider a random walk model with standard notation

yt = yt−1 + νt .

(i) Rewrite yt as a function of lagged errors. [2]

(ii) What are the expected value and variance of yt ? [2]

(iii) What is the covariance between yt and yt−2 ? [2]

(c) Explain with brief reasons whether the following statements are true, false, or uncertain.

(i) In the presence of lagged dependent variables, the Durbin–Watson d statistic for
detecting autocorrelation is practically useless. [2]

(ii) The Durbin h test is valid in both large and small samples. [2]

(iii) There are no differences between the tests of unit roots and tests of cointegration. [2]

(iv) For a random walk stochastic process, the variance is infinite. [2]

AUoBM321 Page 8 Turn over

 20(JBJI) Any Calculator, Statistical tables

1. (a) Consider the wage equation

ln(WAGE) = β1 + β2 EDUC + β3 EDUC2 + β4 EXPER + β5 EXPER2

+ β6 (EDUC × EXPER) + β7 HRSWK + β8 FEMALE + ε ,

where WAGE denotes earnings per hour in pounds, EDUC denotes years of educa-
tion, EXPER denotes years of post education experience, HRSWK denotes usual hours
worked per week, FEMALE is an indicator variable (i.e., FEMALE = 1 if an individual is
female, FEMALE = 0 if otherwise), and ε ∼ N(0, σ 2 ) is the random error term.

The summary statistics of each variable are reported in Table 1 below, and estimation
results for different versions of the above model are displayed in Table 2 on the following
page.

Variable N Mean Standard Deviation Minimum Maximum

WAGE 1000 20.201 12.104 2.030 72.130
EDUC 1000 10.689 2.440 1.000 16.000
EXPER 1000 26.501 12.990 3.000 64.000
HRWKS 1000 39.240 11.446 0.000 99.000
FEMALE 1000 0.501 0.470 0.000 1.000

Table 1: Summary statistics of each variable.

(i) What is the wage difference between women and men using Model (A)? Report both
an approximate calculation and an exact calculation. Perform and report an appro-
priate statistical test (with a level of significance of α = 0.05) to examine whether
women had lower wage than men using the results from Model (A). [6]

(ii) Based on the results in (i), what restrictions on the coefficients of Model (A) would
produce Model (C)? Use an F -test (with a level of significance of α = 0.05) to test
these restrictions. What question(s) can you answer by performing this test? [5]

(iii) Complete the missing AIC for Model (D) and SC for Model (A). Consider all of these
models from Model (A) to Model (E) carefully. Which model would you prefer? Why?
Explain and demonstrate your answer in detail. [5]

Question 1 continued overleaf.

AUoBM331 Page 2 Turn over

 Any Calculator, Statistical tables

Question 1 continued.

Variables Model (A) Model (B) Model (C) Model (D) Model (E)
Intercept 0.576 0.378 0.744 0.927 0.325
(0.266) (0.190) (0.188) (0.080) (0.096)
EDUC 0.0498 0.0289 0.0366 0.1006
(0.0397) (0.0344) (0.0350) (0.0063)
2
EDUC 0.00319 0.00352 0.00293
(0.00169) (0.00166) (0.00170)
EXPER 0.0373 0.0303 0.0279 0.0295
(0.0081) (0.0048) (0.0054) (0.0048)
2
EXPER 0.000485 0.000456 −0.00047 −0.000440
(0.00009) (0.000086) (0.000096) (0.000086)
EDUC × EXPER −0.00051
(0.000482)
HRSWK 0.01145 0.01156 0.01345 0.01524 0.01188
(0.00137) (0.00137) (0.00136) (0.00151) (0.00136)
FEMALE −0.150 −0.164 −0.161
(0.132) (0.145) (0.141)
SSE 222.4166 222.6674 233.8317 280.5061 223.6716
AIC −1.487 −1.490 −1.445 −1.486
SC −1.461 −1.426 −1.237 −1.456
Table 2: Estimation results with standard errors in the parentheses.
(b) Consider an ARDL(1,1) model that can be written as

yt = δ + θ1 yt−1 + δ0 xt + δ1 xt−1 + νt ,
where the δ ’s and θ1 are constant parameters and νt is the random error term. Complete
the following questions, giving as much detail as possible.

(i) What is the cointegrating relationship embedded in the error correction model? [1]

(ii) What is the error correction term? [1]

(iii) Why is the error correction mechanism popular? [2]

(iv) What problem will occur if you add another lag of the error correction term into the
model? Show your derivation. [5]

AUoBM331 Page 4 Turn over

 Any Calculator, Statistical tables

2. (a) The following model examines how the return to education (profits from schooling) and
the gender pay gap have changed from 1978 to 1985 in the United States. The results
are presented as follows (standard errors are shown in the parentheses):

\ = 0.459 + 0.118 Y85 + 0.0747 EDUC + 0.0185 Y85 × EDUC + 0.0296 EXPER
ln(WAGE)
(se) (0.093) (0.124) (0.0067) (0.0094) (0.0036)
− 0.0004 EXPER2 + 0.202 UNION − 0.317 FEMALE + 0.085 Y85 × FEMALE
(se) (0.00008) (0.030) (0.037) (0.051)

with
n = 1084 , R2 = 0.426 , R̄2 = 0.422 ,

where ln(WAGE) is the logarithmic term of hourly nominal wage, EDUC is the years of
education, EXPER refers to the years of experience and EXPER2 is its squared term.
The variable Y85 is a dummy variable that is equal to 1 if the observation comes from
1985 and 0 if it comes from 1978, UNION is a dummy variable that is equal to 1 if the
person belongs to a union, and 0 if otherwise, FEMALE is the gender dummy variable
that is equal to 1 if the person is female and 0 if otherwise. Both Y85 × EDUC and
Y85 × FEMALE are interaction variables. Note that t0.95,1075 = 1.646 and t0.975,1075 =
1.962.

(i) Interpret the return to education in 1985 and 1978, respectively, and comment on
your findings. [3]

(ii) Interpret the coefficient of Y85? (Hint: you must also account for the interaction
terms Y85 × EDUC and Y85 × FEMALE.) [2]

(iii) Let us assume that we refit the above equation and let all wages be measured
in 1978 dollars. In particular, define the real wage as RWAGE which equals to
the WAGE for 1978 and RWAGE equals to WAGE/1.65 for 1985. Then use
ln(RWAGE) in place of ln(WAGE) in fitting the model. Which coefficient(s) will
differ from those in the above equation? Will the R2 from the new regression be the
same as 0.426? Explain your answer. [5]

Question 2 continued overleaf.

AUoBM331 Page 5 Turn over

 Any Calculator, Statistical tables

Question 2 continued.

(b) Suppose you have estimated the following model of fertility and the amount of personal
tax exemption for the years 1913 through 1984 in the United States:

f rt = 92.05 + 0.089 pet − 0.004 pet−1 + 0.0074 pet−2 − 21.34 ww2t − 31.08 pillt
gd
(se) (3.33) (0.126) (0.153) (0.165) (11.51) (3.90)

with
n = 68 , R2 = 0.537 ,

where the variable g f r is the general fertility rate which is the number of children born
to every 1,000 women of childbearing age, and pe is the average real dollar value of the
personal tax exemption. The variable ww2 takes on the value unity during the years 1941
through 1945, when the United States was involved in World War II. The variable pill is
unity from 1963 onward, when the birth control pill was made available for contraception.
t stands for the number of observations in the time series data.

(i) Interpret the coefficient of pet . Be specific. What is this coefficient called? [3]

(ii) How would you modify the model if you suspect that some of the variables exhibit a
linear time trend? [2]

(iii) What is the total multiplier (or long-run effect) of pe on g f r? [1]

(iv) How would you test whether the total multiplier (or long-run effect) is statistically
significant? [5]

(c) Consider a linear regression model that can be written as

yi = β1 + β2 xi2 + β3 xi3 + · · · + βK xiK + εi , i = 1, 2, . . . , n ,

where the β ’s are the unknown parameters, εi ∼ N(0, σ 2 ) are the random error terms, i
denotes the number of observations, and n is the sample size. When you fit the model,
you can find the values of R2 and F -statistic in the ANOVA table. Show that

R2 /(K − 1)
F= ,
(1 − R2 )/(n − K)

where K refers to the number of parameters in the model. [4]

AUoBM331 Page 6 Turn over

 21(JBJI) Any Calculator, Statistical tables

1. (a) You are given a simple linear regression model

yi = β1 + β2 xi + εi , i = 1, . . . , n, (1)

where β1 and β2 are unknown parameters, εi are the random error terms and n is the
sample size. Let b1 and b2 be the best linear unbiased estimators of β1 and β2 , respec-
tively. Let rxy be the correlation coefficient, let R2 be the coefficient of determination and
let ŷ be the fitted values of y.

2 = R2 . Give appropriate details.

(i) Prove that rxy [5]
2 = r 2 . Give appropriate details.
(ii) Prove that rxy [5]
yŷ

(b) You set up a multiple regression model (unrestricted model)

yi = β1 + β2 xi2 + β3 xi3 + εi , i = 1, . . . , 40, (2)

where β1 , β2 and β3 are unknown parameters, εi are the random error terms and the sam-
ple size is 40. You are interested in determining whether the variable x3 would significantly
improve the model or not. To do so, you introduce the restricted model

yi = β1R + β2R xi2 + εiR , i = 1, . . . , 40 (3)

for unknown parameters β1R and β2R and random error terms εiR .

For the restricted model (3), you are given that R2 = 0.786. For the unrestricted model
(2), R2 = 0.801. Moreover, SSEU = 101.341 and SSER = 105.635.

(i) Explain what R2 is. Based on the values of R2 , is adding x3 an improvement to the
model? Describe your reasoning. [7]

(ii) Perform an F -test to determine the hypothesis that adding x3 is an improvement to

the model. Use a significance level of α = 0.05. Clearly explain each of the steps
and interpret the result. [8]

AUoBM331 Page 2 Turn over

 Any Calculator, Statistical tables

2. (a) Sam hopes to investigate football players’ salaries in the Premier League. He denotes the
random variable corresponding to the annual salary of a player by salary. He collected
data on a certain number of football players, and fitted the following two models.

Model (1):

\ = 12.373 + 0.177 years ,

lsalary R2 = 0.337 , SSE = 326.196
(se) (0.098) (0.01325)

Model (2):

\ = 11.861 + 0.0904 years + 0.030 scoreyr ,

lsalary R2 = 0.597 , SSE = 198.475
(se) (0.084) (0.0118) (0.0020)

The dependent variable, lsalary, refers to the natural logarithmic transformation of salary.
The two explanatory variables are the years in the Premier League (years) and the goals
scored per year (scoreyr), respectively. SSE is the error sum of squares.

(i) Find the sample size in Sam’s data. Keep FIVE decimal places in the calculation but
round to the nearest integer for the result. [4]

(ii) What are the mean squared errors (MSEs), denoted as σ̂12 and σ̂22 , respectively, in
each regression model? Keep FIVE decimal places. Which MSE is smaller than the
other? Explain your argument clearly why one MSE is smaller than the other in this
particular case. [4]

(iii) It appears that the standard error for the coefficient on years in Model (2) is smaller
than its counterpart in Model (1). Would it always be the case? Explain your answer
in detail. [5]

Question 2 continued overleaf.

AUoBM331 Page 3 Turn over

 Any Calculator, Statistical tables

Question 2 continued.

(b) Suppose the true model is the usual intercept-present model

yi = α1 + α2 xi + νi , i = 1, 2, . . . , n ,

where α1 and α2 are unknown parameters, νi ∼ N(0, σν2 ) are the random error terms, i
denotes the number of observations, and n is the sample size. Instead, it is fitted by

yi = β xi + µi , i = 1, 2, . . . , n ,

where β is a unknown parameter, µi ∼ N(0, σµ2 ) are the random error terms.

(i) Let b be the least squares estimator of β . What are the expected value and the
variance of b? Is b biased? [7]

(ii) Explain the consequences of the specification error on the model. [5]

AUoBM331 Page 4 Turn over

 Any Calculator, Statistical tables

3. (a) A sample of n = 300 Birmingham households was taken to investigate how far British
households tend to travel when they take vacation. The relevant variables are listed as
follows: MILES measures the distance travelled in miles per year, INCOME measures
the annual income of the household in £1000, AGE measures the average age of the adult
members of the household, and KIDS measures the number of children in the household.
The following model was suggested

MILESi = β1 + β2 INCOMEi + β3 AGEi + β4 KIDSi + εi , i = 1, 2, . . . , n ,

where the β ’s are unknown parameters and εi ∼ N(0, σ 2 ) are the random error terms.

(i) Suppose that you fit the model by the least squares principle and the residuals are
plotted against INCOME. You find that the residuals increase with INCOME. What
does this suggest to you in terms of the variance? What misleading inferences are
there likely to be? [3]

(ii) Ordering the observations according to descending values of INCOME, and apply-
ing the least squares principle to the first 150 observations, and again to the second
150 observations separately, yields the sums of squared errors of SSE1 and SSE2 ,
respectively where,

SSE1 = 8.9471 × 108 , SSE2 = 4.0479 × 108 .

Use the Goldfeld–Quandt test to examine for heteroskedasticity of errors. Include

specification of the null and alternative hypotheses. [7]

(iii) Table 1 on the following page contains three sets of estimates: those from least
squares, those from least squares with White’s standard errors, and those from
generalized least squares under the assumption of σi2 = σ 2 × INCOME2 .

(1) How do vacation miles travelled (MILES) depend on INCOME, AGE, and
KIDS? [3]
(2) How do White’s standard errors compare with the least squares standard er-
rors? Do they change your assessment of the precision of estimation? [3]
(3) Is there evidence to suggest that the generalized least squares estimates are
better estimates? Justify your answer. [3]

Question 3 continued overleaf.

AUoBM331 Page 5 Turn over

 Any Calculator, Statistical tables

Least squares estimates

Variable DF Parameter Estimate Standard Error t Value Pr > |t|
Intercept 1 −391.55 169.78 −2.31 0.022
INCOME 1 14.20 1.80 7.89 0.000
AGE 1 15.74 3.76 4.19 0.000
KIDS 1 −81.83 27.13 −3.02 0.003

Least squares estimates with White standard errors

Variable DF Parameter Estimate Standard Error t Value Pr > |t|

Intercept 1 −391.55 142.65 −2.74 0.007
INCOME 1 14.20 1.94 7.32 0.000
AGE 1 15.74 3.96 3.97 0.000
KIDS 1 −81.83 29.15 −2.81 0.006

Generalized least squares estimates

Variable DF Parameter Estimate Standard Error t Value Pr > |t|

Intercept 1 −425.00 121.44 −3.50 0.001
INCOME 1 13.95 1.48 9.42 0.000
AGE 1 16.72 3.02 5.53 0.000
KIDS 1 −76.81 21.85 −3.52 0.001

Table 1: Regression results.

(b) Suppose that a time series process yt is generated by yt = z + εt , for all t = 1, 2, . . . The
random error z is independent of time, and it has mean zero and variance σz2 . εt is an
independent and identically distributed sequence with mean zero and variance σε2 , and
can be thought of as a shock or disturbance of the random error. We further assume that
εt is uncorrelated with z. Answer the following questions, giving appropriate details.

(i) Find the expected value and variance of yt . [2]

(ii) Find Cov(yt , yt+h ) for any t and h. Is yt covariance stationary? [4]

AUoBM331 Page 6 Turn over

 Any Calculator, Statistical tables

4. (a) From the data for the period of the first quarter in 1971 to the fourth quarter in 1988
for Canada, the following results (with corresponding test statistics, d , t , and τ ) were
obtained.

Model (1):

[
ln M1t = −10.2571 + 1.5975 ln GDPt , R2 = 0.9463 , d = 0.3254
(t) (−12.9422) (25.8865)

Model (2):

ln M1t = 0.0095 + 0.5833 ∆ ln GDPt ,

∆\ R2 = 0.0885 , d = 1.7399
(t) (2.4957) (1.8958)

Model (3):

ct = −0.1958 et−1 ,
∆e R2 = 0.1118 , d = 1.4767
(τ) (−2.2521)

where M1 is the most liquid part of money supply including paper, checking account
etc. GDP refers to the gross domestic product measured in billions of Canadian dollars.
“ln” refers to the natural logarithmic transformation of the associated term. ∆ ln M1t =
ln M1t − ln M1t−1 , ∆et = et − et−1 , and et represents the residuals from Model (1).

(i) State the elasticity of M1 with respect to GDP for Model (1). [1]

(ii) Interpret the fitted regression results for Model (1). [5]

(iii) Based on the results from Models (1) and (2), would you suspect that Model (1) is
spurious? Explain your answer. [4]

(iv) Using the same notation, consider the following Model (4):

ln M1t = 0.0084 + 0.7340 ∆ ln GDPt − 0.0811et−1 ,

∆\ R2 = 0.1066 , d = 1.6697
(t) (2.0496) (2.0636) (−0.8537)

Comment on this model. Consider again whether Model (1) is spurious or not. Ex-
plain your answer. [5]

Question 4 continued overleaf.

AUoBM331 Page 7 Turn over

 Any Calculator, Statistical tables

Question 4 continued.

(b) Consider a linear regression model that can be written as

ln(WAGE)i = β1 + β2 IQi + β3 EDUi + β4 TENUREi + εi , i = 1, 2, . . . , n ,

where the β ’s are the unknown parameters, ln(WAGE) refers to the natural logarithmic
transformation of the real wage for a staff member in a university, IQ represents the score
of the intelligence quotient, EDU stands for the years of education, and TENURE is an
indicator variable denoting whether a staff member has tenured or not, εi ∼ N(0, σ 2 ) are
the random error terms, i stands for the index of an individual staff member in the data,
and n is the sample size.

(i) Describe how you would examine the joint significance of β3 = 0 and β4 = 0 at a
5% significance level. Describe the steps, state the null and alternative hypotheses,
test statistics and the rejection rule. [4]

(ii) If EDU and IQ are positively correlated and we omit EDU from the model, what
would be the likely sign of the bias of the coefficient? [2]

(c) Discuss which of the following three cases can cause ordinary least squares (OLS) esti-
mators to be biased.

(i) Heteroskedasticity.

(ii) A sample correlation coefficient of 0.95 between two independent variables both
included in the model.

(iii) Omitting an important variable.

[4]

AUoBM331 Page 8 Turn over

 22(JBJI)
Any Calculator, Statistical tables

4. Consider an AR( p) model of the general form

yt = δ + θ1 yt−1 + θ2 yt−2 + · · · + θ p yt−p + νt ,

where δ and θ ’s are unknown parameters, and νt are the random error terms. In this model, yt
are stationary if the roots of the polynomial equation

ϕ(z) = 1 − θ1 z − θ2 z2 − · · · − θ p z p

are greater than one in absolute value. The roots are the values of z that satisfy the equation
ϕ(z) = 0. If one of the roots is equal to one, then yt are said to have a unit root.

More specifically, consider an AR(2) model

yt = δ + θ1 yt−1 + θ2 yt−2 + νt .

Suppose that
1 − θ1 z − θ2 z2 = (1 − c1 z)(1 − c2 z) . [25]

(i) Show that c1 + c2 = θ1 and c1 c2 = −θ2 .

(ii) Show that the AR(2) model has a unit root if and only if θ1 + θ2 − 1 = 0. [Hint: The roots
of 1 − θ1 z − θ2 z2 = 0 are 1/c1 and 1/c2 .]

(iii) Show that θ1 + θ2 − 1 < 0 if the AR(2) process is stationary.

(iv) Show that the AR(2) model can also be written as

∆yt = δ + γyt−1 + a1 ∆yt−1 + νt ,

where γ = θ1 + θ2 − 1 and a1 = −θ2 . What are the implications of this result and the
results in parts (ii) and (iii) for unit root tests in an AR(2) model?

(v) Show that the AR( p) model has a unit root if γ = θ1 + θ2 + · · · + θ p − 1 = 0.

(vi) Explain with brief reasons whether the following statement is true, false, or uncertain: If
one of the roots in the AR( p) model is equal to one, then yt are said to have a stochastic
trend and are nonstationary.

AUoBM331 Page 7 Turn over

 23(JBJI) Any Calculator

1. Let n ∈ N∗ . We consider a Simple Linear Regression (SLR) model with output variables yi ∈ R,
(non-random) explanatory variables xi ∈ R, parameters β = (β1 , β2 ) ∈ R2 , and random errors
εi valued in R, for i ∈ {1, . . . , n}. We define x = 1n ∑i xi , y = n1 ∑i yi as well as

Sxx = ∑(xi − x)2 , Sxy = ∑(xi − x)(yi − y), and Syy = ∑(yi − y)2 .
i i i

For any coefficients B = (B1 , B2 ) ∈ R2 , and the associated regressed outputs ybi = ybi (B), for
i ∈ {1, . . . , n}, we define the sum of squared errors SSE as

2
SSE = SSE(B) = ∑ yi − ybi (B) .
i

2
2
Likewise, we define SST = ∑i yi − y and SSR = ∑i ybi − y .

(a) (i) State the 6 standard assumptions of the SLR model.

(ii) Give the definition of the Ordinary Least Square (OLS) estimator b = (b1 , b2 ) and
then show that b is given by

Sxy
b2 = and b1 = y − b2 x.
Sxx

[15]

(b) We consider an estimator βb = (βb1 , βb2 ) for β = (β1 , β2 ).

(i) When do we say that βb is a linear estimator ?

(ii) When do we say that βb is an unbiased estimator ?

(iii) Prove that the OLS estimator b is linear and unbiased.

(iv) State the Gauss–Markov theorem. You are required explain how 2 estimators are
compared.

[10]

AUoBM331 Page 2 Turn over

 Any Calculator

2. We consider a linear regression model

yi = β1 + β2 xi + εi ,

with output variables yi ∈ R, explanatory variables xi ∈ R, coefficients β = (β1 , β2 ) ∈ R2 , and

random errors εi valued in R, and with variance σ 2 > 0, for i ∈ {1, . . . , n}. We assume all the
standard assumptions, and furthermore that the εi are independent. We also assume that the
xi are all different and ordered, i.e. x1 < . . . < xn .

(a) We define an estimator βb = (βb1 , βb2 ) for β = (β1 , β2 ) as follows. We choose two indices
i, j ∈ {1, . . . , n}, with i < j, and approximate the data by the line joining (xi , yi ) to (x j , y j ).
Then, βb1 and βb2 are taken to be the intercept and slope, respectively, of this line.

(i) Express βb1 and βb2 as a function of xi , yi , x j and y j .

(ii) Show that βb is linear.

(iii) Compute E[βb].

(iv) Find the variance matrix of βb.

(v) Determine the distributions of βb1 and βb2 .

(vi) We are interested in the estimation of β2 . What is the optimal choice for i and j ?

(vii) Is βb better than the OLS estimator b ? You are required to justify your answer.

[20]

(b) We denote by R the coefficient of determination, and by y the mean of the observed data
yi , i ∈ {1, . . . , n}. SST and SSR are, as usual, the sum of squares in total and the sum of
squares in the regression.

In the questions below, you are required to provide a literal formula, then a numerical
result, and to box both your literal and numerical answer. Give your results rounded to 2
decimal places.

(i) Compute R2 , given that the sample size is n = 20, ∑i y2i = 5930.94, y = 16.035,
and SSR = 666.72.

(ii) Compute the unbiased estimator of σ 2 , given that R2 =0.7911, SST = 552.36, y =
16.035, and n = 20.

[5]

AUoBM331 Page 3 Turn over

 Any Calculator

3. (a) Consider a financial time series, the daily return of a security in logarithmic form, denoted
by rt , follows an AR(2) model given by as the following:

rt = 0.01 + 0.2rt−2 + at ,

where {at } is the error term with mean zero and variance 0.02, and t is the index of the
time interval from 1, . . . , T .

(i) Calculate the mean and variance of the return series rt . [3]

(ii) Calculate the first-order and second-order autocorrelations of rt . [3]

(iii) Given r100 = −0.01 and r99 = 0.02,forecast the daily return for one month and two
months ahead, respectively at t = 100. [4]

(iv) Calculate the standard deviations in the above 3(a) (iii), respectively. [2]

(b) Examine the following time series data representing a country’s Gross Domestic Product
(GDP) growth over twenty years:

Year GDP Growth Rate (%)

1 2.3
... ...
20 2.4

(i) Describe the Dickey-Fuller test and its significance in time series analysis, dis-
cussing three types of the Dickey-Fuller test. [4]

(ii) Describe the steps for conducting a Dickey-Fuller test for the GDP growth rate series,
given the data above. [3]

(iii) Discuss whether the Dickey-Fuller test is formulated similarly to a t-test, stating the
similarities and differences. [2]

(iv) If the Dickey-Fuller test statistic is -3.5 with a critical value of -2.88 at the 5% sig-
nificance level, perform an appropriate Dickey-Fuller test and interpret the results.
[2]

(v) Discuss the implications of your findings for the forecastability and mean reversion
of the GDP growth rate series. [2]

AUoBM331 Page 4 Turn over

 Any Calculator

4. (a) Consier a regression model as the following:

y = β0 + β1 y1 + β2 y2 + . . . + βk yk + ε

Where y is the dependent variable, ys are the kth explanatory variables and β are the
associated parameters, ε is the random error term.

Use the procedure of the Ramsey Regression Equation Specification Error Test (RESET)
to answer the following questions:

(i) Describe the steps involved in conducting the Ramsey RESET test for the above
model. Include in your discussion how to interpret the test statistic and the decision
rule based on the p-value.

(ii) Assume you have run a linear regression with one independent variable X and ob-
tained the following results:
ŷi = 2.0 + 0.5xi .

Can you add ŷi to the right-hand side of the regression equation to test for misspec-
ification? Explain how to perform the RESET test for the above model.

(iii) Discuss the limitations of the Ramsey RESET test. How would you adjust your
model is the RESET results are significant?

[18]

Question 4 continued overleaf.

AUoBM331 Page 5 Turn over

 Any Calculator

(b) Consider the weekly yields of Moody’s AAA & BAA seasoned bonds from January 5,
1962 to April 10, 2009. The data are obtained from the Federal Reserve Bank at St.
Louis. Table 1 gives the summary statistics for both time series. The sample size is 2467.
Using the information from the table below, answer the following questions using a 5%
significance level. [7]

Table 1: Summary statistics for weekly yields of Moody’s AAA & BAA seasoned bonds from
January 5, 1962 to April 10, 2009
X̄ Std Dev σ̂ Skewness Ŝ(x) Kurtosis K̂(x) Min Max
Aaa 7.83 2.419 0.857 0.578 4.19 15.85
Baa 8.85 2.717 0.930 0.761 4.78 17.29

(i) Are the distributions of the two series skewed? Justify your answer.

(ii) Do the distributions of the two series have heavy tails? Justify your answer.

(iii) Calculate the Jarque-statistics of the two series, respectively, and interpret your find-
ings. Note that the 5% critical value from a chi-squared distribution with two degrees
2
of freedom is χ0.95,2 = 5.9915.

AUoBM331 Page 6 End of paper