Josephus Problem Explored

Josephus Problem restated simply, is this: there are n people standing in a circle, of which you are one. Someone outside the circle goes around clockwise and repeatedly eliminates every other person in the circle, until one person — the winner — remains. Where should you stand so you become the winner?
Here’s an example with 13 participants:


Alternating Elimination with 13 people, order of elimination shown in red (winner is person 11)
Actually, there’s no need to work through the elimination process — a simple formula will give the answer. This formula, you won’t be surprised to hear, has connections to the powers of two and binary numbers. I will discuss my favourite solution, one based on the powers of two.
When the Number of Participants is a Power of Two

Alternating elimination means one of every two participants is eliminated. This is halving, and suggests powers of two are involved. Let’s first explore this with the special case where the number of participants is a power of two, since powers of two halve neatly into powers of two.
Here is an example circle with eight people:


Alternating Elimination (8 people)

The elimination process works like this: the first pass starts at person 1 and proceeds clockwise, and each new pass starts every time person 1 is reached. The people eliminated on a pass are crossed out, and are marked to indicate the order in which they were eliminated. Eliminated people are then omitted in subsequent diagrams.
Three passes are required to determine the winner:
·        Pass 1 eliminates four people: 2, 4, 6, 8.
·        Pass 2 eliminates two people: 3, 7.
·        Pass 3 eliminates one person: 5.
This leaves person 1 the winner.
The number of people eliminated (and equivalently, remaining) per pass follows the same pattern as in a single-elimination tournament with a power of two number of participants.
Analysis

Regardless of the number of participants n, person 1 survives the first pass. Since n is even, as every positive power of two is, person 1 survives the second pass as well. In the first pass, the process goes like this: person 1 is skipped, person 2 is eliminated, person 3 is skipped, person 4 is eliminated, … , person n-1 is skipped, person n is eliminated. The second pass starts by skipping person 1.
As long as the number of participants per pass is even, as it will be for a power of two starting point, the same pattern is followed: person 1 is skipped each time.Therefore, for any power of two, person 1 always wins.
Proof by Induction

You can also show that person 1 is the winner using an inductive proof (for details see Miguel Lerma’s proof of the Josephus problem). Compared to the argument above, induction works in the opposite direction; that is, it builds up to a more complicated problem from a simpler one.
For n = 21 = 2 participants, the base case, it’s easy to see that person 1 is the winner. For the induction hypothesis, assume person 1 is the winner for n = 2m. Show person 1 is the winner for n = 2m+1.
When n = 2m+1, 2m people — all the even numbered people — are eliminated in the first pass, leaving 2m people — all the odd numbered people — remaining. By the induction hypothesis, person 1 is the winner of the n = 2m remaining people, and thus the winner among all n = 2m+1 people. Therefore, for any power of two, person 1 always wins.
When the Number of Participants is NOT a Power of Two

When the number of participants is not a power of two, we know this much: person 1 can’t be the winner. This is because at least one pass will have an odd number of participants. Once the first odd participant pass is complete, person 1 will be eliminated at the start of the next pass.
So is there an easy way to determine who is the winner? Let’s step back and take a closer look at the elimination process in the 13-person example:


Alternating Elimination (13 people)

Four passes are required to determine the winner:
·        Pass 1 eliminates six people: 2, 4, 6, 8, 10, 12.
·        Pass 2 eliminates four people: 1, 5, 9, 13.
·        Pass 3 eliminates one person: 7.
·        Pass 4 eliminates one person: 3.
This leaves person 11 the winner.
Analysis

Powers of two come into play here, but you have to change your perspective to see them. They don’t occur on pass boundaries — they span them. At some point, during pass 1, the number of participants remaining becomes a power of two. In this example, that occurs when 5 of the 13 people are eliminated, leaving an 8 person problem: 11, 12, 13, 1, 3, 5, 7, 9. This means person 11, the first person in the new power of two circle, wins.
Here’s the 13-person example again, with the 8-person power of two sub case shown explicitly with passes realigned:


8-Person Power of Two Subset of 13-Person Problem

(It occurred to me that the alternating elimination process is an indirect way to check whether a number is a positive power of two. A number is a positive power of two if and only if, when halved repeatedly, becomes 1.)
The Equations

We can solve both cases — in other words, for an arbitrary number of participants — using a little math.
Write n as n = 2m + k, where 2m is the largest power of two less than or equal to n. k people need to be eliminated to reduce the problem to a power of two, which means 2k people must be passed over. The next person in the circle, person 2k + 1, will be the winner. In other words, the winner w is w = 2k + 1.

