223 test 2

Question 1

declare a normal vector vs ptr

Answer 1

int* xptr = &x ; // & is the “ address of” operator

Question 2

Dynamically allocating memory at runtime

Answer 2

int* yptr = new int; // allocate new memory on the fly

• yptr = 96;

Question 3

memory leaks

Answer 3

you have memory that nothing can access

Question 4

rule of three

Answer 4

A class that defines a destructor, assignment operator, or a copy constructor
should define all three

Question 5

Dereferencing

Answer 5

a pointer accesses value at the pointer’s stored address

* xptr = 57; // * here is the “ dereference “ operator

Question 6

binary search

Answer 6

Iteratively search for a value v in a non-empty sorted list

1. Pick the middle item in a list
2. If middle item > v, then search in left half of list
3. If middle item < v, then search in right half of list
4. If middle item == v, then found match

Question 7

What is the worst case for binary search?

Answer 7

Keep searching (halving list) until one element left)

Question 8

Assume T(n) = 27, which is O(1)

Answer 8

• In this case, pick n0 to be 0 (any value will work in this case)
• Pick k to be 27, giving:
0 ≤ 27 ≤ 27 · 1 for k = 27 and all n ≥ 0

Question 9

Assume T(n) = 3n + 2, which is O(n)

Answer 9

There are lots, but lets pick k = 5 and n0 = 1, giving:
• 3n + 2 ≤ 5n for all n ≥ 1
• e.g., 3 · 1 + 2 ≤ 5, 3 · 2 + 2 ≤ 10, 3 · 3 + 2 ≤ 15, etc.

Question 10

Assume T(n) = n^2 − 5n + 10,

Answer 10

What values of n0 and k do we pick to solve this?
• There are lots, but lets pick n0 = 2 and k = 4, giving:
• n
2 − 5n + 10 ≤ 4n
2
for all n ≥ 1
• Note: T(2) = 4 − 10 + 10 = 4 ≤ 4 · 2

Question 11

Selection Sort

Answer 11

The basic idea
• Select (i.e., “find”) the largest item
• Swap it with the last item in the list
• Repeat with items 0 to n − 2
• Stop when only one item left

Question 12

selection sort best and worst case

Answer 12

best: n^2
worst: n^2

Question 13

bubble sort

Answer 13

The basic idea
ˆ Compare adjacent items
ˆ Swap if out of order
ˆ Repeat with items 0 to n − 2
ˆ Stop when only one item left

Question 14

bubble best and worst

Answer 14

best O(n)
worst O(n^2)

Question 15

(Linear) Insertion Sort

Answer 15

(Linear) Insertion Sort
The basic idea (note: beginning of list is sorted, rest is unsorted)
• Select first item (in unsorted region)
• Insert item into correct position in sorted region (shifting larger items over)
• Stop when unsorted region is empty

Question 16

best and worst insertion sort

Answer 16

Best case: List already sorted (no shifts, just n-1 passes)
• Worst case: List in reverse order (shift max number of times each pass)

best O(n)
worst O(n^2)

Question 17

merge sort

Answer 17

The basic idea (note: recursive “divide and conquer” approach)
• divide list into two halves
• sort each half (recursive step)
• merge the sorted halves into sorted list

Question 18

merge sort best and worst case

Answer 18

best O(n log n) 
worst O(n log n)

Question 19

quick sort

Answer 19

The basic idea (also a recursive “divide and conquer” approach)
• pick a “pivot” element (e.g., first element in list)
• put values smaller than pivot on left
• put values larger than pivot on right
• put pivot value in the middle
• sort the left and right halves (using quick sort)

Question 20

quick sort best and worst

Answer 20

best O(n log n)
worst O(n log n)

Question 21

Mergesort versus Quicksort:

Answer 21

• quicksort has no “merge” step (which requires extra space)
• each level in quicksort divides list by (n − 1)/2 as opposed to n/2 halves
• these make quicksort faster in practice
• also can improve worst case performance by picking a “better” pivot val
– takes a bit of extra time, but worth the trade off in practic

Question 22

“collision

Answer 22

Map two or more keys to the same index

Question 23

“Selecting Digits”

Answer 23

• Select specific digits of the key to use as the hash value
• Lets say keys are 9-digit employee numbers
– h(k) = 4th and 9th digit of k
– For example: h(001364825) = 35
• Here we insert (find) entry with key 001364825 at table[35]
• This is a fast and simple approach, but
• May not evenly distribute data Q: … why not?

Question 24

“Folding”

Answer 24

Add (sum) digits in the key
• Lets say keys are again 9-digit employee numbers
– h(k) = i1 + i2 + · · · + i9 where h(k) = i = i1i2 . . . i9
– For example: h(001364825) = 29
– Store (retrieve) entry with key 001364825 at table[29]
• This is also fast, but also may not evenly distribute data
• In this example, only hits ranges from 0 to 81
• Can pick different (similar) schemes … e.g., i1i2i3 + i4i5i6 + i7i8i9

Question 25

Modular Arithmetic

Answer 25

h(k) = f(k) mod table size

Question 26

a “weighted” hash function

Answer 26

• Use the Java-based approach where weight is: | i0 · 31n−1 + i1 · 31n−2 + · · · + in−2 · 311 + in−1

Question 27

linear probing

Answer 27

Insert: • Linear probe (sequentially) until first empty bucket found (either type) • Insert at first empty bucket • Note: The table could be full! (which means we can’t insert) Removal: • Use similar approach to find key item • Stop at empty-since-start bucket (item not in table) • Mark item as empty-after-removal Search: • Go to hashed index • Start searching sequentially for key • Stop when an empty-since-start bucket is found or searched entire table

Question 28

Quadratic Probing

Answer 28

``` similar to linear probing • but probe “quadratic” sequences • i + 1, i + 22 , i + 32 , i + 42 , and so on • helps “spread out” primary clusters ```

Question 29

“Separate Chaining”

Answer 29

* Each array index has its own linked list of elements (the “chain”) * The list grows and shrinks with collisions and removals

Question 30

load_factor

Answer 30

load_factor = n / table_capacity

Question 31

root

Answer 31

(no parents

Question 32

leaf node

Answer 32

a node without children

Question 33

internal node

Answer 33

node with children

Question 34

path

Answer 34

is a sequence of nodes ninj . . . nk ˆ the next node after n in the sequence is a child of n ˆ a path by starts at the root and traverses children (possibly ending at a leaf) ˆ a tree has many paths (like many linked lists)

Question 35

ancestor

Answer 35

is its parent and its parent's ancestors

Question 36

descendent

Answer 36

its children and its children's descendents

Question 37

siblings

Answer 37

if they have the same parent

Question 38

height

Answer 38

is the length of the longest root-to-leaf path

Question 39

Binary Trees

Answer 39

In a binary tree, each node has at most 2 children

Question 40

“full” binary tree

Answer 40

- all paths from the root to a leaf has the same height h; and - all internal nodes have two children

Question 41

“complete” binary tree

Answer 41

* the tree is full at height h − 1, and | * the leaf nodes are filled in from left to right

Question 42

A balanced binary tree

Answer 42

• all left and right subtrees that differ in height by at most 1

Question 43

Searching based on key in a BST

Answer 43

Is the key of the root node equal to the search key? – if yes, found a match! • Is the search key less than the key of the root node? – if yes, search left subtree of the root • Is the search key greater than the key of the root node? – if yes, search the right subtree of the root

Question 44

Inserting into a BST

Answer 44

Basic Idea: • Find where the node should be (key search) • And then insert into that location • Will always insert into a leaf node!