For this assignment you will be implementing a hash table data structure for storing different types of structs. The context of the assignment is a simulated book store that will track its books for sale and the actual sales themselves through two different hash tables. Towards the end of the assignment we will also explore a (sorta related) interesting computational problem we will solve using a simple, non-recursive brute-force algorithm. Perhaps in your Algorithms course you will study it (or a similar problem) using a more efficient, recursive algorithm.
Data Structures
The assignment relies on three data structures given as structs:
struct Book { string isbn; // 13-character, null-terminated string [14 bytes] string title; // 25-byte buffer to store the null-terminated title string author; // 25-byte buffer to store the null-terminated author int times_sold; // 4-byte integer the stores # of sales of this book
}
Note that a Book struct requires 14 + 25 + 25 + 4 = 68 bytes. We will assume that the entire struct is word-aligned, which guarantees that times_sold will also be word-aligned. In this assignment we will also assume that a string containing an ISBN consists only of the digit characters (no dashes, spaces, Xs, etc.)
struct BookSale { string isbn; // 13-character, null-terminated string [14 bytes] byte[2] padding; // 2 bytes of zeros int customer_id; // 4-byte customer ID# int sale_date; // date of sale as # of days since 1/1/1600 [4 bytes] int sale_price; // 4 bytes
}
Note that a BookSale struct requires 14 + 2 + 4 + 4 + 4 = 28 bytes. The date of the sale is encoded as a 4-byte integer that provides the number of days that have passed since January 1, 1600. For example, January 5, 1600 would be represented by the number 4. January 1, 1600 itself would be represented by the number 0. November 8, 2020 would be represented by the number 153,714. You will write functions to convert a date-string in the form YYYY-MM-DD (e.g., 2020-11-08) to this numerical encoding. The inspiration for this time format is the UNIX timestam p system.
Instances of the above structs will be stored in two separate hash table data structures, as defined below. The hash table itself will be word-aligned.
struct Hashtable { int capacity; // maximum # of elements in hashtable [4 bytes] int size; // # of elements in hashtable [4 bytes] int element_size; // size of one element in the hashtable [4 bytes] object[] elements; // objects stored in the hashtable
// consumes (capacity*element_size) bytes
}
A hash table in this assignment consists of an array of structs, not an array of pointers to structs. Note how this differs from Java, wherein what we call an array of objects is really an array of references to objects. In C and MIPS it is possible to create an array of pointers to objects, and we will explore that option in the last function of the assignment. But for the functions in the current assignment, we will store the structs directly in the arrays themselves, the reason being that one of the purposes of this assignment is to deal with arrays of varying element sizes.
In the elements array, an empty entry, i.e., an entry in the array that has never stored a struct, is filled entirely with zeros. A deleted (sometimes called available) entry is one that once stored an object that has since been deleted (removed) from the hash table. A deleted element is represented by
(capacity*element_size), one-byte, twos complement representations of -1 (i.e., 0xFF). That is, the entire entry in the array consists of one-byte -1s. Due to a quirk of how we will be using the hash table for this assignment, it will be sufficient to load the first byte of an entry in the elements array and check if that byte equals 0xFF. If so, that entry can be assumed to be deleted. Similarly, to check if an entry in elements is empty, it will be sufficient to load the first byte and check if it equals zero. Every 13-character ISBN must start with 9, so the first character of a non-empty, non-deleted object in elements cannot be 0. In sum, the first byte of a Book struct or a BookSale struct must be the number 0, the number -1, or the ASCII code for the character 9.
Part 1: Copy a Memory Buffer
int memcpy(byte[] dest, byte[] src, int n)
The memcpy function copies n bytes of data from address src to address dest. You may assume that the dest buffer is at least n bytes in size. This function will be used in later functions to copy structs from one place in memory to another. Therefore, you should code for generality and not be concerned about the significance of the bytes that the function copies. For this reason, your code should use lbu to read the bytes from memory.
The function takes the following arguments, in this order:
- dest: the address to copy bytes to
- src: the address to copy bytes from
- n: the number of bytes to copy (must be greater than 0)
Note that src and dest are not necessarily word-aligned.
Returns in $v0:
- n if n > 0, or
- -1 if n 0
Additional requirements:
- The function may only change the contents of the dest buffer and no other parts of main memory.
- Only the first n bytes memory starting at dest may be changed. All other bytes in dest must be left unchanged.
Examples:
| Function Arguments | Return Value | Updated dest |
| XXXXXXX, ABCDEFGHIJ, 3 | 3 | ABCXXXX |
| XXXXXXX, ABCDEFGHIJ, 7 | 7 | ABCDEFG |
| XXXXXXX, ABCDEFGHIJ, -3 | -1 | XXXXXXX |
| XXXXXXX, ABCDEFGHIJ, 0 | -1 | XXXXXXX |
Part 2: Compare Two Strings
int strcmp(string str1, string str2)
The strcmp function takes two null-terminated strings (either or both of which could be empty) and returns an integer that indicates the lexicographic order of the strings. The function begins by comparing the first character of each string. If they are equal to each other, it continues with the following pairs until the characters differ or until a terminating null-character is reached. Note that the strings can be of different lengths.
The function takes the following arguments, in this order:
- str1: the starting address of the first string
- str2: the starting address of the second string
Returns in $v0:
- the difference between the ASCII values of the first mismatch, if any: str1[n] str2[n], where n is the index of the first mismatch; or
- 0 if the contents of both strings are identical (including the case where they are both empty strings); or
- length of str1 if str2 is an empty string but str1 is non-empty; or
- negated length of str2 if str1 is an empty string but str2 is non-empty
Additional requirements:
- The function must not write any changes to main memory.
Examples:
| Function Arguments | Return Value |
| ABCD, ABCGG | -3 |
| WHOOP!, WHOA | 14 |
| Intel, pentium | -39 |
| STONY, BROOK | 17 |
| , mouse | -5 |
| lonely guy, | 10 |
| Wolfie, Wolfie | 0 |
| , | 0 |
| happy, Z | 14 |
| WOLF, WOLFIE | -73 |
| StonyBrook, Stony | 66 |
Part 3: Initialize a Hash Table
int initialize_hashtable(Hashtable* hashtable, int capacity, int element_size)
The initialize_hashtable function takes a pointer to (i.e., address of) an uninitialized Hashtable struct and performs the following steps:
- sets the structs capacity field to the capacity argument
- sets the structs size field to 0
- sets the struct element_size field to the element_size argument
- fills the entirety of the structs elements field to 0 (i.e., all capacity * element_size bytes)
Assume that the uninitialized block of memory referenced by hashtable is large enough to store a hash table of the required size in bytes.
The function takes the following arguments, in this order:
- hashtable: a pointer to an uninitialized block of memory
- capacity: the number of elements in the hash tables elements array
- element_size: the size of a single struct stored in one element of the hash tables elements
Returns in $v0:
- -1 if capacity is less than 1 or element_size is less than 1; or 0 otherwise
Additional requirements:
- The function may only change the contents of the hashtable buffer and no other parts of memory.
Example #1: initializing a hash table to store Book structs.
hashtable = pointer to buffer of 352 (12+5*68) uninitialized bytes of memory capacity = 5 element_size = 68
Return value in $v0: 0
Resulting contents of hashtable :
5 0 68 (capacity, size, element_size)
elements[] array contents in hexadecimal, truncated:
0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
1: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
2: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
3: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
4: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Example #2: initializing a hash table to store BookSale structs.
hashtable = pointer to buffer of 320 (12+11*28) uninitialized bytes of memory capacity = 11 element_size = 28
Return value in $v0: 0
Resulting contents of hashtable :
11 0 28 (capacity, size, element_size)
elements[] array contents in hexadecimal, truncated:
0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
1: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
2: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
3: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 4: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
.
. .
10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Example #3: failed attempt to initialize a hash table to store BookSale structs. hashtable = pointer to buffer of some unknown number of uninitialized bytes of memory capacity = -3 element_size = 28
Return value in $v0: -1
Contents of hashtable are the same as before the function call.
Part 4: Compute the Hash Code for an ISBN in a Given Hash Table
int hash_book(Hashtable* books, string isbn)
The hash_book function takes a pointer to a valid Hashtable struct named books and an ISBN-13 value called isbn for which we want to compute the hash function. The hash function itself is very simple: sum the ASCII codes of the 13 characters in isbn and take the modulus of dividing that sum by the capacity of the books hash table (e.g., sum of the ASCII codes mod the capacity).
The function takes the following arguments, in this order:
- books: the starting address of a valid Hashtable struct
- isbn: a 13-character, null-terminated string that represents a valid ISBN
Returns in $v0:
- The value of the hash function when evaluated for the provided ISBN.
Additional requirements:
- The function may not write any changes to main memory.
Example #1:
hashtable = pointer to a valid hash table with capacity = 9 isbn = 9780671028370
Return value in $v0: 7
Example #2:
hashtable = pointer to a valid hash table with capacity = 17 isbn = 9780071401940
Return value in $v0: 11
Example #3:
hashtable = pointer to a valid hash table with capacity = 13
isbn = 1123121401940
Return value in $v0: 3
Part 5: Retrieve a Book from a Hashtable of Book Structs
int, int get_book(Hashtable* books, string isbn) -> (int, int)
The get_book function attempts to find a struct inside books with the given ISBN and returns the index of that struct, as well as the number of entries in books.elements that needed to be inspected to find that struct by way of linear probing. If an empty entry is encountered during probing, this means that no book of the given ISBN is in the hash table. If a deleted entry is encountered during probing, the linear probing must continue. If no struct has the given ISBN, the function returns -1 in $v0 and the number of inspected entries of elements in $v1.
The function takes the following arguments, in this order:
- books: the starting address of a valid Hashtable struct
- isbn: a 13-character null-terminated string that represents a valid ISBN
Returns in $v0:
- The index in elements where the book was found; or
- -1 if the hash table does not contain a book with the given ISBN
Returns in $v1:
- The number of entries in the elements array that were accessed before a book of the given
ISBN was found or was determined not to be in the elements array.
Additional requirements:
- The function may not write any changes to main memory.
- The function must call hash_book and strcmp .
The examples in this document are not comprehensive nor cover all possible classes of inputs!
Example #1: Attempt to get a book from an empty hash table
isbn = 9780553214830
Contents of books hash table:
9 0 68 (capacity, size, element_size)
0: empty
1: empty
2: empty
3: empty
4: empty
5: empty
6: empty
7: empty
8: empty
Return value in $v0: -1
Return value in $v1: 1
Example #2: Get a book that is present in the hash table at the expected index
isbn = 9780440060670
Contents of books hash table:
7 5 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: 9780670032080 Financial Peace Revisite Dave
Ramsey 0
3: 9780440060670 The Other Side of Midnig Sidney Sheldon 0
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: deleted
6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Return value in $v0: 3
Return value in $v1: 1
Example #3: Attempt to get a book that is not present in the hash table; expected location is empty
isbn = 9780007201780
Contents of books hash table:
7 5 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: 9780670032080 Financial Peace Revisite Dave
Ramsey 0 3: 9780440060670 The Other Side of Midnig Sidney
Sheldon 0
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: deleted
6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Return value in $v0: -1
Return value in $v1: 1
Example #4: Get a book that is not present in the hash table; expected location is deleted (hash table not full); probing required
isbn = 9780060182980
Contents of books hash table:
7 5 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: 9780670032080 Financial Peace Revisite Dave
Ramsey 0 3: 9780440060670 The Other Side of Midnig Sidney
Sheldon 0
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: deleted
6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Return value in $v0: -1
Return value in $v1: 6
Example #5: Get a book that is present in a full hash table
isbn = 9780064408330
Contents of books hash table:
7 7 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: 9780345419580 Moreta: Dragonlady of Pe Anne
McCaffrey 0
2: 9780670032080 Financial Peace Revisite Dave
Ramsey 0 3: 9780440060670 The Other Side of Midnig Sidney
Sheldon 0
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: 9780140168130 Big Sur Jack Kerouac, Aram Saroy 0
6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Return value in $v0: 4
Return value in $v1: 1
Example #6: Get a book that is present in the hash table at a probed index; one or more deleted slots encountered during probing
isbn = 9780140168130
Contents of books hash table:
7 5 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: 9780345419580 Moreta: Dragonlady of Pe Anne
McCaffrey 0
2: deleted
3: 9780440060670 The Other Side of Midnig Sidney
Sheldon 0
4: deleted
5: 9780140168130 Big Sur Jack Kerouac, Aram Saroy 0
6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Return value in $v0: 5
Return value in $v1: 6
Example #7: Attempt to get a book that is not present in the hash table; hash table is full
isbn = 9780316905750
Contents of books hash table:
7 7 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: 9780345419580 Moreta: Dragonlady of Pe Anne
McCaffrey 0
2: 9781516865870 Beacon 23: The Complete Hugh
Howey 0
3: 9780440060670 The Other Side of Midnig Sidney
Sheldon 0
4: 9781573451990 Rumors of War (Children Dean
Hughes 0
5: 9780140168130 Big Sur Jack Kerouac,
Aram Saroy 0
6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Return value in $v0: -1
Return value in $v1: 7
Part 6: Insert a Book Struct into a Hashtable of Books
int, int add_book(Hashtable* books, string isbn, string title, string author)
The add_book function attempts to insert a new Book struct into a given hash table by initializing the contents of the struct with the provided ISBN, title and author. It also sets the times_sold field of the struct to 0. It begins by checking if the hash table is full. If so, the function returns (-1, -1) and makes no changes to the hash tables contents. Next, it checks if a book of the given ISBN is already in the hash table. If so, the function returns the return values of get_book(books, isbn) as its own return values. Otherwise, the function attempts to insert the struct at books.elements[hash_book(isbn)]. Failing that, it performs linear probing to find the next empty or deleted entry in the elements array and inserts the struct at that location. If needed, probing wraps-around from the last entry in elements to the first. The function returns in $v0 the index where the struct was inserted. It returns in $v1 the number of entries in elements it had to read before finding an empty or deleted entry. For example, if it must skip over 3 occupied slots before finding an empty one, $v1 would be 4 in that case. If a book is successfully added to the hash table, books.size is incremented by 1.
Note that at most 24 characters of a books title or author can be stored in a Book struct. Therefore, any characters in title or author beyond the 24th character are dropped. The function must then write a null-terminator for the truncated string.
When writing the title and author string arguments into the Book struct, if the string is shorter than 24 characters in length, the function pads out the remainder of the 25 bytes of the title or author field by appending null-terminators. For instance, if title were MIPS Rocks, which is only 10 characters in length, the function would write the following as the title field in the new Book struct:
MIPS Rocks
The function takes the following arguments, in this order:
- books: the starting address of a valid Hashtable of Book structs
- isbn: a 13-character null-terminated string that represents a valid ISBN
- title: a non-empty, null-terminated string that represents a books title
- author: a non-empty, null-terminated string that represents a books author
Returns in $v0:
- The index in elements where the new book was added (or found, if the book was already in the hash table); or
- -1 if the hash table was full before the function call.
Returns in $v1:
- The number of entries in the elements array that were accessed before the book was added to the hash table; or
- -1 if the hash table was full before the function call.
Additional requirements:
- The function may only change the contents of the books hash table and no other parts of memory.
- The function must call get_book, hash_book and memcpy.
Example #1: Add a book to an empty hash table.
isbn = 9780553214830 title = The Declaration of Independence author = Founding Fathers
Return value in $v0: 4
Return value in $v1: 1
Resulting books contents:
9 1 68 (capacity, size, element_size)
0: empty
1: empty
2: empty
3: empty
4: 9780553214830 The Declaration of Indep Founding
Fathers 0
5: empty
6: empty
7: empty
8: empty
(Note: null-terminators are appended as needed to pad the title and author fields to 25 bytes each.
The final 4-byte word in each struct is the times_sold field, which is 0 in this case.)
Example #2: Add a book to a hash table with existing values; no collisions
isbn = 9781620610090 title = Opal (Lux, #3) author = Jennifer L. Armentrout books contents before function call:
9 4 68 (capacity, size, element_size)
0: empty
1: 9780446695660 Double Whammy Carl
Hiaasen 0
2: empty
3: empty
4: 9780553214830 The Declaration of Indep Founding
Fathers 14 5: 9788433914260 Hollywood Charles
Bukowski 0
6: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
7: empty
8: empty
Return value in $v0: 7
Return value in $v1: 1
Resulting books contents:
9 5 68 (capacity, size, element_size)
0: empty
1: 9780446695660 Double Whammy Carl
Hiaasen 0
2: empty
3: empty
4: 9780553214830 The Declaration of Indep Founding
Fathers 14
5: 9788433914260 Hollywood Charles
Bukowski 0
6: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
7: 9781620610090 Opal (Lux, #3) Jennifer L.
Armentrout 0
8: empty
Note that the Declaration of Independence was sold 14 times.
Example #3: Add a book to a hash table with existing values; collision with one probe required
isbn = 9781416971700 title = Out of My Mind author = Sharon M. Draper books contents before function call:
7 3 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: empty
3: empty
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: empty
Return value in $v0: 6
Return value in $v1: 2
Resulting books contents:
7 4 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: empty
3: empty
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Example #4: Add a book to a hash table with existing values; collisions with multiple probes required
isbn = 9781455525930 title = Crimson Shore (Pendergast, #15) author = Douglas Preston, Lincoln Child
books contents before function call:
11 7 68 (capacity, size, element_size)
0: empty
1: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 251 2: 9781416971700 Out of My Mind Sharon M.
Draper 0
3: 9780156948780 The Waste Land and Other T.S.
Eliot 0
4: 9780670032080 Financial Peace Revisite Dave
Ramsey 422
5: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 1251
6: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 734
7: empty
8: empty
9: empty
10: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0
Return value in $v0: 7
Return value in $v1: 3
Resulting books contents:
11 8 68 (capacity, size, element_size)
0: empty
1: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 251 2: 9781416971700 Out of My Mind Sharon M.
Draper 0 3: 9780156948780 The Waste Land and Other T.S.
Eliot 0
4: 9780670032080 Financial Peace Revisite Dave
Ramsey 422
5: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 1251
6: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 734
7: 9781455525930 Crimson Shore (Pendergas Douglas Preston, Lincoln 0
8: empty
9: empty
10: 97800608550 Equal Rites (Discworld, Terry
Pratchett 0
Note how the title and author were truncated when stored in the hash table.
Example #5: Add a book to a hash table with existing values; collisions with multiple probes required
isbn = 9780451230230 title = The Pacific author = Hugh Ambrose
books contents before function call:
7 4 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 7777 1: 0
2: -1
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 222 4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 333
5: -1
6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Return value in $v0: 5
Return value in $v1: 3
Resulting books contents:
7 5 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 7777
1: 0
2: -1
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 222 4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 333
5: 9780451230230 The Pacific Hugh
Ambrose 0
6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Part 7: Delete a Book Struct from a Hash Table of Books
int delete_book(Hashtable* books, string isbn)
The delete_book function attempts to delete the Book struct from the hash table with the given ISBN. If the book exists, then its entire struct is filled with the value -1 (8-bit, twos complement format) and the function returns the index in books.elements where the book was found. If a book is successfully deleted from the hash table, books.size is decremented by 1. If the book is not found, the function returns -1 and makes no changes to the contents of books .
The function takes the following arguments, in this order:
- books: the starting address of a valid Hashtable struct
- isbn: a 13-character null-terminated string that represents a valid ISBN
Returns in $v0:
- The index where the deleted book had been located; or
- -1 if no book with the given ISBN was found in the hash table
Additional requirements:
- The function may only change the contents of the books hash table and no other parts of
- The function must call get_book .
Example #1: Attempt to delete a book from an empty hash table
isbn = 9780553214830
books contents before function call:
7 0 68 (capacity, size, element_size)
0: empty
1: empty
2: empty
3: empty
4: empty
5: empty
6: empty
Return value in $v0: -1
Resulting books contents:
7 0 68 (capacity, size, element_size)
0: empty
1: empty
2: empty
3: empty
4: empty
5: empty
6: empty
Example #2: Delete a book that is present in the hash table at the expected index
isbn = 9780060855900
books contents before function call:
7 5 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0 3: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: empty
Return value in $v0: 2
Resulting books contents:
7 4 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: deleted
3: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: empty
Example #3: Attempt to delete a book that is not present in the hash table; expected location is empty
isbn = 9781439164630
books contents before function call:
7 5 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0 3: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: empty
Return value in $v0: -1
Resulting books contents:
7 5 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0 3: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: empty
Example #4: Delete a book that is not present in the hash table; expected location is deleted
isbn = 9780064410150
books contents before function call:
7 3 68 (capacity, size, element_size)
0: empty
1: deleted
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0 3: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
4: deleted
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: empty
Return value in $v0: -1
Resulting books contents:
7 3 68 (capacity, size, element_size)
0: empty
1: deleted
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0 3: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
4: deleted
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: empty
Example #5: Attempt to delete a book not present in the hash table; hash table is full
isbn = 9780802122550
books contents before function call:
7 7 68 (capacity, size, element_size)
0: 9780553214830 The Declaration of Indep Founding
Fathers 0
1: 9780446695660 Double Whammy Carl
Hiaasen 0
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0 3: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
4: 9788433914260 Hollywood Charles
Bukowski 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: 9781620610090 Opal (Lux, #3) Jennifer L.
Armentrout 0
Return value in $v0: -1
Resulting books contents:
7 7 68 (capacity, size, element_size)
0: 9780553214830 The Declaration of Indep Founding
Fathers 0
1: 9780446695660 Double Whammy Carl
Hiaasen 0
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0 3: 9780345527780 Wicked Business (Lizzy & Janet
Evanovich 0
4: 9788433914260 Hollywood Charles
Bukowski 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0
6: 9781620610090 Opal (Lux, #3) Jennifer L.
Armentrout 0
Part 8: Compute the Hash Code for an (ISBN, Customer ID #) Pair in a Given Hash Table
int hash_booksale(Hashtable* sales, string isbn, int customer_id)
The hash_booksale function takes a pointer to a valid Hashtable struct named sales , and an ISBN-13 value called isbn and customer ID # called customer_id for which we want to compute the hash function. The hash function itself is very simple: sum the ASCII codes of the 13 characters in isbn and the digits of customer_id , and then take the modulus of dividing the grand total by the capacity of the sales hash table (e.g., sum of all the ASCII codes from isbn and the digits from customer_id mod the capacity).
The function takes the following arguments, in this order:
- books: the starting address of a valid Hashtable of Book structs
- isbn: a 13-character, null-terminated string that represents a valid ISBN customer_id: an integer providing the customer ID#
Returns in $v0:
- The value of the hash function when evaluated for the provided ISBN and customer ID#.
Additional requirements:
- The function may not write any changes to main memory.
Example #1:
hashtable = pointer to a valid hash table with capacity = 11
isbn = 9780671028370 customer_id = 829273
Return value in $v0: 9
Example #2:
hashtable = pointer to a valid hash table with capacity = 13
isbn = 9780071401940 customer_id = 93730282
Return value in $v0: 6
Example #3:
hashtable = pointer to a valid hash table with capacity = 19
isbn = 9712312301940 customer_id = 512312
Return value in $v0: 15
Part 9: Determine if a Year is a Leap Year
int is_leap_year(int year)
The is_leap_year function does what it sounds like it determines if a given year is a leap year. A year is a leap year if it is after 1582 and it is divisible by 4, except centenary years not divisible by 400 (1700, 1800, 1900, 2100, etc.) Feel free to adapt the sample code given in the lecture slides and course materials that implements the logic needed for this function
The function takes one argument:
- year: an integer representinga year
Returns in $v0:
- 0 if year is < 1582; or
- 1 if year is a leap year; or
- the number of years negated until the next leap year if year is not a leap year
Additional requirements:
- The function may not make any changes to main memory.
| Function Argument | Return Value |
| 1244 | 0 |
| 1900 | -4 |
| 2000 | 1 |
| 5602 | -2 |
| 2997 | -7 |
| 3997 | -3 |
Part 10: Convert a String Representation of a Time Interval to an Integer Number of Days
int datestring_to_num_days(string start_date, string end_date)
The datestring_to_num_days function takes two dates given as strings, in the format YYYY-MM-DD, and returns the number of days that elapse from start_date to end_date. For example, if start_date = 2020-10-01 and end_date = 2020-10-10, the return value will be 9. Note that start_date itself is not included in the number of days elapsed. The function must account for leap years by calling the is_leap_year function. You may assume that both arguments are valid.
The function takes the following arguments, in this order:
- start_date: a date given in the format YYYY-MM-DD that is 1600-01-01 or later
- end_date: a date given in the format YYYY-MM-DD that is 1600-01-01 or later
Returns in $v0:
- The number of days elapsed between start_date and end_date, including end_date, but excluding start_date; or
- -1 if end_date is before start_date
Additional requirements:
- The function may not write any changes to main memory.
- The function must call is_leap_year. Not required because at least one student is using the Julian calendar to calculate this!
| Function Arguments | Return Value |
| 2020-10-12, 2020-10-25 | 13 |
| 2020-10-25, 2020-10-12 | -1 |
| 2019-10-25, 2020-10-25 | 366 |
| 1692-11-28, 2602-09-13 | 332293 |
| 2019-01-08, 8410-09-08 | 2334508 |
| 3156-05-08, 3156-05-08 | 0 |
Part 11: Record the Sale a Book
int, int sell_book(Hashtable* sales, Hashtable* books, string isbn, int customer_id, string sale_date, int sale_price)
The sell_book function records the sale of a book by adding an entry into the hash table sales of BookSale objects and updating the times_sold count of the sold book. We will make the following assumptions for this function:
- Deletions from the sales hash table never take place. Therefore, every entry in elements is either all zeros (indicating an empty entry) or a valid BookSale struct.
- No customer ever buys the same book twice.
- The store has an infinite number of copies of every book.
Note that sell_book is similar in spirit to the add_book function from earlier in the assignment. The sell_book function attempts to insert a new BookSale struct into a given sales hash table by initializing the contents of the struct with the provided ISBN, customer ID# and sale price. The value stored in the struct for sale_date is provided by the return value of datestring_to_num_days(1600-01-01, sale_date). sell_book begins by checking if the sales hash table is full. If so, the function returns (-1, -1) and makes no changes to the hash tables contents. It also checks if a book with the given ISBN exists in the books hash table. If not, the function returns (-2, -2). Otherwise, the function attempts to insert the struct at
sales.elements[hash_booksale(sales, isbn, customer_id)]. Failing that, it performs
linear probing to find the next empty entry in the sales.elements array and inserts the struct at that location. If needed, probing wraps-around from the last entry in elements to the first. The value of the times_sold field of the corresponding book in the books hash table must be incremented by 1. The function returns in $v0 the index where the struct was inserted. It returns in $v1 the number of entries in elements it had to read before finding an empty entry. For example, if it must skip over 3 occupied slots before finding an empty one, $v1 would be 4 in that case. If a sale is successfully added to the hash table, sales.size is incremented by 1.
The function takes the following arguments, in this order:
- sales: the starting address of a valid Hashtable of BookSale structs
- books: the starting address of a valid Hashtable of Book structs
- isbn: a 13-character, null-terminated string that represents a valid ISBN
- customer_id: an integer that represents a customers ID#
- sale_date: a 10-character, null-terminated string that represents a valid date on or after January 1, 1600. Available at 0($sp). Assume the date string is value and represents a date on or after January 1, 1600.
- sale_price: an integer that represents the price paid for the book. Available at 4($sp).
Returns in $v0:
- The index in elements where the new BookSale struct was added to the sales hash table; or
- -1 if the hash table was full before the function call or
- -2 if no book of the given ISBN exists in the books hash table.
Returns in $v1:
- The number of entries in the elements array that were accessed before the BookSale struct was added to the sales hash table; or
- -1 if the hash table was full before the function call; or
- -2 if no book of the given ISBN exists in the books hash table.
Additional requirements:
- The function may only change the contents of the books and sales hash tables and no other parts of memory.
- The function must call get_book , datestring_to_num_days, hash_booksale , and memcpy.
Example #1: sales hash table is empty
isbn = 9780670032080 customer_id = 12345 sale_date = 2020-09-14 sale_price = 50
Contents of sales hash table:
9 0 28 (capacity, size, element_size)
0: empty
1: empty
2: empty
3: empty
4: empty
5: empty
6: empty
7: empty
8: empty
Contents of books hash table:
7 6 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 0 4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin Hannah 0 6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Return value in $v0: 5
Return value in $v1: 1
Resulting sales contents:
9 1 28 (capacity, size, element_size)
0: empty
1: empty
2: empty
3: empty
4: empty
5: 9780670032080 0 0 12345 153659 50
6: empty
7: empty
8: empty
Resulting books contents:
7 6 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 0
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 0
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 1 4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 0
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 0 6: 9781416971700 Out of My Mind Sharon M.
Draper 0
Example #2: sales hash table contains some entries; a few steps of linear probing required to insert the BookSale struct
isbn = 9780670032080 customer_id = 6123 sale_date = 2019-11-04 sale_price = 1032
Contents of sales hash table:
9 4 28 (capacity, size, element_size)
0: empty
1: 9781416971700 0 0 2323432 155136 22
2: 9780060855900 0 0 920192 158715 61
3: 9780345501330 0 0 81321 151369 192
4: empty
5: 9780312577220 0 0 2424 152013 125
6: empty
7: empty
8: empty
Contents of books hash table:
7 6 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 1
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 103
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 61 4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 44
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 812 6: 9781416971700 Out of My Mind Sharon M.
Draper 1
Return value in $v0: 4
Return value in $v1: 3
Resulting sales contents:
9 5 28 (capacity, size, element_size)
0: empty
1: 9781416971700 0 0 2323432 155033 22
2: 9780060855900 0 0 920192 158610 61
3: 9780345501330 0 0 81321 151269 192
4: 9780670032080 0 0 6123 153344 1032
5: 9780312577220 0 0 2424 151912 125
6: empty
7: empty
8: empty
Resulting books contents:
7 6 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 1
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 103
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 62 4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 44
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 812
6: 9781416971700 Out of My Mind Sharon M.
Draper 1
Example #3: provided ISBN does not exist in the books hash table
isbn = 9780679744400 customer_id = 5123 sale_date = 2029-11-04 sale_price = 987
Contents of sales hash table:
9 4 28 (capacity, size, element_size)
0: empty
1: 9781416971700 0 0 2323432 155136 22
2: 9780060855900 0 0 920192 158715 61
3: 9780345501330 0 0 81321 151369 192
4: empty
5: 9780312577220 0 0 2424 152013 125
6: empty
7: empty
8: empty
Contents of books hash table:
7 6 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 1
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 103
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 61 4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 44
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 812 6: 9781416971700 Out of My Mind Sharon M.
Draper 1
Return value in $v0: -2
Return value in $v1: -2
Resulting sales contents:
Resulting sales contents:
9 4 28 (capacity, size, element_size)
0: empty
1: 9781416971700 0 0 2323432 155033 22
2: 9780060855900 0 0 920192 158610 61
3: 9780345501330 0 0 81321 151269 192
4: empty
5: 9780312577220 0 0 2424 151912 125
6: empty
7: empty
8: empty
Resulting books contents:
7 6 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 1
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 103
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 61 4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 44
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 812 6: 9781416971700 Out of My Mind Sharon M.
Draper 1
Example #4: the sales hash table is full
isbn = 9781416971700 customer_id = 1523 sale_date = 2022-10-14 sale_price = 323
Contents of sales hash table:
9 9 28 (capacity, size, element_size)
0: 9780345501330 0 0 723341 155332 55
1: 9781416971700 0 0 2323432 155136 22
2: 9780060855900 0 0 920192 158715 61
3: 9780345501330 0 0 81321 151369 192
4: 9780312577220 0 0 777233 155332 55
5: 9780312577220 0 0 2424 152013 125
6: 9780345501330 0 0 26234 155332 55
7: 9780312577220 0 0 12312 155332 55
8: 9780064408330 0 0 73123 155332 55
Contents of books hash table:
7 6 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 3
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 103
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 61
4: 9780064408330 Joey Pigza Swallowed the Jack Gantos 45
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 814 6: 9781416971700 Out of My Mind Sharon M.
Draper 1
Return value in $v0: -1
Return value in $v1: -1
Resulting sales contents:
9 9 28 (capacity, size, element_size)
0: 9780345501330 0 0 723341 155229 55
1: 9781416971700 0 0 2323432 155033 22
2: 9780060855900 0 0 920192 158610 61
3: 9780345501330 0 0 81321 151269 192
4: 9780312577220 0 0 777233 155229 55
5: 9780312577220 0 0 2424 151912 125
6: 9780345501330 0 0 26234 155229 55
7: 9780312577220 0 0 12312 155229 55
8: 9780064408330 0 0 73123 155229 55
Resulting books contents:
7 6 68 (capacity, size, element_size)
0: 9780345501330 Fairy Tail, Vol. 1 (Fair Hiro Mashima, William Fl 3
1: empty
2: 9780060855900 Equal Rites (Discworld, Terry
Pratchett 103
3: 9780670032080 Financial Peace Revisite Dave
Ramsey 61 4: 9780064408330 Joey Pigza Swallowed the Jack
Gantos 45
5: 9780312577220 Fly Away (Firefly Lane, Kristin
Hannah 814
6: 9781416971700 Out of My Mind Sharon M.
Draper 1
In the remainder of the assignment we will explore an interesting computational problem described on geeksforgeeks.com. In our case, we will optimize the sale of books, rather than wines, which is used in the geeksforgeeks problem
Part 12: Compute the Total Sales for a Given Ordering of Books
int compute_scenario_revenue(BookSale[] sales_list, int num_sales, int scenario)
The compute_scenario_revenue function takes an array of at most 32 BookSale structs and, according to the bitstring scenario, computes the total revenue generated by selling the given books in that order, with the small twist that as time goes on, the revenue realized from the sale of a book actually increases. The integer scenario encodes the order in which the books are sold. Note: for the purposes of this function we will ignore the sale_date field in each BookSale struct. For instance, suppose 5 BookSale structs are stored in the sales_list array, and int scenario = 12. The scenario bitstring 01100, read left-to-right, would mean: sell the leftmost book (and remove it), then sell the rightmost book (and remove it), then sell the rightmost book (and remove it), then sell the leftmost book (and remove), and then sell the leftmost book.
As an example, suppose our list of BookSale structs had the following corresponding ISBNs: sales_list[0]: 0000000000000 sales_list[1]: 1111111111111 sales_list[2]: 2222222222222 sales_list[3]: 3333333333333 sales_list[4]: 4444444444444
The bitstring 01100 indicates that the books would be sold in the following order:
- 0000000000000 (leftmost book)
- 4444444444444 (rightmost book remaining)
- 3333333333333 (rightmost book remaining)
- 1111111111111 (leftmost book remaining)
- 2222222222222 (final book)
Note that we are reading the bitstring from left-to-right, not right-to-left!
Now, the significance of this order becomes apparent when we see what happens when we sell a book. Imagine that each book is sold on a different day (again, remember that we are ignoring the sale_date field of the BookSale structs for this problem). On Day 1, the chosen book is sold at its normal price, as given by its sale_price. On Day 2, the next book is sold at 2x its sale_price. On Day 3, the next book is sold at 3x its sale_price, and so on. The n-th book is sold at n times its sale_price.
Lets go back to our example. Suppose the books have the indicated prices: stored in the sale_price field of each struct.
sales_list[0]: 0000000000000 $2 sales_list[1]: 1111111111111 $4 sales_list[2]: 2222222222222 $6 sales_list[3]: 3333333333333 $2
sales_list[4]: 4444444444444 $5
We have our bitstring 01100 that indicates the selling order. As time goes on, we can see how the total revenue of selling the books in that order is realized:
- Sell 0000000000000 $2 Total: 1*$2 = $2
- Sell 4444444444444 $5 Total: $2 + 2*$5 = $12
- Sell 3333333333333 $2 Total: $12 + 3*$2 = $18
- Sell 1111111111111 $4 Total: $18 + 4*$4 = $34
- Sell 2222222222222 $6 Total: $34 + 5*$6 = $64
For this particular selling scenario, the total revenue is $64.
The function takes the following arguments, in this order:
- sales_list: a completely filled array of BookSale structs
- num_sales: the number of BookSale structs in sales_list
- scenario: a 32-bit integer that encodes the order in which to sell the books in sales_list
Returns in $v0:
- The total revenue produced by selling the books in the order specified by scenario .
Additional requirements:
- The function may not write any changes to main memory.
Example #1:
num_sales = 5 scenario = 00000000000000000000000000001100
Contents of sales_list :
0000000000000 0 0 12345 153789 2
1111111111111 0 0 52321 153789 4
2222222222222 0 0 41231 153789 6
3333333333333 0 0 12523 153789 2
4444444444444 0 0 51231 153789 5
Return value in $v0: 64
Example #2:
num_sales = 9 scenario = 00000000000000000000000011001101
Contents of sales_list:
5688198170802 0 0 69170 1836 54
8174611363470 0 0 42817 1416 472
6771105776755 0 0 73451 1537 296
9694257705423 0 0 89692 1796 348
8148291072965 0 0 93505 1860 115
1537177706509 0 0 25366 1488 433
3918738489597 0 0 52178 1247 303
1856189180494 0 0 69428 1731 118
4206531586624 0 0 99857 1083 190
Return value in $v0: 12824
Example #3:
num_sales = 11 scenario = 00000000000000000000001101001101
Contents of sales_list :
0043444591466 0 0 56274 1935 12
0912549927792 0 0 20150 1615 341
8208666153502 0 0 13570 1727 275
7891835066590 0 0 89612 1679 405
7850924139905 0 0 56805 1379 227
7172692040044 0 0 14473 1609 306 8881948157382 0 0 35983 1662 38
6319285981025 0 0 61086 1664 411
5218182478429 0 0 34089 1400 484
9545006833495 0 0 12400 1382 458
6178171431772 0 0 40266 1773 330
Return value in $v0: 19581
Example #4:
num_sales = 13
scenario = 00000000000000000001101101001101
Contents of sales_list :
3318220944005 0 0 68169 1310 429 1790274371133 0 0 12055 1911 67
2323508691228 0 0 25027 1950 382
6580406620516 0 0 14457 1160 390 1220293838689 0 0 26212 1181 79
8838065641525 0 0 38406 1406 239
4140073652158 0 0 91560 1707 231
0358003692171 0 0 97221 1131 492
8102823570747 0 0 64311 1671 147
2694841805861 0 0 81769 1342 380
8985832671846 0 0 33475 1157 455
9649316844603 0 0 74921 1199 446
2768474273172 0 0 48218 1291 474
Return value in $v0: 25886
Part 13: Find the Optimal Selling Order to Maximize Revenue int maximize_revenue(BookSale[] sales_list, int num_sales)
The maximize_revenue function takes an array of BookSale objects and determines in which order to sell the books to maximize the revenue. As laid out in the previous part of the assignment, we imagine a situation in which each day we select one book from the list of books and sell it. However, the next book to sell may be taken only from the front or the rear of the array.
Although the geeksforgeeks web page recommends using recursion to solve this problem, you are not expected or required to do so. In fact, a simple, iterative brute-force algorithm can be applied to solve this problem. Suppose n is the number of BookSale n structs in sales_list . We can simply enumerate all 2n possible bitstrings from 0 to 2 -1 and compute the revenues realized by selling the books in every possible order. In other words, we call
compute_scenario_revenue(sales_list, num_sales, bitstring) for each of the 2 n possible bitstrings and choose the maximum returned value. Thats it!
Enumerating the 2n possible bitstrings is very simple: in a for-loop, just count from 0 to 2n-1 and pass each of those values as scenario to the compute_scenario_revenue function. For large test cases, the maximum MIPS instruction count will be appropriately increased.
The function takes the following arguments, in this order:
- sales_list: a completely filled array of BookSale structs
- num_sales: the number of BookSale structs in sales_list
Returns in $v0:
- The maximum revenue that can be realized by selling the books in sales_list as described in this part and the previous part of the assignment.
Additional requirements:
- The function may not write any changes to main memory.
- The function must call compute_scenario_revenue .
Example #1:
num_sales = 5
Contents of sales_list :
0000000000000 0 0 12345 153789 2
1111111111111 0 0 52321 153789 4
2222222222222 0 0 41231 153789 6
3333333333333 0 0 12523 153789 2
4444444444444 0 0 51231 153789 5
Return value in $v0: 64
Example #2:
num_sales = 9
Contents of sales_list :
0845558347906 0 0 65818 1620 82
5577045702462 0 0 91689 1951 154 6354780489355 0 0 94530 1579 60
1999320995468 0 0 93964 1715 225
0145174318443 0 0 41570 1195 232
5871544817889 0 0 57193 1139 387
7106045480035 0 0 48631 1282 414 1730871923235 0 0 39311 1399 78
8122589552824 0 0 60637 1888 497
Return value in $v0: 12980
Example #3:
num_sales = 11
Contents of sales_list :
5289996563210 0 0 50402 1912 114 4878656880115 0 0 14181 1025 40
1545953167947 0 0 74773 1453 419
4163887205026 0 0 11881 1088 316
3994954632401 0 0 25708 1418 346 2840757350273 0 0 79850 1501 89
2690573805693 0 0 75967 1093 147
6412500793328 0 0 20379 1997 380
1956670228687 0 0 95494 1343 275
4719224196873 0 0 30863 1956 194
1049903854879 0 0 40347 1980 281
Return value in $v0: 18092
Example #4:
num_sales = 13
Contents of sales_list :
0969867337768 0 0 91339 1799 274
7167926219358 0 0 87431 1648 149
5856271181125 0 0 38069 1171 135
1739956344089 0 0 24120 1716 401
2423634816035 0 0 44091 1735 429
7323738407143 0 0 33518 1687 357
0790885414601 0 0 49219 1389 468
2095877382616 0 0 89257 1679 325
7788346465697 0 0 76118 1374 364 7903951955477 0 0 45362 1032 44
2668430009430 0 0 26427 1969 245 5802412331328 0 0 94001 1133 62
0689148237261 0 0 28651 1412 265
Return value in $v0: 29443
Reviews
There are no reviews yet.