AI class and ML class

I attended the online Introduction to AI class and the online Machine learning courses offered by Stanford University Professors. First and foremost I thank Prof. Andrew Ng, Prof. Peter Norvig and Prof. Sebastian Thrun and Stanford for making this available at almost no cost!. The courses were fun, awesome and enjoyable and the teachers were so excellent.

I just got a certificate of accomplishment for the AI course( yet to receive a mail from the Machine Learning Class as it just got completed yesterday). I scored 98.4% and remained in the top 10% of the class. I am glad that I scored 100 in the final examination and the AAAI has announced a one year free membership  for the top 10% as per this link http://www.aaai.org/Membership/ai-course-offer.php"( would have been happier if i would have got free USENIX membership) . I am bit disappointed that i could have done better if i had reviewed some of my homework submissions ( because of lack of time i could not do it). Given the tight time schedule that i was in and no prior experience (other than A* search,propositional logic which i studied long back and having studied in a flawed university higher education system which even had a subject called visual programming(VB/VC++) as mains in the CS engineering curriculum), the experience of receiving high quality education in itself was a fulfilling and fortunate experience.

I felt the ML class was excellent not to say about Prof. Andrew Ng awesome ability to explain tough math equations in simple and intuitive that even a layman could understand and the course had programming exercises(auto graded,very good and interesting applications in real world )and review questions and no examinations[ i had a perfect score on all programming exercises & review questions, hope to see a nice score on certificate of accomplishment when i receive it). The AI class in-class quizzes, homework, midterm and final were all interesting and exciting given the countless discussions it spawned on various discussion forums (like aiqus,reddit,facebook,plus etc) groups and explanations and justification of answers. Finally this idea of online education in itself a big idea in that it is a fundamental shift from the current education system and allows high quality higher education system ( especially of subjects that don't demand too much lab facilities) to be available to a wide set of audience and it's reach across the world to people who could not afford.

Finally here is the statement of accomplishment and my final examination scores:

For those of you who are interested in the lectures/midterm/homework and final of the AI class, here is the linkhttp://www.wonderwhy-er.com/ai-class/ for the videos.

UVA 11616 (Roman Numerals)

Code:

UVA 352(The Seasonal War - DFS flood fill)

Code:

Question & Programs - I

1. There is mxn matrix of 0's and 1's. If a location has 1, then turn that all elements which fall in that row and column corresponding to this element to ones.

2. Write code to print all valid n pairs of parenthesis.

3. Write code to check whether two strings are anagrams of each other.

4. Write code to check if a given binary tree is a binary search tree.

5. Write code to sort an array of 0's and 1's in O(n) time.

6. Implement queue using stack.

7. Write code to print all combination of strings.

Questions/programs

1. Write code to demonstrate livelock.
(the code below end being in a livelock based on timing issues.)

2. Implement memmove function


3. Implement circular buffer

4. Implement aligned malloc/free function where the alignment factor is a power of 2.


5. Sort odd numbers in descending order and even numbers in ascending order.

6. Write code to check if a given linked list is palindrome or not.

7. Write code to print all permutations of a string.

basic low-level and bit manipulation programs/questions.

Question #1: Check whether a platform is little endian or big endian?


Question #2: Convert little endian to big endian and vice-versa.

Question #3: Impelement offsetof macro.

Question #4: Implement count bits set in a number, check if power of power 2 and bit operation to set/reset/reverse/reset the ith bit of a number

Question #5: Implement a method to find maximum of two numbers without using comparsion operators.

Question #6: Add two numbers without using + arithmetic operator.

Question #7: Code to set bits between indexes i and j of a number n equal to y.

Question #8: Swap odd and even bits of a number

Question: Implement a float to string conversion function ( without using sprintf or snprintf)

Code:

Minimum Spanning Tree - Prim's Algorithm (UVA 10034)

Minimum spanning tree of a (connected,weighted) graph is a tree that spans all vertices and has the minimum weight among all the spanning trees of that graph.The UVA problem 10034 can be solved using a minimum spanning tree algorithm. I use the Prim Jarnik algorithm which is a greedy algorithm which starts with any vertex and picking the lowest cost edge from this vertex
and continuing to build by picking lowest edges along each step to this tree.
Algorithm:
Start with any vertex u.
(We maintain dist[v] and parent[v] that indicate the minimum distance to v from parent[v]
in code)
Initialize dist[u] = 0, parent[u]=0(u)
Repeat all vertices are spanned the steps below
Mark u as visited.
Choose the minimal edge (u,v) that spans from this vertex u.
[Find v which is the one with dist[v] min among all vertices and not visited.
Find all w adj to u, update dist[w], parent[w] if dist[w] from this vertex is shorter]
Add this edge to the spanning tree.
Code (for problem UVA 10034):

Topological Sort

UVA problem 10305 is based on topological sort. The problem of topological sort is to find an ordering among vertices(suppose there are n vertices numbered 1 to n ) in a directed cyclic graph such that for paths (i,j) in the graph, i comes before j in the ordering. This can be to schedule tasks that have a precedence/constraint relation (such as in the problem above).
Idea behind the algorithm:
Push all vertices that indegree 0 on to a queue.
Repeat until queue is empty
Remove vertex v from queue.
Output v
for all vertices w adjacent to v
decrement the indegree of w.
if indegree of w becomes zero add it to queue
Code ( for the problem):

Algorithmic Questions(I)

Question #1: There is an array in which all elements of that array get repeated thrice but for one element. Give an efficient algorithm to find the unique element.
Answer: If the elements are repeated twice in the array but for one, we would have got the solution by xor of all elements which would give the element once. But here the elements are repeated thrice so this logic doesn't apply here.
To get solution, we make use of the following:
1. Maintain a variable ones which at any point in iteration of the array contain elements that have appeared
only once.
2. Maintain a variable twos which at any point in iteration of the array will contain elements that appeared twice.
3. Any number that appears the third time should get removed from both ones & twos.
The following code addresses this:
int
finduniq(int *x, int n)
{
int ones=0, twos=0;
int elem, rem;
int i;

for ( i = 0; i < n; i++ ) {
twos |= ones & x[i]; // step #2.
ones ^= x[i]; // step #1.

rem = ~(ones & twos);
ones &= rem; // step #3
twos &= rem; // step #3.
}
return ones;
}


Question #2: Find the majority element (element that appears more than 50% of time). Find it in O(n) times.
One simple solution would be for each element, scan and count number of times they occur. Report the element that more half the number of element in the array. This is clearly O(n^2).
Another solution which is better is sort the array and scan to find the element in majority of the time. This is O(nlogn).
An algorithm that could do this in O(n) time:
1. Maintain two variables current(keeping track of an current element) and counter (initialized to zero).
2. If counter is not zero and the element you see is same as current, increment count else decrease by one.
3. if counter is zero, then change current to the element you are looking at.
4. after iteration of array is over, scan through and check if current appears more than half the time in the array and then report it.

Design Patterns

I am reading the book

The book is very excellent with good examples and nice illustrations written in a very brilliant way and I believe it's a must read for anyone interested in OO design.

Return Value Optimization

Question: How many times does copy constructor will be called in the below piece of code?
#include
using namespace std;
class X
{
public:
X()
{
cout<<"\n constructor called";
}
X(const X& x) {
cout<<"\n copy constructor called";
}
X fun(){
return X();
}
};
int
main()
{
X x;
X x1 = x.fun();
return 0;
}

Answer: Ideally you would expect the copy constructor to be called twice in this case.But if you compile the program g++, you would be surprised to see that no calls to copy constructor would be made. The compiler in this case does some optimization avoiding calls to the copy constructor. This optimization is what is called the Return Value Optimization (RVO). Essentially it does this by allocating an hidden object on the caller's stack and pass a this pointer to the function and the return value is assigned to this hidden object.

Maximum Product (contiguous) in an array

Question: Given an array containing postive, negative and zero integers, find the maximum subarray product in O(n) time.This is same as problem UVA 11059. Here is the code code for this problem(nice one!):

#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
/* Algorithm:
The array contain +ve, -ve and zero numbers.
Multiplying by zero doesn't increase the product.
So partition the array around zero numbers and find
the maximum product in each of the subarray.
` The subarray contain positive and negative numbers.
If the negative array in the subarray is even, the maxproduct
will be the entire array.
In case the number of negative numbers in the array is odd, then
we have to exclude a negative number in the contiguous sequence.
This can be done as follows. We identify the note of the 1st(left)
negative and calculate the product value from it,
*/
long long int
submaxprod(int *a, int start, int end)
{
int i;
int lprod=1,rprod=1;
int lneg=0,rneg=0;
long long int mprod=1;
int negcount = 0;
int num = end - start + 1;
for ( i = 0; i < num; i++ )
{
mprod *= a[i];
if ( a[i] > 0 && lneg == 0 )
lprod *= a[i];
else if ( a[i] > 0 && rneg != 0 )
rprod *= a[i];
else if ( a[i] < 0 && lneg != 0 ) {
negcount++;
rneg=a[i];
rprod=1;
}
else {
negcount++;
lneg=a[i];
rneg=a[i]; 
}
}
if ( (negcount > 0 && num == 1 ) 
( negcount%2 == 0 ) )
return mprod;
else {
long long int maxp = max(lneg*lprod, rneg*rprod);
return mprod/maxp;
}
}
long long int
maxproduct(int *a, int n)
{
int i;
long long int maxprod = INT_MIN;
long long int maxsubprod;
int start = 0;
for ( i = 0; i < n; i++ )
{
if ( a[i] == 0 ) {
maxsubprod = submaxprod(a, start, i-1);
start = i+1;
if ( maxsubprod > maxprod )
maxprod = maxsubprod;
}
else if ( i == n-1 ) {
maxsubprod = submaxprod(a, start,i);
if ( maxsubprod > maxprod )
{
maxprod = maxsubprod;
}
}
}
if ( maxprod < 0 ) maxprod = 0;
return maxprod;
}
int
main(int argc, char** argv)
{
int n,i;
int count = 1;
while ( cin>>n ) {
int a[n];
for ( i = 0; i < n; i++ ) 
{
cin>>a[i];
}
long long int y = maxproduct(a,n);
printf("Case #%d: The maximum product is %lld.\n\n", count++,y);
}
return 0;
}

man pages

Not all man pages are correct!(in fact confusing and wrong). Here is one.

Long time!

I am blogging after a long time. Been busy investigating varied topics(aided by videos on world-wide web and one of my colleague friend at work place) like biomechanics,bone remodelling, heliocopter/aeroplane lift,mechanics,principles etc., magnetic levitation trains only just out of curiosity to know about how this things work. I tried to hack up a apartment search website for bangalore (using google fusion tables,google maps, scraping data from craiglist and other sites & facebook integration) over a weekend and could not be done with it and won't be returning to it until september of this year atleast and so off for now on this activity and i have other personal and professional activity to do.

          Finally Yahoo! in their release of Yahoo! mail had fixed/corrected/acted logically which i mentioned in my previous blog entry on Yahoo! Main New, that is, they replaced it with single text box at top-right and two text boxes 'search mail' and 'search web'. Yahoo! always like top right, okay, it looks okay and the UI looks bit disoriented or font looking bad. Their display advertising on top seems to be gone and appear right ( finally the engineers mind works!) and now on left side, they seem to have some features like integration with facebook which looks cool. Still the search mail doesn't have advanced option that Gmail has got which search by from,to, date ranges. To implement such a feature require strong backend infrastructure which google has BigTable(Yahoo! - PNUTS?).This is particularly useful if you are subscribed to high voluminous mailing lists like the kernel mailing list and you have millions of mails in your inbox and at some point you want to get to a 'previous "important" mail' you remember may be based on date, time, words etc. which will narrow search and time. Other thing in both gmail and yahoo! mail, you get older, oldest,newer,newest links that make jump within search results and instead i believe it should be replaced by number 1,2,3,... + oldest+newest like the bottom on google search result.

  I am hoping to see search within domain in bing which i mentioned in blog post here. Again this kind of the implementation should be flexibly in case of google probably because of  their big table backend infrastructure. Not sure how M$ backend looks like and depending on it, it could take time, messier to support this feature. Hope to convert some drafts into posts. Bye for now.

   

x86 memory management and linux kernel (quick notes)

I am supposed to give a training on memory management. Here are some notes that I made for that purpose:

Real Mode Addressing

Memory is the storehouse for code, data ( which could be stack, heap and global data) of various programs which the CPU acts on. In this talk, I specifically cover memory management with respect to x86 processors and the linux operating system. The goals of  an operating system is to manage the memory among multiple processes giving each process it's own memory(address) space which offers protection and isolation. The Operating System achieves this goals in tandem with the facilities provided by the hardware.

    Memory is byte-addressable and the contents of cell ( which is 8-bits wide) is accessed by an address. The i386 machine when it boots up starts in 'real-mode'(when CS gets reloaded via a jmp) in which 1 MB of memory is addressable. This is due to historical reasons adopted by Intel so that code written would be backward compatible with it's legacy 16-bit processor 8086. 8086 processors have 16-bit registers and this means that using a 16-bit quantity we should be able to address 2¹⁶ = 64K bytes of memory.  But how do we address up to 1MB?       In the intel 8086, the memory is divided into 64K segments and we use a pair of registers (segment register:offset register) to address and derive the 20-bit physical address. The segments start on a 16 byte boundary and the segment registers could be CS,DS,SS,ES,FS(which are 16 bits wide) and the offset registers are IP,AX,BX,CX,DX. The 1 MB of memory is usually what we call as conventional memory. Above 1 MB of memory is what is termed as the extended memory or hi memory.

Here is the schematic diagram of how the MMU unit in 8086/80186 translates the pairs, let's us say CS:IP into a 20-bit physical address.

Protected Mode Addressing

The 80386 introduced the protected mode which has a 32-bit virtual address space and has support for paging. The address translation is a two phase process, in which the MMU makes uses  of segmentation unit to translate the logical address into linear address  and the paging unit translates the linear address into physical address.

First i will describe how the segmentation translation happens. The segments in real mode have a fixed size of 64K. The i386 offered the  flexiblity of segments with variable size with limits of up to 4G and protection information associated with it. Here I describe the various data structures that Intel offers and how segmentation translation happens.

Data Structures Required for Segmentation Translation

Since the initial boot up is in real mode and the processor has to transition to the protected mode. This it does by setting up the PE bit in the CR0 register.

 The code sequence to enter into protected mode is:

 mov %cr0, %eax

bts $0, %eax

mov %eax, %cr0

 Intel introduced the tables Global Descriptor Table (GDT) and Local Descriptor Table (LDT) which contains entries of 8-byte segment descriptors that define regions of memory (segment) and protection information associated with it.

The segment descriptor can of the types:

1. Code Segment Descriptor
2. Data Segment Descriptor
3. Task State Segment Descriptor
4. LTD Segment Descriptor

Usually there is one GDT defined for the system and each process can have it's own LDT. GDT in memory is pointed to by the GDTR register whose format is below.

Likewise the LDT is pointed to by the LDTR register.

How the logical address is translated into linear address by the segmentation unit?

The logical address in the protected mode is specified by segment register(which are CS,DS,SS,ES,FS) and an offset register ( which could be EIP, EAX, ECX, EDX,ESP). The segment selector has the following format:

The CPU segmentation unit performs the following for transaltion of the logical address to the linear address:

• The TI field of the segment selector is checked to see to identify the GDT or LDT  where the descriptor for this segment is stored. The base of  this descriptor tables can found in either GDTR or LDTR register.
• This base address in GDTR or LDTR depending on TI  is added to the segment selector index (multiplied by 8 because each entry is 8-bytes wide) to identify the descriptor entry.
• The base field of the segment descriptor is added to the offset of the logical addresss to get the linear address.

Below is the schematic diagram of how this translation happens:

What are the segments avaliable in linux?

The linux kernel makes limited use of segmentation and process either in user or kernel mode makes use of the segments:
user code segement (defined by the macro __USER_CS)
user data segment ( defined by the macro __USER_DS)
kernel code segment ( defined by the macro __KERNEL_CS)
kernel data segment  ( defined by the macro __KERNEL_DS)
All of this segements start at 0 and span the entire linear address range of  4GB.
Besides there are other descriptor entires in the GDT that identify the following segments:

• Task State Segment for each processor on the system. The task state segment among other things contains the
• Segment containing the default LDT
• Three Thread-Local Storage segments
• Three segments related to Advanced Power Management
• Five segments related to Plug and Play BIOS services
• A special TSS segment used by the kernel to handle Double fault exceptions.

There is GDT for each processor in the system. The kernel defines a default LDT which is shared by all processes.  The LDT has two important entries which are define the call gates for some executables.

Paging ( Translation of logical address into physical address)

Paging provides the ground for virtual memory. It allows dynamic remapping of memory at run-time. In earlier time-sharing systems, at load time of the program address relocations need to be done which is cubersome and this increased complexity at various levels. Paging provides each process with it's own view of the memory that is avaliable to it and process sees all 4 GB of memory on i386 and linker produces the executable code assuming this. At run-time, by means of the paging unit, the OS maps this 'virtual address' to avaliable physical pages.

The following code snippet enables paging(31st bit of CR0 register need to be turned on to enable paging) on an i386 processor:

mov %cr0, %eax

bts $31, %eax

mov %eax, %cr0

In the linux kernel, paging is enabled in the function startup_32(i386 arch) and the cr3 is loaded with physical address of the swapper_pg_dir( the address of the provisional page table set up initially by the kernel).

The linear address space is divided into equal-sized units called pages and this pages corresspond to equal sized units which the physical memory is divided into called page frames. On i386 machines, the default page size is 4K. To address to any location within 4K, we need 12 bits(log₂4096)  and the page frames always start at a multiple of 4K which mean to say that the page frame base address will have it's lower-most 12 bits set to 0.

Let's look at how the paging unit translates the linear address into physical address. This does it by means of a two-level page table (indirection table). The 32-bit linear address is divided into three sections of two 10-bits, 12-bit. The lower 12-bit specifes an offset within a page frame. The upper 10-bit is an index into the page directory array ( array of 1024 entries pointing to the page tables ) and the next 10-bit is index into page table(1024 entry table) which contain the base address of the page frame along with associated access/rights information.

The CR3 register contains the physical address of  the base of the page directory.

Each entry in Page Directory is 4 byte and there are 1024 entries and thus a Page Directory occupies a single page frame.

The PDE points to the base of the next-level page table and the page table has 1024 4-bytes entries. The below is the format of the Page Table Entry (PTE).

Below is the schematic of the how the translation happens with the data structures described above.

Advantage of having a two-level page table over a single page table is that it reduces memory usage ( since a process will never use all of it's 4 GB virtual address space). The Page table are allocated only for the virtual regions used by a process as and when necessary.We can also 4M page sizes, in which the address is divided into upper 10-bit to index into a page directory and 22-bit. PDE entry will have Page Size flag set and PSE bit is set in CR4 register.

When the page attributes of a page table entry is violated ( such as page not present, page not writable etc), it will result in a page fault exception and the CPU pushes the error code onto the OS stack and virtual address it faulted on to CR2 register. I will talk more about page fault handling in my later post. Since 80686 (pentium pro) , Intel provides an extension to address 64 GB of RAM (36 address pins). To use this PAE bit in CR4 register needs to set, the page size can be 2 MB and hence PS bit in PDE needs to be turned on. The paging level and entries in the tables which i plan to cover in subsequent posts.

The virtual to physical translations are costly as these involves table lookups and after the first translation, the virtual to physical address will be cached in a Translation Lookaside Buffer (TLB) so subsequent references doesn't involve page directory/page table walkthrough. The TLB cache needs to be invalidated on a process context switch and TLB caches are automatically invalidated on modification of the CR3 register.

Linux Kernel Virtual Memory Mapping

I will talk about the data structures the linux kernel uses with respect to the x86 processor. Each process has it's 4 GB virtual space which is divided into 1 GB kernel space ( which is accessed only when the process is in the context of supervisor mode(kernel)) and the 3 GB for user space. With PAE disabled, the first 768 entries ( which can 768x4M=3G) depends on the specific process and the rest of the entries is the same for all processes and equal to the master page global directory.There is a permanent mapping set up for 896 MB of memory which is identity mapping offset by 0xC0000000 from the virtual space by the kernel. Above 896 MB of memory, the kernel need to set up page table mapping as and when required and unmap when not needed. This can done is using kmap/kunmap. The remaining 128 MB of virtual address space is used for vmalloc, kmap mapping and fixed address mappings.

In linux, task's memory mapping is maintained in task_struct by mm variable which is of type mm_struct. The mm_struct contains the pointer to mapping tables (pgd) and different areas of virtual memory defined by vma which point to the head of the list whose elements is of type vm_area_struct. The vm_area_struct has fields start and end which defines a space of virtual region. It has in it the address space operations structure vm_ops which contain fields open, close, fault, page_mkwrite etc. Below is the schematic diagram of this data structures:

I will cover 64-bit(x86_64) memory management,how the provisional kernel page tables and linux kernel memory initial setup(with code walkthrough), mmap handlers, page fault handling and memory allocation APIs in the linux kernel in my subsequent posts.

Puzzles - I

1. You have 11 white socks and 13 black socks in a drawer. How many socks you need to pull out from the drawer so as to make sure that you have a matching pair?

Solution: 3. The first sock that you take out let it be white. In the second ,  let's say the worst you get black. In the 3rd pull, whatever be the color of the socks you take out(either white or black), it will form a matching pair.

2. There are 3 Red hats and 2 blue hats. Three people stand in a line and each person wears a single hat and doesn't know the color of the hat they are wearing. The first person in line can see the color of the hat of the other two persons but not his own. The second person can see the color of the hat of the person in front of him but not his own. The third person can't see the color of his own as well as neither of the other two. I ask a question to each of the person: what is the color of his hat? The first person says 'I don't know'. The second person replies the same. The third person says the color of his hat. What is the color of the hat of the third person?

Solution: Since the first person says 'I don't know' which means that the color of the hat of the other two person could not be (Blue,Blue) otherwise he would have said what hat was he wearing.Since the second person also say he doesn't know his color which means that color of the hat worn by the first person is red. If it had been blue, he would have said the color of his hat. Hence the hat of the first person is red which he was able to deduce from the answers of the pervious two persons.

3. Remove 3 line segments from the figure below to form 3 squares.

Solution: 

4. There is a king who is planning for big party tomorrow. For that he has 1000 bottles but unfortunately one of the bottles is poisoned but the king doesn't know. After drinking the wine from poisonous bottle, a person would die only in the 23rd hour. The king has prisoners in his cell and he decides to make use of them. What is the smallest number of prisoners he has to risk in order to have the party tomorrow?

Solution: 10 prisoners. Number the bottles from 1 to 1000. Prepare 10 sample bottles adding wine from ith bottles to the sample bottles that have positions whose bit set in the binary representation of i. 

5. There is a deck of 52 cards and 10 of these cards are facing up. You are blind folded and asked to divide the cards into two piles ( may be of unequal size) with the condition that both the piles should have an equal number of cards facing up. How would you do it?

Solution: Divide the cards into two piles of size 10 and 42. While putting cards into 10 pile size, flip the card and this ensures that number of face up cards in both the piles remain the same.

6. You have five jars of pills. Pills in one of the jars are contaminated. A regular pill weighs 10 grams but a contaminated pill weighs 9 grams. You have a scale and you make only one measurement with it. How will you identify the contaminated Jar?

Solution: Take one pill from jar 1, 2 pills from jar 2, 3 pills from jar 3, 4 pills from jar 4 and 5 pills from jar 5 and weigh it.Ideally the weight should be ∑i,i = 1 to 5 and subtract this value from the weight value you got by weighing and this will give the jar that is contaminated.

7.  A train starts from Chennai towards Bangalore at a speed of 15 km/h. At the same moment, train starts from bangalore for chennai and travels at speed of 20 km/h. At the same time, a bird also leaves chennai towards bangalore at speed of 25 km/h on the same track. The distance between Chennai and Bangalore is around 350 km. When it reaches the train from bangalore, it changes direction and travels at same towards chennai train and the it reverses direction and traverses back and forth until the trains collide. How far the birds would have travelled?

Solution: We need to calculate the time at which the two train meets and the distance the bird would have travelled is this time multiplied by it's speed. In the above case, it will turn out to be 250 km.

8. There are six wires of same color and same dimension running from ground floor of the building to the topmost floor of the building. But unfortunately, the wires are jumbled out in the path so they are not in same order as the order in down floor. You are an electrician and you have multimeter which can test conductivity. What is minimum number trips of you need to make up and down to identify which wire in bottom corresponds to the wire that comes on the top?

Solution: Let's name the wires at down end as A1, A2, A3,A4,A5,A6. let's A2 and A3 together and make one group. Tie A4,A5,A6 and make one group. Now there are three groups {A1}, {A2,A3}, {A4,A5,A6}. Let's go to the other end(assume labeling at top end as B1,B2,B3,B4,B5,B6) and check for conductivity on pairs/triples of wires and this would allow us to identify the groups of wires on top that would correspond to the groups that we have made at the bottom and already by direct correspondence of the sole wire that does not conduct, let's say B6(assume). Now on the top end connect wires in groups identified as {A1(B6), A2/A3(B1&B4), A4/A5/A6(B2&B3&B5)}, {A2/A3,A4/A5/A6} and {A4/A5/A6}. Now come to the down end and untie the connections that we made earlier. Again run conductivity tests and the sole wire (either A4,A5,A6) that doesn't conduct would identified to be in correspondence with the untied at the top(A4/A5/A6), let's say as example A6 corresponds to B5) .We can identify correspondence of A2 by testing conductivity on pairs ignoring A6 and A1, suppose A2  when paired with A5 will conduct in our case, in which case A2's corresponding pair is B1. Similarly we identify A3,A4 and A5.Thus we one trip up and 1 trip down would only to identify all the wires.

9.  How many zeros are there in 1000!?

Solution: An even multiplied by 5 will result in 0. This will turn out to calculate no. of  5's in all factors of numbers between 1 and1000. This is = 200+40(5's in multiples of 25 below 1000 = floor(1000/25))+8(floor(1000/125)+1(floor(1000/625)) = 249.

10. How many cubes are there on the surface of a 3x3x3 cubic array?

Solution: There is only cube right at the center of volume that is not on surface. So number of cubes on surface is 27-1 = 26 cubes. In general, for nxnxn, the number of cubes that are not exposed form cubic array of size of n-2. So number of cubes on surface is n^3 - (n-2)^3.

Cache Oblivious Algorithms(Cont.) - Static Search Trees

This is in my continuation to my earlier post describing an introduction to cache oblivious algorithms. The motivation behind this posts stem from the fact that there are startups tokutek.com and acunu whose products are based on cache oblivious data structures and the performance figures they show appear quite impressive.

Earlier we saw that binary search would take O(log₂N - log₂B) I/O steps. In fact divide and conquer algorithms are cache-oblivious, but binary search doesn't operate on all items of the sub-division and instead looks at one item on each sub-division. The key to making it cache oblivious is to change the ordering of the items so that items that we look all that fit in single-level of cache. Normal binary search is an implicit binary search tree in-order. If we change the ordering ( sorted array ) so that the child nodes of the implicit binary search tree get laid across to each other, we can achieve O(log_BN) I/O steps. In fact this is achieved by a layout called Van Emde Boas layout. ( Also note that I have called the title of this article as static search trees since we are concerned about only searching in the data structure and the data structure doesn't involve any dynamic modification(such as insert, deletion) to it. In my subsequent posts, i will cover dynamic data structures which are key data structures that underlie most of the software subsystems).

