程序代写代做代考 assembly algorithm mips Java ER data structure python CSE220 Spring 2016 – Homework 4

CSE220 Spring 2016 – Homework 4

Due Friday 4/29/2016 @ 11:59pm

In this assignment, you will implement several recursive f unctions in MIPS. In each case, the

high-level source code is provided. You MUST implement all the f unctions in the assignment

using the def ined algorithms. Do not use other algorithms. You will need to use the stack

heavily in this assignment, so make sure you understand the basics of this data structure

bef ore progressing.

Don’t get wrapped up in WHY these f unctions and algorithms work. This is not a

requirement of this assignment, which is why pseudo/java code is g iven to you. Your

goal is to implement the algorithm correctly in MIPS assembly to produce the

correct results.

As always, you must f ollow MIPS register and calling conventions.

DO NOT submit a f ile with the f unctions main or _start def ined.

You may add helper f unctions and use macros to assist you in completing the

assignment.

You are strongly encouraged to start EARLY! Bugs in recursive f unctions can be

very dif f icult to identif y. You should use the MARS debugger and test parts of your

f unctions independently f or correct operation prior to continuing on.

The functions must be implemented recursively.

Any iterative implementations will receive a grade

of zero.

Getting Started

Download the hw4.zip template f rom Piazza.

There will be several java source f iles in addition to the asm f ile templates f or

this assignment.

All f unctionality f or your assignment should be in hw4.asm . This is the f ile which you

will submit f or grading.

At the top of hw4.asm in the comments put your name and id.

# Homework #4

# name: MY_NAME

# sbuid: MY_SBU_ID

Using files in MIPS Assembly as a reminder

Mars provides syscalls f or opening, reading, writing, and closing f iles. Details are shown

below.

syscall

name

syscall

number args return values

open 13 $a0 = f ilename

$a1 = f lags

$a2 = mode

$v0 = f ile descriptor

write 15 $a0 = f ile descriptor

$a1 = address of buf f er

$a2 = max size of

buf f er

$v0 = number of bytes

written

close 16 $a0 = f ile descriptor

Look here f or more inf ormation about the system calls listed.

Recap of File I/O:

In this assignment, you will be expected to work with f iles. Files in assembly and other lower

level systems languages work dif f erently than in a language like Java or Python. When you

ask the Mars runtime to open a f ile, the open system call (syscall 13) will return an integer.

This integer is known as a f ile descriptor. This integer is arbitrarily chosen by the OS/runtime

and is used to access the f ile on the f ile system. If the f ile does not exist or you do not have

permissions to open the f ile, then the return value of the system call will be a negative

http://courses.missouristate.edu/kenvollmar/mars/help/syscallhelp.html
http://en.wikipedia.org/wiki/File_descriptor

number. On most unix like systems, there are 3 special f ile streams known as STDIN ,

STDOUT , and STDERR which are associated with the f ile descriptors 0 , 1 , and 2 .

Typically, f or every process running on your machine, these f ile descriptors will correspond

to the mentioned I/O streams by def ault.

Once you obtain a valid f ile descriptor, the next thing you should do is either read or write to

the f ile descriptor. These system calls only work with bytes; the system calls have no

concept of ASCII characters, integers, strings, etc.

Af ter you are done using the f ile, you MUST close the f ile with the close system call

(syscall 16). This is incredibly important when using the write system call (syscall 15). The

write system call waits until it hits some threshold of data waiting to be written since I/O is

an expensive operation. When you call the close system call on the open f ile descriptor,

any data waiting to be written to the f ile will be written. If you don’t close the f ile, there is a

possibility that it may be empty or it will contain only some of the data that your program

wrote to it due to the system buf f ering the output. Another issue with not closing your f ile

descriptor is that you may be unable to reopen the same f ile again in your program because

it is technically still open.

Part 0 – Main program

You will need to modif y and def ine your own test cases in the main f unction in main.asm

to test the f unctions in Parts 1-5.

As you progress though each part, you should write test cases in your main f unction to

test the f unctions we implement in hw4.asm . You will be responsible f or calling the

f unctions with the appropriate arguments and testing them thoroughly. You should build

up or separate main programs as you complete Parts 1-4 .

As a reminder, you will NOT be handing in main.asm . You will only submit

hw4.asm .

Part 1 – itof

Inside your hw4.asm , you will see a f unction called itof . This f unction writes integers to

f iles as bytes. As mentioned bef ore, you cannot simply write integers to f iles in assembly

language. The buf f er that is being written is simply interpreted as bytes in MIPS. These

