First Section Script

Hi everyone! It’s 2:10 PST so I think we’ll get started. Hope all of you are doing well, staying safe and sane. Welcome to CS 170 discussion! My name is Manan Khattar, and for a little bit about me,

Classes for asymptotic notation

1 < log2 n < n < n log2 n < n2 < n3 < … < 2 n < n! < nn

Also have asymptotic tricks In general, we can observe the following properties ofO/Θ/Ω from this:

• ˆIfd > c,nc=O(nd), butnc6= Ω(nd) (this is sort of saying thatndgrows strictly more thannc).ˆ
• Asymptotic notation only cares about “highest-growing” terms. For example,n2+n= Ω(n2).ˆ
• Asymptotic notation does not care about leading constants.
  
• For example 50n= Θ(n).ˆ
• Any exponential with base>1 grows more than any polynomialˆThe base of the exponential matters. For example, 3n=O(4n), but 3n6= Ω(4n).ˆ
• Ifd > c,nclogn=O(nd).

Divide and Conquer problems:

advice for these problems figure out what the problem is asking as that is usually the what your function returns think about what information is really necessary in order to solve what your function returns

think about how to make a biggest problem either split so you can ignore some portion of the original search space, or do work so that useful invariants are introduced to the smaller problems and can be combined on the way up

Proof techniques

• Invariants and induction are pretty similar.

Loop invariant proofs: One possible scheme: prove an invariant is true for all iterations 1 Initialization: the invariant(s) is true prior to the first iteration of the loop 2 Maintenance: if the invariant is true for iteration n, it is true for iteration n+1 3 Termination: when the loop terminates, the invariant is true on the entire input For bubblesort, the invariant is “At iteration i, the sub-array A[1..i] is sorted and any element in A[i+1..A.size] is greater or equalt to any element in A[1..i]”

Created from: First Section Preparation 202008301313

• Have a zoom poll at the beginning and end (beginning about what topics I want to emphasize, Manan take the wheel), end about my pace and how fast I was going through things

3. Find the Valley

We’re using a top-down approach

Things people could be confused about

1. Asymptotic notation

2. Recurrence relations

3. Divide and conquer problems

4. Algorithm design/proof techniques

   • For this one, use the merge sort pseudocode example

     uid: 202008311933 tags: #teaching

---

---

---