Algorithms & Data Structures

Front 1

Solves an instance of a problem by first solving one or more smaller instances

Back 1

Recursive Algorithm

Front 2

A way of organizing information in memory

Back 2

Data Structure

Front 3

The mathematical entity a queue is based on

Back 3

Sequence

Front 4

The mathematical entity the dictionary ADT is based on

Back 4

set

Front 5

A set of vertices and a set of edges

Back 5

Graph

Front 6

This ADT manages data by position

Back 6

list

Front 7

The number of edges in a tree with N nodes

Back 7

N-1

Front 8

Length of path ABCD in an unweighted graph

Back 8

3

Front 9

A directed graph with no directed edges

Back 9

DAG

Front 10

Worst-case run time for insert in a hash table using linear probing

Back 10

O(n)

Front 11

Average-case run time for contains/find in a binary search tree

Back 11

O(log n)

Front 12

Worst-case run time for insert in a binary search tree

Back 12

O(n)

Front 13

Worst-case run time for clone or makeEmpty (both are traversals) in a binary search tree

Back 13

O(n)

Front 14

This STL container class supports random access with an index, and can grow/shrink at either end

Back 14

deque

Front 15

This STL container class lets you efficiently insert, find, and remove items based on their value, not position, and requires them to be comparable using operator<

Back 15

set

Front 16

An algorithm for finding minimu spanning trees is named after him

Back 16

Kruskal

Front 17

An algorithm for finding optimal prefix codes is named after him

Back 17

Huffman

Front 18

This graph representation allows the presence or absence of an edge to be checked in constant time

Back 18

Adjacency Matrix

Front 19

This graph representation is space-efficient for sparse graphs

Back 19

Adjacency Lists

Front 20

A node with no children in a tree

Back 20

Leaf

Front 21

The number of items in a hash table divided by the table size

Back 21

load factor

Front 22

A function that converts a key value into an array index

Back 22

hash

Front 23

Worst-case run time for find in an AVL tree

Back 23

O(log n)

Front 24

Average-case run time for insert in a hash table

Back 24

O(1)

Front 25

Worst-case run time for insert in a hash table

Back 25

O(n)

Front 26

Worst-case run time for find in an STL set

Back 26

O(log n)

Front 27

Worst-case run time for insert in a binary search tree

Back 27

O(n)

Front 28

This STL container class always stores key-value pairs ordered by key

Back 28

map

Front 29

This STL container class can store any type for which an ordering (e.g., operator<) is defined and traverse the container in sorted order using an iterator

Back 29

set

Front 30

This STL container class can use a string like an array index (with [ ]) for retrieving a value

Back 30

map

Front 31

The minimum number of items a leaf node of a B-Tree of order 7 can store

Back 31

4

Front 32

λ should be approximately equal to this for separate chaining

Back 32

1

Front 33

λ should definately be less than or equal to this with quadratic probing

Back 33

.5

Front 34

This phenomenon makes linear probing take longer than random probing as λ increases

Back 34

primary clustering

Front 35

This collision resolution strategy uses a second hash function to probe at intervals that depend on the value being inserted

Back 35

double hashing

Front 36

(T/F) For a B-Tree stored on a disk, the maximum number of items stored in a leaf node should be chosen to be as small as possible

Back 36

False

Front 37

(T/F) The subtrees of a B-Tree can differ in height, but by no more than 1

Back 37

False

Front 38

(T/F) The subtrees of an AVL Tree can differ in height, but by no more than 1

Back 38

True

Front 39

(T/F) With collision resolution strategy f(i) = i², insertions can fail if λ = 0.51

Back 39

True

Front 40

(T/F) With collision resolution strategy f(i) = i, insertions can fail if λ = 0.95

Back 40

False

Front 41

If an algorithm can reduce the size of a problem by a constant factor (e.g. divide it by 2) in constant time, the growth rate of the algorithm is __________

Back 41

θ(log n)

Front 42

If the running time of an algorithm increases by a factor of 8 whenever the size of the input increases by a factor of 2, the growth rate of the algorithm is ___________

Back 42

O(n³)

Front 43

If an array is nearly sorted, the best sorting algorithm to use is _____________

Back 43

Insertion Sort

Front 44

The fastest sort using C++ on a large, randomly-ordered array (taking into account both growth rate and constant factors) is ______________

Back 44

Quicksort

Front 45

What is the average-case growth rate for Shellsort using Hibbard's increments?

Back 45

θ(n⁵/⁴)

Front 46

If you wanted a non-recursive sort with

O(n log n) worst-case running time, which one would you use?

Back 46

Heapsort

Front 47

(T/F) The insert operation takes O(log n) worst-case but only constant time on average in a heap.

Back 47

True

Front 48

The main advantage of more sophisticated (than a heap) priority queue implementations like binomial queues and fibonnacci heaps is that they support the ____________ operation efficiently (less than linear time).

Back 48

meld

Front 49

A tight, worst-case Big-Oh time bound for the buildHeap operation is ____________

Back 49

θ(n)

Front 50

What is the worst-case running time of Quicksort? Is there a simple ordering of the data that could cause this worst case, using the book's implementation of Quicksort?

Back 50

θ(n²), No

Front 51

Write the line of code you'd need at the top of your source code file to use STL template functions e.g., sort

Back 51

#include <algorithm>

Front 52

A function object (a.k.a functor) is an instance of a struct or class that must define which member function?

Back 52

operator()

Front 53

Which STL class lets you store key-value pairs using primitive types or strings as keys in a hash table without needing to define a structured type or your own hash function.

Back 53

unordered_map

Front 54

If T(n) is Big-Oh of n² but not Big-Theta of n², what can we conclude?

Back 54

T(n) = o(n²)

Front 55

Give the formal definition of Big-Oh, i.e., what does T(n) = O(f(n)) mean precisely?

Back 55

T(n) = O(f(n)) if there exists a constant c & another n₀ that when used with T(n) allows f(n) to be an upper bound for all n ≥ n₀.

i.e. T(n) ≤ c ∗ f(n)