page476.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 159 行
HTML
159 行
<HTML><HEAD><TITLE>Exercises</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6643" HREF="page477.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6641" HREF="page433.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6635" HREF="page475.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6645" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0014600000000000000000">Exercises</A></H1><P><OL><LI> Consider the greedy strategy for counting out change given in Section <A HREF="page435.html#secalgschange"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. Let <IMG WIDTH=104 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67637" SRC="img1704.gif" > be the set of available denominations. For example, the set <IMG WIDTH=146 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68809" SRC="img1956.gif" > represents the denominations of the commonly circulated Canadian coins. What condition(s) must the set of denominations satisfy to ensure the greedy algorithm always finds an optimal solution?<LI> Devise a greedy algorithm to solve optimally the scales balancing problem described in Section <A HREF="page440.html#secalgsscales"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. <OL><LI> Does your algorithm always find the optimal solution?<LI> What is the running time of your algorithm? </OL><LI> Consider the following 0/1-knapsack problem: <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=3 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>i</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67677" SRC="img1712.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" > </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 9 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP COLSPAN=3><I>C</I>=18</TD></TR></TBODY></TABLE></P></DIV> <OL><LI> Solve the problem using the greedy by profit, greedy by weight and greedy by profit density strategies.<LI> What is the optimal solution? </OL><LI> <A NAME="exercisealgsbfsi"> </A> Consider the breadth-first solver shown in Program <A HREF="page444.html#progbreadthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. Suppose we replace the queue (line 3) with a <em>priority queue</em>. <OL><LI> How should the solutions in the priority queue be prioritized?<LI> What possible benefit might there be from using a priority queue rather than a FIFO queue? </OL><LI> <A NAME="exercisealgsbfsii"> </A> Repeat Exercise <A HREF="page476.html#exercisealgsbfsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, but this time consider what happens if we replace the queue with a <em>LIFO stack</em>.<LI> Repeat Exercises <A HREF="page476.html#exercisealgsbfsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page476.html#exercisealgsbfsii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, but this time consider a <em>branch-and-bound</em> breadth-first solver.<LI> <A NAME="exercisealgsgraph"> </A> (This question should be attempted <em>after</em> reading Chapter <A HREF="page519.html#chapgraphs"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>). For some problems the solution space is more naturally a graph rather than a tree. <OL><LI> What problem arises if we use the <tt>DepthFirstSolver</tt> given in Program <A HREF="page443.html#progdepthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to explore a search space that is not a tree.<LI> Modify the <tt>DepthFirstSolver</tt> so that it explores a solution space that is not a tree. <b>Hint</b>: See Program <A HREF="page550.html#proggraphd"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> What problem arises if we use the <tt>BreadthFirstSolver</tt> given in Program <A HREF="page444.html#progbreadthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to explore a search space that is not a tree.<LI> Modify the <tt>BreadthFirstSolver</tt> so that it explores a solution space that is not a tree. <b>Hint</b>: See Program <A HREF="page553.html#proggraphe"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. </OL><LI> <A NAME="exercisealgsqueens"> </A> Devise a backtracking algorithm to solve the <em><I>N</I>-queens problem</em><A NAME=34212> </A>: Given an <IMG WIDTH=48 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline68823" SRC="img1957.gif" > chess board, find a way to place <I>N</I> queens on the board in such a way that no queen can take another.<LI> Consider a binary search tree that contains <I>n</I> keys, <IMG WIDTH=13 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63723" SRC="img1169.gif" >, <IMG WIDTH=13 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63725" SRC="img1170.gif" >, ..., <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68833" SRC="img1958.gif" >, at depths <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65895" SRC="img1433.gif" >, <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65897" SRC="img1434.gif" >, ..., <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68839" SRC="img1959.gif" >, respectively. Suppose the tree will be subjected to a large number of <tt>find</tt> operations. Let <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" > be the probability that we access key <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63737" SRC="img1177.gif" >. Suppose we know <em>a priori</em> all the access probabilities. Then we can say that the <em>optimal binary search tree</em><A NAME=34216> </A> is the tree which minimizes the quantity <P> <IMG WIDTH=297 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath68799" SRC="img1960.gif" ><P> <OL><LI> Devise a dynamic programming algorithm that, given the access probabilities, determines the optimal binary search tree.<LI> What is the running time of your algorithm? </OL><P> <b>Hint</b>: Let <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68121" SRC="img1817.gif" > be the <em>cost</em> of the optimal binary search tree that contains the set of keys <IMG WIDTH=152 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68847" SRC="img1961.gif" > where <IMG WIDTH=33 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68849" SRC="img1962.gif" >. Show that <P> <IMG WIDTH=436 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath68800" SRC="img1963.gif" ><P><LI> Consider the typesetting problem discussed in Section <A HREF="page461.html#secalgstypeset"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. The objective is to determine how to break a given sequence of words into lines of text of the appropriate size. This was done either by stretching or compressing the space between the words. Explain why the greedy strategy always finds the optimal solution if we stretch but do not compress the space between words.<LI> Consider two complex numbers, <I>a</I>+<I>bi</I> and <I>c</I>+<I>di</I>. Show that we can compute the product (<I>ac</I>-<I>bd</I>)+(<I>ad</I>+<I>bc</I>)<I>i</I> with only three multiplications.<LI> Devise a divide-and-conquer strategy to find the root of a polynomial. For example, given a polynomial such as <IMG WIDTH=140 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline68857" SRC="img1964.gif" >, and an interval [<I>u</I>,<I>v</I>] such that <I>p</I>(<I>u</I>) and <I>p</I>(<I>v</I>) have opposite signs, find the value <I>r</I>, <IMG WIDTH=68 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68867" SRC="img1965.gif" >, such that <I>p</I>(<I>r</I>)=0.<LI> Devise an algorithm to compute a <em>normally distributed random variable.</em> A normal distribution is complete defined by its mean and standard deviation. The probability density function for a normal distribution is <P> <IMG WIDTH=375 HEIGHT=38 ALIGN=BOTTOM ALT="displaymath68801" SRC="img1966.gif" ><P> where <IMG WIDTH=9 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline68653" SRC="img1928.gif" > is the mean and <IMG WIDTH=9 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68873" SRC="img1967.gif" > is the standard deviation of the distribution. <b>Hint</b>: Consider the <em>central limit theorem</em><A NAME=34244> </A>.<LI> Devise an algorithm to compute a <em>geometrically distributed random variable.</em> A geometrically distributed random variable is an integer in the interval <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68875" SRC="img1968.gif" > given by the probability density function <P> <IMG WIDTH=332 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath68802" SRC="img1969.gif" ><P> where <IMG WIDTH=23 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline68877" SRC="img1970.gif" > is the mean of the distribution.<P> <b>Hint</b>: Use the fact <IMG WIDTH=197 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68879" SRC="img1971.gif" >, where <I>Z</I> is an exponentially distributed random variable with mean <IMG WIDTH=122 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68883" SRC="img1972.gif" >.<LI> Do Exercise <A HREF="page249.html#exercisehashingrandom"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</OL><HR><A NAME="tex2html6643" HREF="page477.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6641" HREF="page433.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6635" HREF="page475.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6645" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?