CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2022) Homework-1
• Homework solutions should be neatly written or typed and turned in through Gradescope
by 11:59pm on the due date. No late homeworks will be accepted for any reason. You will be
able to look at your scanned work before submitting it. Please ensure that your submission
is legible (neatly written and not too faint) or your homework may not be graded.
• Students should consult their textbook, class notes, lecture slides, instructors, TAs, and tutors
when they need help with homework. Students should not look for answers to homework
problems in other texts or sources, including the internet. Only post about graded homework
questions on Piazza if you suspect a typo in the assignment, or if you don’t understand what
the question is asking you to do. Other questions are best addressed in office hours.
• Your assignments in this class will be evaluated not only on the correctness of your answers,
but on your ability to present your ideas clearly and logically. You should always explain
how you arrived at your conclusions, using mathematically sound reasoning. Whether you
use formal proof techniques or write a more informal argument for why something is true,
your answers should always be well-supported. Your goal should be to convince the reader
that your results and methods are sound.
• For questions that require pseudocode, you can follow the same format as the textbook, or
you can write pseudocode in your own style, as long as you specify what your notation means.
For example, are you using “=” to mean assignment or to check equality? You are welcome
to use any algorithm from class as a subroutine in your pseudocode.
There are 5 questions for a total of 65 points.
1. (10 points) Let f(n) and g(n) be functions from the nonnegative integers to the positive real numbers.
Prove the following transitive property from the definition of big-O:
If f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)) then f(n) ∈ O(h(n)).
2. State True or False:
(a) (2 points) 2 · (3n) ∈ Θ(3 · (2n))
(b) (2 points) (n6 + 2n + 1)2 ∈ Ω((3n3 + 4n2)4)
(c) (2 points) log n ∈ Ω((log n) + n)
(d) (2 points) n log n + n ∈ O(n log n)
(e) (2 points) log(n10) ∈ Θ(log(n))
(f) (2 points)
∑n
i=1 i
k ∈ Θ(nk+1)
(g) (2 points) (log(n))log(n) ∈ O(n/ log(n))
(h) (2 points) n! ∈ O(2n)
3. Show that if c is a positive real number, then g(n) = 1 + c + c2 + ... + cn is:
(a) (3 points) Θ(1) if c < 1.
(b) (3 points) Θ(n) if c = 1.
(c) (3 points) Θ(cn) if c > 1.
4. The Fibonacci numbers F0, F1, ..., are defined by
F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2
(a) (4 points) Use induction to prove that Fn ≥ 20.5n for n ≥ 6.
1 of 2
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2022) Homework-1
(b) (4 points) Use induction to prove that Fn ≤ 2n for n ≥ 0.
(c) (2 points) What can we conclude about the growth of Fn?
5. (20 points) Consider two binary strings x1,,,,xn and y1,,,ym. An interleaving of x and y is a strings
z1...zn+m so that the bit positions of z can be partitioned into two disjoint sets X and Y , so that looking
only at the positions in X, the sub-sequence of z produced is x and looking only at the positions of Y ,
the sub-sequence is y. For example, if x = 1010 and y = 0011, z = 10001101 an interleaving because the
odd positions of z form x, and the even positions form y. The problem is: given x,y and z, determine
whether z is an interleaving of x and y.
Here is a simple back-tracking recursive algorithm for this problem, based on the two cases: If z is an
interleaving, either the first character in z is either copied from x or from y.
BTInterleaving (x1..xn ; y1..ym; z1..zn+m):
1. IF n=0 THEN IF y1..ym = z1...zm THEN return True ELSE return False
2. IF m=0 THEN IF x1..xn=z1...zn THEN return True ELSE return False
3. IF x1 = z1 AND BTInterleaving (x2,...xn, y1...ym; z2...zn+m) return True
4. If y1 = z1. AND BTInterleaving(x1..xn, y2,..ym; z2...zn+m) return True
5. Return False
a. (2 points): Show the tree of recursions the above algorithm would make on the above example.
b. (4 points). Give an upper bound on the total number of recursive calls this algorithm might make in
terms of n and m
c. (3 points). Which distinct sub-problems can arise in the recursive calls for this problem?
d. (7 points): Translate the recursive algorithm into an equivalent DP algorithm, using your answer to
part c.
e. (4 points) Give a time analysis for your DP algorithm
NOTE: For the above question, structure your answer so that the following are included. You should
explicitly give:
1. Description of sub-problems
2. Base Case(s)
3. Recursion (with justification) (A complete proof by induction is NOT required. However, you
should explain why the recursion makes sense and how it covers all possibilities)
4. Order in which sub-problems are solved
5. Form of output (how do we get the final answer?)
6. Pseudocode
7. Runtime analysis
2 of 2

欢迎咨询51作业君