# Computer science

Determines whether a string is legal – syntax

Determines whether a string has meaning – static semantics.

Assigns a meaning to a legal sentence – semantics

## Guess and checks:

### Converting decimal to binary:

take a decimal number -> 0.375

How can we represent this in binary?

Multiply this decimal number by a power of 2 which can convert it into a whole number. 2^3=8 in this case which gives 8*0.375=3

then convert this whole number to binary (11)

Divide by 2^3 (shift right) to get 0.011(binary)=0*2^-1+1*2^-2+1*2^-3

If we can’t find p such that x*2^p doesn’t give a whole number, then we can only get approximate binary representation.

### Recursion:

Can a problem be represented as a smaller version of the same problem?

For example, finding the factorial of n can be n times smaller version of factorial of (n-1).

multiplication of a times b can be a + multiplication of a times (b-1).

Towers of hanoi is the paragon problem used popularly to apply recursion.

gcd(a,b) is same as gcd of (b,a%b) until b becomes 0, when b becomes 0 then the answer is a.

fibonacci

An example of self-referencing.

calling a function from inside the same function with different arguments probably.

Complexity:

Evaluating efficiency of programs:

1. Measure with a timer.
2. Count the operations.
3. Abstract notion of order of growth.

Big OH Notation: Upper bound on the asymptotic growth, often called the order of growth.

1. Upper bound on the asymptotic growth, often called the order of growth.
2. Big oh or O(): to describe worst case.
1. You can say the complexity of 5*n+2 as the order of n, O(n).
2. ignore additive and multiplicative constants.
3. focus on dominant terms.
3. Order of dominancy –
1. c^n(exponential)>n^c(polynomila)>nlog(n)(loglinear)>n(linear)>log(n)>1
2. efficiency in opposite order 🙂
5. Law of multiplication:O(n)*O(n)=O(n^2)

logarithmic complexity:

1. bisection search.
2. binary search of a list.
3. look out for division operations as well (heuristic).

Linear complexity:

1. Factorial – both iterative and recursive.
2. n dependent loop.

Log-linear complexity:

1. Merge sort.

polynomial complexity:

Exponential complexity:

1. mostly in recursive cases-Towers of hanoi, generating all subsets(power set).

Bogo/Monkey/stupid sort:

Shuffling and checking iteratively until all the elements are sorted.

Bubble Sort:

Check two consecutive elements and swap them based on order. Do this all along the list for multiple times.

O(n^2)

Selection Sort:

Find the smallest element and put it at the beginning. find the next smallest and put it at the second place and go on.

O(n^2) – Quadratic, more efficient than bubble sort.

Advantage in this is you can stop after getting certain number of sorted elements.

Merge sort:

Divide and Conquer –

O(n*log(n)) – loglinear