Difference between revisions of "CSC212 Final Exam 2014"
(→Problem #3) |
|||
| Line 6: | Line 6: | ||
<br /> | <br /> | ||
<bluebox> | <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. | + | 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. | TAs '''cannot''' help with the final exam, in any way. | ||
| − | Questions about this exam can be asked in class only, | + | Questions about this exam can be asked in class only, but can be posted 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> | </bluebox> | ||
<br /> | <br /> | ||
Revision as of 10:03, 10 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(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>
