Posted in tips

Long Tables in LaTeX

I was struggling to get a table span across page boundaries in LaTeX with tabular directive, but in vain. Then I found this piece and came to know that there is something called as longtable. Now my table spans multiple pages. 🙂

Posted in software

Reverse a SLL

Here is my pseudocode:

(You will be given a list head and you will have to return another list head that points to the reversed linked list)

curNode = listHead;previousNode = NULL;

if (!curNode) return curNode;

while (curNode != NULL) {

tmpNode = curNode->next;
curNode->next = previousNode;

previousNode = curNode;

curNode = tmp;

}

return previousNode;

Posted in problem solving, Programming

Finding Whether a SLL is circular or not.

SLL – Singly Linked List.

We all know the obvious one:

List *ptr1;

if (!curPtr) return 1; //An empty list is circular or non-circular?

ptr1 = curPtr->next;

while (ptr2 != NULL) {

if(ptr1 == ptr2) return 0;

ptr2 = ptr2->next;

}

return 1;

In this case, if the list has n elements and the list is circular, then there will be n pointer dereferences.

I have another one in mind: instead of traversing ptr1 in single steps, traverse it in double steps – so we will loop over fast:

ptr1=curPtr->next;

while(ptr1 != NULL) {

if(ptr1 == curPtr || ptr1->next == curPtr) return 0;

if(ptr1->next) ptr1 = ptr1->next->next;

else ptr1 = NULL;

}

return 1

Although I wonder if this is any better than the above one. At best, this is some loop unrolling I think. 🙂

I came to know about another mechanism. Instead of having a single pointer, you keep two pointers. You make the second pointer traverse fast – that is instead of walking past single node, you walk past two nodes at a time – the basic idea being if it is a circular list, you will quickly loop over and come back to the slow moving pointer. Even if it is not a circular pointer, you will fall off the list quickly.

The interesting thing here is analysis – first question to ask is – will they meet eventually?, because it may happen that the fast walking pointer might skip the slow walking pointer in a hurry. So this needs some proof that both will meet.

So here is such an argument that they will eventually meet: after the slow and the fast pointers (so to speak) are initialized to i and i+1, it will take exactly n-1 iterations for them to meet. To make sense of it, consider this: after n-1 iterations, the slow pointer will be at (i+n-1)%n th position – which is equivalent to (i-1)%n. The fast pointer will be at:

(i+1 + 2(n-1))%n

= (i+1+2n -2)%n

= (i-1+2n)%n

= (i-1)%n th position.

Hence after n-1 iterations, both will be at (i-1)%n th position which means they both meet. But, this is slower than the alternative where we keep the first pointer static and move only the second pointer.

Posted in Programming

Duff’s Device

We have heard enough about it. I was interested in knowing how it is legal C. Only Wikipedia has a word about this:

The device is valid, legal C by virtue of the relaxed specification of the switch statement in the language’s definition. At the time of the device’s invention this was the first edition of The C Programming Language which requires only that the controlled statement of the switch be a syntactically valid (compound) statement within which case labels can appear prefixing any sub-statement.

FOLDOC says that for maximum obfuscation, the switch braces can be removed to get a code like below. Looks definitely confusing, but should experiment with it more to understand what such statements are valid and what such statements are not valid. However, C bible book also says that cases are just convenient labels for statements.

    register n = (count + 7) / 8;
    switch (count % 8)
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
    } while (--n > 0);
Posted in problem solving, Programming

Which is faster?

memcpy(b,a,sizeof(int)*n) or the following code:

WORD *a;

WORD *b;

for (int i=0; i<n; i++)

*a++ = *b++;

It turns out that Intel microprocessors have an instruction called repz movs[bdw], which when given the source, destination and count in esi, edi and ecx respectively, it will copy the memory in a single go. bdw stand for byte, word and double word. How will the execution performance vary if we give b or d or w, given that count is properly set in ecx? Given the fact that the data bus width is 32 bit (atleast on IA-32 architectures), if count is greater than 4, it would always make sense to move double words at once.

Update: Even otherwise, it looks to me like the book keeping overhead will be less if the memory copy is implemented as a single instruction. Got this thought when I was reading this.

Posted in problem solving, Programming

7-11 Riddle

This is the problem: You go to a shop and buy 4 items. The shop keeper tells you that it costs 7.11/- You ask him how he got it. He says that he multiplied the prices. You shout, “You are not supposed to multiply, but add the prices.” The shopkeeper laughs and says either way the price is the same. What are the prices of the items?

I could not solve this problem. Because at a glance, it occured to me that given the following information:

a + b + c + d = 7.11

abcd = 7.11

this problem cannot be solved analytically. But it never came to that with some tricks one can solve this problem programatically. That is the most revealing thing in this problem.

For brevity, lets multiply the prices by 100. Then the sum becomes 711 and the product becomes 711,000,000. One can bluntly keep three nested loops like this to solve it:

m = 711000000;

for (a=1; a< 711; a++) {

for (b=1; b < 711-a; ; b++) {

for (c=1; c < 711-a-b;;c++) {

d = 711 – a – b – c;

if ((a*b*c*d) == m) return true;

}

}

}

return false;

The very first optimization happens by observing the fact that any number that we select should divide m. So, we would not go into the next level of loop if the counter of the current loop cannot divide m.

Posted in problem solving

Regexp ab, ba

Construct a regular expression (or a DFA) which describes (or accepts) strings that have same number of abs and bas in them. I came up with the following automata. It has 6 states. Each half devoted to processing strings that start with either a or b respectively.

s0, <none> (final)

s0, a -> s1

s1, a -> s1

s1, b -> s2

s2, b -> s2

s2, a -> s3 (final)

s3, a -> s1

s3, b -> s2

s0, b -> s4

s4, a -> s5

s4, b -> s4

s5, a -> s5

s5, b ->s6 (final)

s6, a -> s5

s6, b -> s4

This could be easily understood by a diagram, than the above dry equations. But the point is that ab+a and ba+b are the two pumping lemmas that needs to be checked for.

Another problem is to see whether this can be achieved with the alphabet {a, b, c} instead of just {a, b}. That is when we come to understand why the above FA works. 🙂 In the former case, if the string starts with a, then it will be of the form (ab*)* and if the string starts with b, then it will be of the form (ba*)*. In either case, we can keep track of the pumping lemmas I mentioned above.

However, I am tempted to think that just absorbing cs along the way, can get us to recognize the string. William has asked to prove that such an FA cannot exist. But I am not able to see how it cannot exist. I can modify the above table, to add sn, c -> sn, for every n and can be done with it right?

Posted in problem solving, Programming

Swap Contents of Two Variables

So, what is new about this?

We have two well known answers to this question:

a = a – b;

b = a – b;

a = a – b;

and

a = a ^ b;

b = a ^ b;

a = a ^ b;

Interesting to note is that the XOR version does not care about the type of the data. For example, if a and b are int and float, then the subtraction may not result in exact values, but, the XOR operation does it without a hitch.

There are other versions like keeping them in a single statement. One interesting version is this:

((a ^=b) || 1) && ((b ^=1) || 1) && ((a ^=b) || 1);

Without those 1s and ||s, it is clear that it is just a fancy way of putting the normal method. But why are those extra operators? If the result is 0, then the rest of the swap fails because of the logical and operator. So, I think this one is better:

a ^=b, b ^=a, a^=b

There was also a mention of:

a ^= b ^= a ^= b;

This, as I learn, does not work because there are two assignments to a in this line and even though the expressions are evaluated from right to left, the compiler is apparently free to choose any of the one value to update a.

This, as I again learn, has something to do with sequence points in C and C++. Need to figure that out. Man, I am learning a lot from William Wu’s forums. 🙂

Posted in problem solving

Stacks and Heaps

The question is to determine programmatically whether stack and heap grows up or down in memory.

As for stack, one way is to declare two variables in the function and list their addresses. If the first variable’s address is greater than or less than that of second’s. But we cannot make sure that the compiler allocates the variables in the order they were declared.

So, an improvement over that is to see the addresses of the passed parameters and the local variables. This solution assumes that the caller would allocate space for the parameters and then calls the function in which case we can determine whether the stack is growing up or down. But in some cases the ompiler may not ensure that calling parameters are allocated first.

The last option (as far as I know, programmatically) is to know the address of a local variable of a called function from a calling function and comparing it with the address of a calling function’s local variable. We can be reasonably sure that the variables in a called function is allocated after the calling function’s variable are allocated.

As for heap, it is dependent on the memory manager’s implementation. If we some how know the unit of allocation for the memory manager, then we can allocate two such units of memory and see their addresses. But even then, it might happen that due to fragmentation, the memory that is allocated afterwards may get a lower memory address which is then bound to misinterpretation. So for, heap I think we cannot deterministically find out.

Posted in problem solving

FSA to find whether a binary number is divisible by 3

The procedure can be explained as follows: Scan the list of numbers and keep looking for the remainder of the string when divided by 3.

There are three cases (and states):

  1. When the remainder is zero: When we are in this state, no matter how many zeros we add, we will get a remainder of zero. If we add a 1, then the remainder is 1 and it goes to state 1
  2. When the remainder is one: If we add 1, then it is equivalent to multiplying the number by 2 and adding one – which means if we had x that had remainder 1, then now we have (2x+1)%3, which is equivalent to 3%3, which is zero. Hence it goes to state 1. When we add 0, then we multiply the number by 2, whence the remainder becomes 2 and it goes to state 2.
  3. When the remainder is two: If we add 0 to it, then we are multiplying the number by 2. When x%3 is 2, by simple arithmetic we can find that (2x)%3 is 1, so it goes to state 1.  If we add 1 to it, then (2x+1)%3 is 2 only (again by simple arithmetic) in which case it remains in state 2.

Using this reasoning, we can construct a DFA to check for divisibility by any number.