bytes are simply written to a f ile. Thus, in order f or the contents to be human readable we

need to convert the 32-bit representation of your integer to the ASCII representation of

that number.

This f unction will utilize the stack because it is the perf ect mechanism f or what we want to

accomplish. You should take a second to understand why we utilize the stack here.

Please note that itof is NOT a recursive f unction.

/**

* This function writes the ASCII representation of a number to a

file.

* @param integer_to_write Integer that will be written to the

file.

* @param file_descriptor File descriptor of the output file.

(Assume valid FD)

*/

public void itof(int integer_to_write, int file_descriptor);

The f unction will treat the integer_to_write argument as a 32-bit integer.

The value in $a0 is the integer to be written to the f ile as an ASCII string.

You should handle both positive and negative numbers.

Your f unction should assume that the f ile descriptor is valid, meaning that the

f ile is already open and writable (f or output). Your implementation of the f unction

should NOT close the f iles bef ore returning. Your main program MUST close the

f iles prior to exiting main.

This f unction will only write the number to the f ile. No extra spaces or any other

characters aside f rom the ASCII representation of the value should be written to the

f ile.

To get started, we have provided the pseudo code f or the itof f unction to translate into

MIPS:

# $a0 is integer to write to File

# $a1 is the file descriptor to write to (assumes valid FD)

itof:

# Initialize a counter for the number of digits in the number

# Number_of_digits = 0

# If number is negative:

# Set a flag in a register to indicate it is negative

# Make the negative number positive.

#

# do:

# Divide $a0 by 10.

# Save the contents of $a0 with the quotient

# Take the remainder from the division and normalize it to the

ascii character

# Make room on the stack for one BYTE and store the byte to the

address

# Increment the counter for number of digits

# Jump back to top of while loop

# while( $a0 > 0 )

#

# if negative flag is turned on:

# Make room on the stack for one byte and store the ‘-‘

character.

# Increment the number of digits counter.

# Initialize a counter to zero

#

