Assignment 0

Online from February 29 (Monday); solution due by March 7 (Monday) 9am; feedback on March 8 (Tuesday) 4pm. Late submissions cannot be accepted!

This self-assessment is to be solved individually. (Homework assignments #2 and following are to be solved in groups...)

Problem 1 (10P)

A tournament is a directed graph with exactly one edge between every pair of vertices. (So for each pair \((u,v)\) of vertices, either the edge from \(u\) to \(v\) or from \(v\) to \(u\) exists, but not both.) You can think of the nodes as players in a tournament, where each player has to play against every other player. The edge points from the winner to the loser of a game.
A Hamiltonian path (not cycle) is a sequence of consecutive directed edges that visits every vertex exactly once.

Prove that every tournament contains at least one Hamiltonian path.  

 

Problem 2 (10P)

Professor Hastings has constructed a 23-node binary tree in which each node is labeled with a unique letter of the alphabet.

Preorder and postorder traversals of the tree visit the nodes in the following order:

• Preorder: B K X E H L Z J W R C Y T S Q A P D F M N U G
• Postorder: H J W Z R L E C X S Q T A Y K D M U G N F P B

Draw Professor Hastings' tree and list the nodes in the order visited by an inorder traversal. Explain how you arrived at the answer!  

 

Problem 3 (10P)

Solve the following recurrences. State tight asymptotic bounds for each function in the form \(\Theta(f(n))\) for some elementary function \(f(n)\). Assume reasonable but nontrivial base cases.

• \(A(n) = 4A(n-1) + 1\)
• \(B(n) = B(n-3) + n^{2}\)
• \(C(n) = 2C(n/2) + 3C(n/3) + n^{2}\)
• \(D(n) = 2D(n/3) + \sqrt(n)\)

Advice: Don't cheat on yourself by just applying the 'Master Theorem'!  

Problem 4 (10P)

The Fibonacci numbers \(F_{n}\) are defined by the recurrence \(F_{n} = F_{n-1} + F_{n-2}\), with base cases \(F_{0} = 0\) and \(F_{1} = 1\).

Prove that any non-negative integer can be written as the sum of distinct and non-consecutive Fibonacci numbers. That is, if \(F_{i}\) appears in the sum, then \(F_{i-1}\) and \(F_{i+1}\) do not appear in the sum. For example:

• \(17 = F_{7} + F_{4} + F_{2}\)
• \(42 = F_{9} + F_{6}\)
• \(54 = F_{9} + F_{7} + F_{5} + F_{3} + F_{1}\)

 

Problem 5 (10P)

A perfect riffle shuffle, also known as a Faro shuffle, is performed by cutting a deck of cards exactly in half and then perfectly interleaving the two halves. There are two different types of perfect shuffles, depending on whether the top card of the resulting deck comes from the top half or the bottom half of the original deck.

An out-shuffle leaves the top card of the deck unchanged. After an in-shuffle, the original top card becomes the second card from the top. For example:

(If you are unfamiliar with playing cards, please refer to the Wikipedia article.)

Consider a deck of \(2^n\) distinct cards, for some non-negative integer \(n\). What is the effect of performing exactly \(n\) perfect in-shuffles on this deck? Prove your answer!