Month: August 2018

Algorithmic Problem Solving

Posted on by cs daixie
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 1 gives an 4 × 4 magic square and Table 2 gives a partial magic square.

Intro. to Data Structures & Algorithms

Posted on by cs daixie
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

Posted on by cs daixie
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

Posted on by cs daixie

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

Posted on by cs daixie
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

Posted on by cs daixie
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 0 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