Intro To Algorithms - Test 2

Front 1

Sorting based on binary comparisons of the
objects to be sorted admits this as a lower
bound to the worst-case complexity of the
solution.
a. O(nlg n)
b. Ω(n lg n)
c. Ω(n)
d. All of these are appropriate answers
e. None of these is an appropriate answer

Back 1

b. Ω(n lg n)

Front 2

Sorting algorithms that sort objects “in place”
require this much storage allocation.
a. O(nlg n)
b. O(n²)
c. O(n)
d. O(1)
e. None of these is an appropriate answer

Back 2

d. O(1)

Front 3

All of these sorting algorithms sort objects “in
place” except:
a. INSERTION-SORT
b. MERGE-SORT
c. HEAP-SORT
d. BUBBLE-SORT
e. ATROCIOUS-SORT

Back 3

b. MERGE-SORT

Front 4

All of these sorting algorithms sort objects in
optimal worst-case time except:
a. MERGE-SORT
b. HEAP-SORT
c. INSERTION-SORT
d. All of these are optimal algorithms
e. None of these is an optimal algorithm

Back 4

c. INSERTION-SORT

Front 5

In a max-heap, the largest element is stored
at _____.
a. a leaf
b. an internal node
c. the root
d. the “right-most” node
e. the “left-most” node

Back 5

c. the root

Front 6

In a min-heap, the largest element is stored
at _____.
a. a leaf
b. an internal node
c. the root
d. the “right-most” node
e. the “left-most” node

Back 6

a. a leaf

Front 7

Building a max-heap from an unordered
array can be done in ____ time.
a. O(n lg n)
b. O(n²)
c. O(n)
d. O(1)
e. None of these is an appropriate answer

Back 7

c. O(n)

Front 8

Building a min-heap from an unordered
array can be done in ____ time.
a. O(n lg n)
b. O(n²)
c. O(n)
d. O(1)
e. None of these is an appropriate answer

Back 8

c. O(n)

Front 9

________ is based on a technique similar to
the way many people sort a hand of playing
cards.
a. MERGE-SORT
b. INSERTION-SORT
c. ATROCIOUS-SORT
d. BUBBLE-SORT
e. HEAP-SORT

Back 9

b. INSERTION-SORT

Front 10

Heaps are useful in their own right — they
can be used to implement this data structure:
a. dictionary
b. priority queue
c. ordered list
d. stack
e. set

Back 10

b. priority queue

Front 11

ATROCIOUS-SORT from the homework has this
as its best-case running time:
a. Θ(n lg n)
b. Θ(n²)
c. Θ(n)
d. Θ(1)
e. All of these are appropriate answers

Back 11

c. Θ(n)

Front 12

Linear time sorting is possible because ____.
a. objects can be sorted without binary
comparisons
b. the linear time lower bound to sorting is
not valid
c. one can always “tweak” the system clock
d. All of these are valid answers
e. None of these is a valid answer

Back 12

a. objects can be sorted without binary
comparisons

Front 13

A ______ is a full binary tree that represents
the comparisons between elements that are
performed by a particular sorting algorithm.
a. heap
b. binary search tree
c. decision tree
d. 2-3 tree
e. B-tree

Back 13

c. decision tree

Front 14

COUNTING-SORT determines, for each input
element x, the number of elements less than
x. This information is then used to place x
directly into its position in the output.
Therefore, COUNTING-SORT is an “in place”
sorting algorithm. Assess the validity of this
conclusion.
a. It is a valid conclusion.
b. It is not a valid conclusion.

Back 14

b. It is not a valid conclusion.

Front 15

COUNTING-SORT depends on this key
assumption about the numbers to be sorted:
a. They are in reverse order
b. They are in correct order
c. They are all distinct
d. They are all integers in {0, 1, … , k}
e. All of these are appropriate answers

Back 15

d. They are all integers in {0, 1, … , k}

