Author: cs daixie

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 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
3. Submit your zip le containing your solution to Moodle.
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:
Task 1: 10 marks
(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
Task 2: 15 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
your own game.
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,
unlimited subscription if you register your Wits email with them. This gives you access to private
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
1. Go to https://bitbucket.org and sign up for a free account. Either signup using
your Wits email address, or signup with your own address and then add your Wits to your
prole under Manage Account — Email Addresses.
(a) Select a “Personal Account”
(b) Follow the process to prove that you’re not a robot.
(c) Conrm your email address by clicking on the link in the email that was sent to you.
2. Once you’ve added and veried your Wits email address visit the BitBucket Academic Li-
cense Page3 to convert your account to an unlimited academic license.

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.

hotel booking system

Assignment 1
Aims:
Pr#ctice how to #pply # system#tic object-oriented design process
G#in experience in implementing #n object-oriented progr#m with multiple
inter#cting cl#sses
Le#rn more #bout the J#v# cl#ss libr#ries
Due D.te:Week 4, Sund#y, August 19, 11E59 pm
V.lue:10%
Hotel Booking System
In this #ssignment, you will implement # prototype system th#t could serve #s the
“b#ck-end” of # hotel reserv#tion system (im#gine wotif.com). Customers c#n
m#ke, ch#nge #nd c#ncel bookings. A hotel consists of # set of numbered rooms:
e#ch room is either # single, double or triple room (so h#s c#p#city 1, 2 or 3). A
booking is m#de under # n#me #nd consists of one or more room requests for #
number of rooms of # cert#in type (e.g. two single rooms #nd one double room)
for # period of time given by #n #rriv#l d#te #nd # number of nights (#ssume #ll
bookings #re for 2018). A request is either gr#nted in full or is completely rejected
by the system (# request c#nnot be p#rti#lly fulfilled).
Assessment will be b#sed on the design of your progr#m in #ddition to
correctness. You should submit #t le#st # UML cl#ss di#gr#m used for the design
of your progr#m, i.e. not gener#ted from code #fterw#rds.
Allinput will be # sequence of lines of the following form, #nd #ll hotel rooms will
be decl#red before #ny other comm#nds #re issued (you #re not required to
h#ndle #ny inv#lidly form#tted input):
Hotel <hoteln.me> <roomnumber> <c.p.city>
# specify th.t hotel with <hoteln.me> h.s . room with

java swing

1. Submission and Grading Instructions
1.1 Final Code
The project must be named (in Eclipse) with the following format
LabNumber_FirstName_LastName_AssignmentNumber _FInal_StudentNumber, e.g.
D104_Jim_Silvester_Assignment4_Final_1234567
For the code the entire project MUST be submitted (not just the source files)
To submit, export the project (including all the libraries used) into a zip file (Archive
File) and name it exactly the same as the project name
(Please note failure to meet any of these submission requirements above would
result in a penalty of 0.25 pt each)
No late submission will be accepted. If you do not complete the assignment by the
deadline, you will receive 0. For a legitimate reason a late submission might be allowed
pending discussion with your TA before the deadline. You may be required to provide
supporting documents.
For the coding, make sure your code is syntax error free so that it runs properly on the lab
machine. You would receive for the assignment if your code failed to run due to either
syntax errors or runtime exception.
Grading for Milestone 1: Will be done by a quick demo to TA during week 13 lab – make
sure you attend to get marks.
2. Overview of the Assignment
A4 Big picture: You will continue working on your simulation from and Assignment
4 Milestone 2.
You will learn how to build user interface using Java Swing components, and how to
control functionality of your program via UI. You will also expand on the
functionality of the simulation by enriching its content with more media types (e.g.
irregular, complex shapes, images, audio etc.), more intelligent features (e.g. sorting
and search), and some more advanced concepts (e.g. exception handling, design
patterns etc.)
This final assignment will go three iterations: milestone 1 (one week), milestone 2
(one week), and final code (two weeks).
2.1
Learning objectives for Milestone 2
By doing this assignment you will learn how to:
Use packages to organize code properly
Create objects using factory pattern
Add features dynamically using decorator
Create custom irregular shapes
Add sound effects to the simulation world
2.2. Programming Requirements
In the final code, you will make your simulation rich in application of multimedia, must
include texts, custom shapes, sound effects, and more importantly interesting micro-
animations (e.g. wing flapping, tail wiggling, leg alternating etc.) and sensible
interactions that are appropriate in the environment.
I. Coding requirements
1) At least 4 named packages (
default package is NOT allowed) that group your
classes properly (e.g.
main, garden, pond … – create descriptive packages that
fits to the theme of your own application)
2) Follows strict naming convention for package (please note it’s different from
the rest constructs), classes, methods and variables
3) For major objects including preys and predators must be created using
factory pattern (no abstract class is required though)
4) Code must be refactored to have NO redundant code, esp. between
superclasses and subclasses, there should be no redundant fields and/or
methods that are the same or serve exactly the same functionalities
5) Use try-catch to handle potential runtime error, mainly NullPointerException
and IndexOutOfBoundsException. Please note if a runtime error as such