📄 http:^^sac.uky.edu^~newt^cs122^program4.html
字号:
Date: Tue, 14 Jan 1997 22:51:36 GMT
Server: Apache/1.1.1
Content-type: text/html
Content-length: 7928
Last-modified: Fri, 22 Nov 1996 22:40:16 GMT
<html> <title>CS122 Programming Assignment #4</title><body><center><h1>CS122 - Computer Science II</h1><h2>Fall, 1996</h2><h2>Programming Assignment #4</h2></center><h3>Assigned: Friday, November 22nd, 1996</h3><h3>E-mail Proposal Due: Wednesday, November 27th, 1996</h3><h3>External Documentation Due: Tuesday, December 3nd, 1996</h3><h3>Program Listing Due: Tuesday, December 10th, 1996</h3><h3>Scheduled Demonstrations: Tuesday, December 13th, 1996, and following</h3>** NOTE: Standard late penalties will apply after these dates;however, no work will be accepted after the last day of classes,Friday, December 13th, 1996. **<p>Your last programming assignment this semester is to design andimplement a C++ program that visually demonstrates the ideas underlyingone of the advanced sorting techniques we are studying in class.<p>Here are the requirements:<ul><li>Your program must be written in C++.<li>You are not required to use the SAC computers, but rathercan use any of the computer systems that are readily available oncampus, including (but not limited to) the SAC computers, theIBM PC's or Macintoshes in the Library Microlabs, or the NeXTcomputers. (If you would like to use a computer system other than oneof these 4, check with me first.) Whatever system you choose, it musthave some way of proving to me that it was able to compile your C++program (for example, by creating a program listing), and must beavailable on-campus for you to demonstrate your program for me.<li>You must choose one of the advanced sorts we are studying in class,namely Quicksort, Heapsort, or Shellsort, to show in your program.<li>You must design some method of visually demonstrating, through yourC++ program, the ideas that underlie your chosen sort. There are*many* possible different designs -- here are just three ideas: <ul> <li>Using an IBM PC with its graphics capabilities, along with Microsoft C++ or Borland C++, you could demonstrate a Heapsort. First, you could construct a list of 500 randomly chosen integers, graph them as a "cloud of points" (with their list index positions plotted along the horizontal axis and their values plotted along the vertical axis), and then apply a Heapsort to the list and show how the cloud gradually changes shape, first to that of a triangular heap, and from there to the (nearly straight) diagonal line that is the signature of a sorted list. At first, all points could be drawn red (for unsorted); as you swap two points they could briefly blink yellow, then back to red; and finally, when a point is known to have reached its final position in the sorted list, it could permanently become green. You could show running statistics on how many total comparisons and swaps were made, and how much time the the sort is taking. <li>Like the above, showing a cloud of points being sorted by, say, Shellsort, but using SAC, Unix, GNU C++ (g++), and the CURSES screen-control library. (CURSES was the library I used to demonstrate the interactive workings of the MazeCrawler from Program #3.) You won't be able to show as many points in the cloud, being limited to a maximum of 80 by the standard monitor screen's 80 columns, but the effect would be similar. Instead of color, you could use the special hilighting features made available by CURSES. <li>Using SAC, Unix, GNU C++ (g++), and regular "cout" statements to demonstrate a Quicksort. First, you could ask the user to choose between several possible pivot-picking strategies (we'll discuss what these are in lecture soon, which include picking the 1st, middle, or last item on list, or an item chosen at random, or the median value of three items chosen at random, etc.). Then you could ask the user to enter an unsorted list of up to up to 20 numbers: say the user entered the 20 numbers 21, 47, 16, ... , 32, 12. You could then visually display the list on the screen as a series of text bars:<pre> 1 (31) XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 2 (47) XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 3 (16) XXXXXXXXXXXXXXXX . . . 19 (32) XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 20 (12) XXXXXXXXXXXX</pre> where the far-left-hand number is the position of the item in the list, and the next number is the value of the item. Your program could pause, and once the user signals that he/she is ready to continue by pressing the enter key, you would then inform the user of the next step involved in performing your Quicksort ("Now we pick a pivot, namely the item in position #1, which is 21, and use it to partition the list."), and would then visually display your list again. You could display the entire list each time, but could have some special way of marking that portion of the list that is currently undergoing partitioning (say, by drawing it using capital X's, and drawing the rest of the list using small x's). This process of drawing, pausing, explaining, and re-drawing would continue until the entire list was sorted. You could then provide some statistics on how good the chosen pivot-picking strategy was for this particular list (e.g. "During partitioning, the average size of the larger of the two partitions formed contained 58% of the available list items, which is 8% above the optimal value of 50%."). </ul><li>I encourage you to come up with your own design, or you may use oneof the two listed above. Your goals should be to: <ul> <li>Be creative and innovative. <li>Show off your knowledge of programming in C++ and of your chosen sort. <li>Produce an attractive and informative demonstration program. </ul><li>Your program must actually implement your chosen sort; that is tosay, it must be capable of applying your chosen sort to *many*different lists of numbers, not just the same old list over and over.Your program must have some means of acquiring diverse lists ofnumbers: by allowing the user to enter the list, or by creating thelist randomly and in a different fashion each time it is run, etc. Youcan, however, place some reasonable constraints on the size of the listand on the range of the values in the list.<li>Your program must also teach the sort by indicating *both* the strategyused by the sort to order the entire list, and also the strategy usedby the sort in a single sort pass.<li>Here is what you'll need to submit to complete the assignment:<ol><li>You must e-mail me a proposal which specifies:<ul><li>which computer system you have chosen to use<li>which make/version of C++ compiler software you will be using<li>which of the three sorts you have chosen to work with<li>how you are going to visually demonstrate the way your chosen sort works </ul><li>You must turn in standard External Documentation, includingSpecifications, Algorithm, and Justification. In the place of ProposedTestcases, you *must* include some extensive visual samples (hand-drawnare OK here) of how your demonstration program will look when it isrun.<li>You must turn in listing for your program, and have some method ofindicating that your program compiled with no errors.<li>In the place of program executions, you must schedule a 15 minutedemonstration of your program with me. You must have submitted yourproposal, external documentation, and program listing prior to yourdemonstration. I'll talk more during class about how to go aboutscheduling a demonstration with me.</ol><li>For extra credit, you can add demonstrations of additional sorts toyour program, so that the interesting aspects of more than one sort canbe seen and studied.</ul>Good luck!</body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -