Subject: Computer Algorithms

3) Design an efficient algorithm that sorts an array containing 2 sorted sets of numbers, such as A=[3,4,7,9,13,1,5,6,8] (Note that [3,4,7,9,13] and [1,5,6,8] are both sorted, but A is not). Your algorithm declaration should look like this:

MYSORT(A,p,n)

where A is the input array, p is the index to the first element of the second set of numbers, and n is the length of array A.

Calculate the asymptotic running time and space of you algorithm.

Reference book

Introduction to Algorithms 3rd edition

Ebook URL:

http://ce.bonabu.ac.ir/uploads/30/CMS/user/file/115/EBook/Introduction.to.Algorithms.3rd.Edition.Sep.2010.pdf

IN JAVA WITH COMMENTS, The assignment: This program inputs the names of 5 students and the (integer) grades they earned in 3 tests. It then outputs the average grade for each student. It also outputs the highest grade a student earned in each test, and the average of all grades in each test.

Your output should look like this:

Mary's average grade was 78.8%

Harry's average grade was 67.7%

etc... :

In test 1 the highest grade was 93% and the average was 89.2%

In test 2........etc

Your main method should be modular.

Write a method that inputs the 5 names into an array (one dimensional), and returns this array to main

Write a method that inputs the 15 (integer) test grades into a (two-dimensional) array, and returns this array to main.

Write a method that calculates the students averages and stores them in an array , and returns this array to main

Write a method that calculates the average grade for each test and stores them in an array, and returns this array to main

Write a method that determines the highest grade for each test and stores this in an array , and returns this array to main. MAIN will print all the information. The printing could be done easily by the methods instead of having to store the information in an array, but this will give you practice in arrays and methods - all useful for the final exam.

Thanks a lot, please include the comments.

Describe and explain at least three improvements you think came about with the introduction of intrusion prevention technology. Justify your response with at least one credible source.

Explain which of these features you would consider to be the most beneficial if you were a member of the IT team supporting a network. Justify your response with at least one credible source.

Implement these methods (adjust DoubleList.java only for errors if you think needed):

getNode – take in one int parameter indicating the index of the node to retrieve (index 0 is the front). If that index is out of the bounds of the list, throw a DoubleListException with an appropriate message. Otherwise, determine which half of the list the index is in, and traverse to it using the shortest traversal to get there, by calling either traverseForwards or traverseBackwards with the number of steps to get to the index from the corresponding end (if it's the very middle, you can decide which way to go). For example, consider a list with 5 nodes. Calling getNode(1) should retrieve the node immediately after front using traverseForwards. Calling getNode(3) should retrieve the node immediately after rear using traverseBackwards. Return the found node.

setElement – take in two input parameters: index (int) and element (generic type). Call the getNode method described below to find the node to be updated, and then called setElement on that node with the given element

getElement – take in one input parameter: index (int). Call the getNode method with the given index and return the data element of the node at that position.

toString – returns the string representing the list from the front to the rear with a space between each node. If the list is empty, then return the string "Empty list".

DoubleNode.java

public class DoubleNode{

private DoubleNode next;

private DoubleNode previous;

private T element;

/**

* Constructor with no input parameters.

*/

public DoubleNode(){

next = null;

previous = null;

element = null;

}

/**

* Constructor with one input parameter representing the node's data element.

* @param elem

*/

public DoubleNode (T elem){

next = null;

previous = null;

element = elem;

}

/**

* Get the next node.

* @return next node

*/

public DoubleNode getNext(){

return next;

}

/**

* Get the previous node.

* @return previous node

*/

public DoubleNode getPrevious(){

return previous;

}

/**

* Set the next node.

* @param node

*/

public void setNext (DoubleNode node){

next = node;

}

/**

* Set the previous node.

* @param node

*/

public void setPrevious (DoubleNode node){

previous = node;

}

/**

* Get the data element.

* @return data element.

*/

public T getElement(){

return element;

}

/**

* Set the data element.

* @param elem

*/

public void setElement (T elem){

element = elem;

}

/**

* Return the node's data element for printing purposes.

* @return string of node's data element

*/

public String toString () {

return element.toString();

}

}

DoubleList.java

public class DoubleList{

DoubleNode front,rear;

private T count;

public DoubleList () {

front = null;

rear = null;

count = 0;

}

public void addToRear(T elem){

DoubleNode new_node = new DoubleNode(elem);

if (front.getElement() == null){

front.setElement(new_node);

rear.setElement(new_node);

} else if (front.getElement() != null){

new_node.setPrevious(rear);

rear.setNext(new_node);

rear = new_node;

}

count = count + 1;

}

public void traverseForwards(T elem){

DoubleNode numNode = new DoubleNode(elem);

curNode = front.getElement();

for (i = 0; i = numNode; ++i){

System.out.println(curNode);

curNode = curNode.getNext();

} if (front.getElement == null){

System.out.println(null);

}

}

public void traverseBackwards(T elem){

DoubleNode numNode = new DoubleNode(elem);

curNode = rear.getElement();

for (i = 0; i = numNode; ++i){

System.out.println(curNode);

curNode = curNode.getPrevious();

} if (rear.getElement == null){

System.out.println(null);

}

}

Program 4(Total Point 15): You will use the scanner class and ask users following things.

- Student Age (Value)

- Student Name (Key)

You will store information for at least 10 students on Map. You will then use iterator to print all the values. You will print the youngest student’s name.

You need to write and run C programs (as processes on your Linux machine), and monitor their behavior. Consider the following problem: A program is to be written to print all numbers between 1 and 1000 (inclusive) that are not (evenly) divisible by either 2 or 3. This problem is to be solved using three processes (P0, P1, P2) and two one-integer buffers (B0 and B1) as follows:  P0 is to generate the integers from 1 to 1000, and place them in B0 one at a time. After placing 1000 in the buffer, P0 places the sentinel 0 in the buffer, and terminates.  P1 is to read successive integers from B0. If a value is not divisible by 2, the value is placed in B1. If the value is positive and divisible by 2, it is ignored. If the value is 0, 0 is placed in B1, and P1 terminates.  P2 is to read successive integers from B1. If a value is not divisible by 3, it is printed. If the value is positive and divisible by 3, it is ignored. If the value is 0, P2 terminates. Write a program to implement P0, P1, and P2 as separate processes and B0 and B1 as separate pieces of shared memory {each the size of just one integer}. Use semaphores to coordinate processing. Access to B0 should be independent of access to B1; for example, P0 could be writing into B0 while either P1 was writing into B1 or P2 was reading.

************CODING IN C++ ONLY ********************

Instructions

Write a function, remove, that takes three parameters: an array of integers, the number of elements in the array, and an integer (say, removeItem).

The function should find and delete the first occurrence of removeItem in the array. (Note that after deleting the element, the number of elements in the array is reduced by 1.) Assume that the array is unsorted. Also, write a program to test the function.

Your program should prompt the user to enter 10 digits for the array. Display the starting array to the user and prompt them to select an integer to remove. After the selected integer has been removed, the updated list should be displayed to the user. If the value does not exist or the array is empty, output the following message: x is not in the list

GRADING CRITERIA

1)  Defined the remove function

2) Removing elements from the list

