Question 1

Find Min
Write code after everyone

Accepted Answer

1. Make sure N != 0 & Return 0
2. Initialize m
3. Do for loop to find min (int i = 1)
4. Make if condition to see if arr[i] < min
5. Return min

Question 2

Find Max

Accepted Answer

arr[i] > max

Question 3

Sum over Arrays

Accepted Answer

1. Initialize sum 
2. for loop to add up all arr values (i = 0) 
3. sum +=arr[i];

Question 4

Product over Arrays

Accepted Answer

product*=arr[i];

Question 5

No Negative Numbers

Accepted Answer

1. for loop 
2. if loop to ensure no arr is < 0. If so, return 0.
3. Return 1

Question 6

Same Array Elements

Accepted Answer

1. if Lengths N1 & N2 !=, else return 0
2. for loop condition: i < N1
3. Inside if condition checking if arr1 != arr2 (return 0)
4. Return 1

Question 7

Both Strings Equal

Accepted Answer

1. int i = 0
2. while loop s1 == s2
3. if s1[i] reaches '\0', return s1
4. i++
5. Return 0

Question 8

S1 Substring of S2?

Accepted Answer

1. if sSmall = ‘\0’ → return 1
2. for loop condition: sBig[i] != '\0'
3. while sBig & sSmall != '\0' && == each other | Big = [i+j} & Small =[j] 
4. j++
5. if sSmall[j] = ‘\0’ → return 1
6. Return 0

Question 9

S1 Prefix of S2?

Accepted Answer

1. int i = 0
2. while (sSmall[i] != '\0')
3. if sBig == '\0' or sBig != sSmall -> return 0
4. Return 1

Question 10

S1 Suffix of S2?

Accepted Answer

1. bigLen & smallLenen = 0
2. Find out Big & Smalllen with while loops (!= '\0')
3. if smallLen > bigLen
4. int i
5. while sSmall != '\0'
6. if(sBig[bigLen - smallLen + i] != sSmall[i]){ return 0; }
7. i++
8. Return 1

Question 11

S1 Subsequence of S2?

Accepted Answer

1. int i & j
2. while sBig & sSmall != ‘\0’
3. if loop sBig[i] == sSmall[j] → j++
4. i++;
5. if sSmall == ‘\0’ → return 1
6. Return 0

Question 12

Replace

Accepted Answer

1. for loop condition: s[i] != '\0'
2. if s[i] == oldch → s[i] = newCh

Question 13

Upper Chars

Accepted Answer

1. int i
2. while s[i] != '\0
3. if s[i] >= ‘a’ && <= ‘z’ → s[i] -= 32
4. i++;

Question 14

Binary Search: Iterative

Accepted Answer

1. left = 0 & right = N - 1 (Arrays)
2. while left <= right
3. mid = left + (right - left)/ 2
4. if A[mid] == val → return mid
5. else A[mid] < val → left = mid + 1
6. else A[mid] > val → right = mid - 1
7. return -1;

Question 15

Binary Search: Recursive

Accepted Answer

1. if left > right → return -1
2. mid = left + (right - left) / 2
3. if A[mid] == val → return mid
4. else if A[mid] < val → return binary_search(val, A, mid + 1, right)
5. else A[mid] > val → return binary_search(val, A, left, mid - 1)

Question 16

Insertion Sort

Accepted Answer

1. for loop condition: i < n
2. int key = arr[i], j = i - 1;
3. while (j >= 0 && arr[j] > key)
a. arr[j + 1] = arr[j]
b. j -= 1;
1. arr[j + 1] = key

Question 17

Stable & Adaptive: Sorts

Accepted Answer

- Insertion Sort: Stable & Adaptive
- Count Sort: Stable
- Radix Sort: Stable
- Merge Sort: Stable
- Quick Sort: Nothing

Question 18

Insertion Sort: Process

Accepted Answer

- Processes from the 2nd element/Index 1
- Flips 1st two then sort one ahead 1 by 1

Question 19

Insertion Sort: Time & Space Complexity

Accepted Answer

- Worst TC: Most Amount of Work -> O(N^2)
- Best TC: Least Amount of Work -> O(N)
- Average TC is always Worst Case
- SC: O(1)

Question 20

Count Sort: Process

Accepted Answer

- Count
- Prefix Sum (Add then go)
- Iteration: Last One 1st (Right to Left)
- Subtract # - 1 then copy to 2nd arr

Question 21

Count Sort: Time & Space Complexity

Accepted Answer

All O(N + k)

Question 22

Radix Sort: Process

Accepted Answer

- Sort through LSD (Ones)
- Sort through Tens
- Sort through Hundreds

Question 23

Radix Sort: Time & Space Complexity

Accepted Answer

