2005 ICWS
2005 ICWS camera ready web site
http://www.computer.org/proceedings/final/icws2005.htm#step8
- posted by Pop @ 10:51 AM

 
Deeper inside of Page Rank
The ongoing search for efficient web search algorithms
From SIAM News, Volume 37, Number 9, November 2004
By Sara Robinson
http://www.siam.org/siamnews/11-04/websearch.pdf

The Use of The Linear Algebra by Web Search Engine
By Any N. Langville and Carl D. Meyer
http://meyer.math.ncsu.edu/Meyer/PS_Files/PS_Files_Index.html
- posted by Pop @ 4:55 PM

 
ACM Regional Collegiate Programming Contest and Solution
The Link
http://www.acmgnyr.org/
- posted by Pop @ 4:52 PM

 
CAMEL BANANA TRANSPORT
You have 3,000 bananas and a camel which can carry at most 1,000 bananas at a time. The camel eats a banana before moving a unit. You want to transport the bananas 1,000 units. What is the maximum number of uneaten bananas that you can move 1,000 units?
Problem source: 11th Grade Honors Precalculus, Dr. James J. Hogan High School

See:
http://puzzle.dse.nl/math/bananas_us.html
- posted by Pop @ 8:33 AM

 
5 cards trick
This is a magic trick performed by two magicians, Alice and Bob, with one shuffled deck of N unique cards. (Nothing is mentioned about suits: you may consider these cards to be simply enumerated from 1 to N.) Alice asks a member of the audience, Carol, to randomly select 5 cards out of a deck. Carol then returns her chosen 5 cards to Alice. After looking at the 5 cards, Alice picks one of the 5 cards and gives it back to Carol. Alice then arranges the other four cards in some way, and gives them to Bob in a neat, face-down pile. Bob examines these 4 cards and determines what card is in Carol's hand (the missing 5th card). Carol is astonished!
What is the largest number of cards N that the deck can contain before the trick is no longer performable? Prove it.
How specifically do you execute the trick on a deck of maximal size N?

Equation: N = P(M,M) + (M-1)
Explanation: Permutation of M is P(M,M), that is the information M cards can code, plus M-1 (because M-1 will be shown)

For M=5;
P(5,5) + (M-1) = 120 + 4 = 124.

For M=3;
P(3,3) + (M-1) = 6 + 2 = 8.

we have P(2,8) = C(3,8), and C(3,8) = C(5,8) if we can find a map from P(2,8) to C(5,8) and the 5 out 8 cards do not contain the 2 out 8 cards, we are done.
- posted by Pop @ 8:16 AM

 
An evil king and 1000 bottles of wine
An evil king has 1000 bottles of wine. A neighboring queen plots to kill the bad king, and sends a servant to poison the wine. The king's guards catch the servant after he has only poisoned one bottle. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. Rather than using 1000 prisoners each assigned to a particular bottle, this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned, and will still be able to drink the rest of the wine in 5 weeks time. How does he pull this off?

1. using timing trick, like radix sorting,
credit to Bigswede
Use 10 prisoners. Label each prisoner with a digit, 0, 1,......,9 Label the bottles of wine 000, 001, ......., 999

