# Contents of /pubs/books/ucbka/trunk/c_ras0/c_ras0.tex

Revision 6 - (show annotations) (download) (as text)
Fri Oct 7 01:36:46 2016 UTC (7 years, 8 months ago) by dashley
File MIME type: application/x-tex
File size: 3330 byte(s)
Initial commit after migrating from CVS.

 1 %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_ras0/c_ras0.tex,v 1.4 2003/11/03 02:14:24 dtashley Exp$ 2 3 \chapter[Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}] 4 {Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}, \cratzerolongtitle{}} 5 6 \label{cras0} 7 8 \vworkexercisechapterheader{} 9 \begin{vworkexercisesolution}{\ref{exe:crat0:sexe0:01}} 10 The value of the \texttt{state} variable when 11 evaluating the \emph{if()} clause on the 12 $n+1$'th invocation is 13 14 15 \label{eq:cras0:exe01:01} 16 K_1 - nK_4 + (n+1) K_2 . 17 18 19 We require on the $n+1$'th invocation, in order for the 20 test of the \emph{if()} clause to fail (i.e. that the function 21 \texttt{A()}'' has been run on the first $n$ invocations of 22 the base subroutine but is not run on the $n+1$'th invocation), 23 that: 24 25 26 \label{eq:cras0:exe01:01b} 27 K_1 - nK_4 + (n+1) K_2 < K_3. 28 29 30 Solving this inequality for the smallest integral 31 value of $n$ yields: 32 33 34 \label{eq:cras0:exe01:01c} 35 n = \left\lceil 36 \frac{K_1 + K_2 - K_3 + 1}{K_4 - K_2} 37 \right\rceil . 38 39 40 It can be verified using an example that 41 (\ref{eq:cras0:exe01:01c}). For example, with 42 $K_1 = 10$, $K_2 = 3$, $K_3 = 7$, and $K_4 = 5$, 43 (\ref{eq:cras0:exe01:01}) predicts that on the first 44 $\lceil 7/2 \rceil = 4$ invocations of the base subroutine 45 the subroutine \texttt{A()}'' will be run but on the 5th 46 invocation it will not. Tracing the algorithm with the 47 parameters specified reveals that at the 48 test in the \emph{if()} statement 49 on the first invocation of the 50 subroutine, \texttt{state}=13 (\texttt{A()}'' executed); 51 on the second invocation of the 52 subroutine, \texttt{state}=11 (\texttt{A()}'' executed); 53 on the third invocation of the 54 subroutine, \texttt{state}=9 (\texttt{A()}'' executed); 55 on the fourth invocation of the 56 subroutine, \texttt{state}=7 (\texttt{A()}'' executed); 57 and on the fifth invocation of the 58 subroutine, \texttt{state}=5 (\texttt{A()}'' not executed). 59 This is in agreement with 60 (\ref{eq:cras0:exe01:01}). 61 \end{vworkexercisesolution} 62 %\vworkexerciseseparator 63 %\begin{vworkexercisesolution}{\ref{exe:cfry0:sexe0:02}} 64 %Placeholder. 65 %\end{vworkexercisesolution} 66 \vworkexercisechapterfooter 67 68 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 69 \vfill 70 \noindent\begin{figure}[!b] 71 \noindent\rule[-0.25in]{\textwidth}{1pt} 72 \begin{tiny} 73 \begin{verbatim} 74 $RCSfile: c_ras0.tex,v$ 75 $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_ras0/c_ras0.tex,v$ 76 $Revision: 1.4$ 77 $Author: dtashley$ 78 $Date: 2003/11/03 02:14:24$ 79 \end{verbatim} 80 \end{tiny} 81 \noindent\rule[0.25in]{\textwidth}{1pt} 82 \end{figure} 83 84 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 85 % $Log: c_ras0.tex,v$ 86 % Revision 1.4 2003/11/03 02:14:24 dtashley 87 % All duplicate labels as flagged by LaTeX removed. Additional files added 88 % to Microsoft Visual Studio edit context. 89 % 90 % Revision 1.3 2003/03/08 04:11:19 dtashley 91 % Friday evening safety checkin. 92 % 93 % Revision 1.2 2001/07/01 21:10:59 dtashley 94 % Safety check-in after major re-org. 95 % 96 % Revision 1.1.1.1 2001/07/01 00:14:03 dtashley 97 % Initial import. 98 % 99 % 100 %End of file C_RAS0.TEX

 dashley@gmail.com ViewVC Help Powered by ViewVC 1.1.25