Induction 1.)
Problem Set 1
Find the closed form of(via math or online resource):
𝑛𝑖 ∑4
𝑖=1
Prove your closed-form formula via induction. 2.) Analysis
What is the asymptotic upper bound of the code above?
3.)Analysis
What recurrence equation describes the code above?
4.) MinHeap Review
If you haven’t covered heaps please review here: https://youtu.be/WCm3TqScBM8?si=9XIQqe9qB88OtRXS
a.) See the minHeap below. Please note that in this structure the parents are equal or smaller than their children. Show the resulting tree after you push(2), push(31), pop(), pop(), and update the key of 7 to -2.
b.) Given the following functions push(a[1]), push(a[2]), push(a[3]) ... push (a[n]) The asymptotic upper bound on loading the heap assuming the heap is initially empty is O(n). This video gives a formal explanation. Can you try to explain why the runtime is O(n) in your own words?https://youtu.be/MiyLo8adrWw?si=BI7_LCyoQX1oqg6S
5.)Analysis
6.)
7.a)
7b.) Prove that
8.)
a.i)Given S={z, b, g} List all subsets of S.
a.ii) Given S={z, b, g, r} List all subset of S
is .
b.) List all substrings of cdef
c.) Given S=100, How many subsets can be created?
d.) Create a pseudocode for the following function decode(x)
Input:Intx,setSofsizen,where 𝑥 <(2𝑛 − 1)
Output: the Subset the is represented by the binary digit
Example1 Input: decode(7) S=A,B,C
Because binary(7)=111 that means we include all members of set S
Output:{A,B,C}
Example2 Input: decode(5) S=A,B,C
Because binary(7)=111 that means we include all members of set S
Output:{A,C}
e.) Provide pseudocode the creates list all subsets of any set S?
f.) Provide pseudocode for all possible substrings of a single string your code could list duplicates.
9.)
a.)How many ways can you make a group of 2 out of S= {y, b, g}. Show the groups.
b.) Provide pseudocode to list all sets of 2 given S.
10.) Analysis for(int i=1 to i=n)
for(j=1 to j=n){ j++;
i++; }//for j
//for i
What is the runtime of the code above?
11.) Provide pseudocode to find the smallest number in a array of ints. What is the runtime of your code?
12.) Provide pseudocode to finding the sum of an array of ints. What is the runtime of your code?