Month: March 2019

Programming for Scientists and Engineers

Posted on by cs daixie
Problem A: String Overlap (30 points)
In this problem you will design and implement C++ code that identies overlap in strings.
Specically, design and implement a C++ program that does the following:
1. Asks a user to input a lename and then opens that le. If the le open fails, then
print the message “Unable to open le” and terminate the program using exit(1).
2. Reads the le contents, in order, into an array of strings. (See the le format expla-
nation below.)
3. Computes the string overlapping order described below, and then prints the strings
out, one per line, in that order.
4. Closes the le.
File Format: The data le consists of a number of strings, each on its own line. You do
not know in advance how many strings will be in the le, other than there will be no more
than 30 strings. Assume (i) there is at least one string in the le, (ii) the strings do not have
any whitespace in their interior, and (iii) the strings consist entirely of alphabetic, upper
case characters.
Here is an example of a data le containing four strings:
AGGTGTGGA
AAAATTA
AATTGTCGCTGA
GGAAAA
Overlapping Order: Here is the explanation of the string overlapping your program is
to nd in Step (3) above. Suppose we have the strings above read, in order, into an array
of strings. We start with the rst string in the array, AGGTGTGGA. What we want to
determine is which of the other strings’ beginning overlaps the most with the end of the
this rst string. Note this is a nontrivial problem since we do not know without further
analysis what the size of the overlapping substring will be. For example, if we just look
at the last character of AGGTGTGGA, the A, there are two other strings that begin with
A. If we look at the last two characters, GA, there are no strings starting with GA.

Traverse the Maze

Posted on by cs daixie
Objective
This project provides experience of implementing recursive methods and using a generic linked
stack data structure for the purpose of an efficient depth-first search for the longest path in a
special tree structure. You will also review how to construct and use Java classes as well as
obtain experience with software design and testing.
ABET Program Learning Outcomes:
The ability to recognize the need for data structures and choose the appropriate
data structure (1,2,6)
The ability to implement and use stacks (1,2,6)
The ability to implement and use linked list and array based structures (1,2,6)
The Problem
The programming problem in this project is to find a path from the entry cell (upper left corner)
to the exit cell (lower right corner) of a maze. In our model the rectangular maze is represented
by a grid of cells. Each cell is bordered by 4 walls, and some of these walls are passable to the
neighboring cell(s). The outside wall of the whole maze is not passable. There are however (at
least) two very different interpretations of a passable wall. We say that the maze is directed if
for any given pair of cells A and B there are four cases:
– there is no passage between A and B
– each of A or B is accessible from the other
– B is accessible from A, but A is not accessible from B
– A is accessible from B, but B is not accessible from A
On the other hand, in an undirected maze each passage provides a two-way access, that is, there
are only two cases, #1 and #2 as listed above.
In this project your program shall exercise both options of building a maze, moreover in the
directed maze every passage will be selected by a given probability, while the undirected maze
will be built upon a pattern of predetermined passable walls. Your completed program is able to
build a maze based upon input wall pattern read from a file
build a maze with a random selection of all relevant directional passage
find a path through a maze if such a path exists
display the maze solution on the console showing the length of the path and the
locations of the cells along the path from the entry cell to the exit cell
report the failure of the search in an output message

Commandline Console

Posted on by cs daixie
Description
Create a site that provides a web, form-based “Linux Shell” supporting basic commands that can be
performed on a remote “fake” in-memory le system. In this homework you’ll be working with:
Serving static les
Middleware
Handling forms, both GET and POST
Templating
A JavaScript Object Representation of a Simple File System
You’ll be creating 2 pages:
home – / : a basic form that allows users to select a distribution of Linux Operating System.
vfs (virtual le system) – /vfs : a page that allows users to manipulate resources of a virtual le
system by submitting Linux commands through two forms and see system states returned from the
server (This is an in-memory le system).
Your directory layout should look similar with the following
once you’re done with the assignment (though
it can deviate from this example based on your implementation):

In the
views directory, you are not required to have the same les as above. If you’d like, you can use
template partials to reduce redundant markup. This was not covered in class, but you can check out the

pipeline

Posted on by cs daixie
1
Single Cycle versus Pipeline
In a single-cycle design, every instruction takes exactly one cycle. In other words, the single-cycle design
must allow the slowest instruction. While in pipelining, the datapath is broken into separate stages in-
dependant from each other, named IF (Instruction Fetch) , ID (Instruction Decode), EXE (Execution),
MEM (Memory) and WB (Write Back) in RISC-V. All the pipeline stages take a single clock cycle. As
a result, every instruction in RISC-V datapath takes exactly ve cycles to be executed. According to the
following gure, pipeline registers are located between every two stage. All the gures in this document
extracted from [1].
We can pipeline the tasks as long as we have separate resources for each stage. Pipelining improves
performance by increasing the instruction throughput. The idea behind pipelining is to keep all the stages
busy at all the times. As an example, when an instruction is using the ALU, the register le and the
instruction memory are used by the other instructions. Every instruction seems to have its own datapath.
All instructions advance during each cycle from one pipeline register to the next. In this case, all the required
information of an instruction such as control signals and registers need to be stored in pipeline registers.
Therefore, the instruction is able to restore all the required information for the next pipeline stage. According 

to the following gure, all the datapath information as long as control outputs generated by Controller are
stored in pipeline registers for every instruction.

Practice Stack and Queue Operations

Posted on by cs daixie
The Problem
1. Integer numbers are stored in a queue in a random order.
2. All numbers must eventually be removed from the queue and loaded over to a stack.
3. Elements can only be stored in the stack such that at any time the values are placed in
an increasing order from top down, like the disks in the game of Towers of Hanoi. In
particular, the minimum element is always at the top position.
4. (5 pts) No additional storage is allowed, at any given time each number is either in the
queue or in the stack.
Analysis and Design
1. The algorithm follows the following steps:
– if stack is not empty and first in the queue is greater than top in the stack, pop top
and add it to the queue
– else remove first from the queue and push it on the stack
– repeat until queue is empty
2. Both queue and stack are linked lists
3. (20 pts) Implement the Node class supporting the lists as you see it best. Using generic
type is optional. Defining Node methods not needed for the current solution is optional.
Redefine the displayList() method from your HW 3
4. (10 pts) Design additional classes as you need them and as you see it best. There has to
be a Test class containing the main method in your project.
5. (20 pts) Design and implement the queue and stack methods as necessary for linked list
based structures. Give the specifications to document the methods
Implementation and Requirements
1. (20 pts) The implementation must be tested and the result (decreasing storage) verified
on the console, use the displayList( ) method.

Practice Stack and Queue Operations

Posted on by cs daixie
The Problem
1. Integer numbers are stored in a queue in a random order.
2. All numbers must eventually be removed from the queue and loaded over to a stack.
3. Elements can only be stored in the stack such that at any time the values are placed in
an increasing order from top down, like the disks in the game of Towers of Hanoi. In
particular, the minimum element is always at the top position.
4. (5 pts) No additional storage is allowed, at any given time each number is either in the
queue or in the stack.
Analysis and Design
1. The algorithm follows the following steps:
– if stack is not empty and first in the queue is greater than top in the stack, pop top
and add it to the queue
– else remove first from the queue and push it on the stack
– repeat until queue is empty
2. Both queue and stack are linked lists
3. (20 pts) Implement the Node class supporting the lists as you see it best. Using generic
type is optional. Defining Node methods not needed for the current solution is optional.
Redefine the displayList() method from your HW 3
4. (10 pts) Design additional classes as you need them and as you see it best. There has to
be a Test class containing the main method in your project.
5. (20 pts) Design and implement the queue and stack methods as necessary for linked list
based structures. Give the specifications to document the methods
Implementation and Requirements
1. (20 pts) The implementation must be tested and the result (decreasing storage) verified
on the console, use the displayList( ) method.

Foundations of Artificial Intelligence

