# Homework 3

Instructions:
You are expected to solve the problems in the easier section on your own. For the harder section you are expected to
think about a problem alone for at least 24 hours before discussing it with others. Discussions are meant to help you
understand the problem better. You should not ask someone for solutions. If we nd evidence of cheating then you
will be reported to the university and could be subject to disciplinary action. Be prepared to come and explain your
solution to us in person if we feel the need. You can discuss the harder section in groups of 1, 2 or 3. In the end you
must write up your own solution and write names and RUIDs of students you collaborated with. For each problem,
The name of the le should be your netid. Late homeworks will not be accepted.
In this homework whenever the problem mentions a string s of length n, you can assume that each of the n
characters is one of the 26 lowercase alphabets. If the problem mentions a bit string of length n, then each character is
either 0 or 1.
1
Easy Questions. 5 points each.
For each of the problems in the easy section it is enough to describe in English the idea of your algorithm, dene the
memo table, write the base case and the recursive step to ll the table, and analyze the run time. No need for pseudo
code.
Given a string s of length n, design an algorithm that outputs the smallest number k such that s = w1w. . . wk
where each wis a palindrome. In other words, nd the smallest k such that s can be written as a concatenation
of k palindromes. For the denition of a palindrome see practice problems. For example if s = “add” then the
algorithm should output k = 2 since we can take w=“a” and w=“dd”. On the other hand, if s = “ada”, then
the algorithm should output k = 1.
Given two strings of length n and m, design an algorithm that outputs the length of the longest common substring
of the two strings. If A[1, . . . n] is the array representing a string, then any contiguous chunk A[i, . . . , j] is a
substring of A.
Given an array A[1, . . . , n] of integers, design a dynamic programming algorithm running in time O(n) to nd
indices i, j such that the subarray A[i, . . . , j] has the maximum sum.
You are given a set of n non-negative integers, and a target integer K. You need to nd out of there exists a
subset of the n integers that adds up to K. Design a dynamic programming algorithm for this problem that runs
in time O(nK).
Given a string of length n, a subsequence is any non empty subset of characters read from left to right. For
example, if A = atc then a, t, c, at, tc, ac, atc are all subsequnces of A. Given two strings of length n, m,
design an algorithm that outputs the length of the longest common subsequence (LCS) of the two strings.
Modify the algorithm for the longest common subsequence (LCS) problem that you designed above such that it
runs in time O(nm) but only uses O(min(n, m)) space.

2
Harder Questions
2.1
Weekend Planning (20 pts)
It’s Friday night and you have n parties to go to. Party i has a start time si, end time t> sand a value v≥ 0. Think
of the value as an indicator of how excited you are about that party. You want to pick a subset of the parties to attend so
that you get maximum total value. The only constraint is that in order to get a value vfrom party i you need to attend
the party from start to nish. Hence you cannot drop in midway and leave before the party ends. This means that if
two parties overlap, you can only attend one of them. For example, if party 1 has a start time of 7pm and ends at 9pm
and party 2 starts at 7:30pm and ends at 10pm, you can only attend one of them. On the other hand, if party 2 starts at
9pm or later then you can attend both. Given as input start times, end times and values of each of the n parties, design
an O(n log n) time algorithm to plan your night optimally. Describe in English the idea of your algorithm. If you use
dynamic programming dene the memo table, base case and recursive steps. You don’t need to write the pseudo code
or provide a proof of correctness.
2.2
Knapsack (20 pts)
In the knapsack problem we have n items, where each item i has an integer value vand an integer price pi, and we
also have a budget of B. The goal is to nd the maximum total value of items that can be picked without exceeding the
budget. In particular, out of all sets of items whose total price is at most B, we want the set of highest total value. In
class, we gave a dynamic programming algorithm to solve this problem whose running time was O(nB). One issue,
though, is that if the prices are large, then O(nB) may not be so good. In this problem, we want you to come up with
an alternative algorithm whose running time is O(nV ), where V is the value of the optimal solution. So, this would be
a better algorithm if the prices are much larger than the values. Describe in English the idea of your algorithm. Dene
the memo table that you will use and write the base case and recursive step needed to ll the table. Finally write the
pseudo code. You don’t need to provide a proof of correctness.
[Note: Your algorithm should work even if V is not known in advance, but you may want to rst assume you are given
V up front and then afterwards gure out how to remove that requirement.]
2.3
How to make money via DP (30 pts)
An option (specically, an “American call option”) gives the holder the right to purchase some underlying asset (e.g.,
one share of IBM) at some specied exercise price (e.g., \$200) within some specied time period (e.g., 1 year). For
instance, if the price of IBM went up to \$212 in this period, you could exercise the option and then sell the stock,
making \$12 (or you could keep the option, hoping the price will increase further before the option expires).
If you have a probabilistic model for how a stock will behave, then this gives you a well dened notion of the value
of a given option: the expected prot for having the option if you were to follow the optimal strategy for deciding
when to exercise it under that model.
For example, to take an easy case, suppose we have an option to buy one share of IBM at \$200 that expires right
now. If IBM is currently going for \$210, then the value of this option is \$10. If IBM is currently going for \$190, then
the value of this option is 0 (we wouldn’t want to exercise it). However, suppose the option expires tomorrow, and
suppose our model says that each day, with probability 1/4 the share price goes up by \$20, and with probability 3/4
the share price goes down by \$10 . In that case, if IBM is currently worth \$190, then the value of this option is \$2.50
because that is our expected gain if we use the optimal strategy “wait until tomorrow, and then exercise the option if
IBM went up” (our expected gain under this strategy would be
1
× 10 +
3
× 0). If IBM is currently worth \$210, then
the value of the option is \$10 (because if you work it out, our optimal strategy in this case is to exercise the option
right away).
Formally, the value of an option is the expected prot it will produce under the optimal strategy for using the
option, given our probabilistic model for the stock. Note that the optimal strategy need not commit in advance to what
day the option will be exercised: the date it gets exercised (if ever) may depend on how the stock has performed so

