📄 page413.html
字号:
<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="tex2html5933" HREF="page414.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5931" HREF="page386.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5925" HREF="page412.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5935" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0012600000000000000000">Exercises</A></H1><P><OL><LI> <A NAME="exercisesetsi"> </A> For each of the following implementations derive an expression for the total memory space required to represent a set which contains of <I>n</I> elements drawn from the universe <IMG WIDTH=149 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66651" SRC="img1553.gif" >. <OL><LI> <tt>SetAsArray</tt> (Program <A HREF="page389.html#progsetAsArraya"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>),<LI> <tt>SetAsBitVector</tt> (Program <A HREF="page393.html#progsetAsBitVectora"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>),<LI> <tt>MultisetAsArray</tt> (Program <A HREF="page397.html#progmultisetAsArraya"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>), and<LI> <tt>MultisetAsLinkedList</tt> (Program <A HREF="page400.html#progmultisetAsLinkedLista"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>). </OL><LI> <A NAME="exercisesetscomparison"> </A> In addition to = and <IMG WIDTH=10 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66769" SRC="img1571.gif" >, a complete repertoire of set operators includes <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline66781" SRC="img1573.gif" >, <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline66783" SRC="img1574.gif" >, <IMG WIDTH=10 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66785" SRC="img1575.gif" > and <IMG WIDTH=11 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61127" SRC="img760.gif" >. For each of the set implementations listed in Exercise <A HREF="page413.html#exercisesetsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> show how to implement the remaining operators.<LI> The <em>symmetric difference</em><A NAME=29589> </A><A NAME=29590> </A> of two sets <I>S</I> and <I>T</I>, written <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67339" SRC="img1672.gif" > is given by <P> <IMG WIDTH=344 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath67315" SRC="img1673.gif" ><P> For each of the set implementations listed in Exercise <A HREF="page413.html#exercisesetsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> devise an algorithm to compute symmetric difference. What is the running time of your algorithm?<LI> The <em>complement</em><A NAME=29595> </A> of a set <I>S</I> over universe <I>U</I>, written <I>S</I>' is given by <P> <IMG WIDTH=290 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath67316" SRC="img1674.gif" ><P> Devise an algorithm to compute the complement of a set represented as a bit vector. What is the running time of your algorithm?<LI> Devise an algorithm to sort a list of integers using a multiset. What is the running time of your algorithm? <b>Hint</b>: See Section <A HREF="page512.html#secsortingbucket"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> <A NAME="exercisesetsmultiseti"> </A> Consider a multiset implemented using linked lists. When the multiset contains duplicate items, each of those items occupies a separate list element. An alternative is to use a linked list of ordered pairs of the form <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67347" SRC="img1675.gif" > where <I>i</I> an the element of the universal set <I>U</I> and <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline62243" SRC="img937.gif" > is a non-negative integer that counts the number of instances of the element <I>i</I> in the multiset.<P> Derive an expression for the total memory space required to represent a multiset which contains of <I>n</I> instances of <I>m</I> distinct element drawn from the universe <IMG WIDTH=149 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66651" SRC="img1553.gif" >.<LI> <A NAME="exercisesetsmultisetii"> </A> Consider a multiset implemented as described in Exercise <A HREF="page413.html#exercisesetsmultiseti"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. Devise algorithms for set union, intersection, and difference. What are the running times of your algorithms?<LI> <A NAME="exercisesetspartition"> </A> Consider the initial partition <IMG WIDTH=196 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline67363" SRC="img1676.gif" >. For each of the methods of computing the union listed below show the result of the following sequence <em>join</em> operations: <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67365" SRC="img1677.gif" >, <IMG WIDTH=62 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67367" SRC="img1678.gif" >, <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67369" SRC="img1679.gif" >, <IMG WIDTH=62 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67371" SRC="img1680.gif" >, <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67373" SRC="img1681.gif" >, <IMG WIDTH=62 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67375" SRC="img1682.gif" >, <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67377" SRC="img1683.gif" >, <IMG WIDTH=62 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67379" SRC="img1684.gif" >, <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67381" SRC="img1685.gif" >. <OL><LI> simple union,<LI> union by size,<LI> union by height, and<LI> union by rank. </OL><LI> For each final partition obtained in Exercise <A HREF="page413.html#exercisesetspartition"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, show the result of performing a <em>collapsing find</em> operation for item 9.<LI> Consider the initial partition <I>P</I> of the universe <IMG WIDTH=149 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66651" SRC="img1553.gif" > comprised of <I>N</I> sets[<A HREF="page610.html#horowitz2">24</A>]. <OL><LI> Show that <I>N</I>-1 join operations can be performed before the number of elements in the partition is reduced to one.<LI> Show that if <I>n</I> join operations are done ( <IMG WIDTH=74 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67393" SRC="img1686.gif" >), the size of the largest element of the partition is at most <I>n</I>+1.<LI> A <em>singleton</em><A NAME=29619> </A> is an element of a partition that contains only one element of the universal set. Show that when <I>n</I> join operations are done ( <IMG WIDTH=74 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67393" SRC="img1686.gif" >), at least <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67401" SRC="img1687.gif" > singletons are left.<LI> Show that if less that <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67403" SRC="img1688.gif" > join operations are done, at least one singleton is left. </OL></OL><HR><A NAME="tex2html5933" HREF="page414.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5931" HREF="page386.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5925" HREF="page412.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5935" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -