CSC212 Final Exam 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 n^th 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 n^th 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 0^th term is 1, the 1^st is 1, the 2^nd is 1, the 3^rd 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>