Let’s apply these equations to a few examples:
·        n = 8: The equations still apply, although using them is unnecessary: n = 8 + 0, so k = 0 and w = 0 + 1 = 1.
·        n = 13: n = 8 + 5, so k = 5 and w = 2*5 + 1 = 11.
·        n = 1000=512 + 488, so k = 488 and w = 2*488 + 1 = 977.
The Formula

We can combine the equations n = 2m + k and w = 2k + 1 to get a single formula for w:
·        Rearrange n = 2m + k to isolate k: k = n – 2m.
·        Substitute this expression for k into w = 2k + 1:
w = 2(n – 2m) + 1
The Formula as a Function of One Variable

As written, the formula is a function of two variables, n and m. This works fine, but ideally it should be a function of only one variable — n. This means we have to eliminate m, or more precisely, make m itself a function of n.
We described 2m loosely as “the largest power of two less than or equal to n,” but that is an algorithmic description. Described mathematically, m is the integer part of the base 2 logarithm of n; that is, m = floor(log2(n)), or log2(n)
So now we have a formula in terms of the number of participants n:

                                                        w = 2(n – 2m) + 1 where m= log2(n);
Summary

An alternating elimination Josephus problem has a deep connection to the powers of two, a connection reflected in the formula we derived to find the winning spot. The formula requires a few simple calculations, and is a function of the number of participants n: find the largest power of two in n, subtract it from n, double the result, and add 1. The person in that spot will be the winner.


VLC-A Life Saver!

How to rotate and save a video using VLC media player

Maybe you have captured a video with your cellphone or camcorder and when you try to play it in your computer, you discover that it is rotated 90 degrees. This error happens because many cellphones don’t understand the orientation. 
When you have a rotated video, you can use two free programs to rotate and save you video in the orientation you want: VLC Media Player and Windows Live Movie Maker. This tutorial guides you on how to use VLC Media Player to rotate and save your videos.
* Click here to see a detailed video on how to rotate and save a video using VLC media player (Ver 2.0.2).

Note – Update: The method bellow is working great with VLC Media Player Ver 2.0.2. If you want to use the latest VLC Media Player (Ver. 2.1.2) to rotate your videos then navigate to this link : How to Rotate Video using VLC Media Player ver 2.1.2
1. First download and install VLC Media Player from here : http://www.videolan.org/

For Windows 32Bithttp://download.videolan.org/pub/videolan/vlc/2.0.2/win32/vlc-2.0.2-win32.exe
2. Then choose your rotated video from your computer and “right click” to open it with VLC Media Player
3. In the VLC Media Player main menu go “Tools” > “Effects and Filters
image
4. In “Adjustments and Effects” window, choose the “Video Effects” tab
image
5. In “Video Effects” tab, choose “Geometry
image
6. In “Geometry” click the “Transform” box to enable transform and make sure that the “Rotate by 90 degrees” setting below is selected.  Then choose “Close” to close the window.Notice*: The “Rotate by 90 degrees” setting, rotates your video by 90 degrees clockwise. If you want to rotate your video in a different angle then choose the corresponding angle.

image
Now you can view and play your rotated video with VLC Media player (only) in the right angle.

7.If you like to save your recent rotated video, from the main menu go to “Tools” > “Preferences
image
 8. In Interface Settings look at the left side’s bottom and choose to “Show All Settings
image
 9. At the left pane under “Stream Output” expand “Sout stream” >”Transcode” and at right pane under “Video filter” choose the “Video transformation filter“. Then click “Save” to save your settings.
image
 10. From the main menu choose “Media” > “Convert / Save
image
 11. At “Convert/Save” options at “File” tab, choose “Add…” to add your recently rotated video file and then press the drop-down arrow on the right of “Convert / Save” button to choose “Convert
image
 12. At “convert” options, choose “Browse“, select the destination folder (e.g. “Desktop”), give a file name for the converted file (e.g. “IMG_1822Rotated”) and specify the output video file type (e.g. “.MOV”)
image
 13. While in “convert” options, choose your profile output: “Video – H.264 + MP3 (MP4)” and then press the “Tools” button on the right side to edit the selected profile.
image
 14. In profile settings, find and click the “Audio codec” tab
image
 15. Inside “Audio codec” settings use the drop-down arrow in codec’s line and from the list of codecs choose “MP3“. Then click Save.
