relocatable address

The address generated by the compiler are relocatable addresses.
See : Introduction to computer-based imaging systems By Divyendu Sinha, Edward R. Dougherty , page.213 :

Assuming the page size as 64 KB (2¹⁶):
The compiler generated relocatable addresses as if the entire program were to be loaded at once. The page number and offset can be easily computed from the relocatable address. Since the offset must be a nonnegative number smaller than the page size, the offset is the least significant 16 bits of the relocatable address. The remaining 25-16 = 9 bits specify the page number. Consider the relocatable address 145678. Since

145678 (decimal) = 0 00000010 00111001 00001110 (binary),
we have the page number as 2 (or 000000010 in binary) and the offset as 14,606( or 0011100100001110 in binary).

If the page size is changed later on to 32KB, programs need not be recompiled to run on the system. Computation of page number and offset is done by the memory manager

Basic introduction to probability

Surprisingly the basic introduction to probability was found in a biology book!
Here is the summary:
Product Rule:
When two or more events are independent, the probability that they will occur in succession is calculated using the product rule--their individual probabilities are multiplied. Ex : probability of getting two heads in succession is 1/2 x 1/2 = 1/4

Sum Rule:
Sum Rule is applied when there are two or more different ways of obtaining the same outcome; that is, the probability tat either event A or event B will occur equals P(A) + P(B)

Source: Billogy: Te dynamic science by Peter Russell p.240

reversing a linked list

Few of the most elegant solutions for reversing a linked list:
1. Stanford : Linked list problems
2. Algorithms : 4th Edition : Stacks and Queues
The code is reproduced here and is very elegant:

public Node reverse(Node first) {
    if (first == null || first.next == null) return first;
    Node second = first.next;
    Node rest = reverse(second);
    second.next = first;
    first.next  = null;
    return rest;
}

Implementing stack using queues and vice versa

To implement stack using queues, with two cases : constant insertion time, linear removal time and vice-a-versa, see this stack overflow discussion

To implement a queue using two stacks,

// Basic solution
class Queue
{
    Stack s1; // used as main stack
    Stack s2; // used as stack for temp storage
    
    enqueue(T& t)
    {
        if ( !s1.empty() ) s1.push(t);
        else  s2.push(t);
    }

    T dequeue()
    {
        T t;
        if ( s1.isEmpty() && s2.isEmpty() ) throw Exception();
        return __dequeue(s1,s2);
    }
    T __dequeue(Stack& from, Stack& to) 
    {
        size_t n = from.count();
        if (!n) return __dequeue(to, from);
        move(from, to, n-1);
        t = from.pop();
        move(to, from, n-1);
        return t;
    }
}

// optimized solution : by saving the last operation
class Queue
{
    Stack s1; // used as main stack
    Stack s2; // used as stack for temp storage
    
    enqueue(T& t)
    {
        if ( last_operation == Dequeue ) 
            move( s2,s1);
        s1.push(t);
        last_operation = Enqueue;
    }

    T dequeue()
    {
        if ( s1.isEmpty() && s2.isEmpty() ) throw Exception();
        // if the last operation was dequeue, the required element
        // is already on the temp usage stack s2
        if ( last_operation == Dequeue )
            return s2.pop();

        T t= __dequeue(s1,s2);
        last_operation = Dequeue;
    }
    T __dequeue(Stack& from, Stack& to) 
    {
        size_t n = from.count();
        if (!n) return __dequeue(to, from);
        move(from, to, n-1);
        t = from.pop();
        move(to, from, n-1);
        return t;
    }
}

Also there is a interesting solution in Algorithms and Programming: Problems and Solutions - Page 90

We maintain the following invariant relation: stacks whose bottoms are
put together, form the queue. (In other words, listing all elements of one stack from
top to bottom and then of the other stack from bottom to top, we list all the queue
elements in the proper order.) To add an element to the queue, it is enough to add it to
one of the stacks. To check if the queue is empty, we must check that both stacks are
empty. When taking the first element from the queue, we should distinguish between
two cases. If the stack that contains the first element is not empty, there is no problem.
If that stack is empty, the required element is buried under all the elements of the
second stack. In this case, we move all the elements one-by-one onto the first stack
(their ordering is reversed) and return to the first case.
The number of operations for this step is not limited by any constant. However,
the requirement posed in the problem is still met. Indeed, any element of the queue
can participate in such a process at most once during its presence in the queue.

