Coupon Accepted Successfully!


Question 11

Explain the BigOh notation.

Time complexity

The Big Oh for the function f(n) states that

f(n)=O(g(n)); iff there exist positive constants c and d such that: f(n) <=c*g(n) for all n,n>=d.

Here are some examples...

1       ->Constant
logn    ->Logarithmic
n       ->Linear
nlogn   ->nlogn
n*n     ->quadratic
n*n*n   ->cubic
2^n     ->exponential
n!      ->Factorial

We also have a few other notations...

Omega notation

f(n)=Omega(g(n)), iff positive constants c and d exist such as f(n)>=cg(n) for all n, n>=d.

Theta notation

f(n)=Theta(g(n)), iff positive constants c1 and c2 and an d exists such that c1g(n)<=f(n)<=c2g(n) for all n, n>=d.

Little Oh(o)

f(n)=og(n), iff f(n)=Og(n) and f(n)!=Omega(g(n)).

Then there is also something called Space complexity...

Fixed part : This is the independent of the instance characteristics. This typically includes the instruction space (i.e. space for the code), space for simple variables and fixed-size component variables, space for constants, and so on.

Variable part: A variable part that consists of the space needed by the component variables whose size depends on the particular problem instance being solved, dynamically allocated space (to the extent that this space depends on the instance characteristics); and the recursion stack space (in so far as this space depends on the instance characteristics).

A complete description of these concepts is out of the scope of this website. There are plenty of books and millions of pages on the Internet. Help yourself!

Question 12

Give the most important types of algorithms.

There are five important basic designs for algorithms.

They are:

  • Divide and conquer : For a function to compute on n inputs the divide and conquer strategy suggests the inputs into a k distinct subsets, 1
  • The greedy method : The greedy method suggests that one can devise an algorithm that works in stages, considering one input at a time. At each stage, a decision is made regarding whether a particular input is an optimal solution. An example for solution using greedy method is "knapsack problem". Greedy algorithms attempt not only to find a solution, but to find the ideal solution to any given problem.
  • Dynamic programming : Dynamic Programming is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions. An example for algorithm using dynamic programming is "multistage graphs". This class remembers older results and attempts to use this to speed the process of finding new results.
  • Back-tracking : Here if we reach a dead-end, we use the stack to pop-off the dead end and try something else we had not tried before. The famous 8-queens problem uses back tracking. Backtracking algorithms test for a solution, if one is found the algorithm has solved, if not it recurs once and tests again, continuing until a solution is found.
  • Branch and bound : Branch and bound algorithms form a tree of subproblems to the primary problem, following each branch until it is either solved or lumped in with another branch.

Question 13

What is marshalling and demarshalling?

When objects in memory are to be passed across a network to another host or persisted to storage, their in-memory representation must be converted to a suitable out-of-memory format. This process is called marshalling, and converting back to an in memory representation is called demarshalling. During marshalling, the objects must be respresented with enough information that the destination host can understand the type of object being created. The objects? state data must be converted to the appropriate format. Complex object trees that refer to each other via object references (or pointers) need to refer to each other via some form of ID that is independent of any memory model. During demarshalling, the destination host must reverse all that and must also validate that the objects it receives are consistent with the expected object type (i.e. it validate that it doesn?t get a string where it expects a number).

Test Your Skills Now!
Take a Quiz now
Reviewer Name