what is Dynamic Programming

what is Dynamic Programming

  2월 18, 2022    Eunhan's library

---

Dynamic Programming

Definition

One of problem solving technique

Split huge problem into many simple subproblems and reduce steps of subproblems.
Then get solution by addition of all subproblems.

Example

if you calculate $2^1+2^2+2^3+2^4+2^5$,

You can find answer by calculating
$2+(2*2)+(2*2*2)+(2*2*2*2)+(2*2*2*2*2)$

However, there is another way in computer.
$2^1=2=2$
$2^2=2*2=2^1*2$
$2^3=2*2*2=2^2*2$
$2^4=2*2*2*2=2^3*2$
$2^5=2*2*2*2*2=2^4*2$

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.

Read More

what is Tail Recursion

  2월 10, 2022    Eunhan's library

---

what is Tail Recursion

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.
Return should not contain any operation.

Compiler

Since tail recursion is depend on compiler, computer language need to support

• Java: No
• Kotlin: Yes
• C++: Yes
• C : Yes
• C# : Yes
• Swift : Yes
• goLang: No

Example-factorial calculation, Kotlin

fun main() {
    println(TailFactorialRecursive(5, 1))
    println(NormalFactorialRecursive(5))
}

tailrec fun TailFactorialRecursive(n: Int, sum: Int): Int {
    if (n == 1) {
        return sum
    }
    return TailFactorialRecursive(n - 1, n * sum)
}


fun NormalFactorialRecursive(n: Int): Int {
    if (n == 1) {
        return 1
    }
    return n * NormalFactorialRecursive(n - 1)
}

Explaination

For the NormalFactorialRecursive, the recursive class have to wait for calculating

n * NormalFactorialRecursive(n - 1)

For the TailFactorialRecursive, the recursive class do not need to wait for calculating

FactorialRecursive(n - 1, n * sum)

Read More

what is Good Code

  2월 09, 2022    Eunhan's library

---

what is Good Code

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. However, we cannot find why the integer overflow exist if you do not know the computer structure.

The result should come out on time.

It does not matter how good codes you made, the output should be come out currectly on time.

The algorithm should be possible to porting.

In other word, we should not use some function that specific programming languages have. For example, Lisp is specialized in AI and it have many functions to help building good AI. If you use finction that only Lisp has, then you need to change the language to Python, it may cause issues. Unless you have to, you should avoid it.

The algorithm should be most efficient.

There are verious way to solve problems and algorithm should be most effective in the situation.

Read More

What is Algorithm

What is Algorithm

  2월 08, 2022    Eunhan's library

---

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,

1. put cash
2. select drink
3. get drink

This is kind of algorithm. However, it specfic enough for computers.

1. get $3 cash from wallet
2. find input location
3. insert cash into the cending machine
4. check how many kinds of drink
5. choose drink what you want
6. push button for the drink
7. pick up the drink.

It can be more specific and detailed. It can be depend on computer languages and what you want to do.

Read More

i++ Vs. ++i

i++ Vs. ++i

  2월 06, 2022    Eunhan's library

---

what is difference between prefix operator (++i) and postfix operator (i++)

Definition

Some programming languages provide short code for increase or decrease value.
By using the prefix and postfix operators, you can write code faster.

Purpose

Thus, i=i+1 is same as i+=1 is same as i++ and ++i.
But, what is difference between prefix operator (++i) and postfix operator (i++)?

Inner code

Example 1

int x = 2;
int y = 2;
  
System.out.println(x * y++); //4
System.out.println(x); //2
System.out.println(y); //3

Because i++ happens after run the code,

1. run $x*y$
2. print $x*y=2*2=4$
3. add 1 to y

Example 2

int x = 2;
int y = 2;

System.out.println(x * ++y); //6
System.out.println(x); //2
System.out.println(y); //3

Because ++i happens before run the code,

1. add 1 to y
2. run $x*y$
3. print $x*y=2*3=6$

conclusion

• ++i wil give you slightly better speed and memory.
• If you are working with backend(such as Java), this is not important. However, if you are working with console games(such as C++), this is important.
• i++ will happen after run the code
• ++i will happen before run the code

Read More

stable sorts Vs. unstable sorts

stable sorts Vs. unstable sorts

  2월 05, 2022    Eunhan's library

---

what is difference between stable sorts vs. unstable sorts

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(position 1), 7(position 2), 3(position 3), 4, 7(position 5), 9]
stable sorted list=[3(position 1), 3(position 3), 4, 7(position 2), 7(position 5), 9]
unstable sorted list=[3(position 3), 3(position 1), 4, 7(position 5), 7(position 2), 9]

Stable Sorting

Bubble Sort
Insertion Sort
Merge Sort
Counting Sort
Bucket Sort
Radix Sort

Unstable Sorting

Selection sort
Heap Sort
Shell Sort
Quick Sort

Read More

For, While, Recursion - Which loop statement is best?

For, While, Recursion - Which loop statement is best?

  1월 30, 2022    Eunhan's library

---

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

Read More