# A Day at the Random Races

Objectives
In completing this project you will gain experience with the following Java features:
MVC architecture
ArrayLists
building GUI with various components
listeners, event driven GUI elements
delay loops
Problem Statement
For this project we are going to simulate a horse race. Our horses, or perhaps their jockeys, are
a bit peculiar. When racing, each horse moves either one unit forward or one unit backwards
with each stride. The probability of the forward stride (‘fitness’) is the same for all horses. In
order to avoid an inordinate long race the probability shall be chosen by you between 0.55 and
0.6. A more sophisticated program may allow individual fitness selections for the horses. If we
set the fitness to 0.5 it would follow that if a horse is, say 20 units down the track, about half the
time it ends up 19 units, and about half the time 21 units down the track. If the fitness is greater
than 0.5, then the horse makes forward strides more likely than backwards, a good chance that
all horses finish the race within a reasonable short time. The setup sure makes for an
interesting, and sometimes still very long, race.
The user is allowed to configure the race track by specifying the number of tracks (1-12) which
is also the number of horses running in the given race. The length of the track is a preselected
value, recommended choice is 25.

We will simulate the race by keeping track of how far each horse has galloped down the track.
The program provides a graphical display of the race, horse positions are continually updated
and displayed on the race GUI. At the start of the race each horse is at the starting gate (a
distance of 0). During each step we will simulate each horse making one random stride and we
update its distance. We will not allow any horse to stride backwards from the starting gate.
Whenever a horse finishes the race, meaning that the distance down the track is equal to the
pre-set track length, we will no longer generate a random stride for that horse neither shall we
update its distance. In addition to keeping track of where each horse is on the track, we will also
maintain the number of strides taken and the placement in order of finish.
When all horses have crossed the finish line the race ends, and the final results, the finishing
placement and the number of strides can be read on the race GUI. An independent score board
showing the same outcomes is optional.
The required visual representations of the race at developing phases are shown on Figures 1

# HAIL CAESAR

