Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
37 Cards in this Set
- Front
- Back
|
Sort named for its creator
|
Shell
|
|
|
sort good for almost sorted data
|
quick sort
|
|
|
sort with Big Oh of N^2
|
selection sort
|
|
|
Sort often used and often referred to as the fastest
|
quick sort
|
|
|
sort that never swaps
|
radix sort
|
|
|
sort good for very large records bc there is at most one swap per pass
|
selection sort
|
|
|
how do u find the height of a heap
|
2^n = nodes
|
|
|
a type of tree that is never more than one level out of balance
|
AVL
|
|
|
a tree with all its leaves on the same level
|
2-3
|
|
|
a balanced tree of height 3 has between ___ and ____ nodes
|
3 and 7
|
|
|
give an example of a list that would create a binary search tree with access time of N
|
1,2,3,4,5,
|
|
|
The first graph algorithm was described by ________
The problem was about _____ |
-Euler
-Koneisburg (river routing problem) |
|
|
The science of encyption
|
-cryptology
|
|
|
the process of enciphering and deciphering codded messages
|
cryptography
|
|
|
the methodologies used to obtain information from encoded messages when the algorithm and/or keys are unknown
|
cryptanalysis
|
|
|
The oldest known code is
|
Caesar's cipher
|
|
|
which algorithm has a running time of n^2 in worst case but nlogn on average
|
quicksort
|
|
|
what is an algorithm
|
a set of precise and simple instructions that solves a problem. Includes finiteness, definiteness, input, output, and effectiveness.
|
|
|
the first known algorithm was ____ and written by _____
|
-GCD
-Euclid |
|
|
what is the big oh of linear search
|
n
|
|
|
what is the big oh of binary search
|
logn
|
|
|
what is the advantage of huffman code
|
less work for searching
|
|
|
what is an abstract data type
|
a set of objects with a set of operations
|
|
|
what is an example of an abstract data type (ADT)
|
array, stack
|
|
|
what is the access time of a hash table
|
O(1)
|
|
|
The word algorithm comes from
|
mathematician Abu Abdullah Muhammad
|
|
|
what are the three types of algorithms
|
greedy, divide-and-conquer, dynamic programming
|
|
|
what are examples of dynamic programming
|
-floyd
-knapsack -matrix chain multiplication |
|
|
what are examples of greedy algorithms
|
-prim
-kruskall -dijkstra |
|
|
what are examples of divide-and-conquer algorithms
|
-quicksort
-merge sort |
|
|
what is the difference between online and offline bin packing algorithms
|
online - fills bins as it goes through
offline - looks at data first and then fills bins |
|
|
when should i use prim or kruskall
|
-prim for large number of edges because big oh does not depend on edges
-kruskal if there is a small amount of edges |
|
|
which methods will allow merge sort to work in nlogn time
|
doubly linked list and array
|
|
|
name two minimum spanning tree algorithms
|
prim
kruskall |
|
|
Strassen improves the big oh from ____ to ____
|
n^3 to n^2.81
|
|
|
what is the most used sort
|
quick sort
|
|
|
what is the average search time for a binary tree
|
logn
|
