Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 306, Fall 2019
Programming Assignment 3
Due: November 10th, 11:59 pm
Yale N. Patt, Instructor
TAs: Sabee Grewal, Arjun Ramesh, Joseph Ryan, Chirag Sakhuja, Meiling Tang, Grace Zhuang

You must do every programming assignment by yourself. You are permitted to get help ONLY from the TAs and the instructor. 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. The file you submit should be an assembly language file called intersection.asm. This is the only file you need to submit.


This program is going to make use of a common data structure, the linked list.

The Linked-List

As discussed in class, a linked-list is a set of elements connected to each other via pointers. We often refer to these elements as "nodes." Each node
in a linked-list is comprised of k+1 words. The first word contains a pointer to (i.e., the address of) the next node, and the remaining k words contain
data associated with that node. The first word of the last node contains x0000, indicating that there are no more nodes in the list. We refer to x0000 as
the null pointer.

In programming lab 3, each node in our linked lists will consists of two words. The first word will contain a pointer to the next node. The second word will
contain a pointer to a character string representing the name of the person associated with that node. A character 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 signified by the NULL character
which is ASCII code x00.

Below is a graphical representation of two linked-lists. One consists of three nodes, representing three people: Chen, Grey, and Patel. The other
consists of three nodes, representing Brown, Chen, and Patel. Note that each linked list terminates with the null pointer x0000. Note also that each
character string terminates with a null entry x0000. Finally, note that each list has a list head (memory locations x4000 and x4001 in the example) which
contain pointers to the first node in their respective linked lists.

Below we show the layout in memory of the two linked lists described above.

Address Contents Description
x4000 x4050 Pointer to the first node of the first list
x4001 x4100 Pointer to the first node of the second list
x4002 x0000 Pointer to the first node of the third list (which you will create from existing nodes), initially invalid
... ...
x4050 x4150 Next-pointer
x4051 x4025 Pointer to the first ASCII code of the last name
... ...
x4025 x0043 ASCII code for "C"
x4026 x0068 ASCII code for "h"
x4027 x0065 ASCII code for "e"
x4028 x006E ASCII code for "n"
x4029 x0000 NULL character which signifies the end of the major
... ...
x4077 x0047 ASCII code for "G"
x4076 x0072 ASCII code for "r"
x4077 x0065 ASCII code for "e"
x4078 x0079 ASCII code for "y"
x4079 x0000 NULL character which signifies the end of the last name
... ...
x4100 x5000 Next-pointer
x4101 x5650 Pointer to the first ASCII code of the last name
... ...
x4150 x4550 Next-pointer
x4151 x4077 Pointer to the first ASCII code of the last name
... ...
x454E x0000 Next-pointer, x0000 indicates the end of the list
x454F x5500 Pointer to the first ASCII code of the last name
x4550 x0000 Next-pointer, x0000 indicates the end of the list
x4551 x5525 Pointer to the first ASCII code of the last name
... ...
x5000 x454E Next-pointer
x5001 x5600 Pointer to the first ASCII code of the last name
... ...
x5500 x0050 ASCII code for "P"
x5501 x0061 ASCII code for "a"
x5502 x0074 ASCII code for "t"
x5503 x0065 ASCII code for "e"
x5504 x006C ASCII code for "l"
x5505 x0000 NULL character which signifies the end of the last name
... ...
x5525 x0050 ASCII code for "P"
x5526 x0061 ASCII code for "a"
x5527 x0074 ASCII code for "t"
x5528 x0065 ASCII code for "e"
x5529 x006C ASCII code for "l"
x552A x0000 NULL character which signifies the end of the last name
... ...
x5600 x0043 ASCII code for "C"
x5601 x0068 ASCII code for "h"
x5602 x0065 ASCII code for "e"
x5603 x006E ASCII code for "n"
x5604 x0000 NULL character which signifies the end of the major
... ...
x5650 x0042 ASCII code for "B"
x5651 x0072 ASCII code for "r"
x5652 x006F ASCII code for "o"
x5653 x0077 ASCII code for "w"
x5654 x006E ASCII code for "n"
x5655 x0000 NULL character which signifies the end of the last name
... ...

