You must do the programming assignment by yourself. You are permitted to get help from ONLY the TAs and the instructor.  The file you submit should be an assembly language file called directory.asm. This is the only file you need to submit.

University Directory

Overview: 
You will design the user-interface of a university directory that associates each student with a student ID. Your program will prompt the user for a student ID and print the name of the student. For example, if the name of the student with ID 5 is ‘John’, then if the user types ‘5’ at the prompt, your program will print ‘John’.

Your job:
Write a program in LC-3 assembly language that will (1) prompt the user to type a student ID, (2) search the directory to find the student with the entered ID, (3) print the name of the student on the screen if the student was found in the directory, or print a message saying no such entry exists, if the student was not found in the directory, (4) return to step 1 and prompt the user for another student ID and (5) when the user signals he/she has no more students to look up, then halt the machine. We now discuss each step in turn. 

1. Prompting for a student ID: Your program will print on the screen the string "Type a student ID and press Enter:" and wait for the user to enter the student ID, followed by the <Enter> key. To simplify the program, we will assume that the university has no more than ten students so the student ID consists of a single decimal digit (e.g. one of the digits 0,1,…,9). Once the user has entered the single decimal digit representing the student ID and pressed the <Enter> key, your program will search the directory for the name associated with the ID.
2. Searching the directory: The directory stores for each student ID the student’s name. You will find a match for the ID in the directory only if the ID exists in the directory. Note that it is possible to not find a match in the directory. The directory is organized as a data-structure called a binary search tree. The workings of the binary search tree is described below. The address of the first node (the root) of the directory is stored in memory location x3300 before the program is run.
3. Printing the student name: If your program does not find a match for a student ID in the directory, your program must EXACTLY print the string "No Entry" on the screen. If your program finds a match in the directory, your program will print the name. You will then print a line feed character (ASCII code x0A) to the console to bring the cursor to the next line in the console.
4. The program will return to step 1 and prompt the user for another student ID
5. Halting the machine: When the user has no more students to look up, he/she will enter the letter ‘d’ (as opposed to a decimal digit) as the student ID. The ‘d’ stands for “done”. The machine halts after the user enters ‘d’ as the student ID.

The Binary Search Tree

In class, we learned about two different data structures for storing data in order: sequential arrays and linked lists. We showed that sequential arrays perform well when searching for an element, but perform poorly when inserting/deleting an element; conversely, linked lists perform poorly when searching for an element, but perform well when inserting/deleting an element. In this programming assignment we introduce a third data structure, the binary search tree, which has decent performance on BOTH searches and insertions/deletions.

Like a linked list, a binary search tree consists of a set of nodes connected to each other via pointers. However, unlike a linked list, each node in the binary search tree contains pointers to two other nodes in the binary search tree. These two nodes are commonly known as the ‘children’ of the parent node. The two children are differentiated as the “left child” and the “right child” of a node. If a node does not have a left child (and/or a right child) the pointer to that child will be x0000. We call x0000 in this context a NULL pointer.

For a given node, its descendants are all the nodes that are its children, or children of its children, or children of children of its children, and so forth. Similarly, for a given node, its ancestors are all the nodes that are its parent, or its parent’s parent, and so forth. Think of the way descendants and ancestors work in a family tree. Unlike a family tree, however, each node in a binary search tree only has one parent, and each node has at most two children.

A binary search tree wherein each node has a unique identifier has the following special property: The value of the left child of a node is less than the value of the node, and the value of the right child of a node is greater than the value of the node.

Furthermore, cycles are not permitted in a binary search tree. That is, a node cannot be both the descendant and ancestor of another node. Equivalently, this means if you start from any node in the tree and keep following pointers, you will eventually reach a node with no children.

The following images show two examples of binary search trees. Note that, for a given set of values, there is not a unique binary search tree, as both examples below are valid binary search trees for the same set of values. The particular tree used depends on how it is created. Luckily, you do not have to worry about creating a binary search tree in this program. You are simply searching for a value in it.

Figure 1. Two binary search trees with the same set of data values but different tree structures

In general each node in a binary search tree is comprised of k+2 words: two words containing the pointers to its children and k words of data which are stored at the node. In our particular example of a binary search tree representing a directory of student names , each node consists of four words in the following order:

1. The pointer to the left child.
2. The pointer to the right child.
3. The student ID of the student (stored as a numeric value between x0000 and x0009; note we do NOT store the student ID as an ASCII character)
4. A pointer to an ASCII string representing the student’s name.

Recall that a string consists of ASCII codes stored in consecutive memory locations, one ASCII code per location. The string is null-terminated, i.e., the end of a string is marked by the NULL character which is the value x0000. Below we show an example directory implemented as a binary search tree. This directory contains four nodes: the students with IDs 0, 4, 6, and 9. The node containing the student with ID 6 is at the root of the tree.