- TC: O(d(N+k))
- SC: O(N + k_

Question 24

Merge Sort: Process

Accepted Answer

- Half the array
- 1st Merge: Take 1st 2 #s of 1st half & sort 
-  2nd Merge: Add other numbers from 1st half
- 3rd Merge: Focus on 1st 2 #s of 2nd half

Question 25

Merge Sort: Time & Space Complexity

Accepted Answer

- TC: O(NlgN)
- SC: O(N)

Question 26

Quick Sort: Process

Accepted Answer

- Val =index 0
- shorter closer, flipping places with biggers
- after last short, flip with val
- 1 partition: after last short flip with val

Question 27

Quick Sort: Time & Space Complexity

Accepted Answer

- Worst TC: Sorted array -> O(N^2)
- Best TC: O(NlgN)
- Average: O(NlgN)
- Worst SC: O(N)
- Best SC: O(lgN)

Question 28

Linear Search TC

Accepted Answer

- Worst Case is always → O(N)
- Best Case (Unsorted A, item found) → O(N)
- Best Case (Other possibilities) → O(1)

Question 29

Binary Search TC

Accepted Answer

- Only works on Sorted Arrs
- Worst Case is always → O(lgN)
- Best Case (Sorted A, item not found) → O(lgN)
- Best Case (Sorted A, item found) → O(1)

Question 30

Binary: Iterative vs Recursive SC

Accepted Answer

- Iter. Space: O(1)
- Recur. Space: O(lgN)
- If tail recursion is optimized, Recur. Space: O(1)

Question 31

Math Review

Accepted Answer

Look at Exam 1 Info

Question 32

Comparing 2 f(x)s

Accepted Answer

- M is very large and N is small
- N is very large and M is small
- Both M and N are very large

Question 33

Asymptotic Bounds

Accepted Answer

- Θ: Theta (==): Tight bound 
- O: Big-Oh (≤): Upper Bound & Can be tight
- Ω: Omega (≥): Lower Bound & Can be tight
- o: Little-Oh (<): Upper Bound
- ω: Little-Omega (>): Lower Bound

Question 34

Asymptotic Bounds Examples

Accepted Answer

- n! = o(n^n)
- n! = ω(2^n)
- n^2 = O(n^3)
- n^2 = Ω(n)

Question 35

TC for Strings: O(1)

Accepted Answer

- Printing 1 char/fixed
- Printing an array at specific index
- %p prints the memory address of the string & it’s constant
- %s but only if it’s a hardcoded text | Ex: printf( "%s", "This program will..." );
- Comparisons(Ex: j < N)

Question 36

TC for Strings: O(L)
Length of Strings

Accepted Answer

- %s Printing a string depends on String Length
- strlen(); Has to count String Length

Question 37

Array size = N
Assume this is the Mergesort version that stops the recursion at N=1. What is the maximum number of  recursive calls that can be open at the same time?

Accepted Answer

O(lgN)

Question 38

Log Facts

Accepted Answer

- lg = log2()
- - N, N/2, N/4, N/8 use lgN steps
- All log f(x)s (that differ in only the base) have the same growth rate | Ex: log7(N) = log7(N^2)
- Log f(x)s grow slower than a polynomial f(x)s

Question 39

Estimate a Log

Accepted Answer

Place it between 2 Ints | Ex: Estimate log3(12)

- 2 < log3(12) < 3 = 3^2 < log3(12) < 3^3

Question 40

Binary Search: Process

Accepted Answer

- left = 0 & right = N - 1
- Get m -> A[m]
- Depending on A[m] size, if bigger left+, smaller right-
- Stop when left > right

Question	Answer
Find Min Write code after everyone	1. Make sure N != 0 & Return 0 2. Initialize m 3. Do for loop to find min (int i = 1) 4. Make if condition to see if arr[i] < min 5. Return min
Find Max	arr[i] > max
Sum over Arrays	1. Initialize sum 2. for loop to add up all arr values (i = 0) 3. sum +=arr[i];
Product over Arrays	product*=arr[i];
No Negative Numbers	1. for loop 2. if loop to ensure no arr is < 0. If so, return 0. 3. Return 1
Same Array Elements	1. if Lengths N1 & N2 !=, else return 0 2. for loop condition: i < N1 3. Inside if condition checking if arr1 != arr2 (return 0) 4. Return 1
Both Strings Equal	1. int i = 0 2. while loop s1 == s2 3. if s1[i] reaches '\0', return s1 4. i++ 5. Return 0
S1 Substring of S2?	1. if sSmall = ‘\0’ → return 1 2. for loop condition: sBig[i] != '\0' 3. while sBig & sSmall != '\0' && == each other \| Big = [i+j} & Small =[j] 4. j++ 5. if sSmall[j] = ‘\0’ → return 1 6. Return 0
S1 Prefix of S2?	1. int i = 0 2. while (sSmall[i] != '\0') 3. if sBig == '\0' or sBig != sSmall -> return 0 4. Return 1
S1 Suffix of S2?	1. bigLen & smallLenen = 0 2. Find out Big & Smalllen with while loops (!= '\0') 3. if smallLen > bigLen 4. int i 5. while sSmall != '\0' 6. if(sBig[bigLen - smallLen + i] != sSmall[i]){ return 0; } 7. i++ 8. Return 1
S1 Subsequence of S2?	1. int i & j 2. while sBig & sSmall != ‘\0’ 3. if loop sBig[i] == sSmall[j] → j++ 4. i++; 5. if sSmall == ‘\0’ → return 1 6. Return 0
Replace	1. for loop condition: s[i] != '\0' 2. if s[i] == oldch → s[i] = newCh
Upper Chars	1. int i 2. while s[i] != '\0 3. if s[i] >= ‘a’ && <= ‘z’ → s[i] -= 32 4. i++;
Binary Search: Iterative	1. left = 0 & right = N - 1 (Arrays) 2. while left <= right 3. mid = left + (right - left)/ 2 4. if A[mid] == val → return mid 5. else A[mid] < val → left = mid + 1 6. else A[mid] > val → right = mid - 1 7. return -1;
Binary Search: Recursive	1. if left > right → return -1 2. mid = left + (right - left) / 2 3. if A[mid] == val → return mid 4. else if A[mid] < val → return binary_search(val, A, mid + 1, right) 5. else A[mid] > val → return binary_search(val, A, left, mid - 1)
Insertion Sort	1. for loop condition: i < n 2. int key = arr[i], j = i - 1; 3. while (j >= 0 && arr[j] > key) a. arr[j + 1] = arr[j] b. j -= 1; 1. arr[j + 1] = key
Count Sort (Didn't do it, see if I have time)
Stable & Adaptive: Sorts	- Insertion Sort: Stable & Adaptive - Count Sort: Stable - Radix Sort: Stable - Merge Sort: Stable - Quick Sort: Nothing
Insertion Sort: Process	- Processes from the 2nd element/Index 1 - Flips 1st two then sort one ahead 1 by 1
Insertion Sort: Time & Space Complexity	- Worst TC: Most Amount of Work -> O(N^2) - Best TC: Least Amount of Work -> O(N) - Average TC is always Worst Case - SC: O(1)
Count Sort: Process	- Count - Prefix Sum (Add then go) - Iteration: Last One 1st (Right to Left) - Subtract # - 1 then copy to 2nd arr
Count Sort: Time & Space Complexity	All O(N + k)
Radix Sort: Process	- Sort through LSD (Ones) - Sort through Tens - Sort through Hundreds
Radix Sort: Time & Space Complexity	- TC: O(d(N+k)) - SC: O(N + k_
Merge Sort: Process	- Half the array - 1st Merge: Take 1st 2 #s of 1st half & sort - 2nd Merge: Add other numbers from 1st half - 3rd Merge: Focus on 1st 2 #s of 2nd half
Merge Sort: Time & Space Complexity	- TC: O(NlgN) - SC: O(N)
Quick Sort: Process	- Val =index 0 - shorter closer, flipping places with biggers - after last short, flip with val - 1 partition: after last short flip with val
Quick Sort: Time & Space Complexity	- Worst TC: Sorted array -> O(N^2) - Best TC: O(NlgN) - Average: O(NlgN) - Worst SC: O(N) - Best SC: O(lgN)
Linear Search TC	- Worst Case is always → O(N) - Best Case (Unsorted A, item found) → O(N) - Best Case (Other possibilities) → O(1)
Binary Search TC	- Only works on Sorted Arrs - Worst Case is always → O(lgN) - Best Case (Sorted A, item not found) → O(lgN) - Best Case (Sorted A, item found) → O(1)
Binary: Iterative vs Recursive SC	- Iter. Space: O(1) - Recur. Space: O(lgN) - If tail recursion is optimized, Recur. Space: O(1)
Math Review	Look at Exam 1 Info
Comparing 2 f(x)s	- M is very large and N is small - N is very large and M is small - Both M and N are very large
Asymptotic Bounds	- Θ: Theta (==): Tight bound - O: Big-Oh (≤): Upper Bound & Can be tight - Ω: Omega (≥): Lower Bound & Can be tight - o: Little-Oh (<): Upper Bound - ω: Little-Omega (>): Lower Bound
Asymptotic Bounds Examples	- n! = o(n^n) - n! = ω(2^n) - n^2 = O(n^3) - n^2 = Ω(n)
TC for Strings: O(1)	- Printing 1 char/fixed - Printing an array at specific index - %p prints the memory address of the string & it’s constant - %s but only if it’s a hardcoded text \| Ex: printf( "%s", "This program will..." ); - Comparisons(Ex: j < N)
TC for Strings: O(L) Length of Strings	- %s Printing a string depends on String Length - strlen(); Has to count String Length
Array size = N Assume this is the Mergesort version that stops the recursion at N=1. What is the maximum number of recursive calls that can be open at the same time?	O(lgN)
Log Facts	- lg = log2() - - N, N/2, N/4, N/8 use lgN steps - All log f(x)s (that differ in only the base) have the same growth rate \| Ex: log7(N) = log7(N^2) - Log f(x)s grow slower than a polynomial f(x)s
Estimate a Log	Place it between 2 Ints \| Ex: Estimate log3(12) - 2 < log3(12) < 3 = 3^2 < log3(12) < 3^3
Binary Search: Process	- left = 0 & right = N - 1 - Get m -> A[m] - Depending on A[m] size, if bigger left+, smaller right- - Stop when left > right

"Know" box contains:
Time elapsed:
Retries:

Stefan Exam