Posted on by cs daixie
Problem Description
LAX is the world’s fifth-busiest airport. It is therefore impossible to manually coordinate all of
the planes that are trying to land, make sure there is an open gate for each plane upon landing,
and again coordinate the planes trying to take off again. LAX’s air traffic controllers are asking
for the USC CS department to design a program to help them do this job.
The problem starts with
N airplanes flying over LAX, waiting to land, unload passengers, board
new passengers, and take off again. Each plane has only limited fuel remaining, allowing it to
stay in the air for at most
R minutes. A plane must begin its landing procedure before its fuel
runs out. The plane will arrive at a boarding gate
M minutes after starting its landing procedure.
It will then take
S minutes to unload passengers, refuel, board new passengers, etc. before it is
ready to take off again. If the plane spends more than
C minutes at the gate, the waiting
passengers will complain, which must be avoided at all cost. Once the plane leaves the gate, it
will take
O minutes for it to finally take off and for the inflight beverage service to begin.
Unfortunately, LAX does not have enough runways or boarding gates to allow all of the
airplanes to land, board, and take off whenever they want. Due to the crowded airspace and
the limited number of runways, there can be at most
L planes landing and at most T planes
taking off at the same time. Also, there are only
G boarding gates, and each gate can
accommodate only one plane at a time.
The problem facing the air traffic controllers is to assign each plane in the air a time when it
should begin its landing procedure and a time when it should begin its takeoff procedure. Each
plane must have enough fuel to stay in the air until its assigned landing time, a gate to stay at
before its time to take off again, and an early enough take off time so that its waiting
passengers do not complain.
Input Format
The input file name is “input.txt”.
<AIRPORT INFORMATION>:
contains 3 integers, L G T, separated by spaces. The first is the
maximum number of planes that can be landing at the same time. The second is the number of

Multiple Selection and Grouping in JavaFX

Posted on by cs daixie
Multiple Selection
Add to the blob demo so that the user can select multiple blobs, either with Control-click or with rubber-band selection.
Interaction requirements and required code changes:
The selection is now persistent (i.e., the selected blobs stay selected after the user releases the mouse)
Clicking on the background now clears the selection rather than creating a new blob
o
Change the demo’s Controller so that pressing on the background clears the selection rather than creating a blob
Control-clicking: holding the Control key and pressing with the mouse now adds or removes a blob from the selection
o
Add to the Controller to handle the pressing and releasing of the Control key
o
Add a boolean variable controlDown to the InteractionModel
o
Add to the View to show whether the Control key is pressed or not
o
Change the selection variable in the InteractionModel to represent a list of blobs instead of a single blob
o
Add method addSubtractSelection() to the InteractionModel that adds a blob to the selection list (if not already in the
list) or removes the blob from the selection list (if already in the list)
Rubber-band selection: if the user presses on the background and moves, a yellow rectangle will be drawn from the initial press
to the current mouse location. When the user releases the mouse, any blobs completely contained in the yellow rectangle will
be selected.
o
Create a class Rubberband to store the coordinates of the rectangle, and add an instance of Rubberband to your
InteractionModel
o
Add to the controller to handle the new interactions (draw the state diagram first)
o
Add another version of method addSubtractSelection() that can take a list of blobs found inside the rubberband, and
add them to / subtract them from the selection
o
Add a method to the model to return a list of blobs inside a given rectangle
Control + rubberband: holding Control and doing rubberband selection behaves similarly to Control-clicking (anything in the
rubberband on mouse release is added to / subtracted from the current selection list).
If the user presses on a blob that is selected (without the Control key), and then moves the mouse, all selected blobs will be
dragged.
If the user presses on a blob that is not selected (without the Control key), any existing selection is removed and the just-clicked
blob is selected.
If the user presses on the background and drags (without the Control key), any existing selection is removed and the
rubberband selection proceeds as above.
If the user presses and releases on the background (without the Control key), all selections are removed.
See the video (381-A4-multiselect.mp4) for illustrations of these actions.
Grouping and Ungrouping
Once you have a selection that includes a list of blobs rather than a single blob, add the ability to group and ungroup the selection.
Interaction requirements and required code changes:
When the user has selected multiple blobs, they can press the G key to group the items
o
Add to your Controller to handle the pressing of the G key
o
Add method createGroup() in your model to create a new group from the current selection list
Convert your model to work with Groupable items rather than Blobs
o
Create an interface Groupable that will have methods needed for both Blobs and Groups