QuestionQuestion

Intro to Computer Science

Better Array
Problem Description:
This lab will use the concept of a doubly-linked list to provide the capability for a more flexible array structure. The traditional array while being very efficient as regards execution time is relatively inflexible. It is a modern programming language implementation of a block of memory, accessed as a fixed number of data elements.
Good points:
a. No meta-data in memory (no wasted memory)
b. Random access with a simple calculation
c. Access to known index in constant time
Bad points:
a. Number of elements is fixed (cannot be expanded dynamically)
b. Each element’s location in the array is fixed (no insertions)
In order to make a “better” array we will add meta-data in memory (bad) and give up the ability to access a known index in constant time (bad). However, we will gain the ability to extend the array indefinitely (good) and to insert or delete an element anywhere in the array (good).
The key is to replace a block of memory and data elements adjacent to each other (an array) with a doubly-linked list, each node containing a data element (better array). The linked list gives us the ability to (a) add new elements indefinitely and (b) insert or delete an element anywhere in the list. The use of double linking gives us the ability to access an arbitrary sequence of elements more efficiently than repeated sequential access from the head-node. It also gives us the ability to sort the nodes in-place rather than duplicating the array size as workspace.
The exercise will involve three classes, the node class, the linked list class and the main program that instantiates, uses, sorts and tests an array.
The node class will be used to create each individual node as it is added to the list. It should contain no more than attributes for the data and the fore- and back-links and necessary methods for setting and retrieving the data value.
a. public node(int v) – class constructor, v = data value
b. public node( ) – class constructor
c. public int get( ) – returns the data value from the node
d. public void set(int v) – saves the data value v in the node
The linked list class will define the array-like interface between the main program and the linked list array implementation. It will provide for creation of the head and tail nodes and initialization of them. It will also maintain an integer value containing the current number of nodes in the array. A second integer value will contain the index of the most-recently addressed node and a node reference value will refer to the most-recently addressed node itself.
a. public BetterArray(int n) – class constructor, n is the initial allocation (the starting array size).
b. public BetterArray( ) – class constructor, use default initial allocation
c. public int get(int index) – uses the index to access a specific array element (node) and returns the value to the caller.
d. public void put(int value, int index) – uses the index to find the specific array element (node) and saves the data value in the node. If the requested node is outside the current size of the array (linked-list), expand the list to accommodate the new element.
e. public void insert(int value, int index) – uses the index to find the specific array element (node) and saves the data value in the preceding node. If the requested node is outside the current size of the array (linked-list), expand the list to accommodate the new element.
f. public void delete(int index) – uses the index to find the specific array element (node) and deletes it from the list.
Testing:
The main class will create an object of the BetterArray class and run it through some tests.
a. Create the object and make its size 10 elements.
b. Store a random sequence of 10 numbers in the array.
c. Read back the elements 0 thru 19 and display the values.
d. Store a random sequence of 20 numbers into the array.
e. Read back the elements 0 thru 19 and display the values.
f. Insert the number 999 immediately before element 14.
g. Read back the elements 0 thru 20 and display the values.
h. Delete element 15
i. Read back the elements 0 thru 19 and display the values.
j. Create another object and make its size 1000 elements.
k. Fill it with randomly-generated integers
l. Sort the array in either increasing or decreasing order
m. Your program will test the result by comparing each element of the sorted array to the one adjacent to it and reporting any out-of-order results.

ATC AC-inventory
Problem Description:
This lab will use the concept of a doubly-linked list to simulate part of an air traffic control system. The program will manage the arrival and departure of flights into and out of your airspace.

The job of air traffic controller involves taking responsibility for all of the aircraft in a specific area of the airspace. The airspace for this problem will be a piece of the traffic corridor between the cities of Buffalo and Boston, Ma. Other controllers will have responsibility for the area to the east, west, north and south of you but your area will be under your exclusive control.

The program will accept certain commands from you and will display certain information to you in response. The commands and their responses will be as follows:

Command: “Entering” – This command will signal that an aircraft has entered your airspace. You will be able to specify
a. The ID int    of an aircraft
b. The altitude int thousands of feet
c. The speed int miles per hour
d. The name String (ex: “U566”)
Response: one aircraft will be added to your problem

Command: “Leaving” – you will give the aircraft name
Response: it will be removed from your problem
Command: “Show” – you will give the aircraft name
Response: all information for that aircraft will be displayed
Command: “Display” –
Response: all aircraft in your problem will be displayed in a list

Implementation:
You will create a doubly-linked list in Java. You will implement an “aircraft” class which will take the place of the node class which was discussed. Objects of this aircraft class will be linked together in a list, as they are entered into the problem. When the “Display” command is entered, all the aircraft currently on the list will be displayed to the user.
Remember:
Use object reference variables for links between nodes
Implement two classes
a. linked list class which will be used by main to manipulate objects of the aircraft class
b. an aircraft class whose objects will contain aircraft information.
The main program should be the place where all of the “conversation” with the user takes place. This means that;
1. The linked list object will be able to return a single aircraft object in response to the “Show” command and will return an array of aircraft objects in response to the “Display” command.
2. The aircraft class should have a method that returns a String, suitable for displaying all of its information (used in the “Show” command) and another method that returns its name (used in the “Display” command). This will prevent the main program from having to know the details of the data inside the aircraft class.
3. There will be NO keyboard or display accessing in the aircraft class nor in the linked list class

Outline of classes

Main
Create linked list object
Loop while cmd not “quit”
Enter
Get AC info from user
Add an AC to list
Leave
Get AC name from user
Delete AC from list
Display
Get AC count from list
Loop from 1 to count
Show each AC
Display all existing AC in order of altitude
Show
Get AC name from user
Search list for name
Show AC found
When quitting, tell list to delete all remaining AC (if any).

