CS315 (Prof. Szajda) Exam 1 February 25, 2008

Name (3 points):______

This is an open book, open note exam: you may consult ONLY our class text and your notes from this class. Texts and notes related to other classes may be consulted as needed for those other classes (so if you get lucky and find a solution in one of them by accident, that’s OK – you just cannot go to those books with the intention of finding a solution to a problem on this exam). You may not consult any other resources or people regarding the contents of this exam during the completion of the exam. To be specific, the term “completion of exam” refers to the time from when you first examine the contents of any part of the exam until the moment that the exam has been turned in to me.

This exam is due (at my office or in my email) by 11:59:59pm on Monday, March 3, 2008.

Please be succinct and precise.

NOTE: IF I CANNOT READ YOUR SOLUTION, OR HAVE THE LEAST BIT OF DIFFICULTY INTERPRETING YOUR HANDWRITING, I WILL ASSUME YOUR SOLUTION TO THE PROBLEM IN QUESTION IS NOT CORRECT AND YOU WILL RECEIVE NO CREDIT FOR THAT PROBLEM!

Also, when a problem asks you to provide an O(f(n)) complexity algorithm, part of your solution must be an explanation of why your algorithm meets the required complexity constraint!

All binary trees on this exam are assumed to be proper. Also, so that all of our definitions are consistent with the text, the depth of a node v is recursively defined to be 0 if v is the root of a tree, and depth(parent) + 1 if v is not the root. The height of a tree is the maximum depth among the depths of all external nodes in the tree. Finally, the height of a node v is 0 if v is an external node, and one plus the maximum depth of a child of v if v is not an external node.

  1. (15 points) Prove the following using the precise definition of the “Big-Oh” concept (i.e. tell me what c is as well as the value of n0).
  2. If f(n) is a polynomial of degree d (i.e. ) then f(n) is O(nd).
  3. nx is O(an) for any fixed x>0 and a > 1.
  1. (8 points) Let T be a proper binary tree with n nodes. Define the lowest common ancestor (LCA) between two nodes v and w as the lowest (i.e. farthest from the root) node in T that has both v and w as descendents (where we allow a node to be a descendent of itself). Given two nodes v and w, describe a linear time algorithms for finding the LCA of v and w.
  1. (8 points) The Fibonacci function F(n) is defined by Show using induction that .
  1. (8 points) Suppose that each row of an n ×n array A consists of 1’s and 0’s such that, in any row of A, all of the 1’s come before any of the 0’s in that row. Assuming that A is already in memory, describe a method running in O(n) time (not O(n2) time) for finding the row of A that contains the most 1’s.
  1. (8 points) Suppose that each row of an n  n array A consists of 1’s and 0’s such that, in any row of A, all the 1’s come before any 0’s in that row. Assuming A is already in memory, describe a method running in O(n log n) time (not O(n2) time!) for counting the number of 1’s in A.
  1. (6 points) Consider the following game. There are N cards face down on a table. Each card has a number on it, which need not be an integer and need not be positive. You know nothing about the values on the cards, i.e. you have no knowledge of the lowest nor highest card. You are to play the following game. You can turn cards over one at a time and look at the value on the card. Once a card is turned over, it stays turned over. You win the game if and only if the last card you turn over is the card with the maximum number. Devise a strategy that will let you win, on average, at least one quarter of the time. Put another way, your strategy must guarantee that the probability that you win any game, regardless of the number of cards on the table, is at least 0.25.
  1. (8 points) Two ordered trees T′ and T″ (both not necessarily binary) are said to be isomorphic if one of the following holds
  2. Both T′ and T″ consist of a single node
  3. Both T′ and T″ have the same number k of subtrees, and the ith subtree of T′ is isomorphic to the ith subtree of T″, for i = 1,2,3,…

If n is the number of nodes contained by the “larger” of the two trees, design a O(n) time algorithm that tests whether two given ordered trees are isomorphic. So you are clear on the definition of isomorphic, two trees are isomorphic if and only if there is a one-to-one map of the vertices of one tree onto the vertices of the other and such that corresponding vertices have the same number of children. This means that they have the same exact structure but with possibly different vertex labels.

  1. (12 points) Consider the single machine scheduling problem, where we are given a set T of tasks, their associated start and finish times, and are asked to maximize the number of tasks from T that this single machine (with a single processor) can run. Design a greedy algorithm for this problem and show that your algorithm is correct. What is the running time of your algorithm? You may assume that the following constraints are obeyed:
  2. All task have starting times that are greater than or equal to zero.
  3. Once a tasks is started, it must run to completion (e.g., we do not allow preemtive scheduling).
  1. (8 points) Find an O(n) time algorithm for "randomizing" the integers from 1 to n inclusive. That is, when your algorithm is finished, it should produce an array of size n that contains all of the numbers from 1 to n but in a random order. You may assume that you have the use of pseudorandom number generation code (such as that in the Java Random class) that produces pseudorandom numbers in a given range in constant time. Thus, this problem is not about designing a random number generator, but instead about using one in a way that solves the given problem in linear time.
  1. (8 points) Suppose we are given an n-element sequence S such that each element in S represents a different vote in an election, where each vote is given as an integer representing the ID of the chosen candidate. Suppose further that the number of candidates running, k, is known to us beforehand, and that k < n. Suppose also that the representing number of the candidates are not necessarily the integers from 1 through k (i.e. we know there are k candidates, but we don’t know their numbers beforehand). Describe an O(n log k) time algorithm for determining who wins the election.
  1. (8 points) An independent set of an undirected graph G = (V,E) is a subset I of V, such that no two vertices in I are adjacent. That is, if u and v are in I, then (u,v) is not in E. A maximal independent set M is an independent set such that, if we were to add any additional vertex to M, then it would not be independent any longer. Every graph has a maximal independent set (though you need not prove this). Assuming that G has n vertices, describe an O(n) time algorithm that computes a maximal independent set for graph G.