ipark-CS

"""
TH(3,Src->Dest)
+---TH(2,Src->temp)
|   +---TH(1,Src->Dest)                 
|   |   +---TH(0,Src->temp)  moving 1 Src->Dest  1)
|   |   +---TH(0,temp->Dest) moving 2 Src->temp  2) 
|   +---TH(1,Dest->temp)             
|       +---TH(0,Dest->Src)  moving 1 Dest->temp 3) 
|       +---TH(0,Src->temp)  moving 3 Src->Dest  4) 
+---TH(2,temp->Dest)

ipark-CS

"""
EPI - Recursion

Review:
1. Recursion is suitable for problems:
    decomposing a complex problem into a set of similar instances,
    searching, enumeratation, divide-and-conquer, etc. 
2. Recursion is consits of 
    1) base cases; 2) recursion stack, i.e. calling the same 
    function with different arguments

ipark-CS

"""
EPI - Graph BootCamp

Review:
1. Graphs are ideal for modeling and analyzing relationships 
    between pairs of objects (any binary relationships).
2. Graphs are ideal data structures/algorithms for the 
    problems that are spatially connected.    
3. DFS is a suitable algorithm for analyzing structures such as
    detecting a cycle or number of connected components.

ipark-CS

import collections
import copy
import functools
from typing import List

from test_framework import generic_test
from test_framework.test_failure import TestFailure
from test_framework.test_utils import enable_executor_hook

"""

ipark-CS

"""
Bubble Sort: sorting by swapping with adjacent element
             over several passes (best O(N), avg O(N^2))
            i    0  1  2  3
first pass   a= [7,  6,  4,  3] 
           i=0  [6*, 7,  4,  3]
           i=1  [6,  4*, 7,  3]
           i=2  [6,  4,  3*, 7] 
second pass  a= [6,  4,  3,  7] 
           i=0  [4*, 6,  3,  7]

ipark-CS

"""
Merge Sort
1. keep splitting an array in half until l >= r
   by recursion with array index manipulation
2. merge the two  


i    0   1   2   3  4  5
a = [12, 11, 13, 5, 6, 7]

ipark-CS

"""
Quick Select
(same as QuickSort)
1. partition the array w/r/t pivot (last element) by swapping
2. recursive calls with left, right index manipulation w/r/t pivot index
+ in addition, use pivot index to select k-th smallest values after sorted
   

a = [0, 5, 2, 1, 6, (3)], (#) is pivot
    /                 \

ipark-CS

"""
Given the binary array, a move is defined as a swapping adjacent 1 and 0. 
Return the min number of moves to sort the array.
Here "sort" is defined as a grouping all 1's in one end, all 0's in the other end,
and which end doesn't matter. For example, arr=[1,1,0,0], no need to move as it's
already sorted.

Example 1:
Input:  arr = [1, 0, 1, 1]
Output: 1 

ipark-CS

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the minimumSwaps function below.
def minimumSwaps(arr):

ipark-CS

"""
Given binary integer array consisting of only 1's and 0's.
Rule1: You can jump either 1 or 2 steps at the current position.  
Rule2: The 1's must be avoided.
Determine the minimum number of jumps it will take to jump from the starting postion to the last cloud. 
Assuming that it is always possible to win the game.
"""
#!/bin/python3

import math