The idea behind Van Emde Boas Layout involves recursively subdivide a binary search tree so that the child and parent fit into levels of cache. Let's say we have N items which are in sorted order. Let it represent a complete binary tree of N items and the height of the tree is h=log₂N. We cut the tree at the middle level at (log₂N)/2. This top half will have approx. 2^log₂N/2 nodes which is N^1/2.(let log₂N=y. N=2^y by def. of log,N^1/2=^(2y)1/2=2^y/2=2^(log₂N)/2.)The top half will be recursively subdivided until we end up in a triangular portions(some power of 2 as base case that would fit in a block size B) that all would fit in different levels of cache. Similar is the case with the bottom √ N  subtrees each of size √ N
Now the trees are recursively laid out in memory in BFS manner with top tree followed by the leftmost bottom tree in that order.

They will be laid in memory as:

Let me present a concrete example. Suppose we have the array of numbers (1,2,3,4,5,6,7,8,9,10,11,12,13,15). As per layout policy, the tree when partitioned will look like:

And this will be laid out in memory as:

Let's see how this layout produces O(log_BN) I/O transfers. We stop the recursive layout of the tree when the size of the subtrees <= B. At this point height of the subtrees will be >= (log B/2). The number of subtrees that you need to visit from  root to leaf would be height of tree divided by height of each subtree which is log N/(logB/2). Each subtree can fit in atmost two blocks ( can span 2 blocks when not aligned properly). So this turns out to be 4log N/log B which is O(log_BN).