image
 16. In “Convert” window press “Start” to start the conversion.
image
 17.As “Conversion/Streaming” process is executed, you see the following screen.
image
18. When  the “Conversion/Streaming” process is completed, you can play your video in any media player you like.
Attention: After you rotate and save your videos, you must reset VLC player to it’s default settings , by going to: “Tools” > “Preferences” and press the “Reset Preferences” button at the bottom side of Preferences window.

Tricky C Questions with explained answers

Tricky c programs question and answers with explanation. Enjoy yourself!



(1) What will be output if you will compile and execute the following c code?

struct marks{
  int p:3;
  int c:3;
  int m:2;
};
void main(){
  struct marks s={2,-6,5};
  printf("%d %d %d",s.p,s.c,s.m); 
}

(a) 2 -6 5
(b) 2 -6 1
(c) 2 2 1
(d) Compiler error
(e) None of these

Answer: (c)
Explanation:
Binary value of 2: 00000010 (Select three two bit)
Binary value of 6: 00000110
Binary value of -6: 11111001+1=11111010
(Select last three bit)
Binary value of 5: 00000101 (Select last two bit)

Complete memory representation:


(2) What will be output if you will compile and execute the following c code?

void main(){
   int huge*p=(int huge*)0XC0563331;
   int huge*q=(int huge*)0xC2551341;
   *p=200;
   printf("%d",*q);
}

(a)0
(b)Garbage value
(c)null
(d) 200
(e)Compiler error

Answer: (d)
Explanation:
Physical address of huge pointer p
Huge address: 0XC0563331
Offset address: 0x3331
Segment address: 0XC056
Physical address= Segment address * 0X10 + Offset address
=0XC056 * 0X10 +0X3331
=0XC0560 + 0X3331
=0XC3891
Physical address of huge pointer q
Huge address: 0XC2551341
Offset address: 0x1341
Segment address: 0XC255
Physical address= Segment address * 0X10 + Offset address
=0XC255 * 0X10 +0X1341
=0XC2550 + 0X1341
=0XC3891
Since both huge pointers p and q are pointing same physical address so content of q
 will also same as content of q.

(3) Write c program which display mouse pointer and position of pointer.(In x coordinate, y coordinate)?

Answer:
#include”dos.h”
#include”stdio.h”
void main()
{
union REGS i,o;
int x,y,k;
//show mouse pointer
i.x.ax=1;
int86(0x33,&i,&o);
while(!kbhit()) //its value will false when we hit key in the key board
{
i.x.ax=3; //get mouse position
x=o.x.cx;
y=o.x.dx;
clrscr();
printf("(%d , %d)",x,y);
delay(250);
int86(0x33,&i,&o);
}
getch();
}

(4) Write a c program to create dos command: dir.

Answer:

Step 1: Write following code.

#include “stdio.h”
#include “dos.h”
void main(int count,char *argv[]){
   struct find_t q ;
   int a;
   if(count==1)
      argv[1]="*.*";
      a = _dos_findfirst(argv[1],1,&q);
      if(a==0){
         while (!a){
            printf(" %s\n", q.name);
            a = _dos_findnext(&q);
         }
      }
      else{
         printf("File not found");
      }
}

Step 2: Save the as list.c (You can give any name)
Step 3: Compile and execute the file.
Step 4: Write click on My computer of Window XP operating system and select properties.
Step 5: Select Advanced -> Environment Variables
Step 6: You will find following window:
Click on new button (Button inside the red box)




Step 7: Write following:
Variable name: path
Variable value: c:\tc\bin\list.c (Path where you have saved)


Step 8: Open command prompt and write list and press enter.
Command line argument tutorial.

(6) What will be output if you will compile and execute the following c code?

void main(){
   int i=10;
   static int x=i;
   if(x==i)
      printf("Equal");
   else if(x>i)
      printf("Greater than");
   else
      printf("Less than");
}

(a) Equal
(b) Greater than
(c) Less than
(d) Compiler error
(e) None of above

Answer: (d)
Explanation:
static variables are load time entity while auto variables are run time entity. We can not initialize any load time variable by the run time variable.
In this example i is run time variable while x is load time variable.


(7) What will be output if you will compile and execute the following c code?

void main(){
   int i;
   float a=5.2;
   char *ptr;
   ptr=(char *)&a;
   for(i=0;i<=3;i++)
      printf("%d ",*ptr++);
}

