Difference between revisions of "CSC212 Final Exam 2014"
| Line 13: | Line 13: | ||
=Problem #1= | =Problem #1= | ||
* If you were to change the queue in the BFS algorithm with a stack. In general, is the order in which the vertices get visited by this new BFS the same as the order of DFS? True or false? We assume that both searches would start on the same vertex. | * If you were to change the queue in the BFS algorithm with a stack. In general, is the order in which the vertices get visited by this new BFS the same as the order of DFS? True or false? We assume that both searches would start on the same vertex. | ||
| − | + | ||
| − | |||
| − | |||
<br /> | <br /> | ||
=Problem #2= | =Problem #2= | ||
<br /> | <br /> | ||
* in a heap of ''N'' items, that keeps the largest item at the top, we can find the smallest item in the heap in O(log(N)). True or False? | * in a heap of ''N'' items, that keeps the largest item at the top, we can find the smallest item in the heap in O(log(N)). True or False? | ||
| − | + | ||
| − | + | ||
| − | + | ||
<br /> | <br /> | ||
=Problem #3= | =Problem #3= | ||
| Line 30: | Line 28: | ||
* Assume we do not use any form of tail-end truncation of the recursion. | * Assume we do not use any form of tail-end truncation of the recursion. | ||
* What it the best complexity we can expect for computing recursively the ''n''<sup>th</sup> Fibonacci term, if we are very efficient in our coding? O(1), O(n log(n) ), O(n), O(n^2), O(2^n)? | * What it the best complexity we can expect for computing recursively the ''n''<sup>th</sup> Fibonacci term, if we are very efficient in our coding? O(1), O(n log(n) ), O(n), O(n^2), O(2^n)? | ||
| − | + | ||
| − | + | ||
| − | + | ||
<br /> | <br /> | ||
| Line 46: | Line 44: | ||
</source> | </source> | ||
:O(N)? O(N^2)? O(N^3)? O(N^4)? O( N.log(N) )? | :O(N)? O(N^2)? O(N^3)? O(N^4)? O( N.log(N) )? | ||
| − | + | ||
| − | + | ||
| − | + | ||
<br /> | <br /> | ||
=Problem #5= | =Problem #5= | ||
| Line 54: | Line 52: | ||
* InsertionSort can sometimes sort faster than QuickSort? True or False? | * InsertionSort can sometimes sort faster than QuickSort? True or False? | ||
<br /> | <br /> | ||
| − | + | ||
| − | + | ||
| − | + | ||
<br /> | <br /> | ||
=Problem #6= | =Problem #6= | ||
<br /> | <br /> | ||
| − | * We cannot create a BST of nodes containing strings, because the string's hash function generates an index that is not related to the alphabetical order of the string. For example, "Alpha" has a hashCode of 63357246, "Bravo " a hashCode of 1997811958, and "Claro" a hashCode of 65190197. These are not sorted in the same order as the strings are. So we cannot create a BST of strings. True or False? | + | * We cannot create a BST of nodes containing strings, because the string's hash function generates an index that is not related to the alphabetical order of the string. For example, "Alpha" has a hashCode of 63357246, "Bravo " a hashCode of 1997811958, and "Claro" a hashCode of 65190197. These are not sorted in the same order as the strings are. So we cannot create a BST of strings. True or False? (If you think we cannot, then answer True. If you think that we can, answer False.) |
<br /> | <br /> | ||
| − | + | ||
| − | + | ||
| − | + | ||
=Problem #7= | =Problem #7= | ||
| Line 70: | Line 68: | ||
* If we visit a BST using BFS, the nodes will get visited in order (either increasing or decreasing). True or False? | * If we visit a BST using BFS, the nodes will get visited in order (either increasing or decreasing). True or False? | ||
<br /> | <br /> | ||
| − | + | ||
| − | + | ||
| − | |||
=Problem #8= | =Problem #8= | ||
| Line 78: | Line 75: | ||
* Assume that we have this series: 1, 1, 1, 3, 5, 9, 17, 31, 57, etc. Each term is the sum of the previous 3. The 0<sup>th</sup> term is 1, the 1<sup>st</sup> is 1, the 2<sup>nd</sup> is 1, the 3<sup>rd</sup> is 3, etc. | * Assume that we have this series: 1, 1, 1, 3, 5, 9, 17, 31, 57, etc. Each term is the sum of the previous 3. The 0<sup>th</sup> term is 1, the 1<sup>st</sup> is 1, the 2<sup>nd</sup> is 1, the 3<sup>rd</sup> is 3, etc. | ||
* The 73rd term is 9088947301592921387. True or False? | * The 73rd term is 9088947301592921387. True or False? | ||
| − | |||
| − | |||
| − | |||
* The 70th term is 70 1460714212526492817. True or False? | * The 70th term is 70 1460714212526492817. True or False? | ||
| − | + | ||
| − | |||
| − | |||
<br /> | <br /> | ||
=Problem #9= | =Problem #9= | ||
<br /> | <br /> | ||
| − | * Assume we have a function that generates random RPN expressions: | + | * Assume we have a java function that generates random RPN expressions: |
<source lang="java"> | <source lang="java"> | ||
static String randomRPN( int n ) { | static String randomRPN( int n ) { | ||
| Line 117: | Line 109: | ||
* If we call it and pass it 200 as an argument, it prints a fairly long string that starts with "11 4 8 + 4 4 + 5 5 %" and ends with " - - - - - - - - - -". | * If we call it and pass it 200 as an argument, it prints a fairly long string that starts with "11 4 8 + 4 4 + 5 5 %" and ends with " - - - - - - - - - -". | ||
* If we evaluate this RPN expression, the result is -725. True of False? | * If we evaluate this RPN expression, the result is -725. True of False? | ||
| + | |||
| + | </onlydft> | ||
| + | <br /> | ||
| + | <br /> | ||
| + | <br /> | ||
| + | <br /> | ||
| + | |||
<onlydft> | <onlydft> | ||
| − | :(answer: False, it's -726) | + | =Answers= |
| − | + | * 1 ) :(answer: No) | |
| + | * 2 ) :(answer: False, O(N)) | ||
| + | * 3 ) :(answer: O(n)) | ||
| + | * 4 ) :answer O(N^3) | ||
| + | * 5 ) :answer (true) | ||
| + | * 6 ) :(answer false) | ||
| + | * 7 ) :(answer: False) | ||
| + | * 8 ) :(answer: False, it's 9088947301592921385), (answer: True) | ||
| + | * 9 ) :(answer: False, it's -726) | ||
</onlydft> | </onlydft> | ||
| + | <br /> | ||
| + | <br /> | ||
| + | <br /> | ||
| + | <br /> | ||
| + | <br /> | ||
| + | <br /> | ||
| + | [[Category:CSC212]] | ||
