In lecture, we have seen that a deque can serve both as a stack and as a queuedepending on usage. We have also seen that a deque can be implemented using alinked list or an array to store its data. We will employ both of those features in thisproject.

Because we will use a deque as the storage medium for our queues and stacks, wewill begin there. You will implement two deque classes, one using an array to storethe contents and one using a linked list to store the contents. Notice that regardlessof how you store the data, the six operations that define a deque must be present:two pushes, two pops, and two peeks. If something calls itself a deque, it mustprovide at least those six methods. The programming pattern that enforces this iscalled an interface or more generally an abstract base class. We provide a completeabstract base class called Deque in the file Deque.py. Notice that the file does notcontain implementations; it only defines the functions that must be present. If youattempt to inherit from Deque, the child class must contain the methods listedin the abstract base class, or Python will refuse to construct the object andterminate. This is done via the special method __subclasshook__:

def __subclasshook__(child): required_methods = {‘push_front’, ‘push_back’, \ ‘peek_front’, ‘peek_back’, \’pop_front’, ‘pop_back’} if required_methods <= child.__dict__.keys(): return True return False

Python will call this method to see if a child class is allowed to inherit from the Dequeclass—that is, are the six required methods a subset of the methods in the child’snamespace? (In Python a set B is a subset of set A if and only if A <= B is True.) If allsix methods are there, __subclasshook__ will return True, indicating that child lookslike a deque and instantiation can proceed. If any method is missing,__subclasshook__ will return False, indicating that the child does not qualify as adeque and instantiation cannot proceed. This file is complete; do not modifyDeque.py.

Linked_List_Deque and Array_Deque should both inherit from Deque.Linked_List_Deque’s constructor will initialize an empty linked list for the data.Array_Deque’s constructor will initialize an empty array for the data. The six requiredmethods will have different implementations in each class because we interact witharrays and linked lists differently. Except for performance differences, the user ofyour deque should not be able to tell whether the implantation used a linked list oran array. Their functionality (and string representations) must be identical.

Each question counts for 50 points, for a total of 100 points for AN-
SWERING *** TWO *** QUESTIONS ONLY. (DO NOT SUBMIT AN-
SWERS FOR MORE THAN TWO QUESTIONS. ONLY TWO WILL BE
MARKED.)
1. (a) (25 points) Consider 2-player strategic form game, G, specied
by the following \bimatrix”:
2664
(7; 4) (9; 5) (2; 3) (2; 6)
(4; 1) (9; 2) (2; 1) (3; 6)
(8; 7) (6; 7) (5; 8) (2; 7)
(3; 3) (7; 4) (4; 6) (2; 4)
3775
As usual, player 1 is the row player, and player 2 is the column
player. If the content of the bimatrix at row i and column j is
the pair (a; b), then u1(i; j) = a and u2(i; j) = b.
Compute all of the Nash equilibria (NEs) of this game G, together
with the expected payo to each player in each NE. Explain why
any prole x that you claim is an NE of G, is indeed an NE of G,
and furthermore, explain why there are no other (pure or mixed)
NEs of G, other than the prole(s) you claim are NE(s) of G.
(b) (25 points) Consider a nite game, G, with pure strategy sets
S1; : : : ; Sn for the n players, and with a payo function ui(s)
for each player i 2 f1; : : : ; ng that assigns a payo to each pure
strategy prole s = (s1; : : : ; sn) 2 S = S1  S2  : : :  Sn.
Now consider a dierent n-player game, G0, which has exactly the
same strategy sets S1; : : : ; Sn, as G, but where the payo function

u0i(s) for each player i diers from ui(s) as follows:
u0i(s) = ui(s) + gi(s􀀀i)
where, for each player i, gi : S􀀀i ! R is a function (any function)
that depends only on the other players’ pure strategies and not
on player i’s own pure strategy.
Prove that G and G0 have exactly the same set of Nash equi-
libria. In other words, prove that a mixed strategy prole x =
(x1; : : : ; xn) is a NE for G if and only if x is a NE for G0.
(Note, however, that the same NE may yield entirely dierent
payos to the dierent players in G and in G0.)

