[rochester] / trunk / rochester_problib / setDiscrete4Functions / ur_dis_4_13.pg Repository: Repository Listing bbplugincoursesdistsnplrochestersystemwww

# View of /trunk/rochester_problib/setDiscrete4Functions/ur_dis_4_13.pg

Thu Jun 13 14:31:14 2002 UTC (10 years, 11 months ago) by ad001h
File size: 2187 byte(s)
```new problem
```

```    1 ##DESCRIPTION
2 ##Question 10, Section 2.2 of Discrete Math by Kenneth Rosen
3 ##ENDDESCRIPTION
4
5 DOCUMENT();        # This should be the first executable line in the problem.
6
8 "PG.pl",
9 "PGbasicmacros.pl",
10 "PGchoicemacros.pl",
12 "PGauxiliaryFunctions.pl"
13 );
14
15 TEXT(&beginproblem);
16
17 BEGIN_TEXT
18 You are the head of a division of a big Silicon Valley company and have assigned one
19 of your engineers, Jim, the job of devising an algorithm to sort through an English
20 text of \(n\) words and convert it into an Esperanto document.\$PAR Jim comes up with an algorithm which takes \(2n^2+2^n\) bit operations to handle an
21 input text with n words. \$PAR Suppose the computers in your business can handle one bit operation every nanosecond
22 (\(1\) nanosecond \(= 10^{-9}\) seconds).\$PAR How many nanoseconds would it take Jim's algorithm to convert a text with \(10\) words
23 on these computers?\{ans_rule(15)\}\$PAR How many DAYS would it take Jim's algorithm to convert a text with \(50\) words on these
25 END_TEXT
26 ANS( num_cmp( 1224 ) );
27 ANS( num_cmp( (2*50**2+2**50)/1000000000/60/60/24 ));
28
29 \$multiple = new_multiple_choice();
30
31 \$multiple -> qa(
32 "For an input text of \(100\) words, the statement that best describes the performance
33 of Jim's algorithm is:",
34 "His algorithm would take more than \(40\) trillion years to run."
35 );
36
37 \$multiple -> extra(
38 "His algorithm would take between \(4\) and \(40\) years to run.",
39 "His algorithm would take between \(4000\) and \(40,000\) years to run.",
40 "His algorithm would take between \(40\) million and \(40\) billion years to run.",
41 "His algorithm would take between \(40\) thousand and \(40\) million years to run.",
42 "His algorithm would take between \(40\) billion and \(40\) trillion years to run.",
43 "His algorithm would take between \(40\) and \(400\) years to run."
44 );
45
46 BEGIN_TEXT
47 (Recall a million is \(10^6\), a billion is \(10^9\) and a trillion is \(10^{12}\).)\$PAR
48 \{\$multiple -> print_q\}
49 \{\$multiple -> print_a\}
50 END_TEXT
51
52 ANS( checkbox_cmp( \$multiple->correct_ans ));
53
54 ENDDOCUMENT();        # This should be the last executable line in the problem.;
```