Reference no: EM133720143

Homework: Algorithms & Data Structure Design & Analysis Project

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, homework 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), homework 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)

Task

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.