A Caesar cipher is a simple substitution cipher based on the idea of shifting each letter
of the plaintext message a xed number (called the key) of positions in the alphabet. For
example, if the key value is 2, the word “sourpuss” would be encoded as “uqwtrwuu” The
original message can be recovered by ”reencoding” it using the negative of the key. Write a
program that can encode and decode Caesar ciphers. If encoding, the input to the program
will be a string of plaintext and the value of the key. If decoding, the input to the program
will be encoded text and the key value will be the negative of the original key.
Here are some sample runs of the program:
The encrypted string is: uqwtrwuu
The decrypted string is: sourpuss
The encrypted string is: fgte
Here are some hints and notes:
You can assume that all the letters used are lower case.
if ch is a character in the string and key is the amount to shift, then the character
that replaces ch can be calculated as: chr (ord (ch) + key).
One additional case to worry about is when we ”drop o the end” of the alphabet.
A true Caesar cipher does the shifting in a circular fashion where the next character
after ”z” is ”a.” You can make your solution circular by doing some arithmetic and
using the modulus operator %.
the key is positive and with “The decrypted string is: ” if the key is negative. One
way to this is to use the following snippet:
s = “The encrypted string is:
” if key > 0 else “The
decrypted string is:

# Simplicity, Correctness, Style

EXAMPLE
What is the simplest way to print a text bar chart? Look at these two versions for input 3, 2, 5, 1
Version 1
Version 2
*
***
*
**
* *
*****
***
*
****
Issues to consider:
Reading in the input data set
o
What would be easiest for a user? Input text file? Keyboard input? One-line input?
The control structure (algorithm)
o
The fewer loops and ifs the better. The least convoluted the better.
The ease of testing (validation)
o
What would be easiest for testing? Text file? Keyboard? File redirection? Other?
What would be the optimal compromise?
Algorithm for version 1 output:
Algorithm for version 2 output:
// assume int array[] = {3,2,5,1};
// assume int array[] = {3,2,5,1};
for(i=0; i<array.length; i++) {
max=0;
for(j=0; j<array[i]; j++) printf(“*”);
for(i=0; i<array.length; i++) if (array[i]>max) max=array[i];
println();
for(i=0; i<array.length; i++, max–)
}
for(j=0; j<array.length; j++) {
if (array[j]>=max) printf(“*”);
else printf(“ “);
}
Notice that in the above algorithms to print the vertical bar chart we must also print blank spaces. For example, the bar
of 5 stars is in the third column. We need to print spaces for the first two columns before printing the top star. The
version 2 output requires us to think in a 2D grid. The version 1 algorithm does not have this 2D grid requirement. We
can simply print starts horizontally and then go to the next line of stars. When looking at the sample pseudo-code, we
can see that version 1 is easier to understand, and shorter.
Unless there is a requirement by the product owner that they want a vertical bar chart, then version 1 would be the
simplest to develop, understand, maintain, write documentation and test.

PROBLEM 1
In the “Issues to consider” section of the example there are two items that are dependent on each other: “Reading in
the input data set” and “The ease of testing”. They are related because they both deal with giving the program a data
set. In one case the user is providing the real data set, and in the second case the developer is providing many test data
sets to validate the algorithm. A good program makes it easy to do both. The use-case is however different. The user
will probably want to input only 1 or 2 data sets. The developer will want to input 100 data sets. The order of
magnitude is different.
What would be the simplest way that ensures ease of use and correctness?
PROBLEM 2
Write the complete optimal program using a professional writing style.

# Distributed Systems

Problem Description
Using a client-server architecture, design and implement a multi-threaded server that allows concurrent
clients to search the meaning(s) of a word, add a new word, and remove an existing word.
This assignment has been designed to demonstrate the use of two fundamental technologies that have
been discussed during the lectures:
Sockets
Hence, the assignment must make an EXPLICIT use of the two above. By explicit, we mean that in your
application, sockets and threads must be the lowest level of abstraction for network communication and
concurrency.
Architecture
The system will follow a client-server architecture in which multiple clients can connect to a
(single) multi-threaded server and perform operations concurrently.
worker pool architecture. This is a design decision for you to make.
Interaction
All communication will take place via sockets. These sockets can be either TCP or UDP, however,
keep in mind that all communication between clients and server is required to be reliable.
You are responsible for designing your own message exchange protocol. Some data formats
that you may use include XML, JSON, Java Object Serialization, or you may choose to design
Failure Model
All communication between components has to be reliable. If you are using TCP, then the
reliability guarantees offered by the protocol are sufficient. If you decide to use UDP, then you
have to implement an infrastructure that offers reliable communication over UDP. For those of
you with previous experience using TCP, using UDP may be a rewarding challenge.