(a)0 0 0 0
(b)Garbage Garbage Garbage Garbage
(c)102 56 -80 32
(d)102 102 -90 64
(e)Compiler error

Answer: (d)
Explanation:
In c float data type is four byte data type while char pointer ptr can point one byte of memory at a time.
Memory representation of float a=5.2




ptr pointer will point first fourth byte then third byte then second byte then first byte.
Content of fourth byte:
Binary value=01100110
Decimal value= 64+32+4+2=102
Content of third byte:
Binary value=01100110
Decimal value=64+32+4+2=102
Content of second byte:
Binary value=10100110
Decimal value=-128+32+4+2=-90
Content of first byte:
Binary value=01000000
Decimal value=64
Note: Character pointer treats MSB bit of each byte i.e. left most bit of above figure as sign bit.

(8) What will be output if you will compile and execute the following c code?

void main(){
   int i;
   double a=5.2;
   char *ptr;
   ptr=(char *)&a;
   for(i=0;i<=7;i++)
      printf("%d ",*ptr++);
}

(a) -51 -52 -52 -52 -52 -52 20 64
(b) 51 52 52 52 52 52 20 64 
(c) Eight garbage values.
(d) Compiler error
(e) None of these

Answer: (a)
Explanation:
In c double data type is eight byte data type while char pointer ptr can point one byte of memory at a time.
Memory representation of double a=5.2




ptr pointer will point first eighth byte then seventh byte then sixth byte then fifth byte then fourth byte then third byte then second byte then first byte as shown in above figure.
Content of eighth byte:
Binary value=11001101
Decimal value= -128+64+8+4+1=-51
Content of seventh byte:
Binary value=11001100
Decimal value= -128+64+8+4=-52
Content of sixth byte:
Binary value=11001100
Decimal value= -128+64+8+4=-52
Content of fifth byte:
Binary value=11001100
Decimal value= -128+64+8+4=-52
Content of fourth byte:
Binary value=11001100
Decimal value= -128+64+8+4=-52
Content of third byte:
Binary value=11001100
Decimal value= -128+64+8+4=-52
Content of second byte:
Binary value=000010100
Decimal value=16+4=20
Content of first byte:
Binary value=01000000
Decimal value=64
Note: Character pointer treats MSB bit of each byte i.e. left most bit of above figure as sign bit.

(9) What will be output if you will compile and execute the following c code?

void main(){
   printf("%s","c" "question" "bank"); 
}

(a) c question bank
(b) c
(c) bank
(d) cquestionbank
(e) Compiler error

Answer: (d)
Explanation:
In c string constant “xy” is same as “x” “y”


(10) What will be output if you will compile and execute the following c code?

void main(){
   printf("%s",__DATE__); 
}

(a) Current system date
(b) Current system date with time
(c) null
(d) Compiler error
(e) None of these

Answer: (a)
Explanation:
__DATE__ is global identifier which returns current system date.

(11) What will be output if you will compile and execute the following c code?

void main(){
   char *str="c-pointer";
   printf("%*.*s",10,7,str);
}

(a) c-pointer
(b) c-pointer
(c) c-point
(d) cpointer null null
(e) c-point

Answer: (e)
Explanation:
Meaning of %*.*s in the printf function:
First * indicates the width i.e. how many spaces will take to print the string and second * indicates how many characters will print of any string.
Following figure illustrates output of above code:




(12) What will be output if you will compile and execute the following c code?

void start();
void end();
#pragma startup start
#pragma exit end
int static i;
void main(){
   printf("\nmain function: %d",++i);
}
void start(){
   clrscr();
   printf("\nstart function: %d",++i);
}
void end(){
   printf("\nend function: %d",++i);
   getch();
}

(a)
main function: 2
start function: 1
end function:3
(b)
start function: 1
main function: 2
end function:3
(c)
main function: 2
end function:3
start function: 1
(d) Compiler error
(e) None of these

Answer: (b)
Explanation:
Every c program start with main function and terminate with null statement. But #pragma startup can call function just before main function and #pragma exit
(13) What will be output if you will compile and execute the following c code?

void main(){
   int a=-12;
   a=a>>3;
   printf("%d",a); 
}

(a) -4
(b) -3
(c) -2
(d) -96
(e) Compiler error

Answer :( c)
Explanation:
Binary value of 12 is: 00000000 00001100
Binary value of -12 wills 2’s complement of 12 i.e.




So binary value of -12 is: 11111111 11110100




