Massachusetts
Institute Of Technology
18.310 Principles
of Applied Mathematics
Review Questions
for Exam 1
Exam Date:
October 13, 2000
1.When using a non-adaptive weighing scheme
you must satisfy 3 conditions. The "weighing matrix" must have
distinct
columns, must have no column the "
reverse" of another, and the same number of L's and R's in each row. What
is the reason
for each condition?
Give an inductive description of such a
scheme for appropriate number of coins.
2.Here is a list of keys, described by
their values. 1, 7, 9, 2, 3... (the list on exam will be different).
Suppose they are placed in the obvious
regular way on the vertices of a binary tree starting from the root. List the
comparisons
that would then be made in setting up a
heap, and then in sorting the heap, sorting by value. Assume that you make the
heap
by doing so from the bottom up.
3.Given a list of keys as in the previous
problem, list the comparisons you would make in sorting them by repeating
simple
merging, and also by successive
insertion. Which method requires fewer comparisons in this case? What is the
worst case
lower bound on the number of comparisons
for this number of keys?
4.Describe quick-sort in your own words,
and apply it to an illustrative example having 15 keys.
5.Find an initial ordering of 16 distinct
keys that is "worst case" for simple merging; also find one that is
worst case for
successive insertion. (Worst case means
requiring the most comparisons.) How many are required in each case?
6.Draw an intelligible picture of the
comparisons and switches of Batcher's algorithm on 32 keys. Sort the following
list of keys [to be supplied] using it. How many sort-switches are used in it?
7. Given twenty five keys, give an explicit
algorithm for finding their median.
8.Apply Huffman's (data compression)
algorithm and also the Hu-Tucker algorithm to the following ordered frequency
data:
[to
be supplied]
give
the trees and codes you get.
Compute H({pi}) for this data. Give n
H({pi}), and the total length of the message in the two codes you find.
9.State and outline a proof of Shannon’s
first theorem in your own words.
10.Use Sterling’s formula for the factorial
to show that log C(n.m) is asymptotic to n H(n/(n+m)) where:
H(p) = p ln 1/p +
(1-p)ln1/(1-p).
11.State and outline a proof of Shannon’s
Second Theorem
12.Give the conditions on the rows of Z for
(IZ) to define a ternary matrix single error correcting code. (Ternary means
addition
goes as 1+1=2, 1+2=0, 0+x=x)
Find the error in the garbled message
m=(........) given code defined by matrix M (M and m given on test).
13.Is the following polynomial (with binary
coefficients) primitive?
1+...+x7? Use some logical argument
14.Given the following garbled message with
the two error correcting code (1+x+x4)(1+x+x2+x3+x4), find the error locator
polynomial and, if you have time, where the errors are. (Message given
on exam).
15.State and prove the relations linking
the elementary symmetric functions (coefficients in polynomial) and power sums
of roots.
16.Consider a field of remainders defined
over the ternary field. Which powers obey the same equation? That is, what is
the
analogue of x and x2 obeying
the same equation when calculations are mod 2? Suppose the polynomial has
degree 3, so that the field has 27 elements
including 0, identify the sets of powers
whose members all obey the same equation.
17.Consider the field defined as the
remainders on dividing by a primitive binary polynomial of degree 6.
Construct the left side of an equation
table for this code; That is, deduce which powers obey the same equation.
Deduce from this the pair of equations
that x9 and x54 obey. Suppose we construct an 8 error correcting BCH polynomial
code
using remainders on dividing by this
polynomial. How many errors will it actually be able to correct? How many check
bits will
it have?
18.From the fact that no two non-zero
elements of a field have product 0, prove that an equation of degree k with
coefficients in a
field can have at most k roots in the
field.
19.Draw a shift register device that will encode the polynomial
1+x+x5.
And also one that will compute remainders
and divide by this polynomial.
20.If the probability of error in 1 bit is
10-4, how many errors must you correct given 255 bit coded messages
plus one extra parity bit, in order to reduce the probability of a false
message getting through to 10-20
assuming errors are independent? (if you correct k errors you will detect if
there are k+1.)
21.State and outline a proof of the (weak)
law of large numbers: that with probability approaching 1 the proportion of
errors in a
long string of independent bits each with
probability p of being in error is p.
22.State and prove the Chebychev
inequality.
23.You deal out two decks of cards (each of
52 cards) next to each other; compute or estimate the probability that no two
cards
match;
i.e. the same card never occurs in the same place in both decks.
a. find the expected number of matches.
b. find the probability of never getting
a match if you pick one card randomly from each deck , and reshuffle and do
this again a
total of 52 times.
24.Suppose you wander randomly around a set
of n places, so that at any step you have equal chance of going to any other
place
and that same chance of staying put. After k steps, what is your chance, call it
p(k, n) of having been at k different places? (assume you enter on the first
step so that this means you never go somewhere twice.)
What is the average number of steps until
you go someplace you have already been? (The probability of this happening on
the
kth step is p(k-1,n) - p(k, n))
25.
Write down equations to determine s(2) and s(3) given t(1), t(3) and t(5) and
given t(1)=s(1) , when there are three errors. Here s(j) is the jth elementary
symmetric function of the error monomials and t(j) is the sum of the jth powers
of the error monomials. (the third and fifth power equations) Solve them to
find s(2) and s(3) in terms of the t's.
26.
Explain how to determine a function like (t3+t13)/t1
as a remainder given t3 and
t1 as remainders in a polynomial field mod2. Explain how to divide
one polynomial by another in such a field.
|
Syllabus Assignments Test Review Questions Fall 2000 Lecture Notes Additional Course Notes Home |
 |