Data structures and algorithms

Question 1

Characteristics of an Abstract Data Type (ADT)

Answer 1

Specifies an interface, not an implementation. While it must respond to method calls, implementation is not important.

Question 2

Bag ADT

Answer 2

• add
• remove
• contains
• numItems
• grab
• toArray

Question 3

Formula for comparisons in selection sort

Answer 3

O(n^2)

This will be the efficiency regardless of input

Question 4

Formula for moves in selection sort

Answer 4

O(n)

This will be the efficiency regardless of input

Question 5

Radix Sort

Answer 5

-Sort by properties rather than values.
Example: sort by the individual digits in a three-digit number instead of the value of the number.

• properties move from right to left (i.e. one’s place first)
• original array is processed from left to right

Question 6

Bubble Sort Performance

Answer 6

O(n^2)

note: even worse performance than other O(n^2) algorithms.
- not adaptive (won’t be any faster, even on fully sorted input)
- high number of moves and comparisons (other O(n^2) algorithms only have a high number of moves or comparisions

Question 7

Algorithm performance classes

Answer 7

O(1) constant time
O(log n) logarithmic time
O(n) linear time
O(n log n) n log n time
O(n^2) quadratic time
O(c^n) exponential time (c is comparisons)

Question 8

Selection Sort Performance

Answer 8

O(n^2)

Question 9

Selection sort moves

Answer 9

O(n) moves

Question 10

Selection sort comparisons

Answer 10

O(n^2) comparisons

Question 11

Basic steps for recursive backtracking

Answer 11

1. Define base case at top. Return true happens here
2. Try first iteration
3. If first iteration works, go to the next one (or return true). If first iteration fails, go back (return false/undo method happens here).
4. Repeat this until the base case is reached
5. If you’re not able to reach the base case, return false

Question 12

Starting index for selection sort

Starting index for insertion sort

Answer 12

starting index for selection: 0

starting index for insertion: 1 (compares items immediately to the left, so can’t start at 0)

Question 13

Radix sort performance

Answer 13

O(n*m)

better than n log n IF m < log n

m is number of properties to look at.
example: in 999 m would equal 3, because there are three digits to look at

Question 14

Notes on quicksort

Answer 14

worse case O(n^2) (both comparisons and moves)
best and average case O(n log n) (both comparisons and moves)

note: performance very dependent on picking a good pivot around the median of the range

Question 15

notes on mergesort

Answer 15

performance of n log n in every case

note: requires n additional space

Question 16

notes on insertion sort

Answer 16

starts at index of 1

Question 17

notes on shell sort

Answer 17

performance is generally about O(n^1.5), although it’s hard to precisely measure

performance highly dependent on a good gap sequence (increment values)

Question 18

Preorder traversal of a tree

Answer 18

visit root
recursively visit left side
recursively visit right side

Question 19

Postorder traversal

Answer 19

recursively visit left side
recursively visit right side
visit root

Question 20

Inorder traversal

Answer 20

recursively visit left side
visit root
recursively visit right side

Question 21

level-order traversal

Answer 21

visit from top to bottom, left to right

visits one level at a time