COMP2804: Discrete Structures
Algorithm代写 | 代写assignment | math代写 – 这个题目属于一个math 离散的代写任务, 涉及了离散数学等代写方面, 该题目是值得借鉴的assignment代写的题目
II
assignment 2
If your browser has trouble rendering MathJaX, then use this PDF file
Administrivia
Your assignment must be submitted as a single PDF file through cuLearn
Late assignments will not be accepted under any circumstances. If you're unable to complete
the assignment due to a valid and documented medical or personal situation then the weight
of this assignment can be shifted to the weight of the remaining assignments.
You are encouraged to collaborate on assignments, but at the level of discussion only. When
writing your solutions, you must do so in your own words.
Past experience has shown conclusively that those who do not put adequate effort into the
assignments do not learn the material and have a probability near 1 of doing poorly on the
exams.
When writing your solutions:
You must justify your answers.
The answers should be concise, clear and neat.
When presenting proofs, every step should be justified.
Meat
1. ID
1. Make sure the first thing on page 1 of your assignment is your name and student number.
2. Arrangements of MOOSONEE
1. How may distinct ways are there to rearrange the letters in MOOSONEE (the name of a town
in northern Ontario)?
3. Self-Inverting Functions
A function is called self-inverting if for every. A point is called a fixed point of if.
1. Prove that, if is a self-inverting function that has fixed points, then is
even.
2. Prove that, for even , the number of self-inverting functions on an -element set is
(there are three formulas here because different ones are more natural depending on how you
approach the problem.)
4. Pigeonholing
Use the pigeonhole principle to prove each of the following statements:
1. Pied Piper is a data-compression company that claims to have an Algorithm to losslessly
compress any 1024-bit binary string so that it's size is not more than 1023 bits. Prove that
their claim is false.
2. Let and be positive integers such that. Prove that every
-element subset of contains a 4-element subset such that
.
3. The -grid is
f : S S f ( f ( x ))= x x S x S
f f ( x )= x
f : S S k | S | k
n n
( )( )( )( n / 2 k )!
k = 0
n / (^2) n 2 k
1
2 n /^2 k
n 2 k
n / 2 k
=( )( )( ) k!
k = 0
n / (^2) n 2 k
1
2 k
2 k
k
=( )( )
k = 0
n / (^2) n 2 k ( n 2 k )! 2 n /^2 k ( n / 2 k )! k n 4 n 2 k ( k 1 ) n ( n 1 ) k { 1 ,…, n } { a , b , x , y } a + b = x + y ( n n )
In other words, is the set of points whose coordinates are integers coordinates between 1
and. The mid-point of a pair and is defined as
Prove that, if , then any -element subset of contains a -element
subset such that. In words: The line-segment and the line-
segment cross exactly at their common midpoints.
4. Consider the square. Prove that, if is a set of points
contained in then there are two distinct points such that the distance between
and is at most.
5. Two strings and are anagrams if is a permutation of. For example, dilly and idyll are
anagrams. Prove that any set of -bit binary strings contains a pair of anagrams.
6. Prove that any set of 456 12-character strings over the alphabet contains a pair of
anagrams.
5. Recurrences
1. The function is defined by
Prove that for every integer.
2. Solve the following recurrence:
3. Consider the set of strings over the 3-character alphabet whose length is and
for which does not appear as a consecutive substring. For example:
G ={( i , j ): x , y { 1 ,..., n }}.
G
n a =( ia , ja ) b =( ib , jb )
m ( a , b )=( a + b )/ 2 =(( ia + ib )/ 2 ,( ja + jb )/ 2 ).
k ( k 1 )> 2 ( 2 n 1 )^2 k G 4
{ a , b , x , y } m ( a , b )= m ( x , y ) ab
xy
n n Q =[ 0 , n ][ 0 , n ] S n^2 + 1
Q p , q S p
q 2
s t s t
n + 2 n
{ a , b , c , d }
f :NN
f ( n )={^11 f ( n 1 )
2 4
n
if n = 0
if n 1.
f ( n )= 2 n^2 n 0
f ( n )={^13 f ( n 2 ) iiff^ nn =>^01 .or^ n =^1
An { a , b , c } n
aa
A 0 ={ }
Write a recurrence for. Then, using induction, show that this recurrence solves to
- Consider the set of strings over the 3-character alphabet whose length is and for which does not appear as a consecutive substring. For example,
a. Argue that
b. Write a program to compute for and look up the resulting sequence in
the Online Encyclopedia of Integer Sequences. What did you find?
- Solve the following recurrence equation
A 1 ={ a , b , c }
A 2 ={ ab , ac , ba , bb , bc , ca , cb , cc }
| An |
| An |=( 3 / 3 + 1 / 2 )( 1 + 3 ) n ( 3 / 3 1 / 2 )( 1 3 ) n
Sn { a , b , c } n
ab
S 0 ={ },
S 1 ={ a , b , c },
S 2 ={ aa , ac , ba , bb , bc , ca , cb , cc },
S 3 ={ aaa , aac , aca , acb , acc , baa , bac , bba , bbb , bbc , caa , cac , cba , cbb , cbc }.
| Sn |= 2 | Sn 1 |+| |+ 1.
k = 2
n
Sn k
| Sn | n = 0 ,..., 20
f ( n , k )=
0
1
f ( n 1 , k )+ f ( n 1 , k 1 )
if k > n
if k = 0
if n k > 0