CPI 220 Quizzes

Algorithms can write themselves with machine learning methods.

True

Who is famous for his work on merge sort and with the Manhattan Project?

John von Neumann

Which algorithm is considered to be the oldest?

Euclid’s Greatest Common Divisor

The ________________________________ is a matching problem that has been used to improve kidney donation matches.

Stable Marriage Problem

In Java, real is a primitive type.

False

Java has only two primitive data types.

False

An object is an entity that can take on a data-type value.

True

API is an acronym for 

Application Programming Interface

Objects are characterized by three essential properties: The state of an object is a value from its data type; the identity of an object distinguishes one object from another; the behavior of an object is the effect of data-type operations.

True

As a general principle, we want to avoid compile time errors and rather have run time errors.

False

In implementing a queue with a linked-list

aa --> bb --> ab --> a --> zz--> oo --> ff --> null

the "back of the queue" pointer will be located at

ff

The add and delete operation for a stack are enqueue and pop.

False

A queue cannot be implemented with an array.

False

When an item is removed from a queue, this item is the most recently added item.

False

Floating point multiplication and division take the same amount of time.

False

How many operations are executed in the following code.

for(i=0; i<N; i++)

      for(j=0; j<N; j++)

             a = j;

N²

Many algorithms have an order of growth that falls into one of the following function categories. Which sequence of these functions is in the correct order from slowest to fastest running algorithm?

N^3, N^2, NlogN, N, logN, 1

The power law is used to model run time. For input size N, it is

T(N) = 

aN^b

When modeling the run-time of an algorithm with the power law, T(N) = aN^b, we can use the "doubling hypothesis" method. By repeatedly doubling the input size, we will find an estimate of "a" in T(N). The second step is to estimate "b".

False

The API for dynamic connectivity describes the functions

find, connected, union.

The graph

0 ‐‐‐ 2 ‐‐‐‐ 3 ‐‐‐‐ 5            6‐‐‐‐‐ 7‐‐‐‐‐8‐‐‐‐‐9

has _____ connected components.

2

An equivalence relation has three properties: reflexive, symmetric, and intransitive.

False

The following array is storing _______ connected components

array index = 0 1 2 3 4 5 6 7 8 9
               id = 0 1 9 4 9 6 6 7 8 9

7

Weighted Quick-union uses more memory than Quick-union for the purpose of reducing tree height.

True

In the game "rock, paper, scissors" there is a total order on the tools.

False

The condition that entries to the left of a[i] are fixed and in ascending order is an invariant in selection sort.

True

In sorting algorithms in this section, the compareTo() method, when used as a.compareTo().(b), must return

    -1  when  b < a 
     0  when  a = b
     1  when  a < b

False

Insertion sort is a divide and conquer algorithm.

False

Binary insertion sort sorts 0s and 1s only

False

A stable sort preserves the relative order of items with equal keys.

True

A sorting algorithm sorted the following items first by time and then by city. It a stable sorting algorithm.

Mesa    10:00
Mesa     09:00
Phoenix   9:00
Phoenix  11:00
Scottsdale  12:00

False

Merge sort uses extra space proportional to the input array size.

True

Merge sort in run time complexity is for N items.

False

The basic merge sort algorithm can be improved by using insertion sort on "small" subarrays. 

True

Quick sort runs in optimal time if the array is sorted.

False

Quick sort worst case time complexity is N lg N.

False

Quick sort always partitions at the midpoint of the array.

False

Quick sort can benefit from using insertion sort on small subarrays.

True

Quick sort is a divide and conquer algorithm.

True

Priority queues are a good choice when input data is streaming and at any point in time, some "small" number of items with the largest or smallest values need to be identified.

True

Insertion in a binary heap requires the new node to sink.

False

In a heap ordered binary tree, a parent key is greater than its children's keys.

False

Heap sort uses a stack.

True

In a MaxPQ, the method delete the maximum requires a call to the binary heap sink method.

True