Machine Problem 4, due at the end of Mar 25
Part of
the homework for CS:2630, Spring 2024
|
A problem:
Consider the following ASCII-art representations of binary trees:
/\
/ \
/ \
/ \
/\ /\ /\
/ \ / \ / \
/\ /\ /\ /\ /\ /\ /\
A tree of height n occupies 2n–1 lines of text.
A tree of height n can requires lines 2(2n–1) characters wide.
Your problem is to write a SMAL Hawk program to display the largest such tree that will fit in the Hawk emulator's display window. Ideally, the tree should be approximately centered in the text window.
Note that you should not resize the window while the emulator is running, but you can make it as big (or small) as you want before launching the emulator. For really big windows, try shrinking the font size before stretching the window.
Framework: Your program must begin and end as follows:
TITLE "mp4.a by YOUR NAME HERE" USE "hawk.h" USE "stdio.h" ... your code here ... END
Obviously, where it says YOUR NAME HERE put your name, and where it says ... your code here ... put SMAL Hawk code to solve the problem.
Tools: The external symbol TERMINFO is the address of a 2-word block of memory holding the number of rows and columns available for text in the Hawk emulator's display window. The Hawk monitor function PUTAT allows a program to set the row and column where the next character output by PUTCHAR will be displayed. See the text of the stdio.h header file for more information about these.
The SL and SR Haw instructions are the easiest way to multiply and divide by two. Repeated multiplication by 2 is the easiest way to compute 2n on the Hawk.
Grading: 5 points. Correct output is worth 2.5 points. The remaining credit will be offered only for those who have correct output.
Code that does not assemble will not earn any credit.
Stylistically clean code is important; that is why half the credit is reserved for style, but only if the code works. Awkward indenting will be penalized up to 1 point from the 2.5 style points. Excessive or inadequate white space within and between lines will be penalized, again, up to 1 point. Excessive or inadequate comments will be judged similarly.
Note: Comments should not repeat the assignment. Assume that the reader of your code has read the assignment. Assume that the reader knows how to program, so commenting ADDSI R3,1 with increment R3 would be stupid. Comments should help the reader when the code is hard to follow.
Comments that give a high-level language equivalent for one or a small block of machine level statements are appropriate. If that style of commentary is used, please use sensible indenting and spacing rules for the "code" in the comments and use sensible variable names. So it might make very good sense to comment ADDSI R3,1 with counter++ because this explains that R3 is a counter and consistent use of high-level language code in the comments allows you to read the algorithm in the comment part of the assembly code. Of course, the high-level language code itself may still need comments. Don't omit those!
Note: As a general rule, the first lines of every file should identify that file. The TITLE in the code framework above does this. Please avoid using lines longer than 80 characters -- this is a common rule in the style guidelines of many employers. As a consequence, it is almost always a bad idea to maximize your editing window, since the default width of the window is 80 characters. Better to use the remainder of your screen realestate to open other windows for reference.
You can use the following tool flag many common file format problems such as overly long lines or invisible characters:
[HawkID@fastx?? ~]$ ~dwjones/format mp4.a
This format checker does not know anything about C or SMAL, it is looking for things that cause trouble with files imported from Windows systems, over-length lines, and non-printable characters.
Submission: To submit your work, it must be in a file named mp4.a in your current directory on the CLAS Linux system, and you must know your section number. In the following, what you type is shown in bold face. Begin at the linux command-line prompt:
[HawkID@fastx?? ~]$ ~dwjones/submit 0A0X mp4.a
Note: The ~dwjones must be verbatim, do not substitute another name. Also, use your section number (one of 0A01 to 0A05).
The submission script will copy your code and, after the copy is made, it will output a message saying "successful submission." You may resubmit as many times as you want; each time you resubmit, your previous submission of that file will be replaced, so we will only see your final submission. The completed dialogue on your screen will look like this when you are done:
In the event of insurmountable trouble, do not delete or edit files you have submitted until the graded work is returned. The operating system record of the last edit time and date and the backups maintained by the operating system are proof of what you did and when, and they allow us to investigate what happened. until your graded work is returned. This way, the time stamp marking the time of last edit is a trustworthy indicator of whether you did the work on time.
I don't know where to begin! Help!
This problem was designed to give you choices and designed to give you a chance to make your own design decisions. The only thing specified is the final appearance of the output. There are many design choices you need to make to get that output.
First, this problem is large enough that you need to divide it into parts and address them separately:
These problems are, to a significant extent, independent. You need to solve all of them to solve the problem, but you can debug each part separately, and you can substitute trivial code for any part you have not solved yet.
To actually plot the tree, the third problem above, you have more choices:
Note that none of the solutions I will post use any kind of arithmetic other than adding, subtracting or shifting, where shifting is used to multiply or divide by two. Yes, the size of a tree is an exponential function of its number of levels, but the problem does not require use of exponentiation.
Note also that off-by-one errors in positioning are easy mistakes to make and also easy to fix by trial and error. As of this writing, I've debugged two solutions, and in debugging both, I came to the point where my output looked something like this:
/\
/ \
/ \
/ \
/\ /\
/ \ / \
/\ /\ /\ /\
Similar off-by-one errors had impacts on the overall centring of the tree. These were easiest to see if I sized the window to be just a little taller than the tree or just a little wider than the tree.
I followed your advice in the discussion to break the problem into 3 parts. I am currently calculating to find the limiting factor between the height and width. ... It compiles (no errors), but that doesn't mean it's all correct.
You can independently test the pieces, although some are easier to test if you finished others first.
These are not all big enough to be worth separate subroutines. The recursive tree plotter will need to be a separate routine, but the other two parts of this problem might be simple enough to fit in the main program, or if you want, you can split them out.
Would it be possible to manipulate my current max size ... in another function? I am worried about having too much in the main program at the moment considering my implementation is a bit lengthy.
If the algorithm starts to look big, break it into separate functions. You probably won't need to compute the size of the tree in a separate function, but if it makes the code easier for you to write and understand there is nothing wrong with doing so.
I am having trouble understanding and implementing the recursion of this problem.
The recursion is exactly the same as the recursion of traversing the tree. To plot a tree at size n, do the following in any order, with the recursion terminating when n is too small:
I've done 3 solutions so far, plotting in different orders, and passing different notions of where to start. To plot one of the trees, do you pass it n, or do you pass it i, where n = 2i? To plot one of the trees, do you pass x and y as the coordinates of the center of the tree, or do you pass x and y as the coordinates of the root where the left / meets the right \? All of these can be made to work.
I don't know the best way to go about this.
I don't know if there is a best way, only many ways that all work.
I don't understand how to use TERMINFO.
Here is a little block of code that (if you plug it into a main program) will plot an X in the lower right corner of the screen. It assumes that you have a USE "stdio.h" up at the head of your program.
LIL R1,TERMINFO LOAD R3,R1,TERMCOLS ADDSI R3,-1 ; -- parameter x = termcols - 1 LOAD R4,R1,TERMROWS ADDSI R4,-1 ; -- parameter y = termrows - 1 LIL R1,PUTAT JSRS R1,R1 ; putat( termcols - 1, termrows - 1 ) LIS R3,'X' ; -- parameter LIL R1,PUTCHAR JSRS R1,R1 ; putchar( 'X' )
The above code is tested and it works. Note that the available screen area does not include the last line on the window because plotting an X there causes the window to scroll, which would mess up any graphics you were trying to construct. To avoid that, TERMROWS always keeps you away from the last line.
I'm working on setting up JSR instructions in the function to properly call two recursions, one for the bottom left side of the tree and another for the right side of the tree. Could you provide guidance on how to structure these JSR instructions to achieve this goal?
Take a look at the demo code distributed with the notes for Thursday, Feb. 20.
That code does binary tree traversal, not to draw a tree but to print out the data at each tree node. The structure of the recursion is the same as you need, the difference is in what it does at each recursion and the terminating conditions it uses.
Repeating what I said in class today:
There will be a 1 week extension to MP4.
Grading: All improvements to the solution you submitted yesterday will earn 3/4 credit if submitted before Friday. All improvements submitted by next Monday will earn 1/2 credit. That is the final deadline. If you have not submitted work that earned any credit, you can still earn 3/4 or 1/2 credit!
Those who have made arrangements to turn in late work prior to yesterday's deadline can, of course, receive full credit.
Rationale: Looking at the submissions this morning before class, I observed that most of the working submissions were made before last Friday. Those who made their first submission after that date largely failed to achieve much. It is very clear that most of the class needs more time on this.
This is a sink-or-swim assignment. This is a programming course! The analysis of the recursion in this problem is well within the expectations for CS II (data structures), and the assembly code involved is at a level comparable to that in MP3, except that there is more of it. Exam II will definitely assume you have solved this assignment.
My solutions to MP4 were 184, 123 and 118 lines of code. That contrasts with MP3, where my solutions were 83, 69 and 60 lines. Both sets of numbers include a fair number of comments and blank lines, and I think both are reasonable measures of the difficulty of the assignments.
If I were to go back in and adjust my comments and code, would this mean that I wouldn't be able to receive full credit since it's submitted after the initial deadline? Or would you suggest I leave the submission as is?
The extension policy is written so that you earn additional credit. You cannot lose credit by resubmitting, but you can gain if your new code represents an improvement in performance or cosmetics over the old code.
I forgot exactly what to put in the console to slow down running the program in the hawk emulator ... it is going too fast for me to understand what is being printed.
Appendix A of the Hawk manual covers the Hawk emulator control panel and commands. Here's a quote:
I just checked the emulator source code (it's on the class web site). By default, the emulator output is updted every 20 instructions while it is running. If you type 1z into the emulator, it will update its output every instruction, making it about 20 times slower.