document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1209467>Question 1209467</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Given an array 𝑎[1..𝑛] containing half zeros and half ones, we need to find a position in 𝑎 that contains the value 1. Consider the following two algorithms:<BR>\n" );
document.write( "Algorithm 1:<BR>\n" );
document.write( "i = 1<BR>\n" );
document.write( "while a[i] != 1:<BR>\n" );
document.write( "    i += 1<BR>\n" );
document.write( "return i\r<BR>\n" );
document.write( "\n" );
document.write( "Algorithm 2:<BR>\n" );
document.write( "while True:<BR>\n" );
document.write( "    i = random(1, n)<BR>\n" );
document.write( "    if a[i] == 1:<BR>\n" );
document.write( "        return i<BR>\n" );
document.write( "The function random(1, n) returns a random integer between 1 and 𝑛.<BR>\n" );
document.write( "a) Compare the two algorithms.<BR>\n" );
document.write( "b) Which algorithm is better? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #848896 by </B><A HREF=/tutors/aboutme.mpl?userid=ikleyn><B>ikleyn(52926)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=ikleyn><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=ikleyn><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=848896\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> .\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "In this post, the question is like this:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Which algorithm would you prefer: one slow algorithm, but giving 100% precise answer with 100% reliability<BR>\n" );
document.write( "or another potentially faster algorithm which probably will NOT give you the 100% precise answer with 100% reliability ?\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "It reminds me a dialog of two mocks in the classic/famous novel \"Gargantua and Pantagruel\" <BR>\n" );
document.write( "by the French writer Francois Rabelais (written in 16th century).  \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;One monk asks another :\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;- If you had to travel to Causak (the city in France), what would you prefer - <BR>\n" );
document.write( "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;- to ride a goose or to pull a pig on a string?\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;To which the other monk replies: - I prefer to drink.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );