CSC212 Final Exam 2014

--D. Thiebaut (talk) 15:16, 9 December 2014 (EST)

---

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, but can be posted on Piazza, at any time. Please phrase your questions carefully; if your question reveals a possible answer, you will lose 15 points on your exam.

All questions are worth the same amount of points, and should be answered on Moodle.

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 of a graph get visited by this new BFS, the same as the order generated by DFS? True or false? We assume that both searches would start on the same vertex.

Problem #2

• in a heap of N items, where the largest item is at the root, 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 have not precomputed the terms and stored them in an array, first. There are no arrays, no additional data structures used here.
• Assume we do not use any form of truncation of the tail-end recursion.
• In this case, 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;

Is it 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? (If you think we cannot, then answer True. If you think that we can, answer 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, except for the first three terms, which are all equal to 1. When identifying them, we start with the first term being the 0^th one. In other words, 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 1460714212526492817. True or False?

Problem #9

• Assume we have a java 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 " - - - - - - - - - -".
• The RPN expression is guaranteed to be correct, and to evaluate to an integer.
• If we evaluate this RPN expression, the result is -726. True of False?

GOOD LUCK!

...