Week 2 Flashcards
1
Q
Basic steps of algorithm?
A
- Simplify problem
- Build mathematically solving plan
- Design an algorithm
- Test correctness of the algorithm
- Implement the algorithm to a programming language
- Documentation
- Analyze complexity of the algorithm
2
Q
Complexity?
A
– Average case • Notationθ(...)read Theta – Best case • NotationΩ(...)read Omega – Worst case • NotationO(...)read Big-O
3
Q
Heap is?
A
Complete binary tree
4
Q
complete binary tree?
A
heap
5
Q
merge sort worst case Big-O?
A
O(n log n)
6
Q
worst case of selection sort?
A
O(n^2)
7
Q
quick sort worst case?
A
O(n log n)
8
Q
do you agree that quicksort is faster than mergesort?
A
YES
9
Q
Prim algorithm was invented by?
A
Robert C. Prim in 1957
10
Q
Dijkstra algorithm was invented by?
A
Edsger Dijkstra in 1959
11
Q
Kruskal algorithm was invented by?
A
Joseph Kruskal in 1956