Address Contents Description x3300 x4000 Pointer to first node ... ... ... x4000 x4100 Left Child x4001 x4200 Right child x4002 x0006 Student ID x4003 x4050 Pointer to first ASCII character of student's name ... ... ... x4050 x0042 ASCII code for "B" x4051 x0045 ASCII code for "E" x4052 x004E ASCII code for "N" x4053 x0000 NULL character which signifies end of name ... ... ... x4100 x0000 Left Child (null) x4101 x4250 Right child x4102 x0000 Student ID x4103 x4160 Pointer to first ASCII character of student's name ... ... ... x4160 x004A ASCII code for "J" x4161 x0041 ASCII code for "A" x4162 x0043 ASCII code for "C" x4163 x004B ASCII code for "K" x4164 x0000 NULL character which signifies end of name ... ... ... x4200 x0000 Left Child (null) x4201 x0000 Right child (null) x4202 x0009 Student ID x4203 x4220 Pointer to first ASCII character of student's name ... ... ... x4220 x004A ASCII code for "J" x4221 x0045 ASCII code for "E" x4222 x004E ASCII code for "N" x4223 x004E ASCII code for "N" x4224 x0000 NULL character which signifies end of name ... ... ... x4250 x0000 Left Child (null) x4251 x0000 Right child (null) x4252 x0004 Student ID x4253 x4300 Pointer to first ASCII character of student's name ... ... ...  x4300 x0041 ASCII code for "A" x4301 x004E ASCII code for "N" x4302 x004E ASCII code for "N" x4303 x0000 NULL character which signifies end of name

Figure 2. Binary tree stored in the memory shown on the left

To search the binary search tree, your program will visit the first node (the root) of the tree and compare the student ID at that node with the ID entered by the user. If the IDs match, then we have found the right student, so your program should print the student’s name, followed by a line feed (ASCII code x0A), and prompt the user for another student ID. If a match is not found, it will visit the appropriate child of the node (depending on whether the entered ID is less than or greater than the node’s ID) and compare the entered ID against the ID at the child node. It will continue to visit nodes until either a match is found or it reaches a node with no appropriate child (e.g., if the entered value is less than the node’s value, but the node does not have a left child, or if the entered value is greater than the node’s value, but the node does not have a right child). This implies that a match was not found.

Input/Output Requirements

Described below are detailed requirements about the Inputs and Outputs of your program. You should adhere to these guidelines to receive full credit for this assignment. 

Your program should prompt the user for the student ID from the keyboard, as follows:

• Print a string "Type a student ID and press Enter:". Note that you will get a 0 on the assignment if you do not print the string EXACTLY. The prompt should always begin on a new line on the console.
• The user will input a character from the keyboard, followed by the <Enter> key. The character is either a decimal digit representing a student ID, or the letter ‘d’, signifying that the user has no more students to look up. You need to print both the character and the line feed character from the <Enter> key back to the console.
• You may assume that only decimal digits or ‘d’ will be entered.
• You may assume that the student ID is typed correctly without using backspace and delete, and is always followed by the <Enter> key. Similarily, you can assume 'd' will always be followed by the <Enter> key.

For each student the user looks up, your program should output one of two strings depending on the outcome of the directory lookup.

• When the student ID entered by the user is found in the binary search tree, output to the screen the name as recorded in the directory, followed by a line feed character (ASCII code x0A).
• When the student ID entered by the user is not found in the binary search tree, output to the screen: "No Entry", followed by a line feed character (ASCII code x0A).

• When program halts, the TRAP x25 service routine will print a line feed character to the console, followed by the message "----- Halting the processor -----". You should NOT be printing your own
  "----- Halting the processor -----" message with TRAP x22 (PUTS); otherwise, you will get two copies of the message.

Type a student ID and press Enter:5
No Entry
Type a student ID and press Enter:1
No Entry
Type a student ID and press Enter:0
JACK
Type a student ID and press Enter:4
ANN
Type a student ID and press Enter:8
No Entry
Type a student ID and press Enter:9
JENN
Type a student ID and press Enter:6
BEN
Type a student ID and press Enter:7
No Entry
Type a student ID and press Enter:d

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

1. Your program must start at location x3000.
2. The binary search tree representing the directory is an input to your program. The directory is loaded in memory before your program begins to run. When we grade your program, we will first load our own directory into memory and set memory location x3300 to the address of the root node of our directory, then run your program. When you are testing your own program, you should load your own directory into memory and set x3300 to the address of the root node of your directory before running your program.
3. Your program will only search the directory, not modify it. You will lose points if you modify the directory.
4. The pointer to the first node (the root) is stored in memory location x3300 before program execution begins. Furthermore, assume that all the nodes are stored between memory locations x4000 and xFDFF. Make no other assumptions about the location of the nodes. Note that the pointer to the first node may be set to NULL (i.e., 0), indicating that there are no nodes in the binary search tree. In this case, all student lookups should result in "No Entry", and you should halt the machine after the user enters 'd', as you would normally.
5. Your program should NOT make any assumptions about the number of nodes in the binary search tree.
6. You may assume that there are no cycles in the binary search tree, and each node has exactly one parent, and at most two children
7. You may assume that everyone in the directory does have a name made up of valid ASCII characters.
8. The <Enter> key is the line feed character which is the ASCII code x0A.
9. You may assume that the directory never contains two nodes with the same student ID.