Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSE 21 Fall 2022

Homework 5

Review question for homework 1 -20 points  A group of n people are play- ing frisbee, throwing the disk from one person to another. Amazingly, no one ever drops the frisbee or misses the throw.  Let Catchi  be the num- ber of times person i has caught the frisbee, Throwi  the number of times person i has thrown the frisbee.   Prove that at the end of the game, i Catchi  = i Throwi .

Review question for homework 2- 20 points  Say we are given two sorted lists A[1..k] and B[1..n] where k < n/2 .  Give an algorithm that decides whether the lists intersect, i.e., is some A[i] = B[j] ?  Your algorithm should work in time O(k log n/k). Hint: use a method similar to window encoding, breaking B up into blocks of size n/k and using binary search for each block.

Review question for homework 3- 20 points  Remember that the Fibonacci sequence is given by F(0) = F(1) = 1,F(n) = F(n − 1) + F(n − 2) for  n ≥ 2. On the review question 1 in the previous assignment, the following  identity was proved, A0 < k < n, Fib(n) = Fib(k)Fib(n − k) + Fib(k −  1)Fib(n − k − 1). Use this identity to give a divide-and-conquer recursive  algorithm that, given n, returns Fib(n) and Fib(n+1). Prove correctness  using the identity, and give a time analysis assuming arithmetic operations   are constant time.

Review question for homework 4- 20 points  Remember that the Fibonacci sequence is given by F(0) = F(1) = 1,F(n) = F(n − 1) + F(n − 2) for  n ≥ 2.  Consider the set of sequences of 0’s and 1’s of length n that do  not have two consecutive 1’s. Prove that the number of such sequences is  Fib(n + 1).

Inclusion-exclusion  (Short answer, with brief explanation, 10 points) How many alphanumeric passwords of length 9 have at least one upper case letter, at least one lower case letter, and at least one numeral?

Coding bounded sequences  A bounded sequence  of length n is a sequence of integers so that the next element is either one greater than or less than the previous element.

Here are a few examples of bounded sequences of length 8, starting with1: (1, 2, 3, 4, 3, 2, 1, 0),   (1, 2, 1, 2, 1, 2, 1, 2),   (1, 0, −1, −2, −3, −4, −3, −2)

1. For m,n ≥ 1, how many bounded sequences of length n are there that

start with an integer between 1 and m?  (give a brief justification.) (5 points)

2. How many bits would the most efficient encoding of such sequences use? (in terms of n and m. Justify your work) (5 points)

3. Develop your own encoding/decoding algorithm where the code uses this number of bits. Describe your algorithms, and show the decoding recovers the encoded message. (10 points)

4. How many bounded sequences of length n have first and last element 0? (10 points)

Coding using ranking  In review problem 4 above, it is shown that the num- ber of binary sequences of length n with no consecutive pair of 1’s is F(n+1), the n+1’st fibonacci number. How many bits do we need to en- code such a string ? (5 points). Give a ranking based encoding algorithm to encode such strings with this number of bits (5 points).  Then give the corresponding deconding algorithm (5 points).Show that the decoding algorithm applied to the coding algorithm is the original string (5 points).

Modelling frisbee problem as graph  For review problem 1 above, explain how we could model the situation with a dircted graph (possibly with parallel edges) and interpret the formula in the problem in terms of degrees of vertices in this graph. (10 points)

Modeling word puzzle as graph  In a word morphing puzzle , you are given a list of words and want to find a way to move from the first word to the second word using only words that appear in the list and only changing one letter each step. Consider the following example:

WORD,LIST,CORD,CORE,WOOD,FOOD, WORE,FOOL,WOOL,FOOT,LOOT,LOST

.

Describe or draw a graph that would help you solve this puzzle for this example, and say what a solution would mean in terms of the graph. (10 points)