# while counter < number of digits: # Perform system call to write syscall 15 # $a0 is the FD # $a1 is the address of the Buffer to write: stack pointer in our case # $a2 is number of bytes to write which is ONE # # Pop byte off stack. (ie: addi $sp, $sp, 1) # Increment counter # # Jump back to top of this while loop # # return to caller Examples: $a0 = 123 #<- li $a0, 123 file contents: "123" $a0 = -123 #<- li $a0, -123 file contents: "-123" Part 2 - Teddy Bears Now that we have f inished the itof f unction, let’s write our f irst recursive f unction. The object of the Teddy Bear Game is to end up with a number of bears equal to some value goal that we choose ahead of time. Your f riend gives you a number of stuf f ed bears, we will call initial . There are two other parameters: increment and n . During each step of the game you may: (a) ask f or and receive f rom your f riend increment more bears; or (b) if you have an even number of bears, g ive your f riend exactly half of your bears. You must have in your possession exactly goal bears af ter at most n steps in order to win. The Teddy bears algorithm works as f ollows : We add print statements to this code later on. You MUST implement the later version with printouts. /** * Teddy Bear Game recursive function. The function returns zero or one. * One indicating that the goal was achieved. Zero otherwise. * * @param initial Number of bears given by your friend * @param goal The desired number of bears * @param increment Number of bears to ask your friend for * @param n The number of steps left in the game * * @return int 1 if the goal is attainable. 0 otherwise. */ public static int bears(int initial, int goal, int increment, int n) { if (initial == goal) return 1; else if (n == 0) return 0; else if (bears(initial+increment, goal, increment, n-1) == 1) return 1; else if ((initial % 2 == 0) && (bears(initial/2, goal, increment, n-1) == 1)) return 1; else return 0; } In order to assist with debugging and to verif y your recursive implementation we will output the recursive calls and the return values to a f ile within your f unction. We have added a parameter fd to the above f unction call and very VERBOSELY added print statements to the code to illustrate how you should print inf ormation to the f ile. We will use this VERBOSE f ormat in all the remaining sections of the homework to assist you with the f ile output. The f ollowing code should be translated to MIPS assembly language. /** * Teddy Bear Game recursive function. The function returns zero or one. * One indicating that the goal was achieved. Zero otherwise. * * @param initial Number of bears given by your friend * @param goal The desired number of bears * @param increment Number of bears to ask your friend for * @param n The number of steps left in the game * @param fd File descriptor of opened file to write to * * @return int 1 if the goal is attainable. 0 otherwise. */ public static int bears(int initial, int goal, int increment, int n, int fd) { write(fd, "bears( ", 7); itof(initial, fd); write(fd, ", ", 2); itof(goal, fd); write(fd, ", ", 2); itof(increment, fd); write(fd, ", ", 2); itof(n); write(fd, " )\n", 3); if (initial == goal){ write(fd, "return: ", 8); itof(1, fd); write(fd, "\n", 1); return 1; } else if (n == 0){ write(fd, "return: ", 8); itof(0, fd); write(fd, "\n", 1); return 0; } else if (bears(initial+increment, goal, increment, n-1) == 1){ write(fd, "return: ", 8); itof(1, fd); write(fd, "\n", 1); return 1; } else if ((initial % 2 == 0) && (bears(initial/2, goal, increment, n-1) == 1)){ write(fd, "return: ", 8); itof(1, fd); write(fd, "\n", 1); return 1; } else{ write(fd, "return: ", 8); itof(1, fd); write(fd, "\n", 1); return 0; } } As bef ore, the f if th argument is passed on the stack to bears due to the f act that in MIPS assembly we only have f our argument registers. To f etch the f if th argument, you need to load it of f the stack into a register of your choice (ex: lw $t0, 0($sp) ). It is the caller f unction’s ( f unction that calls bears ) responsibility to push the f if th argument onto the stack. The caller will also be responsible f or restoring the stack af ter the f unction call. Your f unction should assume that the f ile descriptor is VALID, meaning that the f ile is already open and writable (f or output). Your implementation of the f unction should NOT close the f iles bef ore returning. Your main program MUST close the f iles prior to exiting main. The write f unction above is a f unction available in the C programming language. The f irst argument is the f ile descriptor. The second argument is the string to write to the f ile. The last argument is the number of bytes to write. You will implement this using the write system call in Mars. Make sure you write exactly what is stated above to the f ile. If you do not http://linux.die.net/man/2/write heed this warning, no exceptions will be made. Example 1: From a main program call bears( 99, 93, 53, 4 ). Sample f ile output: bears( 99, 93, 53, 4 ) bears( 152, 93, 53, 3 ) bears( 205, 93, 53, 2 ) bears( 258, 93, 53, 1 ) bears( 311, 93, 53, 0 ) return: 0 bears( 129, 93, 53, 0 ) return: 0 return: 0 return: 0 bears( 76, 93, 53, 2 ) bears( 129, 93, 53, 1 ) bears( 182, 93, 53, 0 ) return: 0 return: 0 bears( 38, 93, 53, 1 ) bears( 91, 93, 53, 0 ) return: 0 bears( 19, 93, 53, 0 ) return: 0 return: 0 return: 0 return: 0 return: 0 Example 2: From a main program call bears( 99, 129, 53, 4 ) Sample f ile output: bears( 99, 129, 53, 4 ) bears( 152, 129, 53, 3 ) bears( 205, 129, 53, 2 ) bears( 258, 129, 53, 1 ) bears( 311, 129, 53, 0 ) return: 0 bears( 129, 129, 53, 0 ) return: 1 return: 1 return: 1 return: 1 return: 1 Part 3 - Find Majority Integer An array of positive integers is said to have a dominant/majority element if more than half of the elements are the same. Given an integer array, you will implement a f unction that will determine if there is a dominant element. If there is a dominant element, return that element. Otherwise, return -1 if there isn’t a dominant element. The array will have all positive integers in it, and a -1 will indicate the end of the array. Do not include the -1 in the calculations of the length of the array. It is only a signif ier that you have reached the end of the array. All arrays will have a length of , at least, one (not including the -1). You must implement the two f unctions below. We have provided the pseudo code f or you. Again as with the f unctions above, you will be writing output to an open f ile. These f unctions will assume that the f ile has been opened correctly. The f irst f unction we will write is recursiveFindMajorityElement which recursively computes the number of occurrences of a candidate element. /** * This function returns the occurrences of candidate in the integer array. * * @param input_array Integer array * @param candidate Integer being searched for in the array * @param startIndex Start index of the array * @param endIndex End index of the array * @param fd File descriptor of opened file * * @return int the number of times candidate occurred in the array. */ public static int recursiveFindMajorityElement(int [] array, int candidate, int startIndex, int endIndex, int fd){ int array_length = (endIndex - startIndex) + 1; write(fd, "recursiveFindMajorityElement( ", 30); itof(startIndex, fd); write(fd, ", ", 2); itof(endIndex, fd); write(fd, ", ", 2); itof(array_length, fd); write(fd, " )\n", 3); if(array_length == 1){ if(candidate == array[startIndex]){ write(fd, "return: ", 8); itof(1, fd); write(fd, "\n", 1); return 1; } else{ write(fd, "return: ", 8); itof(0, fd); write(fd, "\n", 1); return 0; } } else{ int mid = array_length / 2; int LHS_sum = 0; int RHS_sum = 0; LHS_sum = recursiveFindMajorityElement(array, candidate, startIndex, (startIndex + mid -1)); RHS_sum = recursiveFindMajorityElement(array, candidate, (startIndex + mid), endIndex); write(fd, "return: ", 8); itof((LHS_sum + RHS_sum), fd); write(fd, "\n", 1); return (LHS_sum + RHS_sum); } } As bef ore, the f if th argument is passed on the stack due to the f act that in MIPS assembly we only have f our argument registers. To f etch the f if th argument, you need to load it of f the stack into a register of your choice (ex: lw $t0, 0($sp) ). It is the f unction caller’s ( f unction that calls recursiveFindMajorityElement ) responsibility to place and remove the f if th argument on/f rom the stack. You are given startIndex and endIndex to indicate the start and ending index of the array, as we are only looking at a portion of the array. You must index into the appropriate position f rom the starting address which is g iven in input_array . Use zero-based indexing. It is standard in CS. Make sure you understand how to index into an integer array, and see the contents of the integer array. Your f unction should assume that the f ile descriptor is valid, meaning that the f ile is already open and and writable (f or output). Your implementation of the f unction should NOT close the f iles bef ore returning. Your main program MUST close the f iles prior to exiting main. Again, the write f unction above is a f unction available in the C programming language. The f irst argument is the f ile descriptor. The second argument is the string to write to the f ile. The last argument is the number of bytes to write. You will implement this using the write system call in Mars. We need to iterate through all the possible candidates in the input_array . Thus, we will now write a f unction called iterateCandidates . This f unction will loop through each index in the integer array, making each element a candidate. If the sum is enough to be the majority, that element is returned. /** * This function iterates though the candidate elements and call the * recursiveFindMajorityElement function. If a majority is found it * returns the element. -1 if there isn't a majority element. * * @param input_array Array of positive integers. * @param fd File descriptor of opened file to write to. * * @return int The element that is the majority. -1 if no majority. */ public static int iterateCandidates(int [] input_array, int fd) { int end_index = 0; int start_index = 0; while(input_array[end_index] != -1){ end_index++; http://linux.die.net/man/2/write } for(int i = 0; i <= end_index; i++){ write(fd, "candidate: ", 11); itof(input_array[i], fd); write(fd, "\n", 1); int candidate_sum = recursiveFindMajorityElement(input_array, input_array[i], start_index, end_index, fd); if (candidate_sum >= ((end_index + 1)/ 2)){