Now we are ready to describe the program you are being asked to solve.

Finding suitable tenants

Overview: A realtor is trying to rent out apartment units and is struggling to find the right tenants. They need to find tenants that earn at least $75,000/year.
Additionally, they would prefer to rent to tenants that have at least three children. Fortunately, the realtor has a list of people, organized as a linked list, that
earn over $75,000/year and another list of people, also organized as a linked list, that have at least three children -- both lists are stored in memory. The
realtor wants you to provide them with a list of all the people, also organized as a linked list, that earn over $75,000/year who have at least three children.

Your Job: Write a program in LC-3 assembly language that takes as input two linked lists stored in memory, the first one containing the names of all people who earn
over $75,000/year, and the second one containing the names of all people who have at least three children, and produce as output a third linked list, also stored in memory,
containing the names of people who earn over $75,000 and have at least three children. More specifically, the result of your program will be 3 linked lists: people
who earn over $75,000/year who have fewer than three children, people that have at least three children and earn less than $75,000/year, and people who earn over $75,000/year
and have at least three children. You will achieve this by removing from the first linked list those people who have at least three children, and from the second list
those people who earn more than $75,000/year, and produce the third list from people who are removed from the first two lists.

In the example linked lists shown above, if the first list consisted of people earning more than $75,000 (Chen, Grey, and Patel), and the second list
consisted of people with at least three children (Brown, Chen, and Patel), your result would be: The first list consists of the single node Grey, the second list
consists of the single node Brown, and the third list consists of the two nodes Chen and Patel.

Finally, assume LC-3 is sufficiently constrained that you can not waste space. That is, you are not allowed to create any additional nodes to help
you solve this assignment, but instead you will construct your third list from nodes removed from your first list.

The address of the first node of the list (the list head) of people that earn over $75,000/year will be stored at location x4000. The address of
the first node of people with at least three children will be stored at location x4001. You will store the address of the first node of the result at location x4002.
A node will consist of two words: a pointer to the next node and a pointer to a character string. All nodes in each list will be ordered in alphabetical
order, based on their names. Each of the three final lists must also be sorted in alphabetical order based on person's name. The string of characters
will represent the name of the individual in question. For purposes of this lab, we will assume no two people have the same name. Thus, each name uniquely
identifies one individual who either earns $75,000/year, has at least three children, or both. The string will be null-terminated and stored in memory like so:
one ASCII character per memory location, the last character will be the null character.

Notes

  1. Your program must start at location x3000.
  2. The linked-lists representing the people who earn over $75,000/year and the people that have at least three children are inputs to your program. The lists are loaded
    into memory before your program begins to run. Your program will only need to modify the pointers of each node. You will lose points if you modify anything
    in the list or create new nodes in memory
  3. Either list can initially be empty (location's x4000 or x4001 contain x0000) or your resulting list may be empty (there are no childless people who earn
    over $75,000/year). Your program must work correctly in all cases.
  4. Your program should NOT make any assumptions about the number of nodes in the list.
  5. You can assume that the linked list will always contain a last node. I.e., a node whose next-pointer is x0000.
  6. To help you with debugging your program, we have provided you with a test case written in assembly language. Copy/paste this below your code to help you
    with your debugging. Note that this test case is not comprehensive and you are responsible to test your program using other test cases.
  7. Save your test cases. If you come up with additional test cases, save them in separate files (e.g. lab3_testcase2.asm, etc.). That way, when you modify your code,
    you can quickly re-run old tests to verify your modification didn't break anything.


Submit your Program: The program you are to submit is the .asm file. Save your .asm file, and give it the name intersection.asm. Submit this file on Canvas.