Front 16

RADIX-SORT is the algorithm that was once
used by _______ machines.
a. typewriting
b. voting
c. flying
d. perpetual-motion
e. card-sorting

Back 16

e. card-sorting

Front 17

RADIX-SORT requires that the intermediate
sorting algorithm (the one that sorts on the
basis of the digits) be _______, which means
that “numbers with the same value appear in
the output array in the same order as they
do in the input array.”
a. efficient
b. stable
c. optimal
d. linear
e. transparent

Back 17

b. stable

Front 18

BUCKET-SORT assumes that the input is
generated by a random process that
distributes element uniformly over this range:
a. {0,1, … , k}, i.e., natural numbers up to k
b. {1,2, … , k}, i.e., positive integers up to k
c. [0,1], i.e., the closed unit segment
d. [0,1), i.e., the closed unit segment except 1
e. (0,1], i.e., the closed unit segment except 0

Back 18

d. [0,1), i.e., the closed unit segment except 1

Front 19

BUCKET-SORT has an expected time
complexity of Q(n). In theory, it can have a
worst-case time complexity of _______,
although this is highly improbable.
a. O(n²)
b. O(2ⁿ)
c. O(n!)
d. All of these are appropriate answers
e. None of these is an appropriate answer

Back 19

a. O(n²)

Front 20

A hash table is effective for implementing a
dictionary, a data structure that supports
this/these functionality/functionalities:
a. INSERT
b. SEARCH
c. DELETE
d. All of these answers are appropriate
e. None of these answers is appropriate

Back 20

d. All of these answers are appropriate

Front 21

In an ordinary array, we store the element
whose key is k in position k of the array. By
contrast, in a hash table, we use a(n) ______
to generate from the key k a value h(k) to
index into the hash table.
a. random number generator
b. Turing machine
c. automaton
d. oracle
e. hash function

Back 21

e. hash function

Front 22

The expected time to search for an element
in a hash table is O(1) under reasonable
assumptions. However, the worst-case search
time is _________.
a. Θ(n)
b. Θ(n²)
c. Θ(2ⁿ)
d. Θ(lg n)
e. Θ(n lg n)

Back 22

a. Θ(n)

Front 23

The analysis of hash table operations is
performed in terms of the ratio of n, the
number of elements in the table, and m, the
number of slots in the table. This ratio is
called the _______.
a. golden mean
b. load factor
c. key factor
d. All of these are appropriate answers
e. None of these is an appropriate answer

Back 23

b. load factor

Front 24

Hash functions assume that the keys are
natural numbers. This assumption is not too
severe because:
a. all keys are numerical anyway (no reinterpretation
necessary)
b. all keys are stored in binary anyway
(readily interpreted as binary numbers)
c. all keys are physical entities that have
numeric dimensions (readily convertible
to natural numbers)
d. All of these are appropriate answers
e. None of these is an appropriate answer

Back 24

b. all keys are stored in binary anyway
(readily interpreted as binary numbers)

Front 25

Hash functions that use the division method,
e.g., h(k) = k mod m, are fast but have the
disadvantage of having to avoid certain
values of m. Assess the validity of this
statement:
a. It is a valid statement
b. It is not a valid statement

Back 25

a. It is a valid statement

Front 26

Hash functions that use the multiplication
method, e.g., h(k) =
m (k A mod 1), may be
slower but have the advantage of not having
to avoid certain values of m. Assess the
validity of this statement.
a. This is a true statement.
b. This is a false statement.

Back 26

a. This is a true statement.

Front 27

In open addressing, the action of examining
a slot in the hash table is known as a(n)
_____.
a. collision
b. probe
c. successful landing
d. examination
e. rehash

Back 27

b. probe

Front 28

The technique known as linear probing
suffers from the increasing probability of
primary clustering. This is when long runs of
_____ hash table slots build up.
a. empty
b. occupied
c. vacated
d. oversized
e. garbage-collected