write(fd, “majority element: “, 18);

itof(input_array[i], fd);

write(fd, “\n”, 1);

return input_array[i];

}

}

write(fd, “majority element: “, 18);

itof(-1, fd);

write(fd, “\n”, 1);

return -1;

}

Negative one indicates that the end of the array has been reached. Negative one

is not part of the length of the array.

You can assume all arrays have a length of , at least, one element.

Your f unction should assume that the f ile descriptor is valid, meaning that the

f ile is already open and and writable (f or output). Your implementation of the

f unction should NOT close the f iles bef ore returning. Your main program MUST

close the f iles prior to exiting main.

The write f unction above is a f unction available in the C programming language.

The f irst argument is the f ile descriptor. The second argument is the string to write

to the f ile. The last argument is the number of bytes to write. You will implement

this using the write system call in Mars.

Make sure you write exactly what is stated above to the f ile. If you do not

heed this warning, no exceptions will be made.

Example:

From main program initialize input_array = {1, 2, 2, 4 , 1, 4 , 4 , 4 };

Sample f ile output:

http://linux.die.net/man/2/write

candidate: 1

recursiveFindMajorityElement( 0, 7, 8 )

recursiveFindMajorityElement( 0, 3, 4 )

recursiveFindMajorityElement( 0, 1, 2 )

recursiveFindMajorityElement( 0, 0, 1 )

return: 1

recursiveFindMajorityElement( 1, 1, 1 )

return: 0

return: 1

recursiveFindMajorityElement( 2, 3, 2 )

recursiveFindMajorityElement( 2, 2, 1 )

return: 0

