General Definitions

Question 1

Binary Search

Answer 1

Searching an array by recursively chopping it in half

Question 2

Insertion Sort

Answer 2

Inserting element x into the sorted portion of the array 0..x

Question 3

Selection Sort

Answer 3

Building the sorted portion of the array (0..x) by selecting the smallest element in the unsorted portion (x..L) and placing it at x.

Question 4

Merge Sort

Answer 4

Recursively dividing the array in half, then (effectively) performing selection sort when “working back up”/rebuilding the array

Question 5

Quick Sort

Answer 5

Choose an element as pivot (p), move elements less than p to left, elements greater than p to right. Do this recursively.

Question 6

Radix Sort

Answer 6

Element length must be equal!
Place each element in the array into queue buckets, then pull from buckets to rebuild array. Do this for each character in the element’s “key”/value

Question 7

Abstract Data Type

Answer 7

Semantic behavior of a data structure

Question 8

Data Structures

Answer 8

A specific implementation of an ADT

Question 9

Pre-condition

Answer 9

A statement that must be true before method execution

Caller’s responsibility

Question 10

Post-condition

Answer 10

A statement that must be true after the method execution

Implementer’s responsibility

Question 11

Loop invariant

Answer 11

A statement that must always remain true, including during execution

Question 12

Constant time operation

Answer 12

An operation that does not depend on the input size

e.g. reading/writing memory, math, returns

Question 13

asymptotic runtime complexity

Answer 13

Number of constant time operations an algorithm performs relative to the input size.

Question 14

Big O classes

Answer 14

The asymptotic runtime complexity of an algorithm with lower-order terms dropped
e.g. N!, K^N, N^K, N log(N), N, log(N), 1

Question 15

Recursion

Answer 15

A method that calls itself during execution

Question 16

Recursion: Well-defined

Answer 16

A recursive method that contains valid base cases such that it will (eventually) terminate

Question 17

Recursion: Phases

Answer 17

Divide, Conquer, Combine

definitions for each phase straightforward

Question 18

Merge Sort: Where does the “actual sorting” happen?

Answer 18

Combine

Question 19

Quick Sort: Where does the “actual sorting” happen?

Answer 19

Divide

Question 20

Sorting algorithms: Stable

Answer 20

Maintains the original order of elements with the same key while sorting

Question 21

Sorting algorithms: In-place

Answer 21

Requires less than O(N) storage space, excluding the input

Question 22

Comparison Sort

Answer 22

A sorting algorithm that sorts by using comparisons

everything except Radix

Question 23

Tree

Answer 23

ADT where keys are stored as nodes with a parent (and potentially children)

Question 24

Heap

Answer 24

A complete binary tree where each element is greater than or equal to its parent

Question 25

Trie

Answer 25

A tree where keys are stored by tracing the edges between nodes

Question 26

Priority Queue

Answer 26

ADT where elements are pulled based on some pre-defined priority.

Question 27

Trie methods

Answer 27

Contains: Returns boolean if the path to target exists
Insert: Creates nodes along the target path if they don’t already exist
Delete: Lazily deletes a key by setting terminates to false (does not actually remove from memory!)

Question 28

Heap methods

Answer 28

Peek: Returns root without removing it
Poll: Returns and removes the overall root, then moves last element to root, then swap down until invariant is true
Add: Place element on end, then swap upwards until invariant is true

Question 29

Map

Answer 29

ADT for unique keys being associated with a value

Question 30

Generics

Answer 30

A thing in Java that lets you use any non-primitive type in its place

Question 31

Comparable

Answer 31

Java interface that defines how a data type can compare to itself using compareTo() (and thus Object.equals())