MIEG Interview Quiz
The Chinese University of
Copyright By PowCoder代写 加微信 powcoder
Time Limit: 30 minutes
Question 1: Communication
[10 pts] Charles wishes to communicate a message which is an integer m in 0, . . . , k − 1 to William. To
accomplish this, Charles sends a string of n bits to William. However their butler is nasty and by a force of
habit, he always flips exactly one bit. Charles and William are aware of this habit of their butler.
For example, when k = 2, n = 3, one communication scheme is to have Charles send 000 if m = 0, and 111
if m = 1. If 000 is sent, it becomes 001, 010 or 100 after flipping. If 111 is sent, it becomes 110, 101 or 011
after flipping. Since these two collections do not overlap, William can tell whether m = 0 or m = 1.
Given this, what is the largest k such that Charles can communicate k different messages with William so
that William can recover the intended message m precisely from the altered data for the cases below:
(c) n = 6.
Question 2: Counting
Your home is located on a road that extends indefinitely on both sides. You are at home in the beginning.
During each time slot t = 1, 2, 3, . . ., you can move 1 km to the east or to the west along the road. You can
either follow the same direction as at time slot t − 1 (e.g. if you went east at time t − 1, you can continue
going east at time t), or you can make a U-turn and move in the opposite direction to the one that you did
in time slot t − 1 (e.g. if you went east at time t − 1, then you can go west at time t). Note that at time
t = 1, you are allowed to move east or west, and this does not count as a U-turn. Your journey ends at the
moment you return home. Suppose your journey ends right after the n-th time slot (i.e., you return home
right after time slot n, but you are not at home after time slots 1, 2, . . . , n− 1). The following figure shows a
possible path for n = 8 where you make 3 U-turns, where the steps taken are E,E,W,E,E,W,W,W (E stands
for east, W stands for west):
0 1 2 3-1-2-3 4
Find the number of different possible paths (in terms of n) if:
(a) You must make exactly 1 U-turn.
(b) You must make exactly 2 U-turns.
(c) You must make exactly 3 U-turns.
(d) You must make exactly 5 U-turns.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com