recursiveFindMajorityElement( 3, 3, 1 )

return: 0

return: 0

return: 1

recursiveFindMajorityElement( 4, 7, 4 )

recursiveFindMajorityElement( 4, 5, 2 )

recursiveFindMajorityElement( 4, 4, 1 )

return: 1

recursiveFindMajorityElement( 5, 5, 1 )

return: 0

return: 1

recursiveFindMajorityElement( 6, 7, 2 )

recursiveFindMajorityElement( 6, 6, 1 )

return: 0

recursiveFindMajorityElement( 7, 7, 1 )

return: 0

return: 0

return: 1

return: 2

candidate: 2

recursiveFindMajorityElement( 0, 7, 8 )

recursiveFindMajorityElement( 0, 3, 4 )

recursiveFindMajorityElement( 0, 1, 2 )

recursiveFindMajorityElement( 0, 0, 1 )

return: 0

recursiveFindMajorityElement( 1, 1, 1 )

return: 1

return: 1

recursiveFindMajorityElement( 2, 3, 2 )

recursiveFindMajorityElement( 2, 2, 1 )

return: 1

recursiveFindMajorityElement( 3, 3, 1 )

return: 0

return: 1

return: 2

recursiveFindMajorityElement( 4, 7, 4 )

recursiveFindMajorityElement( 4, 5, 2 )

recursiveFindMajorityElement( 4, 4, 1 )

return: 0

recursiveFindMajorityElement( 5, 5, 1 )

return: 0

return: 0

recursiveFindMajorityElement( 6, 7, 2 )

recursiveFindMajorityElement( 6, 6, 1 )

return: 0

recursiveFindMajorityElement( 7, 7, 1 )

return: 0

return: 0

return: 0

return: 2

candidate: 2

recursiveFindMajorityElement( 0, 7, 8 )

recursiveFindMajorityElement( 0, 3, 4 )

recursiveFindMajorityElement( 0, 1, 2 )

recursiveFindMajorityElement( 0, 0, 1 )

return: 0

recursiveFindMajorityElement( 1, 1, 1 )

return: 1

return: 1

recursiveFindMajorityElement( 2, 3, 2 )

recursiveFindMajorityElement( 2, 2, 1 )

return: 1

recursiveFindMajorityElement( 3, 3, 1 )

return: 0

return: 1

return: 2

recursiveFindMajorityElement( 4, 7, 4 )

recursiveFindMajorityElement( 4, 5, 2 )

recursiveFindMajorityElement( 4, 4, 1 )

return: 0

recursiveFindMajorityElement( 5, 5, 1 )

return: 0

return: 0

recursiveFindMajorityElement( 6, 7, 2 )

recursiveFindMajorityElement( 6, 6, 1 )

return: 0

recursiveFindMajorityElement( 7, 7, 1 )

return: 0

return: 0

return: 0

return: 2

candidate: 4

recursiveFindMajorityElement( 0, 7, 8 )

recursiveFindMajorityElement( 0, 3, 4 )

recursiveFindMajorityElement( 0, 1, 2 )

recursiveFindMajorityElement( 0, 0, 1 )

return: 0

recursiveFindMajorityElement( 1, 1, 1 )

return: 0

return: 0

recursiveFindMajorityElement( 2, 3, 2 )

recursiveFindMajorityElement( 2, 2, 1 )

return: 0

recursiveFindMajorityElement( 3, 3, 1 )

return: 1

return: 1

return: 1

recursiveFindMajorityElement( 4, 7, 4 )

recursiveFindMajorityElement( 4, 5, 2 )

recursiveFindMajorityElement( 4, 4, 1 )

return: 0

recursiveFindMajorityElement( 5, 5, 1 )

return: 1

return: 1

recursiveFindMajorityElement( 6, 7, 2 )

recursiveFindMajorityElement( 6, 6, 1 )

return: 1

recursiveFindMajorityElement( 7, 7, 1 )

return: 1

return: 2

return: 3

return: 4

majority element: 4

Part 4 – Find Lone Element

Given a sorted array of positive integers in which each number occurs twice except f or

possibly one number, f ind the unique number in the integer array.

Again, the end of the array is indicated by a negative one, which is not part of the array. Do

not count the -1 in the length of the array. You can assume the all integer arrays will have a

length of , at least, one.

/**

* This function finds the lone element in an integer array using

recursion.

*

* @param input_array Integer array

* @param startIndex Start index of the array

* @param endIndex End index of the array

* @param fd File descriptor of opened file

*

* return int Unique element in the array or -1 if no unique

element in array.

*/

