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.

In this mini-project, you’ll implement an agent that can solve the Sheep and Wolves problem for an arbitrary number of initial wolves and sheep. You will submit the code for solving the problem to the Mini-Project 1 assignment in Gradescope. You will also submit a report describing your agent to Canvas. Your grade will be based on a combination of your report (50%) and your agent’s performance (50%).

About the Project

The Sheep and Wolves problem is identical to the Guards & Prisoners problem from the lecture, except that it makes more semantic sense why the wolves can be alone (they have no sheep to eat). Ignore for a moment the absurdity of wolves needing to outnumber sheep in order to overpower them. Maybe it’s baby wolves vs. adult rams.

As a reminder, the problem goes like this: you are a shepherd tasked with getting sheep and wolves across a river for some reason. If the wolves ever outnumber the sheep on either side of the river, the wolves will overpower and eat the sheep. You have a boat, which can only take one or two animals in it at a time, and must have at least one animal in it because you’ll get lonely (and because the problem is trivial otherwise). How do you move all the animals from one side of the river to the other?

In the original Sheep & Wolves (or Guards & Prisoners) problem, we specified there were 3 sheep and 3 wolves; here, though, your agent should be able to solve the problem for an arbitrary number of initial sheep and wolves. You may assume that the initial state of the problem will follow those rules (e.g. we won’t give you more wolves than sheep to start). However, not every initial state will be solvable; there may be combinations of sheep and wolves that cannot be solved.

You will return a list of moves that will solve the problem, or an empty list if the problem is unsolvable based on the initial set of Sheep and Wolves. You will also submit a brief report describing your approach.

Your Agent

To write your agent, download the starter code below. Complete the solve() method, then upload it to Gradescope to test it against the autograder. Before the deadline, make sure to select your best performance in Gradescope as your submission to be graded.

In this task, you train a sentiment classifier that detects positive and negative sentiment in (English) texts. In machine learning, the choice of learning methods and hyperparameters plays a major role, so you compare different approaches.

Prepare dataset

The “Large Movie Review Dataset” by Maas et al. consists of 50,000 movie reviews from IMDb. Download the dataset (https://ai.stanford.edu/~amaas/data/ sentiment/) and unzip the archive. We are interested in the positive and negative reviews in the training and testing set. Copy the data to the directory structure expected by Scikit-learn:

|– test

• |  |– neg
• |   | |– 0_2.txt
• |   | |– 10000_4.txt
• | | …

o|  `– pos.txt

o|        |– 0_10.txt

o

o|        |– 10000_7.txt

o

o|        …

o`– train

o|– neg

• |  |– 0_3.txt
• |   |– 10000_4.txt
• |  … `– pos
• |–0_9.txt
• |–10000_8.txt
• …

– Train and evaluate models

– Load the training set and the test set.

– Writeafunctionevaluate_pipeline(pipeline, train_set, test_set) that takes a scikit-learn pipeline, a training set, and a test set. The function should train the pipeline on the training set, on the test set with the F1 value

(sklearn.metrics.f1_score) and return it rounded to four decimal places.

Define the following pipelines and train and evaluate them with the

evaluate_pipeline function. Output the evaluation results.

– – Naive Bayes classifier on Tf-Idf values of all words.

– – Naive-Bayes classifier on Tf-Idf values of all words appearing in at least 2 documents.

– Naive Bayes classifier on L2-normalized frequencies of all words.

– – Naive Bayes classifier on L2-normalized frequencies of all words, which occur in at least 2 documents.

– – Linear Support Vector classifier on Tf-Idf values of all words.

– Linear Support Vector classifier on Tf-Idf values of all words occurring in at least 2 documents.

– Linear Support Vector classifier on L2-normalized frequencies of all words.

– Linear Support Vector classifier on L2-normalized frequencies of all words occurring in at least 2 documents.

– Linear Support Vector classifier on Tf-Idf values of all words and word bigrams occurring in at least 2 documents.

– Linear support vector classifier on L2-normalized frequencies of all words and word bigrams occurring in at least 2 documents.

In this project, you will use Software Defined Networking (SDN) principles to create a configurable firewall using an OpenFlow enabled Switch. The Software Defined Networking function allows you to programmatically control the flow of traffic on the network

This project will start with a review of Mininet (this was first used in the optional Simulating Networks project). This review will explain the basic concepts of Mininet and the functionality you may need to complete this project.

The next phase will involve examining network traffic using Wireshark. This will allow you to see the header contents that will be important in building the code necessary to implement the firewall as well as the necessary ruleset you will create to test the firewall.

After this, you will need to perform two tasks that need to be conducted in parallel:

1. You will create a configuration file ruleset that describes certain types of traffic that should be blocked or allowed between individual hosts and networks. You will define this “ruleset” using header packet parameters such as Source IP Address, Destination Port Number, IP Protocol, and Destination MAC Address (there are more parameters, these are given as an example). Your ruleset will contain instruction on whether certain traffic should be blocked or should be allowed. By default, all traffic will be allowed. You will need to specify “routes” that need to be blocked and any specific exceptions to the block that you want to allow.

2. You will create python code that will take the parameters of the configuration from the first task above and create a flow policy object using the POX OpenFlow SDN frameworks. Please start early on this project, especially if you are unfamiliar working with Python APIs.

Part 0: Project References

You will find the following resources useful in completing this project. It is recommended that you review these resources before starting the project.

Project Goals

In this project, you will be developing a simple Java application (processfile) using an agile, test-driven process involving multiple deliverables. While you will receive one grade for the entire project, each deliverable must be completed by its own due date, and all deliverables will contribute to the overall project grade.

Specification of the processfile

Utility processfile is a simple command-line utility written in Java with the following specification:

Summary

processfile allows for simple text manipulation of the content of a file.

Syntax

processfile OPTIONS FILE

Description

Program processfile performs basic text transformations on lines of text from an input FILE. Unless the -f option (see below) is specified, the program writes transformed text to stdout and errors/usage messages to stderr. The FILE parameter is required and must be the last parameter. OPTIONS may be zero or more of the following and may occur in any order:

● -f Edit file in place. The program overwrites the input file with transformed text instead of writing to stdout.

● -n Add line numbers to each line, unpadded starting from 1.

● -s Keep only the lines containing the given string.

● -r Replaces the first instance of string1 in each line with string2.

● -g Used with the -r flag ONLY; replaces all occurrences of string1 in each line with