f(f(n)) = -n

Originally from stackoverflow
While working on this puzzle, became confused, but this can be simplified if we first write the state diagram and then the code. The state diagram should consider odd/even and +ve/-ve numbers.
A simple control flow can be as follows:
A: 1 → 2
B: 2 → -1
C: -1 → -2
D: -2 → 1
E: 1 → 2

Notice that E and A are same.
Once we have this,

if n is +ve:
   if n is odd : return n+1
   if n is even : return -1* (n-1)
else if n is -ve:
   if n is odd : return n-1
   if n is even : return -1 * (n+1)

We get the highest rated solution on stackoverflow.

Sorting and array of 0 and 1's in single pass

Question from Princeton.edu's sorting and searching :

Partitioning. Write a static method that sorts a Comparable array that is known to have at most two different values.

Hint: Maintain two pointers, one starting at the left end and moving right, the other starting at the right end and moving left. Maintain the invariant that all elements to the left of the left pointer are equal to the smaller of the two values and all elements to the right of the right pointer are equal to the larger of the two values.

Solution in python:

"""
Sort an array of 0's and 1's

Loop invariant
[0 0 0 0 0 0 |----unknown-----| 1 1 1 1 1 1]
             i                j
All elements < i are 0
All element > j are 1
elements between i and j are unknown.
"""

a1 = [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1]
a2 = [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
a3 = [ 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ]

def sort_01(a):
    i=0
    j=len(a)-1
    while i < j:
        while i < j and (a[i] < a[j] or a[i]==0): i += 1
        while i < j and a[i] <= a[j]: j -= 1
        if i < j: a[i],a[j] = 0,1
    print(a)

sort_01(a1)
sort_01(a2)
sort_01(a3)

importance of vector::reserve

Not using reserve results in quite some extra work.

struct Foo
{
 static int i ;
 int f;
 Foo():f(i++){ cout << "in ctor:" << i << endl; }
 Foo(const Foo&):f(i++){ cout << "in copy ctor:" << i << endl; }
};
int Foo::i = 1;

void tst_vec()
{
 vector v;
 v.reserve(10);
 Foo f ;
 v.push_back(f);
 v.push_back(Foo());
 v.push_back(Foo());
 cout << "---" << endl;
 Foo& temp = v[0];
}

---

with reserve:
in ctor:2
in copy ctor:3
in ctor:4
in copy ctor:5
in ctor:6
in copy ctor:7
---

without reserve:
in ctor:2
in copy ctor:3
in ctor:4
in copy ctor:5
in copy ctor:6
in ctor:7
in copy ctor:8
in copy ctor:9
in copy ctor:10

virtual destructors and valgrind

Was curious to know the effects of missing a virtual destructor, and ran the program on valgrind:

Valgrind reported a memory leak.

user@ubuntu:~/devel/effective_cpp$ g++ virt_dtor.cpp -ggdb
user@ubuntu:~/devel/effective_cpp$ cat virt_dtor.cpp 
#include 
using namespace std;

class Base{
    public:
    ~Base() { cout << "~Base()" << endl; }
};

class Der: public Base{
    public:
        int* array;
     Der(){ array = new int[10]; }
    ~Der() { cout << "~Der()" << endl; delete[] array; }
};

int main()
{
    Base* b  = new Der;
    delete b;
}
user@ubuntu:~/devel/effective_cpp$ valgrind --leak-check=full ./a.out 
==2791== Memcheck, a memory error detector
==2791== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==2791== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==2791== Command: ./a.out
==2791== 
~Base()
==2791== 
==2791== HEAP SUMMARY:
==2791==     in use at exit: 40 bytes in 1 blocks
==2791==   total heap usage: 2 allocs, 1 frees, 44 bytes allocated
==2791== 
==2791== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==2791==    at 0x4025FE5: operator new[](unsigned int) (vg_replace_malloc.c:299)
==2791==    by 0x80488C8: Der::Der() (virt_dtor.cpp:12)
==2791==    by 0x80487A7: main (virt_dtor.cpp:18)
==2791== 
==2791== LEAK SUMMARY:
==2791==    definitely lost: 40 bytes in 1 blocks
==2791==    indirectly lost: 0 bytes in 0 blocks
==2791==      possibly lost: 0 bytes in 0 blocks
==2791==    still reachable: 0 bytes in 0 blocks
==2791==         suppressed: 0 bytes in 0 blocks
==2791== 
==2791== For counts of detected and suppressed errors, rerun with: -v
==2791== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 19 from 8)

