CS计算机代考程序代写 algorithm CS 124 Section 0

CS 124 Section 0
Biased Coins, Math Review, Sorting/Searching
Lavanya Singh 2021

Goals
• CALCULATIONS
• Sums and Series
• Probability and Counting • PROOFS
• Induction
• Contradiction
• BIG-O
• SORTING/SEARCHING
• Binary Search • Mergesort
1

Calculations
1

Sums and Series
Here are some important sums:
• ∑n1 i=n(n+1)/2
• ∑n1 i2 = n(n+1)(2n+1)/6
2

Sums and Series
Let’s derive this formula:
∑n i 1−sn+1
s=1−s
i=0
3

Probability and Counting
Useful Facts:
• P(A) = 1−P(Ac) = 1−P(A)
• If A and B are independent events, P(A and B) = P(A)P(B)
• independent events = knowing A gives you no information about B • Expectation E(X) = ∑ xP(X = x)
• Linearity of expectation: E(X1 + X2) = E(X1) + E(X2)
4

Probability and Counting
Recall the coin tossing algorithm from Lecture 0. We have a biased coin that is H with probability p and T with probability q. To convert it to an unbiased coin, we leverage symmetry. We consider each set of two flips, and we count HT as a fair heads, TH as a fair tails, and toss the rest.
5

Proofs
8

What is a Proof?
A proof is a mathematical argument. It should start with what the reader already knows and proceed in clear logical steps from there.
9

Proof Strategy: Induction
Use this if you want to show that a statement is true for all natural numbers n.
• Basecase: Showthatthestatementistrueforn=0orn=1 • Inductive hypothesis: Assume that the statement is true for
n = k.
• Inductive step: Show that the statement is true for n = k + 1
Why does this work?
10

Example Inductive Proof
The sum of the first n natural numbers is n(n + 1)/2.
11

Example Inductive Proof
The sum of the first n natural numbers is n(n + 1)/2.
Proof.
• Base case: n = 0. 0 = 0(0 + 1)/2 so the statement holds.
12

Example Inductive Proof
The sum of the first n natural numbers is n(n + 1)/2.
Proof.
• Base case: n = 0. 0 = 0(0 + 1)/2 so the statement holds.
• Inductive hypothesis: Assume that the sum of the first n = k
numbers is k(k + 1)/2.
• Inductive step: The sum of the first n = k + 1 numbers is
k + 1 + k(k + 1)/2 by the inductive hypothesis. Doing some algebra, k+1+k(k+1)/2 = (k2 +3k+2)/2 = (k+1)(k+2)/2.
14

Proof by Contradiction
If you want to prove a statement is true, you can assume it is false and then show that its falsity leads to a contradiction.
15

Proof by Contradiction
If you want to prove a statement is true, you can assume it is false and then show that its falsity leads to a contradiction.
Consider the statement ”there are infinitely many primes.” It’s much easier to think about a world with finitely many primes, than one with infinitely many.
16

Example Proof by Contradiction
There are infinitely many primes.
Proof.
Assume towards a contradiction that there are finitely many primes. Number the primes p1, p2, . . . …pn. Now consider the number N=1+p1 ∗p2 ∗…∗pn. N>pn soNmustnotbeprime,soitmust be divisible by some prime (since every number can be factored into primes). All the pi divide N − 1 so none of them can divide N so there must be some different prime that divides N. This contradicts the earlier statement that the pi were all the primes, so the assumption must be false and there must be infinitely many primes.
17

Advice
DO:
Give us enough details to indicate that you haven’t made any plausible errors
DON’T:
• Give an example instead of a proof • Skip steps/assume too much
• Use inconsistent definitions
18

Big-O
18

Big-O
Sometimes we don’t care about the exact running time of our algorithms. Instead, we just care about their asymptotic behavior: what happens as the input sizes become arbitrarily large?
19

Big-O
Consider two functions F and G. F = O(G) if there exist two positive real numbers a and N such that, ∀n > N, f(n) ≤ ag(n).
Ex. f(n)=n,g(n)=n2 −→f=O(g)1
1f = O(g) and f ∈ O(g) may be used interchangeably
20