2. (a) (20 points) Consider the 2-player zero-sum game given by the
following payo matrix for player 1 (the row player):
266664
5 6 4 7 3
6 4 5 3 8
7 2 5 4 6
4 7 3 5 7
3 5 8 6 3
377775
Compute both the minimax value for this game, as well as a min-
imax prole (NE), i.e. a pair of minmaximizer and maxminimizer
strategies for players 1 and 2, respectively.
(You can, for example, use the linear programming solver package
linprog in MATLAB, available on DICE machines, to do this.
To run MATLAB, type \matlab” at the shell command prompt.
For guidance on using the linprog package, see:
http://uk.mathworks.com/help/optim/ug/linprog.html.)
(b) (30 points) Recall from Lecture 7 on LP duality, the symmetric 2-
player zero-sum game, G, for which the (skew-symmetric) payo
matrix (in block form) for player 1 is:
B =24
0 A 􀀀b
􀀀AT 0 c
bT 􀀀cT 0
35
Suppose that there exist vectors x0 2 Rn and y0 2 Rm, such
that Ax0 < b, x0  0, AT y0 > c and y0  0. (Note the two
strict inequalities.) Prove that for the game G, every minmaxi-
mizer strategy w = (y; x; z) for player 1 (and hence also every
maxminimizer strategy for player 2, since the game is symmetric)
has the property that z > 0, i.e., the last pure strategy is played
with positive probability. (Recall that this was one of the missing
steps in our sketch proof in the lecture that the minimax theorem
implies the LP duality theorem.)
(Hint: Let w = (y; x; z) be a maxminimizer strategy for player
2 in the game G. Note that the value of any symmetric 2-player
zero-sum game must be equal to zero. This implies, by the min-
imax theorem, that Bw  0. Suppose, for contradiction, that
z = 0. What does this imply about Ax , AT y, and bT y􀀀cT x?
Then if y 6= 0, show that this implies (y)T (Ax0 􀀀 b) < 0. In
turn, show that it also implies (x)T (AT y0 􀀀 c) > 0. Use these
and related facts to conclude a contradiction.)

3. Consider the following simple 2-player zero-sum games, where the pay-
o table for Player 1 (the row player) is given by:
A =  1 􀀀1
􀀀1 1 
We can view this as a game where each player chooses \heads” (H) or
\tails” (T), where the rst strategy for each player is denoted H and
the second strategy is denoted T.
(a) (10 points) First, what is the unique Nash equilibrium, or equiva-
lently the unique minimax prole of mixed strategies for the two
players, in this game? And what is the minimax value of that
game?
(b) (40 points) Now, suppose that the two players play the same game
you have chosen in part (a), against each other, over and over
again, for ever, and suppose that both of them use the following
method in order to update their own strategy after each round of
the game.
i. At the beginning, in the rst round, each player chooses ei-
ther of the pure strategies, H or T, arbitrarily, and plays
that.
ii. After each round, each player i accumulates statistics on how
its opponent has played until now, meaning how many Heads
and how many Tails have been played by the opponent, over
all rounds of the game played thusfar. Suppose these num-
bers are N Heads and M Tails.
Then player i uses these statistics to \guess” its opponents
\statistical mixed strategy” as follows. It assumes that its op-
ponent will next play a mixed strategy , which plays Heads
with probability N=(N+M) and plays Tails with probability
M=(N +M).
Under the assumption that its opponent is playing the \sta-
tistical mixed strategy” , in the next round player i plays a
pure strategy (H or T) that is a pure best response to .
If both H and T are a best response at any round, then
player i can use any tie breaking rule it wish in order to
determine the pure strategy it plays in the next round.
iii. They repeat playing like this forever.

Prove that, regardless how the two players start playing the game
in the rst round, the \statistical mixed strategies” of both play-
ers in this method of repeatedly playing the game will, in the long
run, as the number of rounds goes to innity, converge to their
mixed strategies in the unique Nash equilibrium of the game.
You are allowed to show that this holds using any specic tie
breaking rule that you want. Please specify the precise tie break-
ing rule you have used. (It turns out that it holds true for any
tie breaking rule. But some tie breaking rules make the proof a
lot easier than others.)

4. (a) (40 points) One variant of the Farkas Lemma says the following:
Farkas Lemma A linear system of inequalities Ax  b has a
solution x if and only if there is no vector y satisfying y  0 and
yTA = 0 (i.e., 0 in every coordinate) and such that yT b < 0.
Prove this Farkas Lemma with the aid of Fourier-Motzkin elim-
ination. (Hint: One direction of the \if and only if” is easy.
For the other direction, use induction on the number of columns
of A, using the fact that Fourier-Motzkin elimination \works”.
Note basically that each round of Fourier-Motzkin elimination
can \eliminate one variable” by pre-multiplying a given system
of linear inequalities by a non-negative matrix.)
(b) (10 points) Recall that in the Strong Duality Theorem one possi-
ble case (case 4, in the theorem as stated on our lecture slides)
is that both the primal LP and its dual LP are infeasible. Give
an example of a primal LP and its dual LP, for which both are
infeasible (and argue why they are both infeasible).

You may use any programming l anguage you l ike (Python, C++, C, Java… ) . All programming must be
done individually f rom rst principles. You are only permitted to use existing t ools f or simple l inear algebra
such as matrix multiplication/inversion. Do NOT use any toolkit that performs machine learning
functions and do NOT collaborate with your classmates. Cite any resources that were used.
In t his project you will practice the basics of Machine Learning Classication by creating a K-NN clas-sier
for two datasets. You will also practice good practices f or how to describe, evaluate, and write up a report on
the classier performance.
It i s expected that your project report may require 2 pages per dataset i f you are good about making
interesting gures and making them not too l arge, or 3 pages i f your gures are big.
Datasets: The project will explore two datasets, the famous MNIST dataset of very small pictures of
handwritten numbers, and a dataset that explores the prevelance of diabetes in a native american tribe
named the Pima. You can access the datasets here:
1. https://www.kaggle.com/uciml/pima-indians-diabetes-database
2. https://www.kaggle.com/c/digit-recognizer/data
Programming Task: For each dataset, you must create a K-NN classier that uses the training data to
build a classier, and evaluate and report on the classier performance.
(30 points) Dataset details: Describe the data and some simple visualizations (for images, a few exam-
ples from each category; for other data, perhaps some scatter plots or histograms that show a big picture of
the data). Describe your training/test split for K-NN and justify your choices.
(15 points) Algorithm Description: K-NN is a very clear algorithm, so here describe any data pre-
processing, feature scaling, distance metrics, or otherwise that you did.
(45 points) Algorithm Results: Show the accuracy of your algorithm|in the case of the Pima Dataset,
show accuracy with tables showing false positive, false negative, true positive and true negatives. For the
Pima Dataset, use three dierent distance metrics and compare the results.
In the case of the MNIST digits show the complete confusion matrix. Choose a single digit to measure
accuracy and show how that number varies as a function of K.
(10 points) Runtime: Describe the run-time of your algorithm and also share the actual “wall-clock”
time that it took to compute your results.

Exercise 1: Adding Operators to the Point class
By supporting operators, you can make your classes easier and more natural to use. However you must not “overuse” operators. Only use operators if the functionality of the operator is clear without reading documentation. Thus adding mathematical operators to a complex number class is good but using a + operator with a double as an argument on a point to increase the x-coordinate is questionable. So use operators with care. In this exercise we add a few operators to the Point class. Most operators do not change the original objects but return the result as a new object. Normally only the = operator and += and variants change the original object. Add the following operators:

Exercise 2: Ostream << Operator
It would be nice if you could send a point or a line directly to the cout object without calling the ToString() method, just as with the primitive types. This is possible by adding a << operator function that has on the left an std::ostream and on the right the point or line object. Since you can’t add a member function to the std::ostream class, you have to create it as a global function (outside the class definition, but inside the class header file):
ostream& operator << (ostream& os, const Point& p); // Send to ostream.
The implementation uses the << operator to send data to the os input argument. Since it is a global function, you can’t access the private members of Point. To simplify things, you can use the ToString() method of Point to get the string to send to the os argument. Also create a similar << operator for printing lines (and circles if you made a circle class). Adapt the test program to test the << operator for points and lines.

Exercise 3: Constructors as conversion operator
In this exercise we are going to do a little experiment. First add to the Point class a constructor that accepts one double as an argument. The implementation should set both the x- and y-coordinate to this value. Next try the following code in the test program:
Point p(1.0, 1.0);
if (p==1.0) cout<<“Equal!”<<endl;
else cout<<“Not equal”<<endl;
Will this code compile and can you explain why? It turns out that the Point constructor with the single double argument is implicitly used to convert the number in the if statement to a Point object. Thus constructors are used as implicit conversion operators. To prevent the usage of constructors are implicit conversion operators, declare the constructor as explicit:
explicit Point(double value);
Now try to compile the program again and you will see that now the if statement gives a compiler error. You can still use the constructor as conversion operator but then explicitly:
if (p==(Point)1.0) cout<<“Equal!”<<endl;

Exercise 4: Friends
Normally, only member functions of a class can access the private members of that class. Global functions and other classes can’t access the private members of that class. You can make an exception on that rule by declaring certain functions or classes as friend. For example the << operator for sending the point or line to the std::ostream class had to be a global function and thus can’t access the private members. Move the << operator of Point and Line inside the class definition and declare it as friend. The function remains a global function but it can now access the data members directly without the need for calling the getters or ToString() function. Normally, friends are to be avoided because it violates the data hiding principle. But in case of global operator functions it makes sense because you would actually want to make those global operator functions as member function but this was not possible.