Back 28

b. occupied

Front 29

The analysis of open-address hashing
resulted in the expected number of probes in
an unsuccessful search to be at most ______,
where the load factor a is assumed to be
less than 1.
a. α + 1
b. α – 1
c. α²
d. 1/(1 – α)
e. 2α

Back 29

a. α + 1

Front 30

Hash tables are an excellent manifestation
of this seeming “law” in algorithm design that
described opposite tendencies insofar as two
important resources are concerned.
a. Bentley's Rule: “The first 90% of the code
takes 90% of the time. The remaining 10%
takes the other 90% of the time.”
b. Wirth's Law: “Software gets slower
faster than hardware gets faster.”
c. Knuth's Optimization Principle: “We
should forget about small efficiencies,
say about 97% of the time: premature
optimization is the root of all evil.”
d. Pareto Principle: “For many events,
roughly 80% of the effects come from
20% of the causes.”
e. Time-Space Tradeoff: “What you gain in
time, you lose in space tradeoff, and
vice-versa.”

Back 30

e. Time-Space Tradeoff: “What you gain in
time, you lose in space tradeoff, and
vice-versa.”

Front 31

What is an abstract data type that stores elements, each of which is assigned a specific order of importance

Back 31

priority queue

Front 32

Which data structure supports priority queue in Θ (lg n) time and supports insert and delete max?

Back 32

heap

Front 33

In a heap data structure, how do you determine the height of a node?

Back 33

the number of nodes along the longest simple path from that node to a leaf

Front 34

How do you determine the height of a heap?

Back 34

it is the height of the root (the number of nodes along the simplest path from the root to a leaf)

Front 35

In a heap, given the node is at A[i], where is the left child stored in the array?

Back 35

A[2i]

Front 36

In a heap, given the node is at A[i], where is the right child stored in the array?

Back 36

A2[i+1]

Front 37

In a heap, given the node A[i], where is the parent of the parent stored in the array?

Back 37

A[i/2]

Front 38

In a heap, where is the root stored in the array?

Back 38

A[1]

Front 39

What is the time complexity for heap sort?

Back 39

Θ (n lg n)

Front 40

What is the immediate lower bounds of a sort based on?

Back 40

the need to examine all items Ω (n)

Front 41

What is a way to model sorting algorithms based on binary comparisons?

Back 41

decision tree

Front 42

How many leaves are in a decision tree?

Back 42

as many different possible outcomes based on the number of elements to be sorted, n!

Front 43

In a decision tree, how can you determine the worst-case complexity of the algorithm?

Back 43

the longest path from root to some leaf

Front 44

In a decision tree, how can you determine the best-case complexity of the algorithm?

Back 44

the shortest path from root to some leaf

Front 45

Any binary tree of height, h, has a maximum number of how many leaves?

Back 45

2^h

Front 46

Any decision tree for sorting n elements has what height?

Back 46

Ω (n lg n)

Front 47

All binary comparisons have a lower bounds of __________. Give 2 examples of binary comparison sort

Back 47

Ω (n lg n). heap-sort, merge-sort

Front 48

Which sorting algorithms can beat binary comparisons?

Back 48

counting sort, radix sort, bucket sort

Front 49

Why are counting sort, radix sort, and bucket sort faster than binary comparisons?

Back 49

because they sort linearly -- O(n)

Front 50

What is counting sort dependent on?

Back 50

values to be sorted are integers {0, 1, 2, ..., k}

Front 51

What is the maximum value of k when using counting sort?

Back 51

2^32

Front 52

What was the original purpose of radix sort?

Back 52

to sort cards that were punched for the 1890 census

Front 53

What is the process of radix sort?

Back 53

sort each digit, beginning with least significant digit (ones place), then sort to the left

Front 54

What is the basic time complexity of radix sort?

Back 54

O(n+k)

Front 55