On the first day, have each prisoner drink from all the bottles that have his digit in the 100's place. For example, prisoner labeled 3 would taste wine in bottles 300 to 399.
On the second day, same thing, except drink from each bottle with digit in ten's place. e.g. prisoner labeled 3 would drink from bottles 030, 031,..039, 130, ...139, ....930,..939.
On the third day, same thing, except drink from each bottle with digit in 1's place. e.g. prisoner labeled 3 would drink from bottle 003, 013, 023, ...093, 103, ......993.
Wait 31 days (a month) and see which prisoner dies. That gives the first digit (100's place) of the poisoned bottle.
The next day (32), if someone else dies, that gives the 2nd digit, and the third day (33), if someone dies, that gives the 3rd digit.
If nobody dies on day 32, the 2nd digit is the same as the first.
If nobody dies on both days 32 and 33, all three digits are the same (as the first digit).
If a prisoner dies on day 31 and another dies on day 32, but nobody dies on day 33, the bottle could be either of two bottles, with the 3rd digit the same as either the 1st digit or the 2nd digit. Throw both those bottles out.
To resolve this last case, we use a different group of 10 prisoners to taste the 1's digit bottles (at the start), so then someone would die on the 33rd day and the bottle would be uniquely identified. This method uses 10 prisoners, with at most 3 dieing, but 20% of the time, two bottles have to be thrown out, or it uses 20 prisoners, with at most 3 dieing, with only the single poisoned bottle having to be thrown out.

2. No timing trick, binary coding the bottle, 2^10=1024>1000
credit to Vineet Kumar

As for just the plain method, without much explanation: Line up the prisoners in order, each representing a bit. Number each bottle 1 to 1000. For each bottle, convert the serial number to binary, and give a sip to each prisoner corresponding to a 1 bit in the bottle number. After a month, see who dies. Each dead prisoner represents a "1" bit in the poisonous bottle's serial number. For example, if prisoners number 2, 5, 7 and 8 die, that looks like this: prisoner # 0 1 2 3 4 5 6 7 8 9 bit # 0 0 1 0 0 1 0 1 1 0 Assuming we're numbering with 0-9 instead of 1-10 and that 0 is the least significant bit, the number of the poisonous wine bottle is the sum of 2^(prisoner number) for each dead prisoner. In the above example, 0110100100 converted to decimal is 420, so bottle number 420 is the poison.

3. General analysis, credit to AlexH
Lets say we have k "windows" which represent the uncertainty of how long it takes for the poison to show. For example if we know the poison shows sometime between exactly 30 days and exactly 31 days after the poison is drunk, then if we start poisoning at 12am on day 1 we could have 5 windows,then one each for days 31,32,33,34,35 (assuming the wine is needed during day 36) so k=5 in this case. Now we need to label each bottle in base k+1 and have prisoner i drink from the bottle on day j if the ith digit is j and iff the ith digit is 0 he doesn't drink from the bottle at all. If we want to determine how few prisoners we need the answer is (log n)/(log k+1). If we fix a number m of prisoners and want to limit deaths then we need to get n sequences of m digits of base k+1 with the smallest possible bound on the number of non-zero elements. For example, if n=1000 bottles and k=5 windows then we can either use 4 prisoners with a substantial chance that all will die (6^4=1296>1000), or we can use 10 prisoners and have at most 2 die (there are 1176 10-digit base 6 strings with at least 8 0s).

The binary labelling scheme works just fine with 10 prisoners and no timing tricks. This is in fact exactly what my generalized system suggests if you plug in k=1 (i.e we can't do any timing tricks). log 1000/log (1+1) < 10. The optimum binary labelling uses all of the lables containing 0-7 deaths plus most of the labels containing 8 deaths, all together summing to 1000 labels.

Here are some numbers for 1000 bottles, with minimal deaths on 10 prisoners or with minimal prisoners. 1 window: (i.e. no timing possible) 10 prisoners --> at most 8 deaths, avg 4.916
2 windows:
7 prisoners, <=5 deaths, avg 3.567
10 prisoners, <=3 deaths, avg2.777
3 windows:
5 prisoners, <=5 deaths, avg 3.72
10 prisoners, <=3 deaths, avg 2.532
4 windows:
5 prisoners, <=4 deaths, avg 2.976
10 prisoners, <=3 deaths, avg 2.197
5 windows:
4 prisoners, <=4 deaths, avg 3.136
10 prisoners, <=2 deaths, avg 1.948
- posted by Pop @ 8:33 AM

 
Merge two binary search tree into a balanced BST
Quoted from John_Gaughan in Wu::forum
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1102583054

1. Doing a preorder traversal will, of course, get all elements in ascending order: O(n+m).
2. Merging into another array is trivial: O(n+m).
3. Creating another balanced tree using middle-element method is O(n+m).

So the whole thing is O(n+m).

we don't have to create three intermediate arrays.
Merge the trees into the array on the fly while traversing using the same method as merging two sorted arrays, treating the output of the preorder traversals as serialized arrays.

If we know the size of the original trees, we can forgo the intermediate array entirely by calculating the structure of the target tree and inserting nodes directly where they will wind up. This only works, however, if we have a priori knowledge of the tree's size.
- posted by Pop @ 3:35 PM

 
If a point P is in the interior of triangle(A,B,C)?
1.Assuming Vector V1(P1,P0), V2(P2,P0)
P1(x1,y1) P2(x2,y2) P0(0,0)

V1 X V2 =  ( x1 x2 ) = x1*y2 - y1*x2
           ( y1 y2 )

- posted by Pop @ 5:13 PM

 
3-inv by two inverters
You have plenty of ANDs and ORs, but only 2 inverters. Can you invert more than 2 independent inputs?
•CHALLENGE: Come up with a combinational circuit using ANDs, ORs, and at most 2 inverters that inverts A, B, and C !
•Such a circuit exists. What does that mean?
-If we can invert 3 signals using 2 inverters, can we use 2 of the pseudo-inverters to invert 3 more signals?
-Do we need only 2 inverters to make ANY combinational circuit?

#include 
void main(){
 int a,b,c,x,y,z,g,h,a1,b1,c1,x1,y1,z1;
 int i;
 for(i=0;i<8;i++){ //a =" i" b =" (i">> 1;
  c = (i & 4) >> 2;

  x = a & b & c; // == three ones
  y = a & b | a & c | b & c; // == at least two ones
  z = a | b | c; // == at least single one

  //Here are our 2 inverters
  g = !(y); // zero or single one
  h = !(x | g & z); //zero or two ones
  
  x1 = g | h;  //zero or single, or two ones
  y1 = g; // zero or single one
  z1 = g & h; // zero one
  a1 = b & c & x1 | (b | c) & y1 | z1; //three zeros or ...
  b1 = a & c & x1 | (a | c) & y1 | z1;
  c1 = b & a & x1 | (b | a) & y1 | z1;

  //print outputs to verify
  printf("%d-->%d   %d-->%d   %d-->%d\n",a,a1,b,b1,c,c1);
  printf("x1=%d,y1=%d,z1=%d\n",x1,y1,z1);
 }
}

/*
Input output
a b c x1 y1 z1
0 0 0 1  1  1  
0 0 1 1  1  0
0 1 0 1  1  0
1 0 0 1  1  0
1 0 1 1  0  0
0 1 1 1  0  0
1 1 0 1  0  0
1 1 1 0  0  0
*/

- posted by Pop @ 3:10 PM

 
Secure Code
1. Determine the threats to the system
STRIDE:
- Spoofing Identity
*** An attacker poses as another user or a rogue server to pose as a valid server
- Tampering with data
*** malicious modification of data
- Repudiation
*** Refuse to perform an action without other parties having any way to prove.
*** For example, non-repudiation means a receipt for a deal.
- Information disclosure
*** exposure of information to individuals who are not supposed to have access to it
- Denial of service
*** deny service to valid users
- Elevation of privilege
*** an unpriviledged user gains privileged access
- posted by Pop @ 11:02 AM

 
Oracle Query
You are given n programs p1 ... pn, each of which take an ASCII string as input. Each program will either output an ACCEPT signal, or a REJECT signal, or will loop forever. You are also given n strings s1 ... sn, each affiliated with a respective program. Your task is to write a meta-program that determines which of the N program-string pairs output an ACCEPT. To assist you in this task, your meta-program is allowed to query an oracle, a black box that takes a program and a string as inputs, and immediately tells you if the computation ACCEPTs, REJECTs, or loops forever. However, you can only query the oracle log n times.

The oracle is a super-Turning-Machine, which can tell you three results about the input/program immediately: ACCEPTs, REJECTs, or Loops Forever

Answer: From the forum

1. Construct the super machines C1 ... Cn, where Ci is a machine that runs all the given machine-string pairs M1 through Mn in parallel and ACCEPTs only if exactly at least i of those machines accept.

For example: C[i] looks like
CountOfAccepts(P1(s1),P2(s2), ..., Pn(Sn)) > i == TRUE

2. Query the oracle binary search style, using the super machines as input to the oracle. Note that the strings have been hardcoded to the super machines, therefore the query to the Oracle has no input. After at most log(n) queries, we will know exactly how many of the machines accept. Call this number K.

For example: Query C[N] and C[1] first,
if Oracle(C[N], NULL) == Accepts then K=N
if Oracle(C[1], NULL) == Rejected then K=0
Else
we have Oracle(C[N], NULL) == Rejected and
Oracle(C[1], NULL) == Accepts
then we try Oracle(C[N/2]), based on the result, we will always try the middle in the
range with different status, i.e. Rejected..Accepts or Accepts..Rejected
This exactly like the binary searching

3. Finally, simulate all the machine-string pairs in parallel. Once exactly K of the machines have ACCEPTed, terminate the simulation program. Thus we have figured out which machines accept. There can be no more than K, because the oracle says so. And our simulation will not run forever, because if a machine accepts a string, it will accept after a finite amount of time.

Once we have the exactly value of K, We run the Pi(Si) in parallel and wait for the exactly K accepts. This can not be done if we do not know K because some of them will run forever.

- posted by Pop @ 3:56 PM

 
Questions from Xin He, SUNY Buffalo, CSE 531
1. Compute Fibonacci number in O(logn) runtime.

(1)  F(n) = F(n-1) + F(n-2) ==>
     F(n)   = ( 1 1 ) F(n-1) = (1 1) (1 1)F(n-2)
     F(n-1)   ( 1 0 ) F(n-2)   (1 0) (1 0)F(n-3)
            = (1 1)...(1 1) F(1)
              (1 0)   (1 0) F(0)  
              -------------
                n times
(2) Assuming A = (1 1)
                 (1 0) 

Then how to calculate A*A*...*A (N times) in O(logN)?
Because A(N) = A(N/2) * A(N/2)
T(N) = T(N/2) + Theta(1) ==> T(N) = O(logN)


2. Describe an O(N) time algorithm to find k numbers that are closest to the
median of an array S[N].

Method One (in place):
(1) find median x in array S in O(N)
(2) partition S into S1, S2 by pivot x in O(N) such that
    [e|S1] < x, [e|S2] > x
(3) find k/2 biggest numbers in S1 in O(N)
    find k/2 smallest numbers in S2 in O(N)
Method two (extra B[N]), by Xin He:
(1) find median x in array S in O(N)
(2) In another array B[N]: B[i]=abs(S[i]-x) for i=0..N-1
(3) find k-th number y in array B in O(N)
(4) for i=0..N-1 { if (abs(S[i]-x )<= y) output S[i] }

3. Find the median of two sorted array A[N], B[N] in O(N) time

(1) find median x in A[N], separate A[N] into A1<=x<=A2
(2) find median y in B[N], separate B[N] into B1<=y<=B2
(3) if x>y then B1<=A2, that is B1 <= A2, B2
    thus the median(A,B) is the median(A1,B2):
    the median(A1,B2) z must satisfy B1<=z<=A2 
(4) if x< y then A1<=B2, that is A1 <= A2, B2
    thus the median(A,B) is the median(A2,B1)

- posted by Pop @ 12:40 PM

 
Maximum Sum in Integer Array
Consider an array of integers a[1] ... a[n]. Design an O(n) algorithm that finds the pair I,J (with I <= J) such that the sum is maximized. (Note that integers can be both positive and negative.)

  enum {N=10};
  int a[N]={31,-41,59,26,-53,58,97,-93,-23,84};
  int maxsofar = 0;
  int maxhere = 0;
  int lmIndex = 0;
  int rmIndex = 0;
  for (int i=0;i  {
     if(maxhere+a[i]>0)
     {
       maxhere = maxhere+a[i];
     }else
     {
       maxhere=0;
       lmIndex = i+1;
     }

     if (maxhere>maxsofar)
     {
         maxsofar=maxhere;
         rmIndex=i;
     }
  }
  printf("a[%d]--a[%d]=%d\n",lmIndex,rmIndex, maxsofar);

This works on the fact that once temp falls below 0 , we can drop it.
- posted by Pop @ 11:29 PM

 
Solutions on CLR books and Programming Perl
1. Teaching Material for Programming pearls
http://www.cs.bell-labs.com/cm/cs/pearls/teaching.html

2. Solutions to CLR "Introduction to Algorithms" by Cormen, Leiserson and Rivest
http://www.itu.dk/people/beetle/teaching/

3. Xin He: SUNY Buffalo, CSE531
http://www.cse.buffalo.edu/faculty/xinhe/cse531/Homework/
- posted by Pop @ 1:55 PM