CS-UY 1114辅导、辅导Python设计、Python编程调试、讲解canvas留学生 解析Java程序|解析Haskell程序
- 首页 >> CS CS-UY 1114 — Final Project
Contents
1 Introduction 1
2 Projects 1
2.1 Pong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2 Space invaders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 n-bodies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.4 Automatic iris classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Tic Tac Toe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.6 Something else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Important information 10
3.1 Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Hints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Academic honesty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 Getting help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Submission 15
4.1 Status report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 The README file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.3 Dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Materials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1 Introduction
You will complete a final project, accounting for 10% of your final grade.
2 Projects
You must choose one of the following projects to implement. All projects must be completed in Python 3,
using only built-in libraries. If you have previously taken this class, your final project must be different than
any project that you’ve attempted in the past.
You can see video demos of each program at the following address: https://drive.google.com/drive/
folders/1xZkg75hl_GwQdu_OmjwY7jXUFk4JHdGE?usp=sharing
2.1 Pong
You will implement a version of the classic “pong” game, in which the player moves a virtual paddle to
deflect a bouncing ball, while an opponent with artificial intelligence does the same. The user interacts with
the game on the turtle canvas.
1θ
d
The gray horizontal bar represents a paddle, and the dotted line is the path of the ball
after impact. d represents the distance between the point of impact and the paddle’s
center point, which is the only factor in deciding θ.
The ball will move at a constant speed. Initially, the ball will be in the center of the window, moving in
a random direction. The player may control the player’s paddle by using the left and right arrow keys.
If the ball hits a paddle, it will deflect off at an angle depending only on what part of the paddle it hits.
If the ball hits the exact center of the paddle, it will bounce off straight, perpendicular to the paddle (i.e.
θ = 90). If the ball hits the extreme left end of the paddle, it will bounce off left, at a 30 degree angle
relative to paddle (i.e. θ = 30). If the ball hits the extreme right end of the paddle, it will deflect at a 30
degree angle to the right (i.e. θ = 150). The angle of bounce in other positions is proportional between the
extremes of 30 and 150 degrees.
If the ball hits a wall, its vertical velocity will not change, but its horizontal velocity will be mirrored,
i.e. it will move at the same speed in the opposite direction.
If a paddle fails to hit the ball, that player’s opponent will gain a point, and the game will continue with
the ball moved to the center of the window, with its direction randomized. The position of the paddles will
not be reset. The total number of points for each player is displayed on the left side of the screen.
The opponent’s paddle must make a reasonable attempt to deflect the ball. You are responsible for
designing its artificial intelligence.
The game ends when the player’s opponent reaches a score of 5 points. At that time, the player’s score
will be considered for inclusion in the high score table. The high score table will consist of the best 10 scores
that have been won by players, along with the players’ names. The high score table must be stored in a
file, so that its contents will persist between multiple plays of the game. If the player’s score is among the
10 highest, or if at least 10 scores have not yet ben recorded, then the player will be prompted in a dialog
box to enter their name, whereupon their name and score will be saved into the table. Whether or not the
player qualifies for a high score, the current high score table will be displayed, from highest to lowest, in the
turtle window when the game ends. If the game has never been played before, assume the high score table
is empty.
Getting started We provide you with starter code to help you begin this project. See the file in
starter.zip. This is a starting point; you should replace the pass lines with code to perform the appropriate
actions in strict accordance with the given specifications.
2.2 Space invaders
You will implement a version of the classic “space invaders” game, in which the player battles against an
army of invading monsters. The user interacts with the game on the turtle canvas.
In this game, the user uses the arrow keys to control a space ship that can move along the horizontal
axis. Pressing the space key will cause the ship to shoot a single bullet, which will move at a constant speed,
starting from the current position of the ship. If the bullet hits an enemy, both the enemy and the bullet
will be removed from the game. If the bullet leaves the visible area of the screen, it will be removed from
the game. There may be multiple bullets in flight at the same time. If no enemies remain, the player has
won, and the game ends.
2The enemies are initially arranged in rows. As you can see in the video, the enemies move in a distinctive,
jerky pattern that your project must reproduce: they move all together at a regular intervals; initially, this
time interval is one second, but as the game progresses, the time interval will get smaller and smaller, causing
them to move increasingly fast. The enemies move horizontally (left or right), until the reach the end of the
window, whereupon they will move one row closer to the player, and then continue moving horizontally in
the opposite direction (if they were moving left in the previous row, they will move right in the subsequent
row), until they again reach the end of the window. Please consult the provided video for an example of
enemy movement. If an enemy touches the player’s ship, the player has lost, and the game ends.
You may choose to implement any of the following optional components: enemies that can shoot back;
attractive and colorful graphics; scoring; a high-score table. Please discuss these options with your instructor.
Getting started We provide you with starter code to help you begin this project. See the file in
starter.zip. This is a starting point; you should replace the pass lines with code to perform the appropriate
actions in strict accordance with the given specifications.
2.3 n-bodies
You will implement a visualization of the classic “n-bodies” problem, a simulation of the effects of gravitation
acting on various objects on a plane. Your program will graphically display the position all bodies in the
system on the turtle canvas.
You will be given a file named bodies.txt containing the initial state of the simulation. The state of
the simulation consists of: the gravitational constant G, as well as the name, position, velocity, and mass
of an arbitrary number of objects. Your program will read this file in and simulate subsequent interactions
between bodies, while displaying graphically a visualization of the simulation. Note that your program must
work with any valid bodies.txt file: you cannot assume the number of bodies, their attributes, or their
relationships. Here is an example file:
.00005
Sun 500 500 0 0 100000000
Splat 255 255 2 0 1
Arg 745 745 -2 0 2
Magnavolt 270 740 -1.5 -3 12000
Spatula 253 450 0 -2 50000
Smoo 500 0 3 0 1000000
Volt 504 0 4 4 0.000001
The first line contains a value for G, the gravitational constant. In the real universe, G is always
6.67384 × 1011m3kg, but in our simulation, it can be anything. Its magnitude is given as the first
line in the input file.
The subsequent lines contain information about each body. Each line gives:
The body’s name (a str).
The body’s initial horizontal position (a float).
The body’s initial vertical position (a float).
The body’s initial horizontal velocity (a float).
The body’s initial vertical velocity (a float).
The body’s mass (a float).
3So, in the above file, the sun is the most massive object in the universe and it is not moving initially.
The heart of the simulation is the calculation of the forces acting on each body. Given a body located at
position x1, y1 and a body located at x2, y2, the distance between them is
The horizontal distance between the bodies is |x1 x2|, and the vertical distance between them is |y1 y2|.
The gravitational force F between two bodies is
where
G is the gravitational constant
M1 is the mass of the first body
M2 is the mass of the second body
d is the distance between the two bodies
We will focus on a two-dimension simulation. Therefore we are interested in the horizontal force (Fx)
and vertical force (Fy) on each body. These are given as:
Fx = G
M1 × M2 × dx
d
3
Fy = G
M1 × M2 × dy
d
3
where dx and dy are the horizontal and vertical distance between the bodies, respectively.
Recall that there is gravitational force between all objects in the universe. In particular, every object
exerts gravitational force on every other object. The net force on a body is the sum of all forces on it. In the
case of our simulation, this means the sum of the gravitational forces between a body and all other bodies
in the simulation.
The acceleration of a body is given by a = F/m where
F is the net force acting on that body
m is the mass of that body.
Similarly, the horizontal and vertical accelerations are given by ax = Fx/m and ay = Fy/m.
At every frame of the animation, the velocity of each body must be updated, based on its current
acceleration. In this program, the implicit units of the acceleration are in pixels per frame per frame. Thus,
if the horizontal acceleration of a body is 3, then its horizontal velocity will be increased by 3 every frame.
In other words: velocity is the integral of acceleration.
At every frame of the animation, the position of each body must be updated, based on its current velocity.
In this program, the implicit units of the velocity are in pixels per frame. Thus, if the horizontal velocity of
a body is 3, then its horizontal position will be increased by 3 pixels every frame. Likewise, if its vertical
velocity is -1, its vertical position will be decreased by 1 pixel every frame. In other words: position is the
integral of velocity.
Getting started We provide you with starter code to help you begin this project. See the file in
starter.zip. This is a starting point; you should replace the pass lines with code to perform the appropriate
actions in strict accordance with the given specifications.
If you’ve got a working prototype of your project, ask your professor for additional versions of bodies.txt
that you can use to test your program.
42.4 Automatic iris classification
In this project, you will write a program that can automatically classify an iris plant into one of three species,
using machine learning techniques. The program will display its results in a graph on the turtle canvas.
The three species of iris plants observed are iris setosa, iris veriscolor, and iris virginica. Flowers of
iris setosa tend to be larger than flowers of iris veriscolor or iris virginica. If the length and width of the
petals of a number of iris flowers are measured and the species of these flowers is known, we can use this
information about known iris flowers of each species to attempt to classify an unknown flower based on
the size and width of its petals. This technique is called supervised machine learning. Supervised learning
requires a number of examples of iris flowers from the three species with known measurements of the length
and width of their petals. (In contrast, an unsupervised machine learning program might group like flowers
together, but it wouldn’t have any knowledge of which species the flowers actually belonged to.)
For this project, you will be creating a program that classifies an iris flower of unknown species. The
petal size of the flower must be known because the supervised learning program will match this information
to known flowers. In writing this program, some portion of the data for which the species, the petal length,
and the petal width are known will act as the training set. When the program is presented with a new flower
to classify, the program will find the most similar flower from the training set and classify the instance in
the same way as the known similar instance. This method of making predictions is known as the nearest
neighbor algorithm.
Though you might suspect that the nearest neighbor algorithm will make good predictions for the species
of an iris flower based on the measurements of petals, you need to test your program to see if it does.
The portion of the data that wasn’t used in the training set will be used to test the feasibility of making
this prediction based on your information. We will call this portion of data the test set. We do know
the species of the flowers in the test set, but we will ignore this fact in testing. Instead, your program
should classify the flowers in the test set based solely on their observed petal size. You will then compare
your program’s conclusion to the plant’s known species to determine the effectiveness of your program’s
classification strategy. If your program provides reasonable accuracy on this test set, you can be confident
that it can predict the species of iris given the petal size. It is important that when you test your program
using the test set, the program is given new examples of flowers that it has not seen before; in this way, we
simulate using your program on data for which the species is really unknown.
We provide two data files: iris_train.csv (the training set) and iris_test.csv (the test set). These
data files contain measurements for individual iris flowers and the corresponding type of each iris plant. 1
Both files are in CSV format; open them in a text editor to see how their content is represented. Each line in
the file contains a single observation about a particular plant. In particular, the first two comma-spearated
columns in the dataset contain the petal length of the flower (in cm); and the petal width of flower (in cm).
Each of these observable attributes (petal length and petal width) is called a feature. The last column in
the dataset gives the type of iris, either Iris-setosa, Iris-versicolor or Iris-virginica. This column is called
the label.
You will use the file iris_train.csv to build a predictive model. You will test your model on the file
iris_test.csv and determine the accuracy of your model. You can only use modules from the standard
distribution of Python in this project, and specifically the numpy and pandas modules are prohibited. Starter
code has been provided for you. We provide function headers and signatures for you; it’s your task to complete
the function bodies.
In the steps below, we walk you through the process of completing each function body in order. Make
sure that you understand what each function should do before you write code for it. Before moving on to
the next step, test your code thoroughly. Do not modify the main function.
1. Fill in the code for the function create_table which has been given. In order to do so, read the file
iris_train.csv into a tuple containing two lists of type float and one list of type string. The
1This project uses the Iris Data Set, which was referenced in R.A. Fisher’s 1936 paper detailing statistical methods to classify
an iris plant. You can read more about the dataset in the UCI Machine Learning Repository here: https://archive.ics.uci.
edu/ml/datasets/iris. The dataset has been edited for use in this project.
5features of the dataset should be of type float and the label should be of type string.
2. Complete the code for the function print_range_max_min which has been given. Notice that the
features of the dataset are both given in centimeters. Measure the range of each feature. This will
require you to find the min and the max of each column in your dataset. Print your resulting min, max
and range as shown. You will print your calculated values in place of the xxx.
Feature 1 - min: xxx max: xxx range: xxx
Feature 2 - min: xxx max: xxx range: xxx
3. You will use the numerical values of each feature to make your predictions. If you use the values as
they are, the features with higher values or a greater range might be given more importance in the
model. To avoid this effect, you will normalize each of your features. This means that you will rescale
all the values in a particular feature in terms of a mean of 0 and a standard deviation of 1. In order
to normalize your features, find the mean and the standard deviation. Fill in the code for the given
functions find_mean and find_std_dev. The formula for standard deviation is:
where σ is the standard deviation, μ is the mean and N is the number of values in the feature. The
syntax xi
indicates the i-th value of a particular feature.
Print the mean and standard deviation for each feature as shown. Your calculated values should be
printed in place of the xxx.
Feature 1 - mean: xxx std dev: xxx
Feature 2 - mean: xxx std dev: xxx
Determine the new normalized value, xi
′
, for each value, xi
, in a feature by as shown below. Implement
this functionality in the given function normalize_data.
Do this for all of the values in each feature. Check that you have correctly normalized the features
by testing again for their mean and standard deviation. The output of your function normalize_data
should now look at follows:
Feature 1 - mean: xxx std dev: xxx
Feature 1 after normalization - mean: xxx std dev: xxx
Feature 2 - mean: xxx std dev: xxx
Feature 2 after normalization - mean: xxx std dev: xxx
After normalization, each of your features should display a mean of 0 or very close to 0 and a standard
deviation of 1 or very close to 1.
4. You will use an algorithm called k-Nearest Neighbors to predict the type for each iris observation in
the test set. The test set is the file called iris_test.csv. In its simplest implementation, when k =
1, the k-Nearest Neighbors algorithm finds the observation in the training set that is ‘closest’ to the
observation you are trying to make a prediction for and uses the known label of the closest observation
as the prediction value. In order to find the observation that is ‘closest,’ you can think about each
6of the training set observations as a point on a two-dimensional plane. For example, an observation
will be plotted as (x, y), where x is equal to the value of feature 1 (petal length) and y is equal to
the value of feature 2 (petal width). In order to find the ‘nearest neighbor,’ you will calculate the
Euclidean distance between the point in the test set that you are trying to label and all of the points
in the training set. For this project, you will be implementing k-Nearest Neighbors with two features
and with k = 1, but the algorithm can be implemented in other ways. 2
Notice that the main function makes a second call to the create_table function, passing it the file
iris_test.csv. The program reads in the iris_test.csv file and stores the data in a two-dimensional
list called test_data. If you examine the test_data table, you’ll notice that this file also contains
labels for each observation. You will give a predicted label using the k-Nearest Neighbors algorithm as
described and then compare your prediction to the actual label. You will be measuring your error for
all of the observations in the test set.
The data in the test set also needs to be normalized. Notice that the main function makes a second
call to normalize_data, passing it test_data.
Now that the test data is prepared, make a prediction for each observation in the test dataset. Implement
this task in the function make_predictions which has been given. For each observation in
the test set, you’ll need to check all of the observations in the training set to see which is the ‘nearest
neighbor.’ Fill in the code for the find_dist function which has been given. The make_predictions
function should make a call to find_dist. Test your find_dist function independently to make sure
it is working properly. Use the formula for Euclidean distance between two points (x1, y1) and (x2, y2):
Your make_predictions function should accumulate a list of predicted iris types for each of the test
set observations. The function will return this prediction list.
5. Determine the error of your predictions. Implement this task in the given function find_error. You
will need to check the prediction list against the actual labels for the test set to determine how many
errors were made. Return a percentage of how many observations in the test set were predicted
incorrectly. Print the error percentage as shown:
The error percentage is: xxx
In practice (though not as part of this project), after you were confident that you could predict for
your test set with good accuracy, you would use your model to make predictions for observations for
which you did not know the label.
6. You will be using the turtle module to visualize the results of your analysis. See the sample plot for
reference. In order to create your plot, fill in the code for the plot_data function. First, set the turtle
window size to 500 x 500. Then draw the x and y axes in the window. Label your axes as shown in
the sample plot.
Plot each observation from your training set on the plane, using a circle shape and a different color
for each type of iris. Use the value of the first feature for the x-coordinate and the value of the second
feature for the y-coordinate. You can use a dot size of 10. Recall that the features have been normalized
to have a mean of 0 and a standard deviation of 1. You will need to ‘stretch’ your features across the
2While it is beyond the scope of this project, the k-Nearest Neighbors algorithm can be used with more than two features.
In this case, you can think about the values being plotted in an n-dimensional space with n being the number of features. Also,
rather than consulting just one ‘nearest neighbor,’ the algorithm can find any number of ‘nearest neighbors.’ You can specify,
k, as the number of nearest neighbors to find. In this case, the prediction would be for the majority class from the surrounding
nearest neighbors.
7Figure 1: Sample Plot of Results
axes to make the best use of the 500 x 500 window. Ensure that none of your points are plotted off
screen.
Also plot each correct prediction from your test set in the corresponding color. Use a square to indicate
that the value is a prediction. Plot the incorrect predictions that were made for the test set in red,
also using a square to indicate that it was a prediction.
Include a key in the upper left corner of the plot as shown in the sample plot. Fill in the code for the
function draw_key to implement this task. Your function plot_data will make a call to the function
draw_key.
2.5 Tic Tac Toe
You will implement a version of the classic “tic-tac-toe” game (also known as “noughts and crosses”), in
which the player competes against the computer to create a three-in-a-row pattern in vertical, horizontal, or
diagonal directions.
The user interacts with the game on the turtle canvas. The game is played in a 3-by-3 grid, which is
initially empty. There are two players, the human and the computer, who take turns. The human always
moves first. When it’s the human’s turn, he or she may place an “O” symbol in any empty position on the
game grid by clicking on the grid position with the mouse; afterwards, it becomes the computer’s move, and
the computer will place a “X” symbol in any empty position on the grid. The players continue to alternate
moves until the game ends. The game is over when any of the following conditions occurs:
there are three “O” symbols in a line in any row or column, or diagonally from corner to corner, which
means that the human has won
there are three “X” symbols in a line in any row or column, or diagonally from corner to corner, which
means that the computer has won
there are no empty positions on the board, meaning that no further moves are possible, and the game
ends in a stalemate
As part of this project, you must develop a reasonable (but simple) “artificial intelligence” to dictate
the behavior of the computer player. Although you may provide a more advanced algorithm (which your
professor will help you develop, if you ask), at a minimum, you must implement the following logic for the
computer player:
8 If it’s possible for the computer player to win in the current move (i.e. there are two “X”s and one
empty position in a line somewhere on the board), the computer player must win by occupying that
empty position.
If it’s possible for the human player to win on the next move (i.e. there are two “O”s and one empty
position in a line somewhere on the board), the computer player must prevent the human’s win by
occupying that empty position.
If neither of the above cases apply, the computer may randomly occupy any unoccupied position.
Getting started We provide you with starter code to help you begin this project. See the file in
starter.zip. This is a starting point; you should replace the pass lines with code to perform the appropriate
actions in strict accordance with the given specifications.
2.6 Something else
Besides the above projects, you may pursue another project of your own choosing. You may choose a project
relevant to your field of study: for example, if you study biology, you might want to look into a project
involving DNA sequencing; of if you study art, you can develop a program for generating computer art. You
may also propose a project relevant to your hobbies or interests. Your project must be of an appropriate
level of difficulty; must demonstrate an understanding of the techniques taught in this course; and must
solve an interesting problem or address a particular need. In all cases, your project must be approved by
your professor.
The steps for doing a project of your own design are as follows:
1. First, you should discuss your idea with your professor in person as soon as possible. Give an “elevator
pitch”: a summary, in a few sentences, of what your program will be. Your professor will be able to
let you know if it’s an appropriate project idea.
2. If your professor approves your verbal elevator pitch, you must submit a written proposal to your
professor by email. The proposal is much more detailed, and needs to describe exactly what your
program will do. Your professor will be looking for a proposal that demonstrates that you have
thought through the problem and have anticipated the challenges involved.
Your proposal represents a contract with your professor, describing exactly what you intend to create.
It must thoroughly cover all aspects of the behavior of your program. It should be at least as detailed
as the descriptions given above for the other projects. Your description of your program should include:
What is the purpose of the program? What problem is it solving?
What does the program look like? You may provide drawings of the proposed user interface as
illustrations.
How does the user interact with the program? What input is expected from the user? What
output is given to the user?
How does your program behave? Describe in detail a typical use of your program, from beginning
to end.
What errors can arise while your program is running? For example, what will happen if the user
provides unexpected or invalid input? Describe how your program will handle these cases.
Your proposal should be sufficiently detailed so that any competent programmer should be able to
implement your proposed project solely on the basis of your written proposal. However, the proposal
should not include any implementation details: you do not need to discuss functions, variables, or
anything else related to actually writing the code.
9Your professor may give you feedback about your proposal. For example, your proposal may need more
detail or a change in scope before it can be approved.
Insofar as your finished project diverges from your project proposal, any differences must be cleared
with your professor well in advance of the due date.
3. Once your written proposal has been approved by your professor, you are required to meet again with
your professor. At this meeting, you will discuss implementation, i.e. the strategy for converting your
written proposal into actual code. Your professor may have helpful suggestions for how to structure
your code.
4. At this point you may begin coding your project.
5. At the time of the status report, you must present your work so far to your professor, not to a TA.
Please bear in mind that implementing your own project typically requires significantly more work
than one of the default projects, because you won’t have the benefit of the starter code. In addition, it
requires more communication with your professor, to make sure that your development is continuing
in the right direction and that your code meets the required standards. It is your responsibility to
schedule meetings with your professor in furtherance of these goals.
3 Important information
Now that you’ve selected a project, let’s talk about the rules for completing it and how you can ensure a
successful project.
3.1 Rules
Before you start your project, you should prepare by reading this document thoroughly. In it, you will find
rules that you will need to take into account. Be aware that failure to consider these rules will result in a
penalty.
Your professor has provided a starting framework to help you get started. For the projects proposed
above, find the corresponding starting framework in starter.zip. You are welcome to make use of
these files to help you develop your project. If you are developing a different project, you may still
benefit from reading or adapting the starter code.
Please note that the code provided in the starting frameworks is designed to help you, but that does
not absolve you of the necessity to understand the code contained therein. Before you start writing
new code, you should make sure that you understand the structure of the code provided for you,
what it does, and exactly what remains to be done. Read the comments carefully: they tell you
exactly what your code should do. If you have any doubts, contact your professor. Many students
wasted time writing wrong code because they failed to thoroughly read and understand the framework.
Everything you need to know in order to complete the project has been covered in class; if you find
yourself consulting outside
Contents
1 Introduction 1
2 Projects 1
2.1 Pong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2 Space invaders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 n-bodies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.4 Automatic iris classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Tic Tac Toe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.6 Something else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Important information 10
3.1 Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Hints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Academic honesty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 Getting help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Submission 15
4.1 Status report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 The README file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.3 Dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Materials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1 Introduction
You will complete a final project, accounting for 10% of your final grade.
2 Projects
You must choose one of the following projects to implement. All projects must be completed in Python 3,
using only built-in libraries. If you have previously taken this class, your final project must be different than
any project that you’ve attempted in the past.
You can see video demos of each program at the following address: https://drive.google.com/drive/
folders/1xZkg75hl_GwQdu_OmjwY7jXUFk4JHdGE?usp=sharing
2.1 Pong
You will implement a version of the classic “pong” game, in which the player moves a virtual paddle to
deflect a bouncing ball, while an opponent with artificial intelligence does the same. The user interacts with
the game on the turtle canvas.
1θ
d
The gray horizontal bar represents a paddle, and the dotted line is the path of the ball
after impact. d represents the distance between the point of impact and the paddle’s
center point, which is the only factor in deciding θ.
The ball will move at a constant speed. Initially, the ball will be in the center of the window, moving in
a random direction. The player may control the player’s paddle by using the left and right arrow keys.
If the ball hits a paddle, it will deflect off at an angle depending only on what part of the paddle it hits.
If the ball hits the exact center of the paddle, it will bounce off straight, perpendicular to the paddle (i.e.
θ = 90). If the ball hits the extreme left end of the paddle, it will bounce off left, at a 30 degree angle
relative to paddle (i.e. θ = 30). If the ball hits the extreme right end of the paddle, it will deflect at a 30
degree angle to the right (i.e. θ = 150). The angle of bounce in other positions is proportional between the
extremes of 30 and 150 degrees.
If the ball hits a wall, its vertical velocity will not change, but its horizontal velocity will be mirrored,
i.e. it will move at the same speed in the opposite direction.
If a paddle fails to hit the ball, that player’s opponent will gain a point, and the game will continue with
the ball moved to the center of the window, with its direction randomized. The position of the paddles will
not be reset. The total number of points for each player is displayed on the left side of the screen.
The opponent’s paddle must make a reasonable attempt to deflect the ball. You are responsible for
designing its artificial intelligence.
The game ends when the player’s opponent reaches a score of 5 points. At that time, the player’s score
will be considered for inclusion in the high score table. The high score table will consist of the best 10 scores
that have been won by players, along with the players’ names. The high score table must be stored in a
file, so that its contents will persist between multiple plays of the game. If the player’s score is among the
10 highest, or if at least 10 scores have not yet ben recorded, then the player will be prompted in a dialog
box to enter their name, whereupon their name and score will be saved into the table. Whether or not the
player qualifies for a high score, the current high score table will be displayed, from highest to lowest, in the
turtle window when the game ends. If the game has never been played before, assume the high score table
is empty.
Getting started We provide you with starter code to help you begin this project. See the file in
starter.zip. This is a starting point; you should replace the pass lines with code to perform the appropriate
actions in strict accordance with the given specifications.
2.2 Space invaders
You will implement a version of the classic “space invaders” game, in which the player battles against an
army of invading monsters. The user interacts with the game on the turtle canvas.
In this game, the user uses the arrow keys to control a space ship that can move along the horizontal
axis. Pressing the space key will cause the ship to shoot a single bullet, which will move at a constant speed,
starting from the current position of the ship. If the bullet hits an enemy, both the enemy and the bullet
will be removed from the game. If the bullet leaves the visible area of the screen, it will be removed from
the game. There may be multiple bullets in flight at the same time. If no enemies remain, the player has
won, and the game ends.
2The enemies are initially arranged in rows. As you can see in the video, the enemies move in a distinctive,
jerky pattern that your project must reproduce: they move all together at a regular intervals; initially, this
time interval is one second, but as the game progresses, the time interval will get smaller and smaller, causing
them to move increasingly fast. The enemies move horizontally (left or right), until the reach the end of the
window, whereupon they will move one row closer to the player, and then continue moving horizontally in
the opposite direction (if they were moving left in the previous row, they will move right in the subsequent
row), until they again reach the end of the window. Please consult the provided video for an example of
enemy movement. If an enemy touches the player’s ship, the player has lost, and the game ends.
You may choose to implement any of the following optional components: enemies that can shoot back;
attractive and colorful graphics; scoring; a high-score table. Please discuss these options with your instructor.
Getting started We provide you with starter code to help you begin this project. See the file in
starter.zip. This is a starting point; you should replace the pass lines with code to perform the appropriate
actions in strict accordance with the given specifications.
2.3 n-bodies
You will implement a visualization of the classic “n-bodies” problem, a simulation of the effects of gravitation
acting on various objects on a plane. Your program will graphically display the position all bodies in the
system on the turtle canvas.
You will be given a file named bodies.txt containing the initial state of the simulation. The state of
the simulation consists of: the gravitational constant G, as well as the name, position, velocity, and mass
of an arbitrary number of objects. Your program will read this file in and simulate subsequent interactions
between bodies, while displaying graphically a visualization of the simulation. Note that your program must
work with any valid bodies.txt file: you cannot assume the number of bodies, their attributes, or their
relationships. Here is an example file:
.00005
Sun 500 500 0 0 100000000
Splat 255 255 2 0 1
Arg 745 745 -2 0 2
Magnavolt 270 740 -1.5 -3 12000
Spatula 253 450 0 -2 50000
Smoo 500 0 3 0 1000000
Volt 504 0 4 4 0.000001
The first line contains a value for G, the gravitational constant. In the real universe, G is always
6.67384 × 1011m3kg, but in our simulation, it can be anything. Its magnitude is given as the first
line in the input file.
The subsequent lines contain information about each body. Each line gives:
The body’s name (a str).
The body’s initial horizontal position (a float).
The body’s initial vertical position (a float).
The body’s initial horizontal velocity (a float).
The body’s initial vertical velocity (a float).
The body’s mass (a float).
3So, in the above file, the sun is the most massive object in the universe and it is not moving initially.
The heart of the simulation is the calculation of the forces acting on each body. Given a body located at
position x1, y1 and a body located at x2, y2, the distance between them is
The horizontal distance between the bodies is |x1 x2|, and the vertical distance between them is |y1 y2|.
The gravitational force F between two bodies is
where
G is the gravitational constant
M1 is the mass of the first body
M2 is the mass of the second body
d is the distance between the two bodies
We will focus on a two-dimension simulation. Therefore we are interested in the horizontal force (Fx)
and vertical force (Fy) on each body. These are given as:
Fx = G
M1 × M2 × dx
d
3
Fy = G
M1 × M2 × dy
d
3
where dx and dy are the horizontal and vertical distance between the bodies, respectively.
Recall that there is gravitational force between all objects in the universe. In particular, every object
exerts gravitational force on every other object. The net force on a body is the sum of all forces on it. In the
case of our simulation, this means the sum of the gravitational forces between a body and all other bodies
in the simulation.
The acceleration of a body is given by a = F/m where
F is the net force acting on that body
m is the mass of that body.
Similarly, the horizontal and vertical accelerations are given by ax = Fx/m and ay = Fy/m.
At every frame of the animation, the velocity of each body must be updated, based on its current
acceleration. In this program, the implicit units of the acceleration are in pixels per frame per frame. Thus,
if the horizontal acceleration of a body is 3, then its horizontal velocity will be increased by 3 every frame.
In other words: velocity is the integral of acceleration.
At every frame of the animation, the position of each body must be updated, based on its current velocity.
In this program, the implicit units of the velocity are in pixels per frame. Thus, if the horizontal velocity of
a body is 3, then its horizontal position will be increased by 3 pixels every frame. Likewise, if its vertical
velocity is -1, its vertical position will be decreased by 1 pixel every frame. In other words: position is the
integral of velocity.
Getting started We provide you with starter code to help you begin this project. See the file in
starter.zip. This is a starting point; you should replace the pass lines with code to perform the appropriate
actions in strict accordance with the given specifications.
If you’ve got a working prototype of your project, ask your professor for additional versions of bodies.txt
that you can use to test your program.
42.4 Automatic iris classification
In this project, you will write a program that can automatically classify an iris plant into one of three species,
using machine learning techniques. The program will display its results in a graph on the turtle canvas.
The three species of iris plants observed are iris setosa, iris veriscolor, and iris virginica. Flowers of
iris setosa tend to be larger than flowers of iris veriscolor or iris virginica. If the length and width of the
petals of a number of iris flowers are measured and the species of these flowers is known, we can use this
information about known iris flowers of each species to attempt to classify an unknown flower based on
the size and width of its petals. This technique is called supervised machine learning. Supervised learning
requires a number of examples of iris flowers from the three species with known measurements of the length
and width of their petals. (In contrast, an unsupervised machine learning program might group like flowers
together, but it wouldn’t have any knowledge of which species the flowers actually belonged to.)
For this project, you will be creating a program that classifies an iris flower of unknown species. The
petal size of the flower must be known because the supervised learning program will match this information
to known flowers. In writing this program, some portion of the data for which the species, the petal length,
and the petal width are known will act as the training set. When the program is presented with a new flower
to classify, the program will find the most similar flower from the training set and classify the instance in
the same way as the known similar instance. This method of making predictions is known as the nearest
neighbor algorithm.
Though you might suspect that the nearest neighbor algorithm will make good predictions for the species
of an iris flower based on the measurements of petals, you need to test your program to see if it does.
The portion of the data that wasn’t used in the training set will be used to test the feasibility of making
this prediction based on your information. We will call this portion of data the test set. We do know
the species of the flowers in the test set, but we will ignore this fact in testing. Instead, your program
should classify the flowers in the test set based solely on their observed petal size. You will then compare
your program’s conclusion to the plant’s known species to determine the effectiveness of your program’s
classification strategy. If your program provides reasonable accuracy on this test set, you can be confident
that it can predict the species of iris given the petal size. It is important that when you test your program
using the test set, the program is given new examples of flowers that it has not seen before; in this way, we
simulate using your program on data for which the species is really unknown.
We provide two data files: iris_train.csv (the training set) and iris_test.csv (the test set). These
data files contain measurements for individual iris flowers and the corresponding type of each iris plant. 1
Both files are in CSV format; open them in a text editor to see how their content is represented. Each line in
the file contains a single observation about a particular plant. In particular, the first two comma-spearated
columns in the dataset contain the petal length of the flower (in cm); and the petal width of flower (in cm).
Each of these observable attributes (petal length and petal width) is called a feature. The last column in
the dataset gives the type of iris, either Iris-setosa, Iris-versicolor or Iris-virginica. This column is called
the label.
You will use the file iris_train.csv to build a predictive model. You will test your model on the file
iris_test.csv and determine the accuracy of your model. You can only use modules from the standard
distribution of Python in this project, and specifically the numpy and pandas modules are prohibited. Starter
code has been provided for you. We provide function headers and signatures for you; it’s your task to complete
the function bodies.
In the steps below, we walk you through the process of completing each function body in order. Make
sure that you understand what each function should do before you write code for it. Before moving on to
the next step, test your code thoroughly. Do not modify the main function.
1. Fill in the code for the function create_table which has been given. In order to do so, read the file
iris_train.csv into a tuple containing two lists of type float and one list of type string. The
1This project uses the Iris Data Set, which was referenced in R.A. Fisher’s 1936 paper detailing statistical methods to classify
an iris plant. You can read more about the dataset in the UCI Machine Learning Repository here: https://archive.ics.uci.
edu/ml/datasets/iris. The dataset has been edited for use in this project.
5features of the dataset should be of type float and the label should be of type string.
2. Complete the code for the function print_range_max_min which has been given. Notice that the
features of the dataset are both given in centimeters. Measure the range of each feature. This will
require you to find the min and the max of each column in your dataset. Print your resulting min, max
and range as shown. You will print your calculated values in place of the xxx.
Feature 1 - min: xxx max: xxx range: xxx
Feature 2 - min: xxx max: xxx range: xxx
3. You will use the numerical values of each feature to make your predictions. If you use the values as
they are, the features with higher values or a greater range might be given more importance in the
model. To avoid this effect, you will normalize each of your features. This means that you will rescale
all the values in a particular feature in terms of a mean of 0 and a standard deviation of 1. In order
to normalize your features, find the mean and the standard deviation. Fill in the code for the given
functions find_mean and find_std_dev. The formula for standard deviation is:
where σ is the standard deviation, μ is the mean and N is the number of values in the feature. The
syntax xi
indicates the i-th value of a particular feature.
Print the mean and standard deviation for each feature as shown. Your calculated values should be
printed in place of the xxx.
Feature 1 - mean: xxx std dev: xxx
Feature 2 - mean: xxx std dev: xxx
Determine the new normalized value, xi
′
, for each value, xi
, in a feature by as shown below. Implement
this functionality in the given function normalize_data.
Do this for all of the values in each feature. Check that you have correctly normalized the features
by testing again for their mean and standard deviation. The output of your function normalize_data
should now look at follows:
Feature 1 - mean: xxx std dev: xxx
Feature 1 after normalization - mean: xxx std dev: xxx
Feature 2 - mean: xxx std dev: xxx
Feature 2 after normalization - mean: xxx std dev: xxx
After normalization, each of your features should display a mean of 0 or very close to 0 and a standard
deviation of 1 or very close to 1.
4. You will use an algorithm called k-Nearest Neighbors to predict the type for each iris observation in
the test set. The test set is the file called iris_test.csv. In its simplest implementation, when k =
1, the k-Nearest Neighbors algorithm finds the observation in the training set that is ‘closest’ to the
observation you are trying to make a prediction for and uses the known label of the closest observation
as the prediction value. In order to find the observation that is ‘closest,’ you can think about each
6of the training set observations as a point on a two-dimensional plane. For example, an observation
will be plotted as (x, y), where x is equal to the value of feature 1 (petal length) and y is equal to
the value of feature 2 (petal width). In order to find the ‘nearest neighbor,’ you will calculate the
Euclidean distance between the point in the test set that you are trying to label and all of the points
in the training set. For this project, you will be implementing k-Nearest Neighbors with two features
and with k = 1, but the algorithm can be implemented in other ways. 2
Notice that the main function makes a second call to the create_table function, passing it the file
iris_test.csv. The program reads in the iris_test.csv file and stores the data in a two-dimensional
list called test_data. If you examine the test_data table, you’ll notice that this file also contains
labels for each observation. You will give a predicted label using the k-Nearest Neighbors algorithm as
described and then compare your prediction to the actual label. You will be measuring your error for
all of the observations in the test set.
The data in the test set also needs to be normalized. Notice that the main function makes a second
call to normalize_data, passing it test_data.
Now that the test data is prepared, make a prediction for each observation in the test dataset. Implement
this task in the function make_predictions which has been given. For each observation in
the test set, you’ll need to check all of the observations in the training set to see which is the ‘nearest
neighbor.’ Fill in the code for the find_dist function which has been given. The make_predictions
function should make a call to find_dist. Test your find_dist function independently to make sure
it is working properly. Use the formula for Euclidean distance between two points (x1, y1) and (x2, y2):
Your make_predictions function should accumulate a list of predicted iris types for each of the test
set observations. The function will return this prediction list.
5. Determine the error of your predictions. Implement this task in the given function find_error. You
will need to check the prediction list against the actual labels for the test set to determine how many
errors were made. Return a percentage of how many observations in the test set were predicted
incorrectly. Print the error percentage as shown:
The error percentage is: xxx
In practice (though not as part of this project), after you were confident that you could predict for
your test set with good accuracy, you would use your model to make predictions for observations for
which you did not know the label.
6. You will be using the turtle module to visualize the results of your analysis. See the sample plot for
reference. In order to create your plot, fill in the code for the plot_data function. First, set the turtle
window size to 500 x 500. Then draw the x and y axes in the window. Label your axes as shown in
the sample plot.
Plot each observation from your training set on the plane, using a circle shape and a different color
for each type of iris. Use the value of the first feature for the x-coordinate and the value of the second
feature for the y-coordinate. You can use a dot size of 10. Recall that the features have been normalized
to have a mean of 0 and a standard deviation of 1. You will need to ‘stretch’ your features across the
2While it is beyond the scope of this project, the k-Nearest Neighbors algorithm can be used with more than two features.
In this case, you can think about the values being plotted in an n-dimensional space with n being the number of features. Also,
rather than consulting just one ‘nearest neighbor,’ the algorithm can find any number of ‘nearest neighbors.’ You can specify,
k, as the number of nearest neighbors to find. In this case, the prediction would be for the majority class from the surrounding
nearest neighbors.
7Figure 1: Sample Plot of Results
axes to make the best use of the 500 x 500 window. Ensure that none of your points are plotted off
screen.
Also plot each correct prediction from your test set in the corresponding color. Use a square to indicate
that the value is a prediction. Plot the incorrect predictions that were made for the test set in red,
also using a square to indicate that it was a prediction.
Include a key in the upper left corner of the plot as shown in the sample plot. Fill in the code for the
function draw_key to implement this task. Your function plot_data will make a call to the function
draw_key.
2.5 Tic Tac Toe
You will implement a version of the classic “tic-tac-toe” game (also known as “noughts and crosses”), in
which the player competes against the computer to create a three-in-a-row pattern in vertical, horizontal, or
diagonal directions.
The user interacts with the game on the turtle canvas. The game is played in a 3-by-3 grid, which is
initially empty. There are two players, the human and the computer, who take turns. The human always
moves first. When it’s the human’s turn, he or she may place an “O” symbol in any empty position on the
game grid by clicking on the grid position with the mouse; afterwards, it becomes the computer’s move, and
the computer will place a “X” symbol in any empty position on the grid. The players continue to alternate
moves until the game ends. The game is over when any of the following conditions occurs:
there are three “O” symbols in a line in any row or column, or diagonally from corner to corner, which
means that the human has won
there are three “X” symbols in a line in any row or column, or diagonally from corner to corner, which
means that the computer has won
there are no empty positions on the board, meaning that no further moves are possible, and the game
ends in a stalemate
As part of this project, you must develop a reasonable (but simple) “artificial intelligence” to dictate
the behavior of the computer player. Although you may provide a more advanced algorithm (which your
professor will help you develop, if you ask), at a minimum, you must implement the following logic for the
computer player:
8 If it’s possible for the computer player to win in the current move (i.e. there are two “X”s and one
empty position in a line somewhere on the board), the computer player must win by occupying that
empty position.
If it’s possible for the human player to win on the next move (i.e. there are two “O”s and one empty
position in a line somewhere on the board), the computer player must prevent the human’s win by
occupying that empty position.
If neither of the above cases apply, the computer may randomly occupy any unoccupied position.
Getting started We provide you with starter code to help you begin this project. See the file in
starter.zip. This is a starting point; you should replace the pass lines with code to perform the appropriate
actions in strict accordance with the given specifications.
2.6 Something else
Besides the above projects, you may pursue another project of your own choosing. You may choose a project
relevant to your field of study: for example, if you study biology, you might want to look into a project
involving DNA sequencing; of if you study art, you can develop a program for generating computer art. You
may also propose a project relevant to your hobbies or interests. Your project must be of an appropriate
level of difficulty; must demonstrate an understanding of the techniques taught in this course; and must
solve an interesting problem or address a particular need. In all cases, your project must be approved by
your professor.
The steps for doing a project of your own design are as follows:
1. First, you should discuss your idea with your professor in person as soon as possible. Give an “elevator
pitch”: a summary, in a few sentences, of what your program will be. Your professor will be able to
let you know if it’s an appropriate project idea.
2. If your professor approves your verbal elevator pitch, you must submit a written proposal to your
professor by email. The proposal is much more detailed, and needs to describe exactly what your
program will do. Your professor will be looking for a proposal that demonstrates that you have
thought through the problem and have anticipated the challenges involved.
Your proposal represents a contract with your professor, describing exactly what you intend to create.
It must thoroughly cover all aspects of the behavior of your program. It should be at least as detailed
as the descriptions given above for the other projects. Your description of your program should include:
What is the purpose of the program? What problem is it solving?
What does the program look like? You may provide drawings of the proposed user interface as
illustrations.
How does the user interact with the program? What input is expected from the user? What
output is given to the user?
How does your program behave? Describe in detail a typical use of your program, from beginning
to end.
What errors can arise while your program is running? For example, what will happen if the user
provides unexpected or invalid input? Describe how your program will handle these cases.
Your proposal should be sufficiently detailed so that any competent programmer should be able to
implement your proposed project solely on the basis of your written proposal. However, the proposal
should not include any implementation details: you do not need to discuss functions, variables, or
anything else related to actually writing the code.
9Your professor may give you feedback about your proposal. For example, your proposal may need more
detail or a change in scope before it can be approved.
Insofar as your finished project diverges from your project proposal, any differences must be cleared
with your professor well in advance of the due date.
3. Once your written proposal has been approved by your professor, you are required to meet again with
your professor. At this meeting, you will discuss implementation, i.e. the strategy for converting your
written proposal into actual code. Your professor may have helpful suggestions for how to structure
your code.
4. At this point you may begin coding your project.
5. At the time of the status report, you must present your work so far to your professor, not to a TA.
Please bear in mind that implementing your own project typically requires significantly more work
than one of the default projects, because you won’t have the benefit of the starter code. In addition, it
requires more communication with your professor, to make sure that your development is continuing
in the right direction and that your code meets the required standards. It is your responsibility to
schedule meetings with your professor in furtherance of these goals.
3 Important information
Now that you’ve selected a project, let’s talk about the rules for completing it and how you can ensure a
successful project.
3.1 Rules
Before you start your project, you should prepare by reading this document thoroughly. In it, you will find
rules that you will need to take into account. Be aware that failure to consider these rules will result in a
penalty.
Your professor has provided a starting framework to help you get started. For the projects proposed
above, find the corresponding starting framework in starter.zip. You are welcome to make use of
these files to help you develop your project. If you are developing a different project, you may still
benefit from reading or adapting the starter code.
Please note that the code provided in the starting frameworks is designed to help you, but that does
not absolve you of the necessity to understand the code contained therein. Before you start writing
new code, you should make sure that you understand the structure of the code provided for you,
what it does, and exactly what remains to be done. Read the comments carefully: they tell you
exactly what your code should do. If you have any doubts, contact your professor. Many students
wasted time writing wrong code because they failed to thoroughly read and understand the framework.
Everything you need to know in order to complete the project has been covered in class; if you find
yourself consulting outside