CPSC 320

Think about the quantities each problem is trying to maximize and minimize, the restrictions it applies (e.g. no two students who don’t trust each other on the same machine), and what problems might map to these factors.

Use the existing ‘count-inversions’ algorithm, but write a wrapper that places the pivot for the first call in a specific way. You don’t necessarily have to use the results of all returned recursive calls.

See this StackExchange post.

Is q one of the parameters of the instance of SQ?

How many possible assignments are there now?

Consider one ‘part’ as one player’s territories, and the other ‘part’ as the other player’s. Since the graph is bipartite, can there be any connections between territories within a player’s control? What does this say about their territories’ connected components’ maximum size?

If we know the array is sorted, and that there are two different numbers, what are some ’easy’ positions we can look in to find them?

Can you find an expression for the number of dashed edges? What about for the height? Draw out some example trees (e.g. a ‘star’) to see if the height / number of dashed edges changes.

If two men share the same preference list, they will both start by trying to propose to the same woman. Can both of them succeed in the end?

Try n = 5. Then try n = 2.

Is there a sample instance that returns something you didn’t expect? What part of the reduction caused that to happen?

Always try to come up with a counterexample for this type of question, so at least half of the work is done!

This ‘majority’ pattern comes up a lot in past midterms.

The blank A[mid] ___ A[hi] is expecting ‘faces’, ’not equal’ or ’equal’.

The last answer is another way of saying ‘choose the performance that ends first’.

If we ‘run out’ of the first string, we don’t have to continue. We also can’t skip any letters within the first string, so there’s one case of LCS we don’t have to consider.

The base case is still a subproblem.

How many units of time do you need to spend computing E(100)? E(50)? E(0)?

Note the question restriction that m < n. Big-O bounds with multiple variables are incomparable if the relationship differs depending on m or n’s growth rate.

Always try to come up with a counterexample for this type of question, so at least half of the work is done!

Weakly-connected means that if the graph was undirected, it would be connected. A connected graph has a minimum of n - 1 edges.

Consider a situation where a woman’s preferences are 'important' to the resulting matching. Does having any arbitrariness in her decision change the possible matchings?

Being 'unique to that component' means that the colour is only in that component and is unique across components.

Consider what impact requiring that the arrays were sorted has and what parts of the code rely on that assumption.

Fill this in according to the reduction you just formulated.

An STP instance of size k where everyone is indifferent has k! solutions, because no one has any preferences that could cause instabilities, so this is just the number of possible matchings.

Think of a mentorship relationship as being a parent in a tree. Because everyone must have a mentor, can any mentor go without a mentor? What does this say about the number of edges, and by extension, the number of cycles? Is this an upper or lower bound?

What happens if you have a very generous donor who 'fills up' a cause with a very small amount remaining? Was this the best use of their 'one cause'?

Does the first argument ever get used? Which of the arguments contributes to the decision to continue recursing?

What does quick select do even before recursively calling anything?

Try partitioning the elements so that all the majority elements are in one subarray and none are in the others.

What parts of either problem have to do with ‘majority’? BLAME produces an arbitrary set of nodes if a majority of the nodes were not intact. How does this help simplify the ’no instance’ case?

If an element is a majority element, it must occupy the ‘middle’ position of the sorted array. What is the rank of that element?

Consider the definition of little-o.

Consider the property that log (n^k) = k log(n)

What two bounds are implied by a limit of big-theta? If the big-O bound is true, what must not be true?

Consider how raising something to exponent (n^x) versus something to c * exponent (n^(cx)) changes the expression.

The number of 2-exchanges is equal to the number of ways the patients and donors can be paired up.

Does it matter in what order we choose the edges?

Consider a graph that forms a path, and consider what restrictions are imposed on the choice of e for the ’end nodes'.

What is the definition of a tree? One property is guaranteed by the algorithm. If we assume the other property is violated, how can we show a contradiction based on the fact that the weights differ?

One shortcut is to bound the time taken at the root of the tree for a lower bound, then the time taken over infinite levels of the tree for an upper bound.

Consider what the ’natural ordering’ is of the subproblems. What do you have to compute before computing Pell(n)? Also, reference the memoized algorithm you just wrote.

How many entries maximum do you ever reference in computing Soln[n]?

What is the formula for (n+1)!? Recall that (c^x)^y = (c^y)^x.

The Gale-Shapley algorithm always produces the matching that matches each employer to its best valid applicant and each applicant to its worst valid employer.

What extra work does the DP solution have to do for each coin value?

The correct form of reduction from SAT to 3SAT, as shown in class, requires one of the y_i to be negated. What requirement did that impose on the 3SAT reduction? This reduction from 4SAT to 3SAT doesn’t have that negation, but has a similar ‘joining’ structure. Does this cause any issues where an unsatisfiable instance of 4SAT can become satisfiable in the reduced 3SAT?

This becomes the minimum spanning tree problem.

What is the definition of NP - specifically, what does it require about the runtime of one of its certification algorithms? Recall that a polynomial * polynomial = polynomial.

What is the definition of the master theorem? Does it place any restrictions on the size of the different subproblems?

Does this graph have to be directed? If we have word A that can be transformed to word B in one step, can we ‘reverse’ it? Does this graph have to be weighted? What are we counting?

For each word in your dictionary, what transformations can be done on it? Assuming all words were valid, what are the maximum number of unique transformations that can be applied to one word? The english alphabet has 26 letters.

For the recurrence, try coming up with a solution where you assume each step only makes one ‘cut’.

Person 1 will be the first person selected, because they only speak 2 languages. What happens if Persons 2 and 3 share no languages, but they each share a language with Person 1?