It is expected that, on both the server and the client side, errors (by means of exception
handling) are properly managed. The errors include the following:
Input from the console for what concerns the parameters passed as command line.
I/O to and from disk (cannot find the dictionary file, error reading the file, etc…).
Other errors you might come up with.
The application will be tested and validated against all these errors.
Functional Requirements
Query the meaning(s) of a given word
The client should implement a function that is used to query the dictionary with the following
minimum (additional input/output parameters can be used as required) input and output:
Input: Word to search
Output: Meaning(s) of the word
Error: The client should clearly indicate if the word was not found or if an error occurred. In
case of an error, a suitable description of the error should be given to the user.
Add a new word and one or more of its meanings to the dictionary. For the word to be added
successfully it should not exist already in the dictionary. Also, attempting to add a word without
an associated meaning should result in an error. A new word added by one client should be
visible to all other clients of the dictionary server. The minimum input and output parameters
are as follows:
Output: Status of the operation (e.g., success, duplicate)
Error: The user should be informed if any errors occurred while performing the operation.
Remove an existing word
Remove a word and all of its associated meanings from the dictionary. A word deleted by one
client should not be visible to any of the clients of the dictionary server. If the word does not
exist in the dictionary then no action should be taken. The minimum input and output
parameters are as follows:
Input: Word to remove

# Differential Evolution for Hyperparameter Search

Quick Overview
You will implement a simple generic Differential Evolution search
You will apply this generic algorithm to two problems
You are provided with scaffolding code that you will need to complete
You will also perform experiments and report on your results
Introduction
In machine learning, a hyperparameter is a parameter whose value is set before the learning process
begins. By contrast, the values of other parameters like the weights of a neural network are derived
via training. Examples of hyperparameters for neural networks include the number of layers, the
number of neurons in each layer and the learning rate.
Different training algorithms require different hyperparameters. Some simple algorithms (such as
ordinary least squares regression) require none. The optimal values for the hyperparameters depend
also on the dataset. In this assignment, you will implement a search algorithm to find good values
for a small set of hyperparameters of a neural network.
Differential Evolution (DE) is an efficient and high performing optimizer for real-valued functions.
DE is the search technique that you are required to use in this assignment to solve the optimization
problems. As DE is based on evolutionary computing, it performs well on multi-modal,
discontinuous optimization landscapes. Another appealing feature of DE is that it is still applicable
even if the function we try to optimize is not differentiable. This is often the case when some
simulation is involved in the computation of the real-valued function being optimized. In these
scenarios, a gradient descent approach is not applicable. DE performs a parallel search over a
population of fixed size, where each population member is a higher dimensional vector.
In this assignment, the core problem is to adapt DE to perform a search for four hyperparameters of
a neural network. In the next section, we describe in more details DE.
Differential Evolution
Let f(w) be the cost function which must be minimized. Note that maximization can be performed
by considering the function -f . The function f(w) takes a candidate solution as argument in the form
of a vector w of real numbers and produces a real number as output which indicates the cost of the

There exist many variations of the DE algorithm. The variation that you have to implement has
been chosen for its simplicity. In the rest of this section, variable names written in blue italic
correspond to Python program variables used in the provided scaffolding code.
We constrain the search by specifying bounds for each component of with a list of pairs called
bounds in the scaffolding code. That is, we impose
bounds[k][0] <= w[k] <= bounds[k][1]
for k in range(len(w))
For example, if bounds is [(1,100),(1,100),(-6,2),(-6,1)] , then w[1] is constrained to the interval
[1, 100] and w[2] is constrained to the interval [-6, 2].
To make the code generic, we normalize each component of to the interval [0, 1] by mapping
with an affine function the interval [ bounds[k][0], bounds[k][1] ] to the interval [0, 1].
We first initialize all individuals of the initial population with random points from the search-
space.
Until a termination criterion is met (maximum number of iterations/generations done, or acceptable
cost is reached), we repeat the following loop:
For each individual in the population do:
Pick three distinct individuals aand from the current population at random. The
individuals aand must be distinct from as well.
Create a mutant vector mut * (– c) where mut is a constant (passed as an argument to
the differential_evolution function)
Clip the mutant entries to the interval [0, 1]
Create a trial vector by assigning to trial[k] with probability crossp the value mutant[k]
and probability 1-crossp the value of w[k]
Evaluate the cost of the trial vector. If the trial vector is better than w, then replace by the
trial vector
In other words, for each individual in the current population, we create a challenger trial vector.
If this challenger is better than w, then is replaced by the trial vector .
The mutation factor mut with and the crossover constant crossp are numerically defined in the
scaffolding code.
Scaffolding Code
The file “my_submission.py” contains scaffolding code. The key function is differential_evolution.
This function return a generator. You should have seen generators in the Python
tutorial
To validate your implementation of the function differential_evolution, you should first test and
debug it with the function task_1 as it tries to solve a simpler problem than task_2.
In Task 1, you fit a polynomial to a noisy dataset. This is the same problem as you have seen in the
early pracs where you solve this problem with the pseudo-inverse and a gradient descent approach.

# Algorithmic Problem Solving

Objectives
The objectives of this assignment are:
To demonstrate the ability to implement algorithms using basic data structures and operations on them.
To gain experience in designing an algorithm for a given problem description and implementing that
algorithm in Python.
Submission Procedure
1. Put you name and student ID on each page of your solution.
2. Save your les into a zip le called yourFirstName yourLastName.zip
4. Your assignment will not be accepted unless it is a readable zip le.
Important Note:
Please ensure that you have read and understood the university’s policies on plagiarism
will be required to agree to these policies when you submit your assignment.
Marks:
This assignment has a total of 25 marks and contributes to 5% of your nal mark. Late submission
will have 5% o the total assignment marks per day (including weekends) deducted from your assignment mark.
(In the case of Assignment 1, this means that a late assignment will lose 1.25 marks for each day (including
weekends)). Assignments submitted 7 days after the due date will normally not be accepted.
Marking Guide:
(a) Code readability (Non-trivial comments where necessary and meaningful variable names) – 2 marks
(b) Correct input handling – 2 marks
(c) Correct result – 2 marks
(d) Loop calculates each term correctly – 4 marks
(a) Code readability (Non-trivial comments where necessary and meaningful variable names) – 4 marks
(b) Correct input handling – 4 marks
(c) Checking magic square property – 2 marks
(d) Loop allowing for user input – 2 marks
(e) Checking cell contains 0 – 1 mark
(f) Undoing if value not valid – 2 marks

Task 1: Continued Fractions 10 Marks
Write a Python program that takes as input non-negative integer n and then computes an approximation for
the value of e using the rst n + 1 terms of the continued fraction:
e ≈ 2 +
1
1 +
1
2+
2
3+ 3
For example:
If you entered 2, your program would output 2.7272727272727275 as:
e ≈ 2 +
1
1 +
1
2+ 2
3
and if you entered 3, your program would output 2.7169811320754715 as:
e ≈ 2 +
1
1 +
1
2+
2
3+ 3
4
.
Task 2: Magic Squares 15 Marks
Information:
A magic square is a table with n rows and n columns, such that the numbers in each row, and in each column,
and the numbers in the main diagonals, all add up to the same number which we will refer to as the magic sum.
All entries are distinct. A partial magic square is a magic square that has some entries missing. For example,
Table gives an 4 × 4 magic square and Table gives a partial magic square.

# Intro. to Data Structures & Algorithms

1
Introduction
Pacman is an arcade game developed by Namanco in 1980.
Scan the QR code to the right or visit the link below it to
play the game. This next link will give you some inter-
esting facts about the game: http://goo.gl/hpjtjl.
Throughout this course we will cover many different data
structures and algorithms. As we cover these algorithms,
a series of 3 projects will guide you in implementing the
algorithms to construct a working game of Pacman. The
rst project will focus on C++ revision and cover the
development of functions to help render images on the
screen and animate the characters.

As we cover different structures, you’ll be required to implement and integrate them into the
game. By the time the course is complete, you should have a fully working version of Pacman that
includes intelligence to control the ghosts.
You are encouraged to add to the game and make it your own. If you ever nd that you have too
much free time, I recommend going through SDL Tutorials by Lazy Foo (http://lazyfoo.
). They will give you better insight to the structure of 2D
graphics programming in SDL and will give you an architecture in which you can start creating
While the primary outcome of the course is a thorough knowledge of Data Structures and
Algorithms, you will nd that strong programming skills will assist you throughout your career
in CS. Programming is as much of an art as it is a science. Remember that the only good way to
become a good programmer is to practice. So think of interesting ways to extend your game and
try add them in! Maybe try write your own game of Tetris!

2
Background & Tools
2.1
Git & BitBucket
When working in teams or on large projects you are usually required to use a version control sys-
tem so that everyone knows what version of the code you are editing. These systems then help
you keep track of why a change was made to the code (Commit Message), as well as who made
it (Author). They help you keep track of different changes to the code and if you’re working on
multiple features at the same time, it can be helpful to work on each feature in its own independent
branch
.
Git is a version control system that allows you to track different versions of your code while
programming. Git was developed by Linus Torvalds (the same person who started Linux) and is
used by millions of programmers around the world and depending on who you listen to between
30%1 and 70%2 of professional programmers use it. We will be using basic the basic functionality
of Git in this course.
BitBucket and GitHub are online hosting environments for Git. BitBucket will give you a free,
repositories for your school work. I strongly suggest making use of this.
Git is a command line tool, but there are are plenty of very good and free graphical front ends.
I recommend SmartGIT, which is free for non-commercial use, QGit or Git-Gui.
2.1.1
Exercise
prole under Manage Account — Email Addresses.
(a) Select a “Personal Account”
(b) Follow the process to prove that you’re not a robot.

# maze

Assignment Goal
The goal of this assignment was to write a method that could find a path through a randomly generated
maze. Given that the maze was generated recursively, I felt it was appropriate to make the solver
recursive as well.
Design Process
The biggest issue with the randomly generated mazes was that most of them were unsolvable. That is,
there was no path from the top left corner (defined as always being the starting point) and the bottom
right corner (always the ending point). I placed a special “start” character and an “end” character in the
respective positions, instead of the normal blank. However, I realized that this was not needed as start is
always maze[1][1] (maze[0][0] is the corner of the outer wall), and the end is always
maze[LEVEL_HEIGHT – 2][LEVEL_WIDTH – 2] (subtract 1 for 0 index, and subtract 1 again to get out of
the corner for the outer wall), and so I could check for the ending value, rather than need a special
character. The special character could still be useful if we wanted to allow any position to be the end
point.
The algorithm essentially checks each adjacent position in the matrix in a clockwise fashion.
Base Cases
The first base case is to check if we are at the end of the maze. If we are, we have successfully traversed
the maze. The second is to ensure that we are checking a blank spot. If the current spot is a wall, we
cannot go this way and must back up. If the current spot is marked as part of the path, we are already
considering this spot and must back up, otherwise we may get in a loop of continually checking the same
spot over and over.
Clockwise Recursive Order Checking
If neither base case is true, we mark the current position as part of the path. We then do a recursive call
to the position maze[currentY][currentX + 1], which is the position to our right. If it returns false, we
repeat the call on the spot below us. If that fails, we check the spot to our left, and then above us. In this
way, we check all four possible moves from our current position. If all four fail, we re-mark the current
position as a blank to remove it from the path before returning false.
Testing
First, I ran the provided code without any edits to ensure it compiled.

# python

In this assignment we are using Python concepts taught in weeks 1–5 of the semester. This includes

·expressions, statements, programs, data types, operators and strings,

·built-in functions and methods, such as mathematical functions or string methods,

·control flow, such as making decisions, looping over a range, or advanced looping.

The assignment will be submitted via GROK and assessment will be carried out using GROK test cases. The questions have been entered into GROK and initial test cases provided to get you started. You are encouraged to generate your own test cases and test your code thoroughly to avoid surprises.

For each question, you are asked to write a short Python program. The program for each question will be self-contained and will use the `input()` function to gather information from the user (or the test case), and the `print()` statement to report its results.

Each question gives samples sessions with the program you are to write, giving the input and the required output. Due to the GROK assessment process, your output is required to match the sample exactly, including spacing. You should have practiced this procedure in the week 2–5 labs.

You are not expected to check the input for errors, and nor are you expected to print error messages or throw exceptions. For Assignment 1, the test cases will not contain abnormal inputs. On the other hand, there is no penalty for applying ordinary defensive programming practices.