Difference between revisions of "CSC212 Final Exam 2014"
| Line 2: | Line 2: | ||
---- | ---- | ||
<onlydft> | <onlydft> | ||
| + | <br /> | ||
| + | __TOC__ | ||
| + | <br /> | ||
| + | <bluebox> | ||
| + | This Final Exam is to be done individually. It is given under the rules of Smith's Honor Code. You have access to all your class notes, solution programs made available for various labs and/or homework assignments, to the textbook, and to the Web. The exam must be submitted to Moodle before the last day of exam period, 19 Dec. 2014, at 4:00 p.m. No extensions will be granted. | ||
| + | TAs '''cannot''' help with the final exam, in any way. | ||
| + | Questions about this exam can be asked in class only, or on Piazza, at any time. You cannot post significant sections of code on Piazza or you will lose 15 points on your exam for every offense. | ||
| + | </bluebox> | ||
| + | <br /> | ||
=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? We assume that both searches would start on the same vertex. |
| + | <onlydft> | ||
:(answer: No) | :(answer: No) | ||
| + | </onlydft> | ||
| + | <br /> | ||
=Problem #2= | =Problem #2= | ||
| − | * in a heap that keeps the largest item at the top, we can find the smallest item in the heap in O(log(N)) | + | <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? | ||
| + | <onlydft> | ||
:(answer: False, O(N)) | :(answer: False, O(N)) | ||
| + | </onlydft> | ||
| + | <br /> | ||
=Problem #3= | =Problem #3= | ||
| − | * Assume we want to compute the | + | <br /> |
| − | * Assume we do not have precomputed the terms and stored them in an array. No arrays, no data structures used here | + | * Assume we want to compute the ''n''<sup>th</sup> term of a Fibonacci sequence, and do so '''recursively'''. |
| + | * Assume we do not have precomputed the terms and stored them in an array first. No arrays, no data structures used here! | ||
* 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 | + | * 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(n^3), O(2^n)? |
| − | + | <onlydft> | |
:(answer: O(n)) | :(answer: O(n)) | ||
| + | </onlydft> | ||
| + | <br /> | ||
=Problem #4= | =Problem #4= | ||
| − | * What is the time complexity of this group of loops? | + | <br /> |
| + | * What is the time complexity of this group of nested loops? | ||
| + | <br /> | ||
<source lang="java"> | <source lang="java"> | ||
for ( int i=0; i<N; i++ ) | for ( int i=0; i<N; i++ ) | ||
| Line 23: | Line 44: | ||
sum += i + j + k; | sum += i + j + k; | ||
</source> | </source> | ||
| + | :O(N)? O(N^2)? O(N^3)? O(N^4)? O( N.log(N) )? | ||
| + | <onlydft> | ||
| + | :answer O(N^3) | ||
| + | </onlydft> | ||
| + | <br /> | ||
=Problem #5= | =Problem #5= | ||
| − | * InsertionSort can sort faster than QuickSort? True or False? | + | <br /> |
| − | (true) | + | * InsertionSort can sometimes sort faster than QuickSort? True or False? |
| + | <br /> | ||
| + | <onlydft> | ||
| + | :answer (true) | ||
| + | </onlydft> | ||
| + | <br /> | ||
=Problem #6= | =Problem #6= | ||
| − | * 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. | + | <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? | |
| + | <br /> | ||
| + | <onlydft> | ||
:(answer false) | :(answer false) | ||
| + | </onlydft> | ||
| + | |||
=Problem #7= | =Problem #7= | ||
| − | * If we visit a BST using BFS, the nodes will get visited in order (either increasing or decreasing). True or False | + | <br /> |
| + | * If we visit a BST using BFS, the nodes will get visited in order (either increasing or decreasing). True or False? | ||
| + | <br /> | ||
| + | <onlydft> | ||
:(answer: False) | :(answer: False) | ||
| + | </onlydft> | ||
| + | |||
=Problem #8= | =Problem #8= | ||
| − | * 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 | + | <br /> |
| + | * 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? | ||
| + | <onlydft> | ||
:(answer: False, it's 9088947301592921385) | :(answer: False, it's 9088947301592921385) | ||
| + | </onlydft> | ||
* The 70th term is 70 1460714212526492817. True or False? | * The 70th term is 70 1460714212526492817. True or False? | ||
| + | <onlydft> | ||
:(answer: True) | :(answer: True) | ||
| − | + | </onlydft> | |
| + | <br /> | ||
=Problem #9= | =Problem #9= | ||
| + | <br /> | ||
* Assume we have a function that generates random RPN expressions: | * Assume we have a function that generates random RPN expressions: | ||
<source lang="java"> | <source lang="java"> | ||
| Line 68: | Line 114: | ||
} | } | ||
</source> | </source> | ||
| − | * If we call it and pass it 200 as an argument, it prints a fairly long string | + | * 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> | ||
:(answer: False, it's -726) | :(answer: False, it's -726) | ||
| + | </onlydft> | ||
| + | |||
</onlydft> | </onlydft> | ||
Revision as of 18:05, 9 December 2014
--D. Thiebaut (talk) 15:16, 9 December 2014 (EST)
Problem #2
- 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?
Problem #3
- Assume we want to compute the nth term of a Fibonacci sequence, and do so recursively.
- Assume we do not have precomputed the terms and stored them in an array first. No arrays, no data structures used here!
- 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 nth Fibonacci term, if we are very efficient in our coding? O(1), O(n log(n) ), O(n), O(n^2), O(n^3), O(2^n)?
Problem #4
- What is the time complexity of this group of nested loops?
for ( int i=0; i<N; i++ )
for ( int j=i; j<N; j++ )
for ( int k=0; k<j; k++ )
sum += i + j + k;
- O(N)? O(N^2)? O(N^3)? O(N^4)? O( N.log(N) )?
Problem #5
- InsertionSort can sometimes sort faster than QuickSort? True or False?
Problem #6
- 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?
Problem #7
- If we visit a BST using BFS, the nodes will get visited in order (either increasing or decreasing). True or False?
Problem #8
- 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 0th term is 1, the 1st is 1, the 2nd is 1, the 3rd is 3, etc.
- The 73rd term is 9088947301592921387. True or False?
- The 70th term is 70 1460714212526492817. True or False?
Problem #9
- Assume we have a function that generates random RPN expressions:
static String randomRPN( int n ) {
Random generator = new Random();
generator.setSeed( 11 );
String s = "";
int noOps = 0;
int no11s = 0;
for ( int i=0; i<n; i++ ) {
int r = generator.nextInt(5);
int x =(1+generator.nextInt(10));
int y =(1+generator.nextInt(10));
switch ( r ) {
case 0: s += x + " " + y + " + "; noOps++; break;
case 1: s += x + " " + y + " - "; noOps++; break;
case 2: s += x + " " + y + " % "; noOps++; break;
case 3: s += "11 "; no11s++; break;
}
}
noOps--;
while ( noOps-- > 0 )
s += "+ ";
while ( no11s-- > 0 )
s += "- ";
return s;
}
- 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?
</onlydft>
