Month: September 2018

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:
Please enter a string: sourpuss
Please enter a key: 2
The encrypted string is: uqwtrwuu
Please enter a string: uqwtrwuu
Please enter a key: -2
The decrypted string is: sourpuss
Please enter a string: zany
Please enter a number: 6
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 %.
For the output, you want your message to start with “The encrypted string is: ” if
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
Threads
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.
The multi-threaded server may implement a thread-per-request, thread-per-connection, or
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
your own.
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.
Network communication (address not reachable, bad data…).
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
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:
Input: Word to add, meaning(s)
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?w?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?w?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?w?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?w?in the population do:
Pick three distinct individuals?a,?b?and?c?from the current population at random. The
individuals?a,?b?and?c?must be distinct from?w?as well.
Create a?mutant?vector?a?+?mut?* (b?–?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?w?by the
trial?vector
In other words, for each individual?w?in the current population, we create a challenger?trial?vector.
If this challenger is better than?w, then?w?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.