📄 w1_1998.html

📁 Data Structure Ebook
💻 HTML
字号:
<html><head>
<title>Data Structures and Algorithms - Workshop 1</title>
</head>
<BODY BGCOLOR="#fffff">
<H1>Data Structures and Algorithms</H1>
<HR>
<H2>Workshop 1 - 1998</H2>
<H3>Familiarisation</H3>
The basic aims of this workshop are to
<UL>
<LI>familiarise you with techniques to time an algorithm
      written in ANSI C <I>and</I>
<LI>experimentally confirm the time complexity of
addition and searching operations for various
data structures.
</UL>

You will need to write a simple program to insert data into
a tree,
measuring the average time to add an item
and to find a randomly chosen item in the tree.

<OL>
<LI>Download and save into your directory from the download window:
<OL TYPE="a">
<LI><A HREF="Collection.h" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/Collection.h" TARGET="Download Window">Collection.h</A>
<LI><A HREF="Collection.c" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/Collection.c" TARGET="Download Window">Collection.c</A>
<LI><A HREF="tree_struct.c" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/tree_struct.c" TARGET="Download Window">tree_struct.c</A>
<LI><A HREF="tree_add.c" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/tree_add.c" TARGET="Download Window">tree_add.c</A>
<LI><A HREF="tree_find.c" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/tree_find.c" TARGET="Download Window">tree_find.c</A> and
<LI>the test program <A HREF="tc.c" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/tc.c" TARGET="Download Window">tc.c</A>.
</OL>
<P>
<LI>Modify the collection implementation so that it uses a tree
structure rather than the original array.
Edit out the original structure, find and add methods and load
in the new ones. Of course, you will be able to leave the
specification of the Collection class untouched.
<LI>Compile into an executable:
<P>
<CENTER><TT><FONT COLOR=green>gcc -o tc tc.c collection.c</FONT></TT>
</CENTER>
<P>
Note that you will need to use an 
<A HREF="ANSI_C.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ANSI_C.html">ANSI C compiler</A> as the
programs are written in ANSI C. 
On some Unix machines, <TT><FONT COLOR=green>cc</FONT></TT>
only accepts the older "K&R C".
<P>
<LI>Run the program and verify that it runs as expected.
Examine the test program listing to determine how it runs!
<P>
<LI>Now we want to find out how efficiently it runs:
<P>
<OL TYPE="i">
<LI>Modify the test program so that it 
generates and then inserts a large number, <i><B>n</B></i>, of
integers into the collection. <P>
Note that you will need to be careful about the 
choice of the set of numbers that you generate.
Compare what happens to your times when you use
the set of integers, 1 to <I><B>n</B></I>, to
when you use the 
<FONT COLOR=green><TT>rand()</TT></FONT> function to generate
a set of random numbers to add.
<P>
Once you have created a collection with <B><I>n</I></B>
items in it,
determine how long it takes, on average, to find an item
in the collection.
Again you will need to generate a set of "probe" data which
you search for in the collection.
(Searching for the same item multiple times may cause problems
and give you misleading answers - <B>why?</B>)
<P>
<h3>Timing</H3>
Timing an individual function call has some traps:
<A HREF="timing.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/timing.html">read these notes for some guidelines.</A>
<P>
<LI>Determine the average time to search the collection for
a randomly generated integer -
again by finding the time to search for <I><B>n</B></I> 
randomly generated integers.
Use the random number generator, 
<A HREF="rand.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/rand.html"><TT><FONT COLOR=green>rand()</FONT></TT></A>,
to generate random integers.
<P>
<LI>Modify the program so that it prints out the
insertion and searching times for a range of values of
<I><B>n</B></I>.
Suitable values will produce run times between <EM>about</EM>
1 and 20 seconds. About 10 values should enable you to determine the
characteristics of the time <i>vs</i> <I><B>n</B></I> curve.
</OL>
<P>
</OL>
<FONT COLOR=red>Warning: Note carefully that the test program,
<FONT COLOR=green><TT>tc.c</TT></FONT> is a <B>test</B> program -
designed to demonstrate that the collection code is <B>correct</B>.
You will need to re-organise it quite a bit to perform the
timing analyses efficiently.
</FONT>
<P>
<H3>Report</H3>
Prepare a brief report which summarises your results.
(The report should be plain ASCII text - <FONT COLOR=red>
<B>not</B></FONT> the native form of
any word processor.)
<P>
This report should start by forming a hypothesis about your 
expected results.
This should be followed by the actual results.
The conclusion should provide a convincing argument as to why these
results confirm your original hypotheses. 
It should also highlight and attempt to explain any discrepancies.
<P>
You are expected to measure the addition <B>and</B>
searching times.
Your report should also discuss the difference (if any)
in results observed
when a sequence of integers, 1, 2, .. is used for the test data
compared to a randomly chosen list of integers.
<P>
If you design your program efficiently, you will be able to get
it to generate a table of data for you which you can paste
directly into the report.
<P>
<A HREF="new_submit.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/new_submit.html">Submission Instructions will be available soon!</A>
</body>
</html>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -