0

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. 🙂

Advertisements
0

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;

0

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.

1

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);
0

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.

1

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.

0

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?