public static int recursiveFindLoneElement(int [] input_array,

int startIndex, int endIndex, int fd){

write(fd, “recursiveFindLoneElement( “, 26);

itof(startIndex, fd);

write(fd, “, “, 2);

itof(endIndex, fd);

write(fd, ” )\n”, 3);

int array_length = ((endIndex – startIndex) + 1);

if(( array_length % 2 ) == 0){

int ret = -1;

write(fd, “return: “, 8);

itof(ret, fd);

write(“\n”, 1);

return ret;

}

else{

if(array_length == 1){

ret = input_array[startIndex];

write(fd, “return: “, 8);

itof(ret, fd);

write(“\n”, 1);

return ret;

}

else{

int mid = array_length / 2;

int target = input_array[mid + startIndex];

int left = input_array[mid+startIndex – 1];

int right = input_array[mid+startIndex + 1];

if (target != left && target != right){

write(fd, “return: “, 8);

itof(target, fd);

write(“\n”, 1);

return target;

}

else if (target == left && target != right){

int left_half_length = ((mid – 2) – startIndex) + 1;

if ( left_half_length % 2 == 0 ){

int child_start_index = (mid + 1);

int child_end_index = endIndex;

int ret = recursiveFindLoneElement(input_array,

child_start_index, child_end_index);

write(fd, “return: “, 8);

itof(ret, fd);

write(“\n”, 1);

return ret;

}

else{

int child_start_index = startIndex;

int child_end_index = ( mid – 2 );

int ret = recursiveFindLoneElement(input_array,

child_start_index, child_end_index);

write(fd, “return: “, 8);

itof(ret, fd);

write(“\n”, 1);

return ret;

}

}

else if (target != left && target == right){

int right_half_length = (endIndex – (mid + 2)) + 1;

if ( right_half_length % 2 == 0 ){

int child_start_index = startIndex;

int child_end_index = ( mid – 1 );

int ret = recursiveFindLoneElement(input_array,

child_start_index, child_end_index);

write(fd, “return: “, 8);

itof(ret, fd);

write(“\n”, 1);

return ret;

}

else{

int child_start_index = (mid + 2);

int child_end_index = endIndex;

int ret = recursiveFindLoneElement(input_array,

child_start_index, child_end_index);

write(fd, “return: “, 8);

itof(ret, fd);

write(“\n”, 1);

return ret;

}

}

}

}

}

-1 indicates that the end of the array has been reached. It is not part of the

length of the array.

You can assume all arrays will have a length of at least one and that they are

already sorted f or you.

You are given startIndex and endIndex to indicate the start and stop of the

array since we are only looking at a portion of the array each recursive call. You

must index into the appropriate position f rom the starting address which is g iven in

input_array . Use the CS standard zero-based indexing.

Your f unction should assume that the f ile descriptor is valid, meaning that the

f ile is already open and and writable (f or output). Your implementation of the

f unction should NOT close the f iles bef ore returning. Your main program MUST

close the f iles prior to exiting main.

The write f unction above is a f unction available in the C programming language.

The f irst argument is the f ile descriptor. The second argument is the string to write

to the f ile. The last argument is the number of bytes to write. You will implement

this using the write system call in Mars.

Make sure you write exactly what is stated above to the f ile. If you do not

heed this warning, no exceptions will be made.

Example 1:

Initialize main program input_array = {1,1,2,3,3,5,5,8,8,13,13};

Call recursiveFindLoneElement( 0, 10 )

Sample f ile output:

recursiveFindLoneElement( 0, 10 )

recursiveFindLoneElement( 0, 4 )

return: 2

http://linux.die.net/man/2/write

return: 2

Example 2:

Initialize main program input_array = {1,1,3,3,5,5,8,8};

Call recursiveFindLoneElement( 0, 7 )

Sample f ile output:

recursiveFindLoneElement( 0, 7 )

return: -1

Hand-in instructions

See Sparky Submission Instructions on piazza f or hand-in instructions.

When writing your program, try to comment as much as possible. Try to stay

consistent with your f ormatting. It is much easier f or your TA and the prof essor to

help you if we can f igure out what your code does quickly. If your program doesn’t

work correctly the grader may be able to give you partial points, assuming he can

read the code that you have written.

Only submission via sparky will be accepted. T here is no tolerance f or

emailed homework submissions. If you are still stuck on submitting your

homework, please stop by and see one of us.

https://piazza.com/class/hyirt2jcnph6vk?cid=22