School of Mathematics
2022 Semester 2
MAT1841 Continuous Mathematics for Computer Science
Assignment 2
The assignment is to be submitted via MOODLE via 11:55 pm AEST Friday 16 September 2022.
See the instructions under the assessment tab on MOODLE. Be sure to press the “submit assignment”
button to complete the submission. You must submit a single PDF document no larger than 100MB in
size. It’s the student’s responsibility to ensure that the file is not corrupted.
Assignment 2 is worth 20% of the final mark. There are three questions.
The standard penalty of 10% of the total mark per day will apply for late work.
Show your working. You are required to clearly explain your steps in both English and mathematical
expressions. Most of the marks will be allocated for clear working and explanations. A mathematical
writing guide is available on Moodle.
1. Compute the following derivatives, showing all work as required.
a. Using first principles, differentiate () = ?! "? . (Hint: use the ‘difference of
cubes.’)
b. Calculate the second derivative of () = sin(ln(! + 1)). State the domain and
range of (), $() and ′′().
c. Use the inverse method (i.e., the “derivative rule for inverse functions” in §3.3.2 in
the notes) to differentiate ?() = tan%&(").
[8 + 6 + 6 marks]
COMP4600/8460 - Advanced Algorithms S2 2022
Assignment 3
[Your Name] ([Your UID]) Date: August 31, 2022
Note: Plagiarism is strictly prohibited. Even though you may discuss with classmates, you should write your
homework assignment by yourself.
1 Questions
Q1) (5 Marks) Let Sn be a binomial random variable BIN(n, p)
Apply Chernoff bound to prove for any 0 < δ < 1 that
P
(
Sn ≥ (1 + δ)np
) ≤ e?δ2np3
P
(
Sn ≤ (1? δ)np
) ≤ e?δ2np2
Q2) (5 Marks) There are n balls thrown independently and uniformly at random into n bins
1. Show the probability that a particular bin receiving at least M balls is at most
(
n
M
)
( 1n )
M
2. Show the probability that one of the n bins has at least M balls is at most n( e
M
MM
)
Note: Do not use Poisson approximation
Q3) (5 Marks) Given a set of strings S = {s1, ..., sn}, map each string to a bit-string using m bits by an
ideal hashing function, such that each bit has an equal probability of being 0 or 1. Then we use the
set of bit-strings B = {b1, ..., bn} to test if a string is a member of S or not
1. Show m = ?(log n) bits is necessary for the probability of a false positive to be lesser than 1
2. Show m = O(log n) bits is sufficient for the probability of a false positive to be at most 1m
Q4) (2.5 Marks) Let Sn be BIN(n, p). Prove the tail probability is bounded by P(Sn ≥ enp) ≤ e?np
Q5) (2.5 Marks) Let X be the number of draws required to collect all n types of coupons. Prove, for any
constant c,
lim
n→∞P(X > n lnn+ cn) = 1? e
?e?c
You can use Poisson approximation
Q6) (10 Marks) Simulate balls-and-bins model and power of d-choices model, and compare their empirical
maximum loads under various values of m (≤ 10000), n (≤ 10000) and d (≤ 10). Implement your
simulation in Python/Java/C. Plot and discuss the results here in this report, and upload your code
separately on Wattle
1
2 Assignment 3: [Your Name]
2 Answers
. . .
2. Consider the function () = (5 + ? !)/(2 ? + !) over the domain ∈ [0, 5].
a. Present a graph of the function.
b. Calculate the absolute maximum and minimum of ().
[2 + 12 marks]
3. Consider a curve define parametrically as () = 3 ? %& and () = 2 + %&
a. Write the equation of the curve in non-parametric form (i.e. eliminate t between
the two equations.)
b. Find ? in terms of t using parametric differentiation.
c. Find ! !? in terms of t using parametric differentiation.
d. Find the equation of the tangent line to the curve when t = 1.
[4 + 5 + 4 + 3 marks]