Right shifting rule:
Rule 1: If number is positive the fill vacant spaces in the left side by 0.
Rule 2: If number is negative the fill vacant spaces in the left side by 1.
In this case number is negative. So right shift all the binary digits by three space and fill vacant space by 1 as shown following figure:




Since it is negative number so output will also a negative number but its 2’s complement.




Hence final out put will be:




And its decimal value is: 2
Hence output will be:-2

(14) What will be output if you will compile and execute the following c code?

#include "string.h"
void main(){
   clrscr();
 printf("%d%d",sizeof("string"),strlen("string"));
getch();
}
(a) 6 6
(b) 7 7
(c) 6 7
(d) 7 6
(e) None of these

Answer: (d)
Explanation:
Sizeof operator returns the size of string including null character while strlen function returns length of a string excluding null character.

(15) What will be output if you will compile and execute the following c code?

void main(){
   static main;
   int x;
   x=call(main);
   clrscr();
   printf("%d ",x);
   getch();
}
int call(int address){
   address++;
   return address;
}
(a) 0
(b) 1
(c) Garbage value
(d) Compiler error
(e) None of these

Answer: (b)
Explanation:
As we know main is not keyword of c but is special type of function. Word main can be name variable in the main and other functions.
(16) What will be output if you will compile and execute the following c code?

void main(){
   int a,b;
   a=1,3,15;
   b=(2,4,6);
   clrscr();
   printf("%d ",a+b);
   getch();
}
(a) 3
(b) 21
(c) 17
(d) 7
(e) Compiler error

Answer: (d)
Explanation:
In c comma behaves as separator as well as operator.
a=1, 3, 15;
b= (2, 4, 6);
In the above two statements comma is working as operator. Comma enjoys least precedence and associative is left to right.
Assigning the priority of each operator in the first statement:




Hence 1 will assign to a.
Assigning the priority of each operator in the second statement:



(17) What will be output if you will compile and execute the following c code?

int extern x;
void main()
   printf("%d",x);
   x=2;
   getch();
}
int x=23;

(a) 0
(b) 2
(c) 23
(d) Compiler error
(e) None of these

Answer: (c)
Explanation:
extern variables can search the declaration of variable any where in the program.

(18) What will be output if you will compile and execute the following c code?

void main(){
   int i=0;
   if(i==0){
      i=((5,(i=3)),i=1);
      printf("%d",i);
   }
   else
      printf("equal");
}

(a) 5
(b) 3
(c) 1
(d) equal
(e) None of above

Answer: (c)
Explanation:

(19) What will be output if you will compile and execute the following c code?

void main(){
   int a=25;
   clrscr();
   printf("%o %x",a,a);
   getch();
}

(a) 25 25
(b) 025 0x25
(c) 12 42
(d) 31 19
(e) None of these

Answer: (d)
Explanation:
%o is used to print the number in octal number format.
%x is used to print the number in hexadecimal number format.
Note: In c octal number starts with 0 and hexadecimal number starts with 0x.

(20) What will be output if you will compile and execute the following c code?

#define message "union is\
power of c"
void main(){
   clrscr();
   printf("%s",message);
   getch();
}

(a) union is power of c
(b) union ispower of c
(c) union is
Power of c
(d) Compiler error
(e) None of these

Answer: (b)
Explanation:
If you want to write macro constant in new line the end with the character \.

(21) What will be output if you will compile and execute the following c code?

#define call(x) #x
void main(){
   printf("%s",call(c/c++));
}

(a)c
(b)c++
(c)#c/c++
(d)c/c++
(e)Compiler error

Answer: (d)
Explanation:
# is string operator. It converts the macro function call argument in the string. First see the intermediate file:
test.c 1:
test.c 2: void main(){
test.c 3: printf("%s","c/c++");
test.c 4: }
test.c 5:
It is clear macro call is replaced by its argument in the string format.

(22) What will be output if you will compile and execute the following c code?

void main(){
   if(printf("cquestionbank"))
      printf("I know c");
   else
      printf("I know c++");
}

(a) I know c
(b) I know c++
(c) cquestionbankI know c
(d) cquestionbankI know c++
(e) Compiler error

Answer: (c)
Explanation:
Return type of printf function is integer which returns number of character it prints including blank spaces. So printf function inside if condition will return 13. In if condition any non- zero number means true so else part will not execute.


If you have any doubt in above Tricky questions with explanation you can ask through comment section.