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:

Bisection search:

Newton Raphson: next_guess=guess-p(guess)/derivative(p(guess))


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.

complexity orders.PNG

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 🙂
  4. Law of addition:O(n)+O(n+n)=O(n+n^2)=O(n^2)
  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:

  1. Quadratic – nested loops.

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

 

 

 

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s