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

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

Legend:
 Removed from v.139 changed lines Added in v.140