3) List does not contain integer to be removed

TESTING WITH INPUT

2
7
6
8
3
9
10
1
5
4
6

OUTPUT SHOULD BE

2 7 8 3 9 10 1 5 4

*************************************

A SAMPLE OF MY CODE, IT HAS MANY ERRORS

#include <iostream>
using namespace std;

void remove(int arrayList[],int& size,int removeItem)
{
int i, j;
for (i = 0; i < size; i++)
if (arrayList[i] == removeItem)
if(i == size-1)
{
//decrease items
size--;
return;
}
else
{
for (j = i; j < size-1; j++)
arrayList[j] = arrayList [j+1];
size --;
return;
}
cout <<" item" << remove item << is not found in the array";
}

In C++

First create the txt file given below. Then complete the main that is given. There are comments to help you. An output is also given You can assume that the file has numbers in it

Create this text file: data1.txt

-59 -33 34 0 69 24 -22 58 62 -36 
5 45 -19 -73 62 -5 95 42 

Main

#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
using namespace std;

const int MAXSIZE = 100;

// Prototypes





int main()
{
    int nums[MAXSIZE];
    int searchFor;
    int indexFound = -1;
    int numElems;
    double average;
    string fileName;
    char again;

    do
    {

        cout << "Enter the file name: ";
        cin >> fileName;

        // Call the function fillArray. It has the fileName, the nums array and
        // the numElem passed in (in that order). It will calculate the numElems
        // Description of function given below



        // Call the function printArray. It has the nums array and
        // the numElem passed in (in that order). 
        // Description of function given below





        // Call the function findAverage. It has the nums array and
        // the numElem passed in (in that order). It stores the value
        // that is returned in the average variable declared above.
        // Description of function given below




        // Asks the user what number they want to search for
        cout << endl << endl;
        cout << "Enter a number between -100 and 100 to search for: ";
        cin >> searchFor;

        // Call the function findValue. It has the number being searched for
        // the nums array and the numElem passed in (in that order). 
        // It stores the index of the position in the array where the 
        // number was found in the indexFound variable declared above.
        // Description of function given below



        // Right the if statement to print whether the number was found.
        // If it was found, it will print the inde of where it was found.
        // (See output for what should be printed






        cout.setf(ios:: fixed);
        cout.precision(2);
        cout << "The average of all the numbers in the array is " << average << endl;
        cout << endl;
        cout << "Do you want to do this again? (Y/N): ";
        cin >> again;
    } while (toupper (again) == 'Y');
    return 0;
}



