CPI 220 Mock Midterm

What is an Algorithm?

A set of well-defined logical steps that must be taken to perform a task.

What are the properties of an algorithm?

unambiguous, complete, provable

Complete the sentence:

An Abstract Data Type is a class of objects whose behavior is defined by a set of _____________________ and a set of ________________________.

values, operations

Complete the sentence:

API is an acronym for ___________________________________________. It is a list of _________________________ and _____________________ with an informal description of each.

Application programming interface, constructors, instance methods

A program that uses an API is called a _________________

client

Name two collection data types

Stack, Queue

What are the add and delete operations of a stack?

Push()

pop()

What are the add and delete operations of a queue?

enqueue()

dequeue()

What is the 4 letter acronym for the way in which items are removed from a stack?

LIFO (last in, first out)

What is the 4 letter acronym for the way in which items are removed from a queue?

FIFO (first in, first out)

Name two data structures used to implement a stack

Linked lists, Resizing Arrays

Name two types of algorithm analysis

run-time, memory

Run time analysis of algorithms maybe carried out with mathematical models or _____________________________.

Empirical analysis observations

Run time is modeled with the power law,

T(N) = aN^b.

What is the log of this equation?

log(T(N)) = log(a) + b log(N)

Do all basic operations (add, divide, sine, etc) run in the same amount of time?

No. They all have different compute times.

How many operations as a function of N are executed in the following code?
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++)
a = j;

(N(N-1)) / 2

How many operations as a function of N are executed in the following code?

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

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

a = j;

N^2

Analysis shows that a particular algorithm has run time 2N^3 + 3N + 20. What is the tilde notation for the run time?

2N^3 (takes the leading term only)

What is order of growth for the algorithm with run time 2N^3 + 3N + 20?

O(N^3)

Most algorithms have an order of growth that falls into one of the following functions: N^3, N, 2^N, 1, logN, NlogN, N^2

1 < log N < N < N log N < N^2 < N^3 < 2^N

What is the dynamic connectivity problem? (input and two operations)

- The input is a sequence of pairs of integers.

- The operations are connected (find) and union.

How many connected components are in graph?

0 ‐‐‐ 1

2 ‐‐‐‐ 3 ‐‐‐‐ 5

6‐‐‐‐‐ 7‐‐‐‐‐8‐‐‐‐‐9

3

The implementations of Union Find discussed in class were implemented with three functions:

Find, union, connected

The basic Quick‐union algorithm (slide 20) uses trees for each connected component. The trees may be constructed by examining the id array, where id[i] is the parent of i. Sketch the connected component trees defined by the following id array

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

id = 0 1 9 4 9 6 6 7 8 9

0, 1, 7, 9, 6-5, 9-2+4-3

Why is Weighted Quick Union superior to Quick‐union?

Weighted quick union attaches the smaller tree to the root of the larger tree, reducing the tree height and the time complexity of operations.

T/f for Selection Sort: Algorithm finds the index of the minimum remaining entry "min" and swaps a[i] and a[min].

True

T/f For Insertion Sort: Entries to the left of a[i] are fixed and in ascending order. No entry to the right of a[i] is smaller than an entry to the left of a[i].

False

Insertion sort is an Nlog(N) algorithm.

False. O(N^2)

Binary Insertionsort sorts 0s and 1s only.

False. It can sort any comparable elements.

A sorting algorithm has been applied to an input array. Currently the array is A B C D A B C with pointer [i] positioned at the first D. Is it possible that Selection Sort is the sorting algorithm being applied?

No. In selection sort, the first unsorted element is always swapped with the minimum element found in the unsorted portion of the array

A sorting algorithm has been applied to an input array. Currently the array is A B C D A B C with pointer [i] positioned at the first D. Is it possible that Insertion Sort is the sorting algorithm being applied?

Yes. In insertion sort, elements to the left of the current element are sorted.

Apply one h‐iteration of shell sort

H A P P Y D A Y S

with h=4.

H A A P S D P Y Y

What are the three basic steps of Mergesort?

1. Divide the array into two halves

2. recursively sort each half

3. merge the two sorted halves into a single sorted array

Given the left subarray A B D C and right subarray E F G H, which need to be merged to produce the final sorted array. Is it possible that these subarrays are the product of Mergesort?

No, A B D C is not sorted.

How many compares does Mergesort use for an array of length n?

NlogN compares in the worst case, where N is the length of the array.

Does Mergesort use a significant amount of auxiliary memory?

Yes. requires O(N) aux memory

What is the in‐place property of sorting algorithms? Give an example of one that has this property and one that does not.

Insertion sort. Merge sort (does not)

What is a stable sort?

Preserves the relative order with equal keys

Which sorting algorithm was honored as one of the top 10 algorithms of the 20th century?

Quicksort

What are the 3 basic steps of Quicksort?

1. Shuffle

2. Partition the array into two subarrays: elements less than the pivot and elements greater than the pivot

3. recursively sort subarray

Does Quicksort run in optimal time if the items in the array are already sorted?

No. it can degrade to O(N^2) time complexity

Is quicksort a divide and conquer method?

Yes. Quicksort divides the array into subarrays based on a pivot, conquers by recursively sorting the subarrays, and combines the subarrays

The basic operations of collections are insertion and deletion of items. What are these operations called for priority queues?

insert and delMax

What is a binary tree?

A structure with nodes, each having up to two children

what is a complete binary tree?

A binary tree where all levels are filled and perfectly balanced, except for the bottom level (filled left to right)

What is a heap-ordered binary tree?

A complete binary tree where each parent's key is greater than or equal to its children

what is a binary heap?

An array representation of a heap-ordered complete binary tree

In a binary heap, are the children ordered smallest to largest from left to right?

No. Only the heap-order property matters; siblings can be in any order.

When a node is added to a binary heap, it __________ to its correct position. When a node is deleted from the heap, the new root node __________ to its correct position.

Swims up, sinks down

heapsort uses the binary heap to build a sorted array. Fill in the two steps

Builds up a max-heap, Repeatedly removes the maximum and places it at the end.