Thursday, November 13, 2008

Delete a node in single linked list

The solution to this is to copy the data from the next node into this node and delete the next node!. Ofcourse this wont work if the node to be deleted is the last node. Mark it as dummy in that case. If you have a Circular linked list, then this might be all the more interesting.

Tuesday, November 11, 2008

Two problems for the day

Robotic Arm movement: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37

Binary Search: http://codekata.pragprog.com/2007/01/kata_two_karate.html

To be updated...

Monday, November 10, 2008

Optimizing Loops

A few ways to optimize loops

Iterating through loops has the following structure in many cases:

for(int k=0; k<someVar.length(); k++)


Check it out, you execute the k=0 command, then you execute the comparison as well as the length method as many times as you have n variables to loop through. Finally you increment k n+1 times. This all leads to a lot of executions. To make it go faster:

int length = someVar.length();
for(int k=0; k<length; k++)


Taking the method call to length() out will increase the loop's speed slightly. However, you're still calling length from the variable table n times. So try it this way instead:

int length = someVar.length();
for(int k=length; k>0; --k)


This will iterate backwards. What that means, is that now you won't be pulling up 2 variables in the comparison. You'll only compare one variable to 0. Although, it isn't necessarily that much more beneficial to call length outside of the loop statement now since your call to length is only executed once.

Monday, November 3, 2008

Virtual Destructors

If an object (with a non-virtual destructor) is destroyed explicitly by applying the delete operator to a base-class pointer to the object, the base-class destructor function (matching the pointer type) is called on the object.

There is a simple solution to this problem: declare a virtual base-class destructor. This makes all derived-class destructors virtual even though they don't have the same name as the base-class destructor. Now, if the object in the hierarchy is destroyed explicitly by applying the delete operator to a base-class pointer to a derived-class object, the destructor for the appropriate class is called.

Virtual constructor: Constructors cannot be virtual. Declaring a constructor as a virtual function is a syntax error.

To be completed .. (Example)

References
WikiAnswers

Thursday, October 23, 2008

Amortized Analysis

Amortized analysis refers to finding the average running time per operation over a worst-case sequence of operations.

The method requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have state that persists between operations. The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O(n). However, a sequence of n insertions can always be done in O(n) time, so the amortized time per operation is O(n) / n = O(1).

The approach is going to be to somehow assign an artificial cost to each operation in the sequence. This artificial cost is called the _amortized cost_ of an operation. The key property required of amortized cost is that the total real cost of the sequence should be bounded by the total of the amortized costs of all the operations.

There are several techniques used in amortized analysis:

* Aggregate analysis determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the average cost to be T(n) / n.

* Accounting method determines the individual cost of each operation, combining its immediate execution time and its influence on the running time of future operations. Usually, many short-running operations accumulate a "debt" of unfavorable state in small increments, while rare long-running operations decrease it drastically.

* Potential method is like the accounting method, but overcharges operations early to compensate for undercharges later.

References:
http://en.wikipedia.org/wiki/Amortized
http://www.eli.sdsu.edu/courses/fall96/cs660/notes/amortizedAnalysis/amortizedAnalysis.html
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s03/www/amortized-analysis.txt

Sunday, September 14, 2008

GCD of 2 numbers

The algorithm reduces the problem of finding the GCD by repeatedly applying these identities:

  1. gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(0, 0) is not defined.
  2. If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.
  3. If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).
  4. If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u−v)/2, v). If both are odd and u <v, then gcd(u, v) = gcd((v-u)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.
  5. Repeat steps 3–4 until u = v, or (one more step) until u = 0. In either case, the result is 2kv, where k is the number of common factors of 2 found in step 2.

Since this definition is tail-recursive, a loop can be used to replace the recursion.




unsigned int gcd(unsigned int u, unsigned int v)
{
int shift;

/* GCD(0,x) := x */
if (u == 0 || v == 0)
return u | v;

/* Let shift := lg K, where K is the greatest power of 2
dividing both u and v. */
for (shift = 0; ((u | v) & 1) == 0; ++shift) {
u >>= 1;
v >>= 1;
}

while ((u & 1) == 0)
u >>= 1;

/* From here on, u is always odd. */
do {
while ((v & 1) == 0) /* Loop X */
v >>= 1;

/* Now u and v are both odd, so diff(u, v) is even.
Let u = min(u, v), v = diff(u, v)/2. */
if (u <= v) {
v -= u;
} else {
int diff = u - v;
u = v;
v = diff;
}
v >>= 1;
} while (v != 0);
return u;
}

Sunday, September 7, 2008

Strategy Pattern

The strategy pattern (also known as the policy pattern) allows algorithms to be selected at runtime.

The strategy pattern defines a family of algorithms, encapsulate each one, and makes them interchangeable. It lets the strategy (algorithm) to vary independently from the clients that use it.

The pattern uses composition instead of inheritance thus giving the flexibility to change the algorithm dynamically by a simple setStrategy() call. Each algorithm is given its own class.


//StrategyExample test application
public class StrategyExample {

public static void main(String[] args) {
Context context;

context = new Context(new ConcreteStrategyA());
context.execute();

context.setStrategy(new ConcreteStrategyB());
context.execute();
}
}
interface IStrategy {
void execute();
}


class ConcreteStrategyA implements IStrategy {
public void execute() {
System.out.println( "Called ConcreteStrategyA.execute()" );
}
}

class ConcreteStrategyB implements IStrategy {
public void execute() {
System.out.println( "Called ConcreteStrategyB.execute()" );
}
}


class Context {
IStrategy strategy;

// Constructor
public Context(IStrategy strategy) {
this.strategy = strategy;
}

public void setStrategy(IStrategy is){
this.strategy = is;
}

public void execute() {
this.strategy.execute();
}
}


(Example based on the example from wikipedia)
In this example the Context class execute method calls the execute method of the IStrategy class to do some task. The IStrategy interface is implemented by ConcreteStrategyA and ConcreteStrategyB, and the Context's class's method setStrategy can be called anytime to change the strategy from A to B, so that the execute function can switch the algorithm is uses whenever we change the strategy object.
Related Posts with Thumbnails