// Function: findValue
// This function has the value being serachedd for, the array and the number of 
// elements passed in. I searches the array and when it first finds it, it
// stops searching and returns the index of where it was found. If it is not 
// in the array, it returns a -1






// Function: findAverage
// This function has the array and the number of elements passed in.
// It computes the average of the numbers in the array and returns it.






// Function: printArray
// This function has the array and the number of elements passed in.
// It prints the array in neat columns, with 7 numbers per line







// Function: fillArray
// This function should open the file with the name that passed into it. If the file does
// not open correctly it should exit the program. It should
// then read in the numbers and load them into the array. 
// make sure you check that you don't exceed the array size.
// If the file has too many numbers, your program should not put the 
// extra numbers in the array, the array will just be full.
// This function determines the number of elements in the array.
// This function should not call any other user defined functions.

Sample Output

Enter the file name: data.txt
    -59    -33     34      0     69     24    -22
     58     62    -36      5     45    -19    -73
     62     -5     95     42

Enter a number between -100 and 100 to search for: 62
62 was found in index 8
The average of all the numbers in the array is 13.83

Do you want to do this again? (Y/N): Y
Enter the file name: data1.txt
    -59    -33     34      0     69     24    -22
     58     62    -36      5     45    -19    -73
     61     -9     95     42    -73    -64     91
    -96      2     53     -8     82    -79     16
     18     -5    -53     26     71     38    -31
     12    -33     -1    -65     -6      3    -89
     22     33    -27    -36     41     11    -47
    -32     47    -56    -38     57    -63    -41
     23     41     29     78     16    -65     90
    -58    -12      6    -60     42    -36    -52
    -54    -95    -10     29     70     50    -94
      1     93     48    -71    -77    -16     54
     56    -60     66     76     31      8     44
    -61    -74     23     37     38     18    -18
     29     41

Enter a number between -100 and 100 to search for: 52
The number 52 was not found in the array
The average of all the numbers in the array is 1.48

Do you want to do this again? (Y/N): y
Enter the file name: data.txt
    -59    -33     34      0     69     24    -22
     58     62    -36      5     45    -19    -73
     62     -5     95     42

Enter a number between -100 and 100 to search for: 95
95 was found in index 16
The average of all the numbers in the array is 13.83

Do you want to do this again? (Y/N): n

In python language do thee following:

Some password scheme is designed such that the password must start with a special symbol in “$” “@” or “!” followed by four letters that could be in a..z followed by a similar special symbol followed by three letters in A..Z followed by a single digit. Write a program that takes from the user a string, and verifies whether the string abides by this password scheme. Do this once using regular expressions. Another time without using regular expressions.

1) Describe the performance impact of using the LIKE operation with a wild card character at the beginning of the value.

2) Under what circumstances is a non-matching index scan performed?

3) A query is written to access a single table. Furthermore, that query will return only a single row because an equality predicate is coded on the primary key for the table. A unique index exists to support the primary key. What type of access is likely to be the most efficient for that query?

4) How can stored procedures be used to optimize performance in a client/server application?

5) Under what circumstances will a table scan outperform indexed access?

Programming Language: C++

Create a base class called Shape which has 2 attributes: X and Y (positions on a Cartesian coordinate system). Since a shape is amorphous, set the class up so that an object of type Shape can not be instantiated.

Create three derived classes of your choice whose base class is Shape. These derived classes should have accessors/mutators for their class specific attributes, as well as methods to compute the area and the perimeter of the shape.

In main(), create a stack of pointers to Shape and push one object of each derived class onto the stack. Then, pop each shape pointer off of the stack and output that shape's area and perimeter, demonstrating polymorphism.

Clarify the differences between the types of location sensors built-in to the mobile device. And how the Location information is accessed within an app?

Python

Without running / testing the following code, predict what the following program prints on the screen.

freeze = int(32)

boil = int(212)

freeze = 0

boil = 100

print(freeze, boil)

• Write a program that asks the user for a number in the range of 1 through 7. The program should display the corresponding day of the week, where 1 = Monday, 2 = Tuesday and so forth. If the user types in a 6 then "Saturday" should be printed on the screen.
• The program should display an error message if the user enters a number that is outside the range of 1 through 7.
• Name the source code file
• Test and run the program. Capture the output console and save it as an image file