EE 200 pre-class quiz 23
Read chapter 25 of All of Programming
Due via provide, 12/22 at 11:59pm (optional)
`provide ee200 q23 quiz_23.txt`
Congratulations on making it to the final quiz in EE 200!
1) Graph coloring is:
(select one)
[ ] O(N)
[ ] O(N^2)
[ ] O(N^3)
[ ] O(N^4)
[ ] O(2^N)
[ ] Really hard.
2) Table 25.1 shows that an adjacency list + hash table has Big-O runtimes as good or better than an adjacency matrix in every case.
Suggest a reason why we might still want to use an adjacency matrix.
(free response)
3) The book describes a generic search algorithm which can operate with different data structures holding the list to edges to examine next. What kind of search do you get if you use a stack?
(select one)
[ ] Breadth-first search
[ ] Depth-first search
[ ] Djikstra's algorithm
[ ] Min-cut/max-flow
4) What kind of search do you get if you use a queue (first-in-first-out)?
(select one)
[ ] Breadth-first search
[ ] Depth-first search
[ ] Djikstra's algorithm
[ ] Min-cut/max-flow
5) What kind of search do you get if you use a priority queue?
(select one)
[ ] Breadth-first search
[ ] Depth-first search
[ ] Djikstra's algorithm
[ ] Min-cut/max-flow
6) List at least three algorithms discussed in this chapter which are NP-complete.
(free response)
7) What questions do you have about the material in this chapter?
(free response)
8) What concepts would you most like to review?
(free response)