CS 4050 Algorithms & Data Structure Design & Analysis Project

Having Trouble Meeting Your Deadline?

Get your assignment on CS 4050 Algorithms & Data Structure Design & Analysis Project completed on time. avoid delay and – ORDER NOW

Do My Paper

Experiment Sample Preparation

Analysis Unit Centrifuge Control (version 1.0)

Preview

Two autonomous vehicles are involved in scientific exploration of an astronomical object in
our solar system. The first vehicle, called the Sampling Vehicle (SV), stops every kilometer
to collect four samples, sealing them in tubes that also contain reagents. The SV drops the
sealed tubes on the surface for collection and moves to its next location. The tubes may
end up in any orientation on the surface.
The second vehicle, the Collection and Analysis Vehicle (CAV), follows the SV’s path. It can
identify sample tubes with sensors and has a robot arm to pick up and load them into
trays, with each tray holding four tubes. The CAV searches for three additional samples
once it finds one and closes the tray when it secures all four. The CAV doesn’t distinguish
between tube ends, and trays may have tubes with different orientations.
The Analysis Unit (AU) of the CAV accommodates the trays and has three doors: LEFT,
TOP, and RIGHT. Only two doors can be open simultaneously. Doors can’t be closed
unless the centrifuge begins spinning, and all open doors automatically close when
spinning starts. The AU can sense and report the tube orientation, and it can also reverse
the orientation on command.
The centrifuge responds to “spin” and “stop” signals with delays of 10 to 1000
milliseconds. After a “spin” signal, it takes up to 5000 milliseconds to reach maximum
rotation speed due to inertia, and up to 3000 milliseconds to come to a halt after a “stop”
signal.
The controller of the AU is a Turing-machine equivalent processor, capable of executing
programs with standard control structures, assignment statements, and basic data
structures. Pseudo-code can be used to express algorithms for the programmers who will
be writing the final source code for the AU.
The scientific experiment’s validity hinges on ensuring that all four tubes within the
centrifuge tray have a consistent orientation, regardless of whether all tubes have their
cap-ends towards the center or all have their cap-ends towards the outer rim. The specific
orientation (center or outer rim) is not crucial; the key requirement is that they all match.
Only when this consistency in orientation is achieved can the 30-minute centrifuge cycle
commence, ensuring the experiment’s accuracy and reliability.
Your task is to design an algorithm for the AU controller that guarantees that all sample
tubes have the same orientation before initiating the 30-minute centrifuge cycle.
Additionally, you should perform an analysis of the worst-case time complexity using big-
O notation and attempt a proof of correctness for your algorithm. While not mandatory,
creating a simulation of the AU can be insightful for understanding the practical
implications of your algorithm.

Context
Two autonomous vehicles are involved in conducting scientific exploration of an
astronomical object within our solar system (e.g., planet, moon, asteroid). One is a
Sampling Vehicle (SV), the other is a Collection and Analysis Vehicle (CAV).
Sampling Vehicle
The SV stops every kilometer and collects 4 samples at each location it stops. Each
sample is put in a tube that contains a reagent and the tube is sealed with a cap. The
sealed tube is then dropped on the surface for a collection vehicle to pick up. The sample
tubes may end up in any orientation on the surface, including all angular positions
between vertical and horizontal and with no regard for where the cap-end lies.
Collection and Analysis Vehicle
The CAV follows the track of the SV. It has sensors that can identify sample tubes. The
CAV also has a robot arm with which it picks up and loads sample tubes into centrifuge
trays. Each tray accommodates exactly 4 sample tubes. Once the CAV locates a single
sample, it searches the immediate area for 3 more samples. When the fourth
sample has been secured, the tray is closed and transferred to the Analysis
Unit (AU) of the CAV.
The collection portion of the CAV is very simple, designed to
pick up and load a sample tube into a tray. It does not have
the ability to distinguish between the two ends of the sample tube. The
centrifuge tray has been designed to accept tubes in either orientation:
cap-end towards the center or cap-end towards the outer rim. The tubes
in a closed centrifuge tray may thus not be oriented the same; that is, some may have the
cap-end towards the center while others may have the cap-end towards the outer rim.
The AU centrifuge accommodates the centrifuge tray. It also has three doors,
at most two of which may be open at the same time.
The doors are referred to as LEFT (at the nine-o’clock position), TOP (at the
twelve-o’clock position), and RIGHT (at the three-o’clock
position). When the centrifuge comes to a complete stop,
the LEFT door is automatically opened. Thus there are three possible
configurations of open doors: [LEFT], [LEFT and TOP], or
[LEFT and RIGHT].
Once a door has been opened it cannot be closed except by
directing the centrifuge to begin spinning. All open doors are
closed automatically when the centrifuge is directed to begin spinning.
The AU has the ability to sense and report the orientation of any tube exposed by an open
door. The AU can also be directed to reverse the orientation of any exposed tube.
There is a delay of between 10 and 1000 milliseconds between when a command is
issued and when the centrifuge begins to respond.

The centrifuge will begin to spin or stop spinning in response to a “spin” or “stop”
command respectively. When a “spin” signal has been received, the AU closes any open
doors and the centrifuge spins until it receives a “stop” signal.
Due to inertia, there is a period of up to 5000 milliseconds before the centrifuge reaches its
maximum rotation speed following a “spin” signal. It may take up to 6000 milliseconds
before the centrifuge comes to a halt after receiving a “stop” signal.
Scientific Experiment Requirements
The validity of the scientific experiment requires all four tubes to have the same orientation
in the centrifuge tray and for the centrifuge to then run for a period of 30 minutes.
Consistency of orientation is all that’s important, not the particular orientation. Thus all
tubes may have the cap-end towards the center or all may have the cap-ends towards the
outer rim. The only constraint is that they must all have the same orientation before the 30
minute cycle can begin.
Programming Specifications
AU Controller Programming
The AU controller is a Turing-machine equivalent processor. It can execute programs that
use standard control structures (sequence, conditional, looping/recursion, subroutine/
function calls), assignment statements, and data structures (primitives, indexed
sequences, linked structures).
Pseudo-code expressing an algorithm is acceptable for the programmers who will be
writing the final source code for the AU controller.
Controller ? Centrifuge
The centrifuge accepts the following commands from the controller and takes the action
described.
BALANCED Reports whether or not the centrifuge tray is balanced (all tubes have
the same orientation); results are valid only while the centrifuge is
spinning
FLIP_LEFT Flips the orientation of the tube exposed by the LEFT door (if and only
if the LEFT door is open; otherwise shuts down)
FLIP_RIGHT Flips the orientation of the tube exposed by the RIGHT door (if and
only if the RIGHT door is open; otherwise shuts down)
FLIP_TOP Flips the orientation of the tube exposed by the TOP door (if and only
if the TOP door is open; otherwise shuts down)
OPEN_RIGHT Opens the RIGHT door (if and only if the LEFT door is open and the
TOP door is closed; otherwise shuts down)

OPEN_TOP Opens the TOP door (if and only if the LEFT door is open and the
RIGHT door is closed; otherwise shuts down)
REPORT_LEFT Reports the orientation of the tube under the LEFT door (if and only if
the LEFT door is open; otherwise shuts down)
REPORT_RIGHT Reports the orientation of the tube under the RIGHT door (if and only if
the RIGHT door is open; otherwise shuts down)
REPORT_TOP Reports the orientation of the tube under the TOP door (if and only if
the TOP door is open; otherwise shuts down)
SPIN Closes all open doors and starts the centrifuge spinning (if the
centrifuge is already spinning, this command is ignored)
STOP Applies brake to the centrifuge and automatically opens the LEFT
door when the centrifuge has come to a complete stop (if the
centrifuge is already stopped, this command is ignored)

 Assignment

Develop and deliver an algorithm for the AU controller that ensures all tubes have the
same orientation.
Your algorithm should not only fulfill the fundamental task of aligning tube orientations but
should also be efficient and error-resistant, as it’s intended for use in a scientific
experiment without human intervention.
Planning
Tube Orientation Strategy: Formulate a strategy for achieving uniform tube orientation.
Consider different algorithm development strategies and how each might be applied to
this situation.
Algorithm Development: Create a comprehensive algorithm outlining each step the AU
controller should follow. Be explicit about how the controller will inspect and potentially
modify tube orientations to align with your chosen strategy. Consider the possible 6 states for the problem that the algorithm must handle to achieve a balanced tray. You do not need a counter.
Worst-Case Complexity Analysis: Provide a detailed explanation of the algorithm’s
worst-case time complexity using big-O notation.
Proof of Correctness: Demonstrate the correctness of your algorithm. Present a
convincing mathematical or logical proof that your algorithm will reliably ensure consistent
tube orientation as required for the experiment.