Posted: April 17, 2003

Late Penalty

We will only accept the project up to ONE day late. This is 11:59 PM on May 12, 2003. There will be a 10% deduction per day off.

Purpose

The goals of the project are:

• Write MIPS code
• Understand how to implement functions and arrays in MIPS
• Be familiar with the SPIM simulator

Academic Integrity Statement

Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only, unless otherwise specified IN PRINT by official webpages.

Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Hardcoding is considered a violation of academic integrity

Collaboration on P3

You may work with one other person on this project. There should be a single submission for the project, with both your names.

Depth-First Search

You should implement depth-first search, using an adjacency matrix. The adjacency matrix should be implemented using a two-dimensional array. In MIPS (and C), a two dimensional array, is really a one dimensional array, where you use a formula with row and column to access elements. Recall that two dimensional array is stored in row major order.

You may wish to use the stack to store the arrays.

Your depth-first-search should be implemented using recursion. This means you should have function calls in your implementation.

Like C, you should not have to copy arrays. You should pass around the address of element 0 to the array.

We will provide you C-code for depth-first-search. If you can't remember how it works, you may wish to consult your 214 or 351 notes, or ask a TA.

Input Format

We hope to run this via input redirection (if SPIM supports this). If not, we will have to provide you some other means to read in input. In the meanwhile, you can hardcode your file to have certain edges for testing purposes.

If input redirection works, the format will be:

• Number of vertices
• Number of edges
• A list of edges
• A start vertex to perform the DFS

Vertices are numbered from 0 to N-1, where N is the number of vertices.

Thus, the following is a sample input:

5
4
0 2
1 3
2 3
2 1
2

Thus, line 1 tells you there are 5 vertices. Line 2 tells you that there are 4 edges. Line 3 tells you that (0, 2) is an edge (and it also tells you that (2,0) is an edge, since this is an undirected graph).

Lines 3-6 tell you the edges. There are four edges, since line 2 told you there were 4 edges.

Line 2 tells you to start the DFS at vertex 2.

At this point, your program prints out the vertices as visited by DFS, starting at vertex 2. Once it prints, it exits the program.

A sample C program will be posted in the posting account, and you can copy and compile that to see it in action. You can use that program to help you write the MIPS version.

There will be an explanation of DFS in the posting account too.

Should the input format change, we will post this in the FAQ. For now, you can "hardcode" the input, so that you can make progress. You may have to anticipate a change to how the input is read in, so make that part of the code isolated from the rest. In particular, you may want to have that in a "function" (as in readEdges()), which can then be substituted by other means of reading in the edges.

You can assume each edge has unit weight.

Extra Credit

For extra credit, you may wish to implement depth-first-iterative deepening. It probably doesn't teach you that much more about assembly programming, but it does teach you more about DFS.

This idea behind this algorithm will be posted fairly soon, in the posting account.

Submitting

You should tar your file and a README. We will post a name for the name of your spim program (most likely dfs.asm, unless SPIM has any requirements).

You can submit this as project 3. We will post directions to submit in the posting account.

See the class syllabus for policies concerning email Last Modified: Thu Feb 13 09:13:38 EST 2003

Web Accessibility