The question of mapping from array locations of parent to children is not easy in the above layout as in a normal binary search and the building of the above layout from the sorted array efficiently remains and is compute intensive for small sets of data and benefits of cache oblivious binary search could be seen only with large data sets. In my subsequent posts, i will show with some example code the answers to the above two questions.

Puzzles and Richard P Feynman.

Very nicelink as how would Richard P Feynman would do in a M$ 'puzzle' interview questions.

Easy Puzzles

I had opportunity to interview some freshers( people who are in final semester/just finished their engineering degree). Some of the puzzles that i asked:

Puzzles

1. (x-a)(x-b)(x-c)(x-d).....(x-z) = ?

Solution: 0 ( since x - x = 0 ).

2. Three bottles, one bottle contains red balls, the 2nd bottle contains blue balls and the third a combination of red and blue balls. Labels on this boxes are incorrect.Your task is to take balls and identify the correct ones

Solution: Take a ball from the bottle labeled Mixture. If the ball that you get is blue, then obviously that box contains blue balls. Now there are other two bottles that labelled blue and red. The box which is labelled red can't be blue and hence it must be mixture and the other one obviously had to be red.

3. How many cuts are required to break a chocolate bar of dimension x X y in 1x1 pieces?. You are not allowed to stack one piece on top of other or place side by side and cut it.