Given the maximum number of digits, d, what is the time complexity of radix sort?

Back 55

O(dn + dk), where n is the number of elements and k is the range of digits. This becomes O(n) because d is constant and k = O(n)

Front 56

Why is radix sort not appropriate for more than numbers?

Back 56

because it's based on counting sort

Front 57

What do we assume when using bucket sort?

Back 57

that all values are distributed evenly in the interval [0, 1)

Front 58

What is the best case time complexity for bucket sort?

Back 58

O (n)

Front 59

What is an effective way to implement a dictionary?

Back 59

hash table

Front 60

What is an ordinary array?

Back 60

elements whose key, k, is stored in position k of the array

Front 61

What is direct addressing?

Back 61

Given a key, k, the element whose key k is found in the kth position of the array

Front 62

What data structure is a generalization of ordinary arrays?

Back 62

hash tables

Front 63

Which mathematical methods can be used to compute a hash function?

Back 63

multiplication method and division method

Front 64

What is meant by a "collision" in a hash function?

Back 64

when two unique keys hash to the same table entry

Front 65

What are two forms of hash tables can prevent collisions?

Back 65

chaining and open addressing

Front 66

What is a stipulation when using a hash table?

Back 66

all keys are unique (no elements have the same key)

Front 67

What is the average search time of a hash table?

Back 67

O(1)

Front 68

What is the worst search time of a hash table?

Back 68

O(n) -- linear, all items much be searched

Front 69

What is the worst-case search time of hash table with chaining?

Back 69

O(n)

Front 70

What is the best time search of hash table with chaining?

Back 70

O(1)

Front 71

What is the worst time deletion of hash table with chaining?

Back 71

O(1) if doubly linked, O(n) if singly linked

Front 72

What is a disadvantage to using hash tables?

Back 72

high cost -- must keep more slots in table than number of keys

Front 73

What is load factor?

Back 73

the percentage of elements as compared to possible slots in a hash table (# elements/# slots)

Front 74

Under what conditions would the search be worst case when using a hash table with chaining?

Back 74

Θ(n)

Front 75

What is the tight bounds for hashing with chaining?

Back 75

Θ(1+α), where α is the number of unsuccessful examinations

Front 76

What are the advantages to using the division method for hash tables?

Back 76

fast since it requires only one division operation

Front 77

What is the disadvantage to using the division method for hash tables?

Back 77

have to avoid certain powers of m (best to use primes): h(k) = k mod m

Front 78

What is the formula for the division method for hash tables?

Back 78

h(k) = k mod m

Front 79

What is the formula for the multiplication method for hash tables?

Back 79

h(k) = m (k x A mod 1), where A is a constant (0..1)

Front 80

What is the advantage of the multiplication method for hash tables?

Back 80

value of m is not critical

Front 81

What is the disadvantage of the multiplication method for hash tables?

Back 81

slower than division method

Front 82

How does open addressing differ from chaining?

Back 82

open addressing stores keys directly in table ( slot h(k) contains key k), and chaining must use a hash function to compute the slot

Front 83

What is a disadvantage to open addressing?

Back 83

when adding, deleting, or searching, must probe locations based on k until NIL is found. When deleting, you can't just change value to NIL because that value could be part of a probe (must assign value of "deleted")

Front 84

How can uniform hashing be created in open addressing?

Back 84

by guaranteeing the probe sequence is some permutation of the m slots

Front 85

What are three examples of ways to implement uniform hashing?

Back 85

linear probing, quadratic probing, and double hashing

Front 86

What is the worst case complete search of a binary tree?

Back 86

Θ(lg n)

Front 87

What is the worst case search of a linear chain within a binary tree?

Back 87

Θ(n)

Front 88

What is the time complexity of going up or down a path of a binary tree?

Back 88

O(h)

Front 89

REVIEW Ch. 12 SLIDES!!!

Back 89

REVIEW Ch. 12 SLIDES!!!