Thursday, April 28, 2011

Parallelism

Threads and processes:
A computer will often appear to be doing many things simultaneously, such as checking for new e‐mail messages, saving a Word document, and loading a website. Each program is a separate “process”. Each process has one or more “threads”. If a process has several threads, they appear to run simultaneously. For example, an email client may have one thread that checks for new e‐mail messages and one thread for the GUI so that it can show a button being pressed. In fact, only one thread is being run at any given time. The processor switches between threads so quickly that they appear to be running simultaneously. Multiple threads in a single process have access to the same memory. By contrast, multiple processes have separate regions of memory and can only communicate by special mechanisms. The processor loads and saves a separate set of registers for each thread. Remember, each process has one or more threads, and the processor switches between threads.

Titanic Ship Crew Job

Got this code on codechef:
The captain of the ship TITANIC is a little .... off the track. He needs to select the crew for the ship. But everyone seems to be eligible. So to test their intelligence, he plays a game.
The contestants have to stand in a line. They are given the numbers in the order in which they stand, starting from 1. The captain then removes all the contestants that are standing at an odd position.
Initially, standing people have numbers - 1,2,3,4,5...
After first pass, people left are - 2,4,...
After second pass - 4,....
And so on.
You want to board the ship as a crew member. Given the total number of applicants for a position, find the best place to stand in the line so that you are selected.