Big-Ω and Big-Θ
Consider two functions F and G. F = Ω(G) if there exist two positive real numbers a and N such that, ∀n > N, f(n) ≥ ag(n).
Ex. f(n)=n,g(n)=n2 −→g=Ω(f) f=Θ(g) ⇐⇒ f=O(g)andf=Ω(g)
21

Little-o
Consider two functions F and G. F = o(G) if for every positive real number c, there exists a real number N such that ∀n > N,
|f(n)| ≤ c|g(n)|.
Equivalent definition: Consider two functions F and G. F = o(G) if limn−→∞ f(n)/g(n) = 0
22

Sorting and Searching
22

Binary Search
Say I have a sorted array of integers A. How can I determine if A contains the integer 6?
23

Binary Search
Say I have a sorted array of integers A. How can I determine if A contains the integer 6?
Start at the middle. If the middle number is greater than 6 (maybe it’s 8) then we’re too high, and we should be looking at the smaller half of A, and vice versa if it is lower.
Repeat this procedure until you find 6, or realize that it’s not in the array.
24

Binary Search
Let T(n) be the number of comparisons needed to search for an element in an array of n elements.
T(n) = T(n/2) + c
T(n) = T(n/4) + 2c
…
T(n) = T(n/2log2(n)) + log2(n)c
T(n) = c log2 n So binary search runs in time O(log2 n)
25

Mergesort
Sorting a list:
• Divide: Repeatedly divide the list in half
• Conquer: Combine each sublist, sorting as you go
26

Mergesort: Divide
27

Mergesort: Conquer
28

3-way Mergesort
Suppose instead of splitting the array in two 2 pieces during the divide steps, we split it in 3. Let’s analyze the time complexity of this algorithm.
29

3-way Mergesort
Suppose instead of splitting the array in two 2 pieces during the divide steps, we split it in 3. Let’s analyze the time complexity of this algorithm.
T(n) = 3T(n/3) + cn
30

3-way Mergesort
2
T(n) = 3T(n/3) + cn
T(n) = 3(3T(n/9) + cn/3) + cn = 9T(n/9) + 2cn
…
T(n) = 3log3 nT(n/3log3 n) + cn log3 n
T(n) = O(n log3 n)
2Note that log2 is only a constant factor different from log3 so this is the same big-O bound as for the original mergesort algorithm.
31

Master Theorem
Consider T(n) = aT(n/b) + cnk. 
O(nlogb a) O(nk log n) O(nk)
a > bk a = bk a < bk 32 Section Problems 32 Problem 1 Assume arrays never have repeating elements. Here is some pseudocode for the sorting algorithm bogosort: def bogosort(A): while A is not sorted: shuffle A • Say A has n elements. What is the probability that bogosort finds the correct solution on the 4th shuffle? • Consider bogomergesort. This algorithm is like mergesort, except the merge function combines the two sublists by running bogosort until you have a correctly sorted, combined sublist. Write a recurrence for the expected number of comparisons required in bogomergesort, solve it, and prove its correctness. Hint: the expected number of comparisons for bogosort is n*n! 33 Problem 2 Earlier, I said that the recurrence the number of comparison operations required for mergesort is T(n) = 2T(n/2) + cn. This was a lie! • Play along with my lie. Assume n is a power of 2. Prove that mergesort takes O(n log n) comparisons by induction. • Write a recurrence for the number of comparison operations when n is not a power of 2. As a bonus, try to solve it. Hint: you may find the following concept useful: what is 2⌈log2 n⌉? 34 Problem 3 For all of the problems below, when asked to give an example, you should give a function mapping positive integers to positive integers. (No cheating with zeroes!) • Find (with proof) a function f1 such that f1(2n) is O(f1(n)). • Find (with proof) a function f2 such that f2(2n) is not O(f2(n)). • Prove that if f(n) is O(g(n)), and g(n) is O(h(n)), then f(n) is O(h(n)). • Give a proof or a counterexample: if f is not O(g), then g is O(f). 35

Related Posts