Solution: Each cut had produce 1 pieces. There would xy pieces of 1x1 and hence number of cuts should be xy - 1. Mathematically, if you cut along x you need to make x-1 cuts to produce x pieces of dimension of y x 1. Each of the pieces you need to make y -1 . Hence total number of cuts is (x-1) + x*(y-1) = x-1+xy-x = xy -1. 

4. You have a 3 litre jar and 5 litre jar. You do not have a measuring marks and you are allowed to pour water from 3 l to 5 l and vice-versa. How will you measure/make 4 litre using this jars?

Solution: Pour 3 litre water into 3 l jar. Transfer 3 l to 5 l jar. Now pour 3 liter into 3 l jar and transfer into 5 litre and now 1 litre remain in 3 l. Discard the water in 5 litre jar.Now pour 3 litre water into 3 l and transfer it to 5 litre jar. Now 4 litre will be there n in 5 l jar.

5. There are eight balls and all balls are of same weight except for one which is heavier. You have a pan balance. Find the minimum number of weighings required to find the heavier balls?

Solution: 2. Divide into groups of 3,3 and 2. Weigh 3 against 3 balls. If they balance, you can weigh 1 against 1 and find the heavier. In first case, if they do not balance, you take a group of 3 which is heavier and take any two from it and balance 1 against 1. If they balance, then the one which is remaining would be heavier. If they do not, then the heavier ball is one which tilted the balance down. In all cases, you need to do at themost two weighing to find the heavier ball. As a generalization, to find a heavier ball among n balls, the number of weighings required is ceil(log₃n).Note by dividing in groups of 3, each weighing is eliminating 2/3rds as compared to 1/2th when u divide into two which is better.

6. There are 25 horses and you are allowed to race horses in groups of 5 and there are no timing device available. How many races are required to find the fastest three?

Solution: 7 races. Run 5 races dividing into groups of 5 horses. In the 6th, run all the winners of 5 races.  The fastest among this will be fastest among all 25 horses. In the 7th race, take the second and third position horse from the fastest group, take the second position horse from the second fastest group (which is rank 2nd) and race it against 2nd and 3rd horse of race 6. The first two from this race will be occupy the second and third position among the 25 horses.

7. What is the angle between hour and minute hand of a clock when time is at 3:15?
Solution: 7.5 degrees ( simple math). The minute hand moves a quarter of 360 during which moves  a quarter of 30 degree which is 7.5 degree.

8. 4 people arrive in the dark and have only one flashlight. They are struck at a bridge and wanted to cross the bridge. But however only two of them can cross the bridge at a time and each takes different time to cross the bridge and the time taken are 1, 2, 5 and 10 minutes. What is the minimum time by which all can cross the bridge? 

Solution: On first pass, 1 & 2 minute people cross the bridge and the 2 minute guy stays back. The 1 minute comes back with flashlight. Then the 5 and 10 minute guys cross the bridge and hand over the flash light to the 2 minute and he goes back and comes with the 1 minute guy.

