Software Journal

As I may have said elsewhere, I teach CS 212 at GWU, and am happy to make ALL course materials public – lectures etc. Even the mid term, even though it makes it harder for me to use the same mid term next year! . So, in light of that, here is the mid term for CS 212:

Q1 (5 points): Prove the following: (1+ 2 + 3 + … + n) + (1^3+ 2^3 + 3^3 + … + n^3) = O(n^4)

Q2, 3, 4 (5 points each): What is the time complexity of this algorithm, in terms of n?
[Just as an FYI, Sum += y is a short form notation for Sum = Sum + y.]

Q2:
j = 1
while (j < n) {
k = j
while (k < n) {
Sum += a[j]*b[k]
k = 3 * k
}
j = 4 * j
}

Q3:
For (int j = 1 to n) {
For (int k = j to n) {
For (int x = k to n) {
Sum += a[j]*b[k]*c[x]
}
}
}

Q4:
For (int j = 1 to n) {
For (int k = j to n) {
Sum += a[j]*b[k]
}
For (int x = j to n) {
Sum += a[x]*b[j]
}
}

Q5 (10 points): You are given an unsorted array of n unique numbers. Write an algorithm to find the second highest number. A naïve algorithm would simply find the maximum (in n-1 comparisons), and then find the second maximum (in n-2 more comparisons) in a total of 2n-3 comparisons. Your algorithm should do much better than that. For example, given 1000 numbers, your algorithm should be able to find the second largest number in well below 1100 comparisons. Sorting the array is not an option since that would take at least about 5,000 comparisons.

Q6 (10 points): Hospital Triage System: At a hospital, patients arrive and are assigned a priority (“patient arrival process”). When an opening becomes available, the patient with highest priority is served (“patient serve process”). In case the severity of the patient’s problem changes while waiting, then the patient is assigned a new priority (“patient reevaluation process”). What data structure and algorithm do you suggest so that system has best response times for patient arrival, serve and reevaluation processing?

Q7 (10 points): Task scheduling: You are given n tasks and their start and end times. (For example: T1: 7 AM – 9 AM; T2: 8 AM to 3 PM; T3: 4 AM to 8 AM.) You can only be doing one task at a time. For every task that you finish, you are given a fixed reward (100$) irrespective of the length of the task. How do you select the tasks to maximize your reward? What is the time complexity of your algorithm in terms of n?

Q8 (10 points): Around the block party planning
Consider a row of n houses represented as an array: A[1..n], where the phrase “next door neighbor” having its natural meaning. Each house owners are assigned a “fun factor” F[1..n], which represents how much fun they bring to a party. Your goal is to maximize the fun of a party that you are arranging, but with the constraint that no next door neighbors can be in the party. (So for example, if you invite the A[6] family, you cannot invite the A[5] or A[7] families.) How do you select the guest list?

Enter Comments

Posted on Monday, March 15th, 2010 at 10:06 PM in education   |  RSS feed