Linked List
Get AC count
Add an AC
Delete an AC
Show AC by number
Search for AC by name and return the number
Delete all AC

Aircraft
Get name
Set name
Set type
Set altitude
Set speed

Testing:
In order to save a lot of typing, you may use single character commands (Ex: ‘e’ for “entering”, ‘l’ for “leaving” etc.).
You should be able to
a. “entering” the first aircraft
b. “entering” the second aircraft
c. “entering” the third aircraft
d. “display” all three, in altitude-order
e. “show” the first
f. “show” the third
g. “leaving” the second
h. “show” the second (present an approp riate error message)
i. “display” both remaining
j. “leaving” the third
k. “display” the remaining one
l. “leaving’ the first
m. “display” the empty list

Intro to Computer Science
Virtual Memory
Problem Description:
This exercise will require you to create a Java program that mimics the operation of an Operating System virtual memory capability. Virtual memory is still used because although the complement of RAM in a modern PC is huge and growing, the size and number of programs that need to be executing simultaneously is growing even faster.
Your program will not attempt to emulate a complete virtual memory capability but rather will demonstrate a two-level memory. The two levels will be implemented as a file on disk and a Java array in memory.
In “real life” the virtual memory capability depends on the ability of the operating system to detect the situation when a program tries to execute an instruction outside its protected area of memory. We will not be executing any code in our virtual memory but will restrict ourselves to data storage.
We will use virtual memory techniques to store an array of 1000 values in the swap file but use an array of only 100 values in RAM to access the entire 1000-element array.
You will create a class definition for a new class, named vMem which will have defined as a class attribute (data member), an actual Java array of 100 8-byte elements of type long (long integer). The class constructor will construct a direct access file large enough to hold 1000 8-byte values (which is 10 times the size of the actual RAM array).
The user (your “main” method for testing) will use the vMem as though it were actually 1000 elements long. But (in the example) the vMem will be actually 100 elements long and will contain only one of the ten 100-element sections of the larger, conceptual memory. When the user attempts to access data outside of the 100 element array, Java will throw an exception; which you will catch, whereupon the “catch” code will decide which of the stored 100-element pages is needed from the direct-access file. It will find it and replace the data in the 100 element array.
The analogy is that the CPU experiences memory as a huge array of 1-byte elements. It creates a “swap file” where the pieces of a much larger memory are defined. The ram is apportioned to each of the running programs and the apportioning software will allow a program needing 5 megabytes of RAM to exist and execute, using an actual RAM area much smaller. When the in-RAM segment of the program has been used and the CPU attempts to access a part of the larger virtual program, that part is brought into RAM from the swap file on the hard drive.
Your swap-file array will be stored in a direct-access file on the hard drive in its full size (1000 elements). The actual array inside the vMem object will be much smaller, 100 elements. You will use the main test program below, that will test the vMem object by attempting to use the entire 1000 elements that it tried to allocate when the vMem was created. This is done by generating an index value between 0 and (1000-1) and then generating a storage value to be stored at the index and immediately read back from that location. Using the random index will insure that the array accesses will not follow any pattern but will be scattered throughout the entire range of 1000 values.
When the value is immediately read back it is compared with the value that was stored and any discrepancy is noted as an error. Since the storage-retrieval loop executes 1,000,000 times it will use several minutes of elapsed time.
Further testing:
You will add the following functionality to the main program and your exercise will not be considered to be complete until this is complete and error free. You will add a loop which will store a sequence of 1000 descending values in the array. They will then be read and tested to insure that they are still in descending order. Any error will be flagged and the program will be stopped.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.Scanner;

public class AircraftInventory {
   
    class Node {
      
       Aircraft v;
       Node prev;
       Node next;
      
       public Node(Aircraft v) {
            set(v);
       }
      
       public Node() {
            set(null);
       }
      
       public Aircraft get() {
            return this.v;
       }
      
       public void set(Aircraft v) {
            this.v = v;
       }
      
    }
   
    Node head;
    Node tail;
    Integer n;
   
    Node recent;
    int recentIndex;
   
    public AircraftInventory(Integer n) {
       this.n = n;
       head = new Node();
       Node current = head;
       for (int i = 1; i < n; i++) {
            current.next = new Node();
            current.next.prev = current;
            current = current.next;
       }
       tail = current;
       recent = head;
       recentIndex = 0;
    }
   
    public AircraftInventory() {
       n = 10;
       head = new Node();
       Node current = head;
       for (int i = 1; i < n; i++) {
            current.next = new Node();
            current.next.prev = current;
            current = current.next;
       }
       tail = current;
       recent = head;
       recentIndex = 0;
    }
   
    public Aircraft get(int index) {
       while (recentIndex != index) {
            if (recentIndex < index) {
                recent = recent.next;
                recentIndex++;
            } else if (recentIndex > index) {
                recent = recent.prev;
                recentIndex--;
            }
       }
       return recent.get();
    }
   
    public void put(Aircraft value, int index) {
       if (index >= n) {
            Node current = tail;
            while (index >= n) {
                current.next = new Node();
                current.next.prev = current;
                current = current.next;
                n++;
            }
            tail = current;
       }
       while (recentIndex != index) {
            
            if (recentIndex < index) {
                recent = recent.next;
                recentIndex++;
            } else if (recentIndex > index) {
                recent = recent.prev;
                recentIndex--;
            }
       }
       recent.set(value);
    }
   
    public void insert(Aircraft value, int index) {
       if (index >= n) {
            Node current = tail;
            while (index >= n) {
                current.next = new Node();
                current.next.prev = current;
                current = current.next;
                n++;
            }
            tail = current;
       }
       while (recentIndex != index) {
            if (recentIndex < index) {
                recent = recent.next;
                recentIndex...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$60.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats