Level 108
Level 110

#### 68 words 0 ignored

Ready to learn
Ready to review

## Ignore words

Check the boxes below to ignore/unignore words, then click save at the bottom. Ignored words will never appear in any learning session.

**Ignore?**

Greedy algorithms

Choose the highest value first

Why is the naive approach to the rod cutting algorithm bad?

Naive recursive solutions are highly inefficient due to the fact that they solve the same sub problems over and over.

How does the dynamic approach to rod cutting work?

Using memoization, we can solve each subproblem only once, and refer back to the subproblem's solution if needed later.

How is the memoization process more efficient?

The approach trades computation time for memory.

Btree non root

T - 1 to 2t - 1 keys

Btree root

1 to 2t-1 keys

Btree non leaves

One more children than keys

Btree leaves

All at the same level

Internal node property

Has a min (t-1) and a maximum number of keys in the node (2t - 1)

What type of algorithm is Prim's?

greedy algorithm for finding the minimum spanning tree

Prim's complexity

O(E log V)

Differences between Quicksort and Merge sort

Quicksort is a conquer-then-divide algorithm, which does most of the work during the partitioning and the recursive calls. The subsequent reassembly of the sorted partitions involves trivial effort. Merge sort is a divide-then-conquer algorithm.…

Quicksort pseudocode

function quicksort(array)

What is a hash table?

A hash table is a data structure that stores key/value pairs and can be quickly searched by the key

Stack

Data structure for Depth first search

Queue

Data structure for Breadth first search

Quicksort steps

Step 1. Choose a pivot value.

Pseudocode for inserting into a binary search tree

1 Check whether value in current node or new node are equal. If so, duplicate is found. Otherwise:

How do you choose a good hash function?

The function should provide a uniform distribution of hash values. This is because a non-

Euler Path

Euler vs Hamiltonian Paths and Cycles

Greedy Algorithm

an algorithm that follows problem solving heuristic of making optimal choices at each stage. Hopefully finds the global optimum. An example would be Kruskal's algorithm.

Divide and Conquer

works by recursively breaking down a problem into two or more sub problems until the problems become simple enough to be solved directly. An example would be mergesort.

Recursive Algorithms

solve a problem by solving smaller internal instances of a problem -- work towards a base case.

Dynamic Programming

Break down a problem into smaller and smaller subproblems. At their lowest levels, the subproblems are solved and their answers stored in memory. These saved answers are used again with other larger (sub)problems which…

Selection Sort

Non-stable, in place sort. Has an N-squared order of growth, needs only one spot of extra space. Works by searching the entire array for the smallest item, then exchanging it with the first ite…

Insertion Sort

Stable, in place sort with an order of growth which is between N and N-squared, needs only one spot of extra space and is dependent on the order of the items. Works by scanning …

ShellSort

Non-stable, in place sort with an order of growth which is undetermined, though usually given at being N-to-t…

Quick Sort

Non-stable, in place sort with an order of growth of NlogN. Needs lgN of extra space. It has a probabilistic guarantee. Works by making use of a divide and conquer method. The array is div…

3-Way Quick Sort

Non-stable, in place sort with an order of growth between N and NlogN. Needs lgN of extra space. Is probabilistic and dependent on the distribution of input keys.

Mergesort

Stable sort which is not in place. It has an order of growth of NlogN and requires N amount of extra space. Works by dividing an array in half continuously into smaller and smaller arr…

Heap Sort

Non-stable, in place sort which has an order of growth of NlogN. Requires only one spot of extra space. Works like an improved version of selection sort. It divides its input into a sorted…

Lower Bound on the complexity of pairwise comparisons

No compare based sorting algorithm can have fewer than ~NlogN compares

Counting Sort (Key Indexed sort)

An integer sorting algorithm which counts the number of objects that have a distinct key value, and then used arithmetic on those countes to determine the positions of each key value in the output array.

LSD Radix Sort

Stable sort which sorts fixed length strings. Uses an axillary array, and therefore is not in place. Goes through to the last character of a string (its least significant digit), and takes its value.…

