From 5b667ae6912559a326ef580a681cc805f556fcaf Mon Sep 17 00:00:00 2001
From: Louie S <lshprung@yahoo.com>
Date: Thu, 9 Apr 2020 11:44:54 -0700
Subject: Post-class 04/10

---
 04-08.md |   4 ++
 04-10.md | 176 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 180 insertions(+)
 create mode 100644 04-10.md

diff --git a/04-08.md b/04-08.md
index e4c4111..a39e9e5 100644
--- a/04-08.md
+++ b/04-08.md
@@ -180,3 +180,7 @@ for(i=1; i<=n; i++){
 	- x = (n-1)+(n-2)+...+2+1+0
 	- 2x = (n-1)\*n -> x = ((n-1)\*n)/2
 - O(x) = O(((n-1)\*n)/2) -> O(n^2)
+
+---
+
+[04/10 ->](04-10.md)
diff --git a/04-10.md b/04-10.md
new file mode 100644
index 0000000..379e952
--- /dev/null
+++ b/04-10.md
@@ -0,0 +1,176 @@
+[\<- 04/08](04-08.md)
+
+---
+
+## Review - Data Structure
+
+What is a data structure?
+- How data is organized in memory (or hard disk)
+
+Why do we care about data structure?
+- Efficiency - time/space efficiency
+- How to measure time efficiency?
+	- Count # of operations
+	- What types of operations do we care about?
+		- Insertion
+		- Deletion
+		- Access/Search
+		- Min/Max
+		- Union/Merge
+	- When do we care?
+		- We only care about the one with the highest impact on efficiency
+
+## Review - Big-O Notation
+
+The correct form of big-O
+- Drop all but the fastest-growing term
+- Drop the constant coefficient of the remaining term
+- e.g `1500n^2 + 4n + 3log(n) + 2` -> `1500n^2` -> `n^2`
+	- Big-O notation for this example would be O(n^2)
+
+How to evaluate the big-O for a piece of code?
+- We mainly care about repetitive operations
+	- Operations that are only executed once (or constant times) will be ignored
+- Loops
+	- Single layer loop
+	- Nested loop
+
+## Summary: Big-O for Nested Loops
+
+Step 1: Analyze if it's a dependent loop or independent loop. Assume the counter variable of the outsider loop is `i`
+1. if `i` is not involved in insider loop -> **independent loop**
+2. Otherwise -> **dependent loop**
+
+Step 2: If independent loop:
+- O_overall = O(outsider loop) * O(insider loop)
+- Otherwise (dependent loop):
+	- For each iteration of the outsider loop -> count # of operations for the insider loop, add them together
+
+## Nested Loop II - Dependent Loops
+
+```
+for(i=0; i<n; i=i+2){
+	for(j=i; j<n; j++){
+		x++;
+	}
+}
+```
+
+This is a dependent loop
+
+|Iteration|Outsider Loop|Inner Loop Count|
+|---------|-------------|----------------|
+|1        |i=0          |n               |
+|2        |i=2          |n-2             |
+|3        |i=4          |n-4             |
+|n/2      |i=n-1        |1               |
+
+To determine the total number of iterations (let's call it x), add the values from the third column
+- `x = n + (n-2) + (n-4) +...+ 1`
+- Rewrite it as `x = 1 + 3 + 5 +...+ (n-2) + n`
+- Rewrite again as `2x = (n+1) * (n/2)`
+	- `x = ((n+1)*n)/4`
+- Big-O notation simplified: O(x) = O(n^2)
+
+## More Big-O Examples
+
+```
+for(i=0; i<n; i=i+n){
+	x++;
+}
+```
+
+- Only 4 steps of iteration
+	- O(1) (easy level)
+
+```
+for(i=1; i<n; i=i*3){
+	x++;
+}
+```
+
+- Figute out how many steps of iteration:
+	- iteration 1: i=1 (3^0)
+	- iteration 2: i=3 (3^1)
+	- iteration 3: i=9 (3^2)
+	- iteration 4: i=27 (3^3)
+	- iteration x: i=n (3^(x-1))
+
+- 3^(x-1) = n -> x = log3(n)+1
+	- O(x) = O(log(n))
+
+```
+for(i=0; i<n; i=i+3){
+	f(); //f() is O(n^2)
+}
+```
+
+- (n/3) iterations * O(n^2) = O(n^3)
+
+```
+for(i=0; i<n; i++){
+	g(); //g() is O(log(n))
+}
+
+for(j=0; j<n; j++){
+	x++;
+}
+```
+
+- The first loop has n iterations
+	- O(n) * O(log(n)) = O(nlog(n))
+- The second loop has n iterations
+	- O(n) * O(1) = O(n)
+- The total big-O is O(nlog(n)) + O(n) = O(nlog(n))
+	- O(n) is a lower term, so disregard
+
+```
+for(i=n; i>=1; i=i/3){
+	for(j=0; j<n; j++){
+		x++;
+	}
+}
+```
+
+- Notice: independent loops
+- Outer loop: O(log(n))
+- Inner loop: O(n)
+- x++: O(1) (this step is sometimes ignored)
+- O(log(n)) * O(n) * O(1) = O(nlog(n))
+
+```
+for(i=1; i<=n; i=i*2){
+	for(j=1; j<=n; j=j+i){
+		x++;
+	}
+}
+```
+
+- Notice: Dependent Loop
+
+|Iteration|Outsider Loop|Inner Loop Count|
+|---------|-------------|----------------|
+|1        |i=1          |n               |
+|2        |i=2          |n/2             |
+|3        |i=4          |n/4             |
+|4        |i=8          |n/8             |
+|n        |i=n          |1               |
+
+- Now we need to sum each row of the inner loop count column (call it x)
+	- `x = n + (n/2) + (n/4) +...+ 1`
+	- O(x) = `n[1+(1/2)+(1/4)+...+(1/n)]`
+		- Eventually, O(n) (!) (that's pretty good)
+
+## Common Big-O Complexity Classes
+
+The following is listed from most to least efficient
+- Constant O(1)
+- Logarithmic O(log(n))
+- Linear O(n)
+- Log-Linear O(n)
+- Quadratic O(n^2)
+- Cubic O(n^3)
+- Polynomial O(n^k)
+- Exponential O(2^n) or O(k^n)
+- Factorial O(n!)
+- Anything worse than Exponential (actually, even quadratic) are considered pretty bad
-- 
cgit