CodeStudy

Purpose Most programming languages provide for, while, recursion loop statements. Which one is best? for I know how many repeat needed Cannot repeat with certain condition (need to use if and break) Hard to use previous result to next repeated loop Good usage example : print numbers in array. while I do not know how many repeat needed repeat with certain condition Hard to use previous result to next repeated loop Good usage example : count how may words you typed recursion I know how many Stack Memory that will use repeat with certain condition Easy to use previous result to next repeated loop Good usage example: find 88th’s Fibonacci number additional considerable conditions Does your programming language provide tail recursion Program environment such as embedded, Android, or Web Conclusion

Hierarchy package: java.lang.Comparable Definition Sorting interface that designed for a condition by overriding compareTo method. For example, you can sort list in ascending order of size. about the compareTo() method if compareTo() method return positive number, swap the input parameters else will be remain same condition return First parameter < second parameter negative First parameter == second parameter 0 First parameter > second parameter positive How to use customObject implements Comparable<>

Hierarchy package: java.util.Comparator Definition Sorting interface that designed for mutiple special conditions by creating compare method. For example, you can sort list in ascending order of size and descending order of letters. about the compare() method if compare() method return positive number, swap the input parameters else will be remain same condition return First parameter < second parameter negative First parameter == second parameter 0 First parameter > second parameter positive How to use MyComparator implements Comparator<>

Definition Interface that can read any class in the collection framework. Thus, we can read arraylist or linkedlist or hashmap with iterator. why we use iterator? Since we can read any list or set with iterator, we do not have to fix or change code when you work with big projects. Hierarchy method hasNext() next() remove() method Example List list = new ArrayList();// arrayList list.add("1"); list.add("2"); list.add("3"); Iterator <string> itr = list.

conditional statement and loop statement in Python conditional statement (if statement) One Condition Keyword: if if [condition] : [space]code you want to learn Multiple Condition Keyword: elif if must there before use elif if [condition] : [space]code you want to learn elif [condition] : [space]code you want to learn elif [condition] : [space]code you want to learn Other than Condition Keyword: else if must there before use else if [condition] : [space]code you want to learn else : [space]code you want to learn if Statement Example a = 3 if a > 5: print("a is bigger than 5") elif a > 0: print("a is bigger than 0 but smaller than 5") else: print("a is negative") Loop Statement (for Statement) Repeat Example 10 times loop for i in range(10): print("Hi") list loop Example Repeat as much as elements in list a = ["A", "B", "C"] for i in a: print(i) # A B C list loop with index Example Repeat as much as elements in list for i, j in enumerate(a): print(i, ":", j) # 0 : A # 1 : B # 2 : C add two list and loop Example The pair’s data type is tuple numbers = [9, 7, 7] letters = ["z", "x", "y"] for pair in zip(numbers, letters): print(pair) # (9, 'z') # (7, 'x') # (7, 'y') Loop with certain index Example 5 to 9 for i in range(5, 10): # 5 ~ 9 print("Hello", i) # Hello 5 # Hello 6 # Hello 7 # Hello 8 # Hello 9 loop until certain condition loop until i is “o” a = "balloon" for i in a: print(i) if i == "o": break # b a l l o Loop Statement (while Statement) loop until certain condition loop until i is bigger than 5 i = 0 while i < 5: print(i) i = i + 1 # 0 1 2 3 4

Set Definition One of the data structure in python. Create set of data Data Structures in Python List: Tuple: ( ) Dictionary: { key : value } set: { } declaration use { and } to declare setA={1,3,4,"test"} # {1, 'test', 3, 4} setB={2,4,"test",5,6} # {2, 'test', 4, 5, 6} Characteristics No duplicated value Do not care about order set algebra(union, intersection, difference, symmetric difference) Set Algebra union Keyword: “|”, “union()”

Definition one of problems while using the hash algorithm. If the input value is different, the output value should be different. But, the output is same. We calls, “Hash Crash” Characteristics less hash crush is better hash algorithm No hash crush is almost impossible. Example [input]->[output] A->03 B->02 C->03 The output of A and C are same. This is hash crush. solution Most hash algorithm search next output when hash crush happen.

Definition one of properties for Hash algorithm map the expected inputs as evenly as possible over its output range without hash crash. Example [input]->[output] first hash algorithm A->03 B->02 C->03 second hash algorithm A->01 B->02 C->03 explanation if the uniformity of hash algorithm is high, it less create hash crush. Thus, the second hash algorithm’s uniformity is higher than the first hash algorithm conclusion high uniformity = less hash crush = higher possible to learn with O(1) of time complexity other questions Can we possible to make perfect hash algorithm that does not make any hash crush?

