Computational_Thinking.md

Computational Thinking

Two Difficult Aspects of Programming

1. Programming language syntax and library usage
2. Logic (Hard Logic)

Soft Logic vs Hard Logic

• In everyday life
  • Soft Logic is useful because it is fast
  • Although logically imprecise expressions are used, there is an assumption that everyone already knows what they mean
• Programming uses Hard Logic
  • All expressions in programming languages originate from logic
  • Hard Logic is needed to understand the numerous algorithms used

1. Logic and Proof

Proposition

• A statement or sentence whose truth or falsity can be determined

• Expressed as p, q, r ...

  • If p -> q is true, then ~q -> ~p is also true (Contrapositive)

• ex)

  • Seoul is the capital of South Korea

  • 1 + 1 = 3

  • If two sides have equal length, then it is an isosceles triangle.

    -> If it is not an isosceles triangle, then no matter which two sides you choose, the lengths of the two sides are different

Truth Value

• Expresses true or false
• T, F or 1, 0

Tautology

: A proposition whose truth value is always true

Contradiction

: A proposition whose truth value is always false

Contingent Proposition

• A proposition that is neither a tautology nor a contradiction
• A proposition that varies depending on the situation

Conditional Proposition

• When p and q are propositions, a proposition where p is the condition (or cause) and q is the conclusion (or result)
• p -> q (if p then q)
• False only when p is True and q is False

Biconditional Proposition

• When p and q are propositions, a proposition where both p and q are conditions and conclusions
• p <-> q (if p then q, and if q then p)
• True when p and q have the same truth value

Propositional Operations (Connectives)

• Negation NOT

  • When p is a proposition, the truth value of the proposition is reversed
  • Denoted as ~p
    • Read as not p or the negation of p

• Conjunction AND

  • When p and q are propositions, a proposition that is true only when both p and q are true
  • p ^ q
    • p and q

• Disjunction OR

  • When p and q are propositions, a proposition that is false only when both p and q are false
  • p v q
    • p or q

• Exclusive Disjunction XOR

  • When p and q are propositions, a proposition that is true when only one of p or q is true
  • p ⊕ q
    • p xor q

Operator Precedence

• ~ > v , ^ > -> , <->

Proof

• A proof must be expressible as a propositional formula
• Usually the exact propositional formula is not written out, but fundamentally it can be converted into one
• Many misunderstandings about proofs arise from confusing p -> q with p <-> q

Mathematical Induction and Levels of Proof

• Basic form of mathematical induction
  • If P(1) is true and P(n) -> P(n+1) is true, then P(n) is true for all natural numbers n
• Strong form of mathematical induction
  • If P(1) is true and P(1) ^ P(2) ^ ... ^ P(n) -> P(n+1) is true (all cases are true), then P(n) is true for all natural numbers n

Vacuous Truth (pseudo-proposition) Logic

If you're the police chief, then I'm the president!

F -> () is always true

• If you assume a false proposition is true, then any proposition becomes true
  • ex) If you win the lottery, I'll buy you a car
    • If you don't win the lottery, not buying a car is not a lie, and buying one even without winning is also not a lie
    • By the same principle, if we say 2 is odd, then 5 being even or odd is not false

Only T -> F is definitively false

2. Numbers and Representation

• Computers represent numbers by collecting bits that can express 0/1
• Using k bits, it is possible to represent from 0 to 2^k -1 (from 1 to 2^k)
  • In fact, it is not necessarily that range!
  • It depends on the agreed-upon method, but in any case it is possible to represent up to 2^k different values
    • This is exactly the same process as using k digits in decimal to represent from 0 to 10^k -1

How many bits are needed to represent a value n?

• 2^k -1 >= n must hold

  • That is, 2^k >= n+1

  • Equivalently, k >= log(n+1)

    -> Approximately logn bits are needed

  • x = logn and 2^x = n refer to the same thing!

+

What is logn

1. The answer to "what power of 2 gives n"
2. The answer to "how many bits are needed to represent n"
3. The answer to "starting from 1 and continuously doubling, how many times until you reach n"
4. The answer to "when continuously dividing n by 2, how many divisions until you get approximately 1"

• When x = logn, comparing x and n, x is smaller, and as n grows, they diverge enormously
  • When you want to represent something that changes drastically in a smaller scale, use log!
• The value of a 100-digit decimal number is so large it's unreadable!
• In computer science, the base of log is always 2
• The address space of a 32-bit computer is 2^32 = approximately 4 billion addresses
• 
  • When we reach the last (1+1+ ...)
    • n/ 2^k = 1
    • n = 2^k
    • k = logn
  • The total number of parentheses is logn
  • So when factoring the entire expression by n, we get nlogn

Big-O Complexity

Exercises

1. What is the range of numbers that can be represented with logn bits in binary representation?

   • With n bits -> 2^n values

   • With logn bits -> n values

2. If the game of 20 Questions proceeds ideally, how many possible answers can be guessed?

   • Each question can yield 2 possible answers
   • The total number of questions is 20
   • Therefore, the number of possible answers is 2^20

3. When n is sufficiently large, which value is greater?

   1. 2n < n^2
      • When the number is infinitely large, the constant in front of n can be ignored, and the growth rate of n^2 is much greater than n
   2. 2^(n/2) < sqrt(3^n)
      • sqrt(3^n) = 3^(n/2)
      • That is, comparing 2^n and 3^n, 3^n is greater
   3. 2^(nlogn) > n!
      • Assuming base 2,
      • n^n > n!
   4. log2^(2n) < n*sqrt(n)
      • 2n < n*sqrt(n)

4. When x = loga(yz), express x using logarithms with base 2. However, each logarithm function's argument must be a single letter.

   

5. Find the inverse functions of the following functions

   1. f(x) = log(x-3) -5
      • f^-1(x) = 2^(x+5) +3
   2. f(x) = 3 log(x+3) +1
   3. f(x) = 2 x 3^x -1

Sets and Combinatorics

Sets

• To prove that A is a subset of B for two sets A and B is equivalent to showing that any element of A is contained in B
  • ex) To prove that all multiples of 4 are multiples of 2, it suffices to show that 4k = 2(2k)!
• To prove that two sets A and B are equal, it suffices to prove that A is a subset of B and B is a subset of A

Combinations

• Combinatorics generally refers to problems that involve counting the number of cases
• The number of combinations is sometimes expressed using C, but the parenthetical notation such as (5 choose 2) = 10 is used more frequently

+

Mathematical Induction

One of the methods of mathematical proof, primarily used to show that a proposition holds for all natural numbers.

Mathematical induction consists of two steps.

First, show that the given proposition holds for 1 (or generally for k).

Next, show that if the proposition holds for any natural number n greater than or equal to 1 (or k), then it also holds for n+1.

Then, by mathematical induction, the given proposition holds for all natural numbers (or all natural numbers greater than or equal to k).

+

Proof by Contradiction

• When trying to prove a proposition, assume the negation of that proposition is true
• Show that this assumption leads to a contradiction, thereby demonstrating the original proposition is true

Exercises

4. Basic Formulas

master crm

5. Recursion

• Recursion is a function that calls itself

• (Can it ever terminate?)

  • A function has input, and if it calls itself with the same input, it obviously cannot terminate
  • It can terminate with different input!

• A function is something that codes a method to solve a problem

  • It does not solve just a single case of a problem!
    • If properly coded, it must solve all cases of the problem it addresses

• Mathematical induction can be used for proof

  1. The problem can be solved when n is 0
  2. If the problem can be solved for n-1, then it can also be solved for n
     • If the above two are true, then it is true that the problem can be solved for all possible n