Different types of mutexes

Some of the different types of Mutex:
-- Fair / Unfair Mutex : A mutex which allows access in the order of locking
-- Reentrant : which allows recursive locking, helpful when there are recursive calls in the code. See also man page description of PTHREAD_MUTEX_RECURSIVE
-- Scalable Mutex
-- Sleep or spin : spin is optimal for short waits and sleep for long waits. And also while spining, there is no need for context switch.

Reference : Intel threading building blocks: outfitting C++ for multi-core processor ... By James Reinders, p.114

reversing a string in C++

C++ string does not have reverse member function,
this is how we can do it:

string s("abcdef");
reverse(s.begin(), s.end());

Binary Search of a string

Interesting problem : How can we apply binary search to search a string in a big word file?

We use a suffix array and sort this array. Once sorted, we apply binary search on this array. See Bentley Programming Pearls p.172. See also : Large-scale genome sequence processing By Masahiro Kasahara, Shinichi Morishita, p.56

We can optimize this even further by storing the radix representation of strings (see:Cormen's section in Hashing) and the problem will be reduced to binary search of numbers.

C++ : non-local static object initialization problem

If one global object is directly dependent on another global object, the order of their construction is undefined. The best solution for it, suggested by Scott Meyers is to use singletons : ( see : Scott Meyers "Item 47: Ensure that non-local static objects are initialized before they're used." Effective C++ )

The basis of this approach is the observation that although C++ says next to nothing about when a nonlocal static object is initialized, it specifies quite precisely when a static object inside a function (i.e. a local static object) is initialized: it's when the object's definition is first encountered during a call to that function. So if you replace direct accesses to non-local static objects with calls to functions that return references to local static objects inside them, you're guaranteed that the references you get back from the functions will refer to initialized objects. As a bonus, if you never call a function emulating a nonlocal
static object, you never incur the cost of constructing and destructing the object, something that can't be said for true non-local static objects

Multiple Inheritance : Overriding same named functions in derived.

Technique for overriding same named functions in Base classes in a multiple inheritance: ( See : Item 43 in Effective C++ , see also, Exceptional C++ )

#include < iostream >
using namespace std;

class Base1{
    public:
    virtual int func(){ cout << "base1::func" << endl; }
};

class Base2{
    public:
    virtual int func(){ cout << "base2::func" << endl; }
};

class Der : public Base1, public Base2
{
    public:
    // overrides both Base1, and Base func
    virtual int func() { cout << "der::func" << endl; }
};

/** Using auxillary classes  */
class AuxBase1: public Base1{
    public:
        virtual int base1_func() = 0;
        virtual int func() {return base1_func(); }
};
class AuxBase2: public Base2{
    public:
        virtual int base2_func() = 0;
        virtual int func() {return base2_func(); }
};

class Der2 : public AuxBase1, public AuxBase2
{
    int base1_func() { cout << __func__ << endl; }
    int base2_func() { cout << __func__ << endl; }
    
};

int main()
{
    Der *pd = new Der();
    Base1 *p1 = pd;
    Base2 *p2 = pd;
    p1->func();
    p2->func();
    pd->func();

    Der2 *pd2 = new Der2();
    p1 = pd2;
    p2 = pd2;
    p1->func();
    p2->func();
}

Output :

der::func
der::func
der::func
base1_func
base2_func

Finding anagrams, rhyming words and misspelled words in a dictionary.

Surprisingly, finding anagrams, rhyming words and corrections (for misspelled words) have a common O(n) solution.
- To find anagrams, we have a dictionary in which all the words are sorted internally and then compare the input( which is again sorted ). see Bentley (1998) Programming Pearls Addison-Wesley for further discussion on this.

- To find rhyming words, we have a dictionary in which we have the words in reverse order and we reverse the input and compare for similarity towards the end (say last 3 characters )

- A find the spelling correction, we use a related hybrid approach, to quote Knuth The Art of Computer Programming Vol.3 (Sorting and Searching) p.394 :

More complicated search problems can often be reduced to the simpler case
considered here. For example, suppose that the keys are words that might be
slightly misspelled; we might want to find the correct record in spite of this
error. If we make two copies of the file, one in which the keys are in normal
lexicographic order and another in which they are ordered from right to left (as
if the words were spelled backwards), a misspelled search argument will probably
agree up to half or more of its length with an entry in one of these two files.

Binary search to find the last and first occurance of an key

Given an sorted array with duplicates how do we find the first and last occurance of a Key?

There are three solutions in the code fragment below, all take log(n); the most efficient is from Bentley ( see Programming Pearls Column 9, a bit trickier to understand )

The obvious way to solve it is to keep saving the last found location. In case of normal binary search, we stop one the key is found. But to find the first occurrence (or the last occurance), instead of stopping, we set the upper bound to mid-1 ( and to find the last occurrence, we set the lower bound to mid+1 ) and continue. When the element is not found, we simply return the last occurrence. Bentley's method from Programming Pearls is obviously more efficient, since it eliminates one comparison in the inner loop (however, I found it a bit trickier to understand and implement).

Interesting observation in copy constructor

The following code makes an interesting observation w.r.t copy constructors. copy ctor need not be called even when = is used in object definition, a neat optimization by calling the ctor directly..


#include
using namespace std;

class Foo{
public:
Foo(const Foo&){ cout << "in cpy ctor" << endl; }
Foo(int a) { cout << "in ctro:" << a << endl;}
};

int main()
{
Foo f = 1; // Does this call copy constructor??
Foo f2(3);
Foo g = f;
}


When Executed :
in ctro:1
in ctro:3
in cpy ctor

Sorting linked lists

Methods for sorting linked lists :
* Merge sort ( see Knuth Vol.3 p.164 : Alogrithm L )
* Radix sort ( see Knuth Vol.3 p.175 )

He also poses the question "What is the best list-sorting method for six-digit keys, for use on the MIX computer?"(p.309) at the end of the Chapter on sorting and gives the following answer:
For small N : list insertion, for medium N (say 64) : list merge; for large N, radix list sort. (p.701)

Knuth makes an interesting observation:

An ever-increasing number of "pipeline" or "number-crunching" computers have appeared in recent years. These machines have multiple arithmetic units and look-ahead circuitry so that memory references and computation can be highly overlapped; but their efficiency deteriorates noticeably in the presence of conditional branch instructions unless the branch almost always goes the same way. The inner loop of a radix sort is well adapted to such machines, because it is a straight iterative calculation of typical number-crunching form. Therefore radix sorting is usually more efficient than any other known method for internal sorting on such machines, provided that N is not too small and the keys are not too long. (p.175 Vol.3)

Sorting when all the input elements are unknown

While reading Knuth's TAOCP vol.3 Sorting and Searching, p.139, another characteristic of sorting algorithms to me : Few sorting techniques require the entire elements to be present before-hand before sorting, for ex: Selection sort. Other sorting techniques do not need this, for ex: insertion sort (the sort of card-players). To quote Knuth:
A selection method requires all of the input items to be present before sorting may proceed, and it generates the final outputs one by one in a sequence.

This is essentially the opposite of insertion, where the inputs are received sequentially but we don not know any of the final outputs until sorting is complete.
(Knuth(1998) ''TAOCP'', vol.3 p.139)

Segregating the positive and negative numbers

[Problem from Knuth,TAOCP, vol.3, p.136]
Design an algorithm that rearranges all the numbers in a given table so that all negative values precede all nonnegative one. (The items need not be sorted completely, just separated between negative and nonnegative.) Your algorithm should use the minimum possible number of exchanges.


Knuth's solution:
Knuth suggests a modified radix exchange sort which compares the MSB (bit corresponding to sign )

Another way to do this is to write a specialized comparison routine which is passed to a sorting routine. The routine can be something like:

compare(a,b)
  if a<0 and b<0: return 0 // same
  if a>0 and b>0: return 0 // same
  return a>b // one -ve, one +ve

Other solution is to include counting sort technique.
The counting sort technique is implemented below in python and is stable.

import random 

N = 50
# generate an array of +ve and -ve numbers.
array = random.sample( range(-N, N), N )

# counting techinque : 2 pass algorithm
def counting_seperate(array):
    num_pos = 0
    num_neg = 0
    for i in array:
        if i<0: num_neg += 1
        else: num_pos += 1
    # destination array
    dest = [0] * len(array)

    #the final index of a +ve number, can simply be len of array
    num_pos += num_neg

    # Count from n-1 to 0 : stable 
    i = len(array)-1
    while i>=0:
        if array[i]< 0: 
            dest[num_neg-1]=array[i]
            num_neg -= 1 # decrease the index 
        else:
            dest[num_pos-1] = array[i]
            num_pos -= 1 # decrease the index
        i -= 1

    print( "segregated array:", dest )

if __name__ == "__main__":
    print( "Original array: ", array )
    counting_seperate(array)

Finding the mth smallest of a given set on n elements.

[Problem posed by C.A.R.Hoare] Suppose that, instead of sorting an entire file, we only want to determine the mth smallest of a given set of n elements. Show that quicksort can be adapted to this purpose avoiding many of the computations required to do a complete sort. ( Knuth(1998)The Art of Computer Programming Vol.3:Sorting and Searching, p.136 // Bentley (2011) Programming Pearls Column 11 )

In the normal partitioning process of quicksort, if partition position s=m, stop;
if s < m, use the same techinque to find (m-s)th position;
If s > m, find the mth smallest element in the left hand. 

Searching a sorted 2D array

A 2D Array is sorted on its row and columns, find a key.

"""
Program to search an element in a 2-d array
The 2D array has sorted rows and sorted columns
"""
from random import randrange

N=10 # we will generate a NxN array

# initializes a 2-d array sorted on rows and columns
ARRAY = [ [i for i in range(j,N+j)] for j in range(N) ]

KEY = randrange(0,ARRAY[N-1][N-1])

# We will skip the brute force method of O(n^2) 

# Attempt 1 : Use binary search
def binary_search(lst, l, u, key):
    if l > u : return -1;
    m = (l+u)/2
    if lst[m] == key: return m
    if lst[m] < key: return binary_search(lst, m+1,u, key)
    else : return binary_search(lst, l, m-1,key)


def binsearch_method():
    "Use binary search on each row : takes loglinear time: O( n log(n) )"
    for i in range(N):
        idx = binary_search(ARRAY[i],0,len(ARRAY[i])-1,KEY)
        if idx != -1:
            print("found %d at %d,%d" % (KEY, i,idx))
            return

def linear_method():
    "search in linear time"
    currow = 0
    curcol = N-1
    steps = 0
    while curcol > 0 and currow < N:
        steps += 1
        #print(currow, curcol)
        # If the elem in a col is greater than key, we can skip the entire col
        if ARRAY[currow][curcol] > KEY: curcol -= 1 
        # If the first element in a row is > than key or if the last elem is < key, we skip the entire row.
        if ARRAY[currow][0] > KEY or ARRAY[currow][curcol] < KEY: currow += 1
        if ARRAY[currow][curcol] == KEY:
            print("found %d at %d,%d in %d steps" % (KEY, currow,curcol, steps) )
            return

if __name__ == "__main__":
    print("Key is %d" % KEY )
    binsearch_method()
    linear_method()

The Celebrity Puzzle

Celebrity is a person whom everybody knows but he knows nobody. You have gone to a party. There are total n persons in the party. Your job is to find the celebrity in the party. You can ask questions of the form Does Mr. X know Mr. Y ?. You will get a binary answer for each such question asked. Find the celebrity by asking only O(n) questions.

References : Python Algorithms: Mastering Basic Algorithms in the Python Language pp.85-86 By Magnus Lie Hetland

Solution (in python):

####

from random import randrange
# Number of persons
N = 100
# the graph of connections built using random values.
G = [ [randrange(2) for i in range(N)] for i in range(N) ]

def create_celebrity():
    C = randrange(N)
    # ensure that we have celebrity at C
    for i in range(N):
        G[i][C] = 1
        G[C][i] = 0
    print("rand celeb : %d" % C)


def bruteforce():
    """Brute force solution to the celebrity problem"""
    n = len(G)
    steps = 0
    for i in range(N):
        is_celeb = 1
        for j in range(N):
            steps += 1
            if i == j: continue
            # i knows j and is not a celebrity
            # j does not know i, break
            if G[i][j] or not G[j][i]: 
                is_celeb = 0;
                break 
        if is_celeb:
            print("found celeb at %d in %d steps" % (i, steps) )
            return i

def bruteforce_improved():
    """Improvement to brute force"""
    # At every-step we can eliminate either i or j
    u,v = 0,1
    steps = 0
    while u < N and v < N:
        steps += 1
        if u == v: v = u+1
        # if u knows v, then u is not a celeb, 
        # if u does not know v, then v is not a celeb
        if G[u][v]: u = u+1
        else : v = v+1
    print("found celeb at %d in %d steps" % (u, steps) )

def linear_time():
    """ finds in linear time : see : 
        Python Algorithms: Mastering Basic Algorithms in the Python Language p.86
        By Magnus Lie Hetland
    """
    u,v = 0,1 # the first two persons
    steps = 0
    # c corresponds to the third to the last person...
    for c in range(2, N):
        steps += 1
        if G[u][v]: u=c # u knows v, replace u
        else:       v=c # otherwise, u is a candidate

    if v==c : c=u #if v has reached end of list, use u.
    else:     c=v

    for i in range(N):
        if c==i: continue
        if G[c][i]:break
        if not G[i][c]: break
    else:
        print("found celeb at %d in %d steps" % (c, steps) )



if __name__ == '__main__':
    create_celebrity()
    bruteforce()
    bruteforce_improved()
    linear_time()

Maximum subarray problem

Given a array with -ve and +ve integers, find the sub-array with maximum sum.

Answer :
See John Bentley (1986) Programming Perls Addison Wesley for discussion of various implementations, ranging from brute force, O(n^3), solution which remembers previous sums O(n^2), divide and conquer O(n log(n)) and the linear approach. The book can be downloaded here

See also : V.V. Muniswamy in Design And Analysis Of Algorithms

The below code in python uses the technique described in Muniswamy and Bentley above, using dynamic programming and runs in linear time:

a = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]


def linear_method2():
    maxsofar = 0
    maxhere = 0
    for i in range(0, len(a)):
        maxhere = max(maxhere + a[i], 0)
        maxsofar = max(maxsofar, maxhere)
        print( a[:i+1])
        print( 'maxhere %d maxsofar %d ' % (maxhere, maxsofar) )
    print( maxsofar)

def linear_method1():
    # [a] [b] [c] [d]  [e]  [f] [g] ...
    #      |   |   |    |
    #      L   U  i-1   i           
    L = 0 # lowerbound of the max subarray
    U = 0 # upperbound of the max subarray
    summax = 0 # the current max subarray sum, i.e sum(a[L:U])
    sumcur = 0 # the current sum from L to i-1

    for i in range(0, len(a) ):
        # If introducing the next element increases the maximum sum,
        # then include the element
        if (a[i]+sumcur) > summax and sumcur>0 :
            print( ' (a[i]+sumcur) > summax ')
            U = i
            sumcur += a[i]
            summax = sumcur
        # If the current element cannot be introduced above ( since there are -ve in b/w ),
        # but current element is greater than max sum so far => start from this point
        elif a[i] > summax:
            print( 'a[i] > summax' )
            L=i
            U=i
            summax = sumcur = a[i]
        # increase the current sum
        else:
            sumcur += a[i]
        print( 'sumcur %d summax %d L %d U %d Array %s' % (sumcur, summax, L, U, a[L:U+1]) )
    print('maxsubarray : %s' % a[L:U+1])
    print('sum : %d' % summax)
    
linear_method2()
print('------------')
linear_method1()

See also : http://en.wikipedia.org/wiki/Maximum_subarray_problem