1. An OBST (optimal BST) minimizes the average search time across all keys in the BST. Given 5 ordered keys. k1<k2<k3<k4<k5, with probabilities of occurrence (0.25, 0.15, 0.10, 0.20, 0.30), respectively
   1. Use a Greedy algorithm that attempts to construct a BST that is an OBST.
   2. What is the complexity of your Greedy algorithm?  
   3. Is your Greedy BST an OBST? Explain
   4. apply the DP algorithm to acquire an OBST
   5. show your work, including tables and the extraction of the actual OBST
   6. analyze the complexity of the DP algorithm

Let X = {x1,x2,...,xn} a sequence of real numbers. Design an algorithm that in linear time finds the continue subsequence of elements xi,xi+1,...,x, which product is the maximum. Suppose that the product of an empty subsequence is 1 and observe that the values can be less to 0 and less to 1.

Comment the code explaining what each line is doing. The first line has been done for you.

x=[0 0 -1 2 3 -2 0 1 0 0]; %input discrete-time signal

x dtx= -2:7;

y=[1 -1 2 4];

dty=8:11;

z=conv(x,y);

dtz=6:18;

subplot(1,3,1), stem(dtx,x)

subplot(1,3,2), stem(dty,y)

subplot(1,3,3), stem(dtz,z)

Use the cumsum command in MATLAB to show that the cumulative sum of an impulse is a unit step function. Add a line to your code from Problem 2. Plot the unit step function generated by the cumsum command. Turn in a copy of the code and graph.

1. What strategies can be used to test contingency plans? [MANAGEMENT OF INFORMATION SECURITY]

In one paragraph, please briefly explain why cloud customer should use AWS KMS.

Use one sentence to briefly describe the difference between symmetric encryption and asymmetric encryption.

Resource Monitor. Windows 10

Uncheck perfmon.exe.

1. Currently the CPU section is sorted alphabetically by image name. Click on the CPU column to sort it by CPU utilization. What process is using the most CPU?

C++

// Program Description: This program accepts three 3-letter words and prints out the reverse of each word

1. A main(. . . ) function and the use of std::cin and std::cout to read in data and write out data

   as described below.

2. Variables to hold the data read in using std::cin and a return statement.

#include <iostream >

int main(int argc, char *argv[]) {

.... your code goes here

}//main

Example usage:

>A01.exe
Enter three 3-letter space separated words, then press enter to display the reverse:
cat eye fix
tac eye xif
Enter any key to exit:

Python

Problem 4. Estimate pi version 2: write a program that will quickly estimate pi to a precision of 1e-4 using a monte carlo approach. Your program should employ a loop where each iteration produces a new x,y pair. One will then determine whether the x,y pair lies inside or outside the circle. (see below) Since all the points will land within the square shown above but only a fraction will land within the circle, we can estimate pi by relating the area of the quarter circle shown above to the area of the square. As we randomly choose points, we can determine if they fall within the circle or not and form a ratio as shown below: AreaQtrcircle / AreaSqaure = πr 2 / 4r 2 = π / 4 = Points in Circle / All Points, π ≅ 4* Points in Circle / All Points.

Your loop should continue until the absolute value of the difference between the current estimate and the previous estimate is less than 1e-4. The program should output the estimate of pi and the number of iterations (points) needed to reach the desired level of precision. Run your program several times to see if the number of points changes. Note any observations in the comments.

(In Java) Implement a Deque in which addFirst(), addLast(), removeFirst(), removeLast(), and getMin() are all in O(1) (amortized). The getMin() method is supposed to find the minimum value in the deque and update after ever add/remove. I tried implementing this with a Deque and LinkedList but wasn't successful, you do not need to use either. Must use the comparator and iterator. The goal is to be as fast as possible, so this includes avoiding any operations that aren't O(1) as much as possible. I used my own testing class. Thanks!

import java.util.*;

public class FMinDeque<T> implements MinDeque<T> {

    protected Comparator<? super T> comp;
    Deque<T> dq;
    protected List<T> min;
    T m;
    public FMinDeque() {
        this(new DefaultComparator<T>());
    }
    public FMinDeque(Comparator<? super T> comp) {
        this.comp = comp;
        dq = new ArrayDeque<T>();
        min = new LinkedList<T>();
    }
    public Comparator<? super T> comparator() {
        return comp;
    }
    public void addFirst(T x) {

    }
    public void addLast(T x) {

    }
    public T removeFirst() {
        
        return null;
    }
    public T removeLast() {
        
        return null;
    }
    public T getMin() {
      
    }
    public int size() {
        return dq.size();
    }
    public Iterator<T> iterator() {
        return dq.iterator();
    }
}

This extends:

import java.util.Comparator;

    public interface MinDeque<T> extends Iterable<T>
    {
        public Comparator<? super T> comparator();

        public void addFirst(T x);
        public void addLast(T x);

        public T removeFirst();
        public T removeLast();

        public T getMin();

        public int size();

And

import java.util.Comparator;

class DefaultComparator<T> implements Comparator<T> {
    @SuppressWarnings("unchecked")
    public int compare(T a, T b) {
        return ((Comparable<T>)a).compareTo(b);
    }
}

Prove or disprove with a counterexample the next claims:

(a) The complement of a decidable language is decidable.

(b) The Kleene star of a Turing-recognizable language is Turing-recognizable.

A)Write a C++ program using a while loop for Programming Exercise 5.1 on p. 193.

Turn in a printout of the program and a printout of the results.

Test the program for the two test cases in the book along with a third test case that includes 10 valid numbers (including some negative and some positive).

Java

Write a class called Car that contains instance data that represents the make, model, and year of the car.

Define the Car constructor to initialize these values

Include getter and setter methods for all instance data and a toString method that returns a one-line description of the car.

Add a method called isAntique that returns a boolean indicating if the car is an antique (if it is more than 45 years old).

Create a driver class called CarTest, whose main method instantiates and updates several Car objects

Must have two constructors, one accepts nothing and another overloaded constructor that accepts parameters.

Must have accessor and mutator methods for each instance variable, and the toString method

Must test ALL (the two constructors, the accessors, and mutators for each variable and the other methods if there are any) methods explicitly in the driver class’s main method with at least two objects.

Addon:

Create an array of five objects of the class you have created. Use a for loop to display the five objects first. Then test all methods using the objects in the array and finally print out each object using a for loop again.

Write a Java program to convert decimal (integer) numbers into their octal number (integer) equivalents. The input to the program will be a single non-negative integer number. If the number is less than or equal to 2097151, convert the number to its octal equivalent.

If the number is larger than 2097151, output the phrase “UNABLE TO CONVERT” and quit the program.

The output of your program will always be a 7-digit octal number with no spaces between any of the digits. Some of the leading digits may be 0.

Use a while loop to solve the problem. Do not use strings.

Sample Program Run
Please enter a number between 0 and 2097151 to convert: 160000
Your integer number 160000 is 0470400 in octal.

Please enter a number between 0 and 2097151 to convert: 5000000
UNABLE TO CONVERT