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;
25 Cards in this Set
- Front
- Back
|
give examples of greedy algorithms
|
prim, kruskal, dijkstra, scheduling, huffman codes, bin packing
|
|
|
give examples of divide and conquer
|
quicksort, mergesort
|
|
|
give examples of greedy algorithms
|
prim, kruskal, dijkstra, scheduling, huffman codes, bin packing
|
|
|
give example of cryptographic algorithms
|
ceaser, cipher
|
|
|
give examples of divide and conquer
|
quicksort, mergesort
|
|
|
give example of dynamic programming
|
knapsack, floyd, matrix multiplication
|
|
|
give example of cryptographic algorithms
|
ceaser, cipher
|
|
|
what is a greedy algorithm
|
they have a sortsighted approach in -that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future.
-may be used for approximate answers when guranteed optimal answers are too expensive |
|
|
give example of dynamic programming
|
knapsack, floyd, matrix multiplication
|
|
|
what is scheduling
|
-used for jobs such as manufacturing or operating systems
-arises for most modern systems to perform multitasking and multiplexing |
|
|
what is a greedy algorithm
|
they have a sortsighted approach in -that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future.
-may be used for approximate answers when guranteed optimal answers are too expensive |
|
|
what is multiprocesors
|
-order jobs by time
-to minimize final completion time, attempt to give an even sun of times to each processor. -may require excessive computation |
|
|
what is scheduling
|
-used for jobs such as manufacturing or operating systems
-arises for most modern systems to perform multitasking and multiplexing |
|
|
what is huffman codes
|
-allows file compression
-codes are based on frequency of use -saves access time and disk space -extra time is required to build the frequency table |
|
|
what is multiprocesors
|
-order jobs by time
-to minimize final completion time, attempt to give an even sun of times to each processor. -may require excessive computation |
|
|
what is bin packing
|
-Online-place each item as it comes, there is no going back
-Offline-read all input first |
|
|
what is huffman codes
|
-allows file compression
-codes are based on frequency of use -saves access time and disk space -extra time is required to build the frequency table |
|
|
Name the online bin packing algorithms
|
-next fit
-first fit -best fit |
|
|
what is bin packing
|
-Online-place each item as it comes, there is no going back
-Offline-read all input first |
|
|
Name the online bin packing algorithms
|
-next fit
-first fit -best fit |
|
|
what is the running time for divide and conquer algorithms
|
2T(N/2) + O(N)
|
|
|
what is the big-Oh of binary search, merge sort, quick sort
|
-O(logN)
-O(NLogN) -O(NLogN) |
|
|
what is the improvement of Strassen's Matrix Multiplication
|
from N^3 to N^2.81
|
|
|
what is dynamic programming
|
-solving complex problems by breaking them down into simpler steps
-may give a less than optimal but speedy results |
|
|
explain some characteristics of Matrix Chain Multiplication
|
-the number of rows on the left must equal the number of rows on the right
-associative but not commutative |
