Homework 2: When Harry Met Sally Solution

Description

Summary: This assignment explores the use of basic conditional execution, nested iteration, and memory accesses to analyze time/space data such as information collected by GPS-enabled applications In particular, you will write a program that analyzes two timelines, each of which gives a history of major cities in which a person has lived in chronological order. Your program will determine the earliest year in which both people lived in the same city.

 

Data in each timeline TL is stored as a sparse vector of ten elements in the following format (for i=0, 1, …, 4):

 

TL[i*2] = Duration: number of years a person lived in the city that is specified in TL[i*2+1].

 

TL[i*2+1] = City in which the person lived for TL[i*2] years.

 

Objective: For this assignment, you will write two programs, one in C and one in MIPS, to compute the earliest year at which Harry and Sally both lived in the same city. More details are described below.

 

Assume that the two people were both born in the year 1990 and the current year is 2019. So the total number of years (sum of TL[i*2] for i=0,1,…,4) is always 30. Each city is an integer between 0 and 9, inclusive. Also, assume that the total number of moves in each timeline is exactly five. For example, the timelines shown in Figure 1 are represented in C as:

 

HarryTimeline[] = {4, 4, 9, 3, 3, 8, 2, 4, 12, 2};

 

SallyTimeline[] = {1, 3, 11, 2, 4, 4, 6, 2, 8, 4};

 

Miami has city code 4 and Harry spent 4 years living there, then moved to Atlanta (city code 3), where he lived for 9 years. For this example, your program should compute 2008 as the correct answer.

 

 

 

 

 

 

 

 

Figure 1: Timelines showing how long Harry and Sally lived in certain cites. The earliest year in which they both lived in the same city is 2008 (when Harry moved to Paris where Sally was already living).

 

Note that this sparse vector representation is much more storage efficient than storing the city for each time point in the range 1990-2019.

 

Honor Policy: In all programming assignments, you should design, implement, and test your own code. Any submitted assignment containing non-shell code that is not fully created and debugged by the student constitutes academic misconduct. The only exception to this is that you may use code provided in tutorial-0.zip or in the examples on the course website/Canvas as a starting point for your programs (http://ece2035.ece.gatech.edu/examples/index.html or Canvas>Files>Lecture Slides>Code Examples).

 

HW2-1: For this part, design and implement a C program to compute and print the earliest year at which Harry and Sally both lived in the same city. If there is no year in which they are both in the same city, print 0.

 

 

 

 

 

1

 

ECE 2035 Homework 2: When Harry Met Sally

 

 

As a starting point, use the file HW2-1-shell.c. This program includes a reader function Load_Mem that loads the values from a text file. You should use gcc under Linux/Unix to develop your program. Sample test files (fa19-test1990.txt, fa19-test0.txt, fa19-test2004.txt, fa19-test2008.txt) are provided – the number in the name of each file indicates the correct answer. You should compile and run your program using the Linux command lines:

 

• gcc HW2-1.c –g –Wall –o HW2-1
• ./HW2-1 fa19-test2008.txt

 

You can create additional test files: using MiSaSiM to run HW2-2-shell.asm, go to the end of the trace, and use the “Dump” memory menu button to save the memory to a text file with the correct answer (the value in $3) in the name of the file.

 

Name the file HW2-1.C and upload it to Canvas by the scheduled due date.

 

HW2-2: For this part, design and implement a MIPS version of your program. A description of the MIPS library routines you need is given below. Use the file HW2-2-shell.asm as a starting point. The result should be stored by your program in $2 and reported as an answer by software interrupt swi 587 as described below. You must use these register conventions or the automated grader will score your program incorrectly. Memory should only be used for input to your program. Your program must return to the operating system via the jr instruction.

 

Programs that include infinite loops or produce simulator warnings or errors will receive zero credit. Name the file HW2-2.asm and upload it to Canvas by the scheduled due date.

 

MIPS Library Routine: There are two library routines (accessible via the swi instruction).

 

SWI 597: Create Duration Timelines: This routine generates and displays the timelines as shown in the example in Figure 1. It initializes memory with the 20 integers beginning at the specified base address (e.g., Harry). INPUTS: $1 should contain the base address of the 20 words (80 bytes total) already allocated in memory. OUTPUTS: the 20 words allocated in memory contain the 20 sparse vector elements (alternating duration and city) to be used as input data.

 

SWI 587: Report Earliest Overlap: This routine allows you to report your answer and an oracle provides the correct answer so that you can validate your code during testing.

 

INPUTS: $2 should contain the year you computed as your answer.

 

OUTPUTS: $3 gives the correct answer.

 

If you call swi 587 more than once in your code, only the first answer that you provide will be recorded.

 

Easter egg: As a debugging feature, you can load in a previously dumped testcase (pair of time-lines) by putting -1 into register $2 before you call swi 597. This will tell swi 597 to prompt for an input txt file that contains a testcase (e.g., fa19-test1990.txt).

 

 

 

 

 

 

 

 

 

 

 

 

2