MSD Radix Sort

Used to sort an array of strings based on their first character. Is done recursively and can sort strings which are of different lengths. This algorithm will be slower than its counterpart if used…

Unordered Linked List

Data structure with non-efficently supported operations. Is unordered. Has a worst case cost of search and insertion at N, an average case cost of insertion at N, and an average case cost of searching at N/2.

Binary Search

An ordered array of data which has efficiently supported operations. The worst and average case of a search using this structure is lgN. The Worst case of an insertion is N, and the average …

Binary Search Tree

Will have a best case high of lgN. This is also its expected height. In the worst case, it will have a height of N, and thus become similar to a linked list.

2-3 Tree

Balanced tree data structure with logN complexities on searching, inserting, and deleting in both the worst and average cases. In this data structure, every node with children has either two children and one data elem…

Red Black Tree

Worst case height of 2log(n+1). The nodes are either red or black. The root is black. If a node is red, its children MUST BE BLACK. Every path from a node to a leaf …

Tries

A collection of nodes, each of which can hold a key and a value- often the values will be null. The nodes will have a value attached to the last character of the string …

B-Trees

Items are stored in leaves. The root is either a leaf, or it will have between two and M children. All non-leaf nodes will have betwe…

Undirected Graph

Given any path connecting vertices A and B, you can travel from A to B or B to A

Directed Graph

Given a path connecting vertices A and B you can only travel in 1 direction

path

A drive and list of directories pointing to a file such as C:\Windows\command.

Weighted Graph

A graph which places "costs" on the edges for traveling their path

Cycles

When there are at least two unique paths which connect vertices A and B, forming a loop or loops

DAG (Directed Acyclic Graph)

A graph which is directed and contains no cycles

Depth First Search

A method which is used to traverse through a graph. Works by creating a stack of nodes to visit, which consist of all the nodes around your current position. You move to the next loca…

Topological Sort

Linear ordering of the vertices of a directed graph such that for every directed edge "uv" which connects "u" to "v" (u points to v), u comes before v. This ordering is only possibl…

Minimum Weight Spanning Trees (MST)

A spanning tree whose weight is no larger than the weight of any other spanning tree which could be made with the graph. The properties of this thing include that the graph is connected,…

Prim's Algorithm

MST builder/Greedy Algorithm which works by taking a starting vertex and then successively adding the neighbor vertices which have the lowest cost of addition and don't create cycles upon their addition.

Kruskal's Algorithm

MST Builder/Greedy Algorithm which works by taking edges in order of their weight values, continuously adding edges to the tree if their addition doesn't create a cycle.

Union Find

Data structure used to make sure a cycle is not created in a MST.

Dijksta's Algorithm

Finds the shortest path with no negative weights given a source vertex. Tries to find the distance to all other vertices in the graph. It produces a shortest paths tree by initializing the distanc…

Memoization

What happens when a sub problem's solution is found during the process of Dynamic Programming. The solution is stored for future use, so that it may be reused for larger problems which contain this …

Bellman-Ford Algorithm

Algorithm which computes shortest paths from a single vertex to all other vertices in a weighted digraph. Is slower than its counterpart, but is able to handle edge weights with negative values. Works by initi…

Class

A class is the blueprint from which individual objects are created. It is the code template you write.

object

A database item that contains data, as well as the actions that read or process the data.

Method

A sequence of statements that has a name, may have parameter variables, and may return a value

PARAMETER

A value that can be given to a function to get different results from the instructions

signature

Combination of identifiers, return value, name and parameters of a method. Example: public int calculateMonth(String name)

type

Specifies what kind of thing a variable or a parameter is. Example: int, char, boolean...

instance

An object.

multiple instances

The case when there are multiple objects from the same class instantiated at runtime.

State

a value of some condition that occurs during an object's life

return value

The value that comes back from a method after it is run. In the following method: public int calculateMonth(String name), the return value is an integer.

Field

A column in a table.