General Definitions Flashcards

1
Q

Binary Search

A

Searching an array by recursively chopping it in half

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Insertion Sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Selection Sort

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Merge Sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Quick Sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Radix Sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Abstract Data Type

A

Semantic behavior of a data structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Data Structures

A

A specific implementation of an ADT

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Pre-condition

A

A statement that must be true before method execution

Caller’s responsibility

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Post-condition

A

A statement that must be true after the method execution

Implementer’s responsibility

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Loop invariant

A

A statement that must always remain true, including during execution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Constant time operation

A

An operation that does not depend on the input size

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

asymptotic runtime complexity

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Big O classes

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Recursion

A

A method that calls itself during execution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Recursion: Well-defined

A

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

17
Q

Recursion: Phases

A

Divide, Conquer, Combine

definitions for each phase straightforward

18
Q

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

A

Combine

19
Q

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

A

Divide

20
Q

Sorting algorithms: Stable

A

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

21
Q

Sorting algorithms: In-place

A

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

22
Q

Comparison Sort

A

A sorting algorithm that sorts by using comparisons

everything except Radix

23
Q

Tree

A

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

24
Q

Heap

A

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

25
Q

Trie

A

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

26
Q

Priority Queue

A

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

27
Q

Trie methods

A

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!)

28
Q

Heap methods

A

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

29
Q

Map

A

ADT for unique keys being associated with a value

30
Q

Generics

A

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

31
Q

Comparable

A

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