Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 306, Fall 2017
Programming Assignment 4
Due: December 5th, 11:59 pm
Yale N. Patt, Instructor
TAs:Stephen Pruett, Siavash Zangeneh, Aniket Deshmukh, Zachary Susskind, Meiling Tang, Jiahan Liu

You must do every programming assignment by yourself. You are permitted to get help ONLY from the TAs and Dr. Patt. When you have completed the program, and tested it sufficiently so that you are comfortable that it works on any input, submit it for grading according to the submission instructions at the end of this handout.

Programming Assignment 4: The Payroll Program

Your job: Write a program in LC-3 assembly language that prompts the user to enter the name of a professor, searches a database for that professor, and prints to the screen that professor's salary. The database of professors will be stored in memory as a binary tree. We refer to the "top" node of a binary tree as the ROOT of the tree. The address of the root can be found at memory location x4000.

The Binary Tree

A binary tree is a special case of a tree where each node has at most two child nodes. We refer to the two children as the left child and the right child. In this lab, each node of the tree will consist of 4 words: a pointer to the left child if one exists, a pointer to the right child if one exists, a pointer to the ASCII string containing the professor's name, and a 2's complement number representing the professor's salary. If there is no left or right child, the corresponding word will contain the null pointer. We have provided an example binary tree shown below, and provided the assembly code for that tree here.

Note that a binary tree consists of a root and up to two children, each of which is in itself the root of a binary tree. In the example below, Joe is the root of the binary tree, its child Daniel is the root of a binary tree often referred to as the left subtree, and its child Ali is the root of a binary tree often referred to as the right subtree.

Hint: the above paragraph should give you a hint about the best way to solve this programming problem, i.e., by using recursion.

Example Tree Picture
Figure 1

Input/Output Requirements

Described below are detailed requirements about the inputs and outputs of your program. All prompts and outputs should be printed to the screen EXACTLY as shown below to receive full credit.

Input: Your program should print the following prompt to the screen: Type a professor's name and then press Enter:

The user will input either a professor's name or the letter 'd', signifying that the user has no more professors to look up, followed by the Enter key. You must echo each character (including the enter key) to console.

Output: If there is a match, print the professor's salary to the console. If there is no match, print No Entry to the console. If the letter 'd' is typed (followed by the enter key), do not print anything to the console. To assist with printing salaries larger than a single ASCII character, we have provided you with a subroutine that takes as input a 2's complement number in R0 and prints it to the console. You may use this subroutine in any way you choose.

Type a professor's name and then press Enter:Dan
Type a professor's name and then press Enter:Dani
No Entry
Type a professor's name and then press Enter:Daniel
Type a professor's name and then press Enter:dan
No Entry
Type a professor's name and then press Enter:d

----- Halting the processor ----

You may assume:

  • The user input is typed without using backspace or delete, and is always followed by the Enter key.
  • You may assume that no professor earns more than $32,767 as a salary.
  • You may assume that no professor's name (including the name entered by the user) is longer than 20 characters. (Updated 12/3/2017)
  • You may assume that all salaries are zero or positive. (Added 12/4/2017)
  • Your program should be case sensitive. That is, "dan" is not a match for "DAN". (Added 12/4/2017)
  • Submission Instructions: Your program should be submitted as a single file called salary.asm. You MUST name your file EXACTLY as specified. Failure to do so will result in a loss of points on the assignment. The one .asm file should be submitted to Canvas by the deadline.