Hence total time is 2+1+10+2+2 = 17 mins.

9. There are two ropes of uniform density and equal length and each takes 30 minutes to burn. How will you measure 45 minutes?

Solution: Burn one rope and light two ends of the other rope. This will take 45 minutes.

10. There are 100 bulbs in a hall which are in OFF state. On first pass through the hall, you toggle the switches of  all the bulbs. On the second pass, you toggle the switch of every 2nd bulb. Likewise on pass i, you toggle all bulbs which are multiples of i. After pass 100, how many bulbs and what all bulbs will be in ON state?

Solution: If you toggle a bulb an even number of times, it will remain in the same state. An bulb i would toggled on passes which are factors of i. To get ON, bulb needs to be toggled an odd number and you to have find the numbers between 1 and 100 that have odd number of factors. All factors have an even pair other than squares. The squares between 1 and 100 are 1,2,4,9,16,25,36,49,64,81 and 100. So 10 bulbs would remain in ON state after the pass 100. As generalization for n bulbs(initially in OFF state)  that would remain ON after n passes, the number of bulbs  that will be in ON state is floor(sqrt(n)).
I will post some interesting C questions, data structure & algorithms and more puzzles in my subsequent posts.

Book- Algorithms for Interviews

This thread contains the complete e-copy of the book Algorithms for Interviews . This book contains nice collection of problems & puzzles. It seems that nowadays almost all books becomes available on the web :-)

Cache Oblivious Algorithms

Traditionally,  algorithm analysis is done by calculating amount of work done (instructions executed) by CPU as a function of the problem input size. Implicit in this analysis model is the assumption of  a computer system with an infinite amount of memory and the cost to access any location in this memory is

uniform. This model is known as the RAM model.Analysis done using this model applies when the problem input size fits into main memory and is fairly an accurate prediction of how your program will vary as the size of input changes.

Modern computer systems are a hierarchy of storage with decreasing speeds and increasing storage capacity as we move from  top of  hierarchy starting with registers, L1 cache, L2 cache,  main memory and disks.  The access time of a disk is about 100000 slower than main memory and is the main bottleneck. Data sizes whose size doesn't fit into main memory, the RAM model of analysis which measure the CPU time alone doesn't account for the runtime of the algorithm instead the number of disk i/o transfers come into play of the performance of the algorithm.
                                                                        

To do algorithm analysis taking into account the disk i/o transfers, Vitter and Aggarwal introduced the Disk Access Model (DAM). This model is based on the following facts:

• The computer consists of a single processor, with a main memory of size M bytes and an external memory(disk) of infinite size. 
• Data transfers from/to main memory and external memory happen in blocks of size B bytes.
• The input size is N bytes which is usually greater than M bytes.
• The run-time of an algorithm under this model is a factor of the following:
1. I/O Steps: The number of main memory and disk transfers that are required which is the
   dominant factor that needs to be minimized.
2. CPU time: The work done (the number of instructions) executed by the CPU.

There have been great amount of research being done to design data structures and algorithms that minimize the amount of disk transfers and there are two types of algorithms:

• Cache-aware algorithm: Cache-aware algorithms are algorithms which can be tuned to perform better based on system configuration parameters( like cache size, cache block size) than algorithm that doesn't take into system parameter considerations. A common data structure that is cache-aware is the B-Tree data structure commonly used in filesystems and databases. B tree node size needs to tuned according to cache block size to minimize the I/O transfer based on the architectural system parameters. Disadvantages with cache aware algorithms include the tuning or the change in implementation that required is as we move from one architecture to another architecture and the algorithm is not optimal or does adapt-well with multiple levels of cache.
  
• Cache Oblivious algorithm: Cache Oblivious (CO) algorithms are algorithms that are optimal regardless of the system configuration parameters, that is, they adapt themselves to different cache sizes and levels of cache in the system and doesn't require explicit tuning based on architectural system parameters. The performance analysis of this algorithm can be done using the Disk Access Model (DAM) described in the previous paragraph. The idea behind CO algorithm is to minimize number of disk transfers and do as much computation once a block of data is bought in memory ( this calls for a change in the data layout of the data which the algorithm operates). Divide and Conquer algorithms are more of Cache Oblivious type in they they sub-divide the data they manipulate into sizes until the fit it in a cache line and operate on it.

Let's look at cache oblivious algorithms for search and their analysis:

There exists file which contain N elements which are in random order on disk. The objective is to find if an element t exists in this file. Consider the following algorithm:

void externalSearch(t) {

        for(i=0; i

               bring block i into main memory 

               if block i contains t

                     return true

       }

       return false;

}    

Let's look at number of I/O steps required for the above algorithm. For the input size of N elements, there are N/B blocks on disks and hence the number of I/O transfers required is O(N/B).

Now let's assume that N elements are in sorted order.If we use binary search algorithm, the run-time of the algorithm in the RAM access model is log₂ N. Using the DAM model, the number of I/O transfers required is O(log₂ N - log₂ B) = log₂ (N/B). [Binary Search proceeds by subdividing the array and looking at mid and recursing on the necessary 1/2 and repeating/recursing the same step on the half. At each step, the size on which we operates gets reduced by a factor of 1/2. Finally we operate on size which is block B and there are log B elements that we need to look at in this. Hence it is log₂ N - log₂ B))

The question is whether this is optimal? Ideally we know B trees are the data structure that are used in databases/filesystems where search could be done in log_B N where B is the fan-out/branching factor and allows optimal insertion and deletion. The B-tree is not cache oblivious and requires tuning of B across different configurations. I will describe about a tree called Van Emde Boas Tree that allows binary in log_BN I/O steps and is cache oblivious in my next post.

Barrelfish

Researchers at ETH Zurich, MSR Cambridge UK and MSR Redmond have prototyped an entire operating system from scratch called Barrelfish which they say will address the scalability concerns and diversity inherent in modern computer hardware.The approach to this Operating system is based on this paper 'http://www.barrelfish.org/barrelfish_sosp09.pdf . I briefly describe the notion behind the mulitkernel and it's implementation Barrelfish in this post.

   Modern computer hardware exhibits node heterogenity, dynamicity and communication latency. If you look inside of a manycore computer, you will find an increasing number of cores and there are special-purpose programmable Network interface Controllers(NIC) that runs it's own firmware on an ARM core that sit behind an PCIe interconnect, NIVIDA GPU (which is custom specific core) and there are sockets where you can plug FPGA into it with custom processing logic. Thus there is heterogeneity present in modern hardware.There are dyanmic changes like hotplugging of devices, even processors and memory that happen. There are sophisticated power management schemes which causes cores to be powered down/up and buses to put into low-power which cause all devices behind it to be shut down.This is akin to that of a distiributed system where nodes can come up and go and dynamic membership changes are frequent. In addition, the interconnect networks between different cores, caches and memory have different latencies depending on where you are placed and to whom you want to speak to. This resembles a myraid array of point-to-point links exchanging messages which resemble that of a distributed system.

   Some of the newer architectures that exist or are in developement today are Tilera tilepro64 (64 cores connected in a mesh network) , Intel 80 core polaris (which does not have hardware cache coherence and also has a mesh network topology).If you look at any quad core or dual core processor it has a shared banked L2 cache in which all cores are connected via a crossbar interconnect switch. Hence to access any region of the L2 cache from all the cores are the same in terms of access latency. However this is not the case with modern manycore hardware because this design doesn't scale out in hardware for many cores. Contemporary Operating Systems are essentially  multithreaded shared memory kernel which execute on every core in the system and communicates and synchornizes with shared objects by means of explicit locks. Consider a shared data being updated/read by a varying number of cores. All copies of the same data from main memory are cached in the respective caches corressponding to each core. When one processor modifies the data, the respective cache lines of the caches of the other processors need to be invalidated. The cores when it again accesses the shared data, it needs to fetch it from the main memory. During the time, hardware cache coherency is in progress, the processor pipelines are stalled thereby preventing it from doing any useful work. Thus this implies that there is a implicit message passing(the invalidate and fetch cycles) involved between different functional units in the system when update of a shared data structure happens.

   In contrast, consider building a message passing solution in which update to data in shared memory could be done only by a single core which is designated as a server core. The other cores need   to     send messages to server core which in turn would be responsible for updating the data in the memory. Thus there is no need to maintain cache coherency at a h/w level since the data being manipulated is local to a single core. The paper gives an example of a experiment being conducted on 8x4 AMD opteron system in which the overhead of sending and recieving messages wins over 'shared' way of update the data when number of cores exceeds 4 and the data being modified touches more than 2 cache lines.Thus the idea of runing an instance of the same kernel on every core with global state to be shared to be replicated as local state across all cores and maintain consistency of replicas via message passing mechanism (using consistency algorithms from distributed system).This approach is called multikernel. Barrelfish is a prototype operating system built from scratch based on this idea.

  The other nice concept in barrelfish is the system knowledge base which represents the machine capabilities (it' interconnect topology, latencies of memory, caches) and performance data of run-time state of the system.We can make optimization queries on the knowledge base which can used by different run-time systems like the scheduler.The queries can be formulated using the constraing programming language ECLipSE.To give you an idea, let me present a concrete examples where the knowledge in the System knowledge Base can be used to deliver an optimal performance. Consider a hardware architecture in which two cores on a single die share the same L2 cache.If there are mutliple threads which need to be scheduled to many cores on this system, the scheduler can do an intelligent way of scheduling based on the memory access patterns shown by the threads when run in their previous time slices.If the threads show interleaving memory access pattern rather than conflicting one such as parallel matrix multiplication application, then it is better to schedule the two threads onto two cores on the  same die that share an L2 cache because one thread would be benefitting from the data in the cache line that is already populated by the other thread that has done the manipulation.

constant time LCA and related problems

 Here is a nice video explaining how to answer queries to find  the least common ancestor of a tree in O(1) after preprocessing in O(n) time. The algorithm is pretty cool and a clever one!. Also the  topcoder tutorial explaining LCA and RMQ(range minimum query) is pretty good one.
I tried solving the problem frequent values in python based on the above algorithm and i got TLE but surprisingly the same piece of code in C++ got accepted (might have got to do with the way consuming list initialization is being done in the code). Anyway here is the python code for that  problem:

python quirks

I am surprised by the following behavior in a piece of code that i wrote to a simulate 2D array in python to solve a programming problem.