Homework 0

This homework should be done individually. You can start working in groups starting with Homework 1.

Problem 1.

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 is a sequence of directed edges, joined end to end, that visits every vertex exactly once. Prove that every tournament contains at least one Hamiltonian path.

Problem 2.

Herr Professor Doktor Georg von den Dschungel has a 23-node binary tree, in which each node is labeled with a unique letter of the German alphabet, which is just like the English alphabet with four extra letters: Ä, Ö, Ü, and ß. (Don’t confuse these with A, O, U, and B!)

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

• Preorder: B K Ü E H L Z I Ö R C ß T S O A Ä D F M N U G
• Postorder: H I Ö Z R L E C Ü S O T A ß K D M U G N F Ä B

(a) List the nodes in Professor von den Dschungel’s tree in the order visited by an inorder traversal.
(b) Draw Professor von den Dschungel’s tree

Problem 3.

Solve the following recurrences. State tight asymptotic bounds for each function in the form \(\Theta(f(n))\) for some recognizable function \(f(n)\). Assume reasonable but nontrivial base cases if none are given. Do not submit proofs—just a list of five functions—but you should do them anyway, just for practice.

• \(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)\)

Problem 4.

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.

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.)

Suppose we start with 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 is correct!