Definition hash function transfer any value to certain conditioned value such as length. If the input value is same, the output value should be same. In use encryption Hashtable is using hash function to store values quickly. Comparing two huge data to verify same file or not quickly. Kinds cryptographic hash function : hash function that used for encryption hash function : hash function that does not used for encryption Properties efficiency uniformity collision resistance pre-image resistance second pre-image resistance

Dictionary Definition One of the data structure in python. has key and value bined. You can fine value when you know the key very slimier with hashmap Data Structures in Python List Tuple Dictionary set declaration use { and } to declare the value can be list the key can be int or string. But not list. (TypeError: unhashable type: ‘list’) dictionary={"key1":"value1","key2":"value2","key3":"value3"} how to use indexing like List get() method difference between the indexing and get method If key does not exist, the indexing will return error.

Definition enum class is for define constant. It will contain the value that will not change during the program is working Reason for using the enum class Sometimes, the program need constant value that should not changed. We use enum class for define the value. We calls, “define Constant” History The notion of constant is came from C language. C used define Preprocessor and const keyward. C code example #include <stdio.

Definition Certain patterns of numbers. first and second numbers are always 0,1. next number is addition of previous two numbers The List of Fibonacci numbers $0,1,1,2,3,5,8,13,21,34,55…$ Recurrence Relation $F_0=0$ $F_1=1$ $F_n=F_{n-1}+F_{n-2}$ Example index fibonacci numbers calculation 0 0 0 1 1 1 2 1 0+1 3 2 1+1 4 3 1+2 5 5 2+3 6 8 3+5 7 13 5+8 8 21 8+13 9 34 13+21 10 55 21+34 11 89 34+55 12 144 55+89 13 233 89+144 14 377 144+233 15 610 233+377 16 987 377+610 get nth fibonacci number math public static int fib(int num) { double goldenRatio = (1 + Math.

Tuple Definition One of the data structure in python. Almost same as List But Tuple is not editable. Object. Data Structures in Python List Tuple Dictionary set declaration use “(” and “)” to declear. But, if there is a element in Tuple, you need to add comma tuple1=(1,) tuple2=(1,2,3) notTuple=(0) #wrong, this is int type. comma needed index structure same as List characteristic Tuple is not editable.

Definition one of sort array data structure based on binary tree insert data into binary tree and print out from the tree Algorithm steps insert data into binary tree The data sorted as binary tree print Java code public static void heapSort(int arr[]) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapTree(arr, n, i); // One by one extract an element from heap for (int i = n - 1; i > 0; i--) { // Move current root to end int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapTree(arr, i, 0); } } // To heapify a subtree rooted with node i which is // an index in arr[].

Definition one of sort algorithms Technique Decrease and Conquer Algorithm steps Recusively loop Recusively loop left side and right side until the input array cannot separated every separated parts only one element is in there. This is sorted. merge arrays with sort. Java code public static void mergeSort(int[] input) { mergeSortRecurr(input, 0, input.length - 1); } public static void mergeSortRecurr(int[] input, int left, int right) { if (left < right) { int midPos = left + (right - left) / 2; mergeSortRecurr(input, left, midPos); mergeSortRecurr(input, midPos + 1, right); merge(input, left, right, midPos); } } public static void merge(int[] input, int left, int right, int midPos) { //mid pos does not check unlike the left and right int temp1 = midPos - left + 1; int temp2 = right - midPos; //temp array and copy int[] L = new int[temp1]; int[] R = new int[temp2]; for (int i = 0; i < temp1; ++i) L[i] = input[left + i]; for (int j = 0; j < temp2; ++j) R[j] = input[midPos + 1 + j]; int i = 0; int j = 0; int k = left; while (i < temp1 && j < temp2) { if (L[i] <= R[j]) { input[k] = L[i]; ++i; } else { input[k] = R[j]; ++j; } ++k; } while (i < temp1) { input[k] = L[i]; ++i; ++k; } while (j < temp2) { input[k] = R[j]; ++j; ++k; } } Avg.

Definition one of sort algorithms The most important sort algorithm Use this algorithm anywhere with any languages The best way to avoid worst time complexity is pick pivot randomly. if program most not have $O(n^2)$, need to use other sorting algorithm. Technique Decrease and Conquer Algorithm steps Recusively loop based on Lomuto. pick pivot the most right element. left side will be smaller than pivot value and right side will be bigger than pivot.

Definition one of sort algorithms Technique Brute Force Algorithm steps first loop first to the end compare looping number and left side. if left side number is bigger than right side, swap them. since number swapped, check left side numbers and make sure the left side is getting smaller step 4 means that if left side is small and does not swap, it does not need to check further. Repeat 1~5 until all of them sorted.

List Definition One of the data structure in python. Almost same as array in other languages. Object. Data Structures in Python List Tuple Dictionary set declaration temp=[] temp=list() temp=[5,9,44] index structure characteristic List in List is possible. This is same as 2D array in other languages String in python is same as List slicing [starting index : ending index-1 : condition index] [0:8:3] = select index 0 to 7 by adding 3 [:8:] = select index 0 to 7 by adding 1 [7::] = select index 7 to -1 by adding 1 [::-1] = select index 0 to -1 by adding -1 a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] print(a[0:8:3]) # [0, 3, 6] print(a[:8:]) # [0, 1, 2, 3, 4, 5, 6, 7] print(a[7::]) # [7, 8, 9] print(a[::-1]) # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] Arithmetic Operation a=[1,2,3] b=["apple","house","computer"] print(a+b) # [1, 2, 3, 'apple', 'house', 'computer'] # print(a+3) # error # print(a-b) # error # print(a-3) # error # print(a*b) # error print(b*3) # ['apple', 'house', 'computer', 'apple', 'house', 'computer', 'apple', 'house', 'computer'] print(b*0) # [] # print(a/b) # error # print(a/3) # error add element append() = add a new element behind extend() = add new elements behind insert() = add new elements by index [] = add new elements by index condition a=[1,2,3,4,5,6,7,8,9] b=["apple","house","computer"] a.

Definition one of sort algorithms Technique Brute Force Algorithm steps find smallest number in the list swap the smallest number and first place the first element is sorted find smallest number in the list except the sorted element. swap the smallest number and second place Repeat 1~5 until all of them sorted. Example-Java public static int[] selectionSort(int[] input) { for (int i = 0; i < input.length - 1; ++i) { for (int j = input.

Definition one of sort algorithms Technique Brute Force Algorithm steps compare two numbers smaller number will be left and bigger number will be in right side. compare over and over again untill the end of the list Now, biggest number will stay in most right side. This number is sorted Start over from first number except sorted place. Repeat 1~5 until all of them sorted. Example-Java public static int[] bubbleSort(int[] input) { for (int i = 0; i < input.

Definition check every possible way to find answer. Points No efficiency most intuitive way to solving problems increase exponential growth one of exhaustive search Example If you find password with brute force algorithm, n=password digits, let’s assume 4 k=each digit can contain numbers, let’s assume 0~9 Then, all possible ways are $k^n=10^4=10000$ The combination can be in 10000 ways. When the passwords digits are more than 4, it will be exponential growth.

kinds of Arithmetic Operation in Python Symbol explaination return + Addition depend on input type - Subtraction depend on input type * Multiplication depend on input type / Division real number // Division Integer % Remaineder real number ** power of depend on input type and and logic gare T or F or or logic gate T or F < less than T or F > greater than T or F <= less than or equal T or F >= greater than or equal T or F == equal T or F Result +, -, *, /, //, %, **, <, >, <=, >= table A B result int int int A+B result int float float A+B result int bool-T int A+1 result int bool-F int A+0 result int none TypeError int String TypeError float bool-T float A+1 result float bool-F float A+0 result float none TypeError float String TypeError bool none TypeError bool String TypeError none String TypeError When computer created and programming language started, 1 was true and 0 was false.

Basic Search Algorithm Linear Search Binary Search Hashing Linear Search Definition check all of the list one by one. Time complexity O(n) Points It does not matter about date type need memory space as total list n Binary Search Definition check middle of list first. if the number is smaller than what you are looking for, check right side only and doing this continuously. It will decrease search list in half.

Definition Saperate big problem into small repeated parts and solve the problem. All Recursion can be converted to Loop. Good and bad points Loop Recursion intuitive complicated Long codes short codes good readability bad readability use less stack memories use much stack memories very low possiblity to get Stack overflow Stack overflow if too mcuh call very low possiblity to get overhead issue overhead issue: call function repeatly will make program slow each level of variable state will not saved each level of variable state will saved because of stack Actual code We should write recursion because it is good for reading and fixing it.

Definition A method of recursion optimization Principle When there is recursion, the recursive class remain in stack memory and it will cause overflow. The tail call elimination is created for fixing the overflow issue. If the reucursive class return everything at last, the class does need to remain in stack memory. Other Names tail call elimination tail call optimization How to Change return part of recursion to call function only.

Kinds of Variables scalar and non-scalar both object scalar int : integer float : real number bool : True or False none : Null non-scalar String : data values that are made up of ordered sequences of characters, such as “hello world” checking data type print(type(Variable)) Case-Sensitive a and A are different variable Casting x = str(3) # "4" y = int(3) # 4 z = float(3) # 4.

Clarity Input and Output Most mistakes are coming from misunderstanding of range for the input and output. We need to find the range of input and output specifically. Each Steps of Algorithm must be Clear The steps of algorithm separated clearly. Thus, you or co-workers may not misunderstand the code. Need to Study computer structure Some codes got issue because of computer structure. If you calculate int type addition, the result is wrong because integer overflow.

Definition specific method of solving the problem the problem: It need to be clear. input and output is stated in exact range. specific method: If you do not know how to solve that problem, you can solve it with specific steps. Example If you get drink from a vending machine, put cash select drink get drink This is kind of algorithm. However, it specfic enough for computers. get $3 cash from wallet find input location insert cash into the cending machine check how many kinds of drink choose drink what you want push button for the drink pick up the drink.

Definition Both interfaces are very similer because they are for sorting lists and arrays. However, one is for one condition and other one is for mutiple conditions. Difference Comparable Comparator java.lang package. java.util package. Comparable affects the original class Comparator doesn’t affect the original class compareTo() method with 1 parameter compare() method with 2 parameters Collections.sort(List) Collections.sort(List, Comparator) Arrays.

code name How ++i prefix increment operator i = i+1;return i; i++ postfix increment operator final int t = i; i = i+1; return t; –i prefix decrement operator i = i-1;return i; i– postfix decrement operator final int t = i; i = i-1; return t; int x = 2; int y = 2; System.

Definition Stable and unstable is depend on how sort any duplicated list. If the algorithm keeps original position of duplicated values, it is stable sort algorithm If the algorithm positioned duplicated values randomly, it is unstable sort algorithm Example raw list=[3(1), 7(1), 3(2), 4, 7(2), 9] stable sorted list=[3(1), 3(2), 4, 7(1), 7(2), 9] unstable sorted list=[3(2), 3(1), 4, 7(2), 7(1), 9] Stable Sorting Bubble Sort Insertion Sort Merge Sort

Kinds of Data Type in Java Primitive type Java provides 8 kinds of Primitive type. Primitive data types cannot contain null actual value will saved in Stack memory. data type base memory defult value range of data range of data in number boolean 1 byte false true, false true, false byte 1 byte 0 -127 ~ 128 $-2^{7}$~ $(2^{7}-1)$ short 2 byte 0 -32,768 ~ 32,767 $-2^{15}$~ $(2^{15}-1)$ int 4 byte 0 -2,147,483,648 ~ 2,147,483,647 $-2^{31}$~ $(2^{31}-1)$ long 8 byte 0L -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 $-2^{63}$~ $(2^{63}-1)$ float 4 byte 0.

Result code result char type + int type return unicode char type - int type error int type + char type return unicode int type - char type error char type + char type return unicode char type - char type return unicode String is not Primitive Data Type. This is object example of use For lexicographical order for (int i = 0; i < order.

What is Error Programs run something that is not what programmers wanted or shutdown unexpectedly. Any causes of that action are Error. Kinds of Errors compile-time error compile failed. usually, wrong lanuage keyword used. python does not understand “System.out.println” This code is for JAVA. runtime error crash during the programs run. put values in int arr[5] that array size is 3 logical error programmer created wrong process. you wanted to put blue in variable x.

Inclusive - Including the last number Exclusive - Excluding the last number In Computer Science, inclusive/exclusive apply to a number range Example inclusive If a function will compute $2^i$ where $i = 1, 2, …, n$. $i$ can have values from 1 up to and including the value n. We says, n is Included in Inclusive 1 through 10 (inclusive) = [1, 10] 1 2 3 4 5 6 7 8 9 10 exclusive If a function will compute $2^i$ where i = 1, 2, .

Definition algorithmic problem solving technique that split into many simple subproblems and reduce steps of subproblems. In other wards, separates into subproblems and get solution by addition of all subproblems. Example if you calculate $2^1+2^2+2^3+2^4+2^5$ and display each numbers, $2^1=2=2$ $2^2=22=2^12$ $2^3=222=2^2*2$ $2^4=2222=2^32$ $2^5=22222=2^4*2$ since you need to calculate each of numbers ($2^1,2^2,2^3,2^4,2^5$), you can skip some of parts that you already calculated. When you calculate the $2^5$, you done have to calculate $2^4$ if that number $2^4$ is already calculated.