COS 126Calculating Final Grades Due: Wed. 4/30, 11:59pm

Your last COS 126 assignment will calculate the semester grades for the students in an intro computer science class. Your program reads a series of (userid,assignment,score) triples from the standard input, and calculates and prints the average score for each student, and the average score for each assignment. For example, the input file `/u/cs126/data/grades1` contains the following data:
```% cat /u/cs126/data/grades1
ret	hw1	87
rs	hw1	80
dpd	hw1	94
rs	hw2	80
ret	hw2	100
dpd	hw2	72
rs	mid1	72
ret	mid1	81
```
When given the -u option, your program prints a list of userids followed by the average score for that person (all assignments are weighted equally). For example:
```% a.out -u < /u/cs126/data/grades1 | sort
dpd     55.333332
ret     89.333336
rs      77.333336
```
Your program can print the output lines in any order; the pipeline above uses the Unix `sort` command to arrange the lines in lexicographic order. You can use `sort -rn +1` to sort the lines based on the second field, in decreasing numerical order (try it!). The -a option prints the averages for the assignments, rather than the people:
```% a.out -a < /u/cs126/data/grades1 | sort
hw1     87.000000
hw2     84.000000
mid1    51.000000
```
Specifying both -a and -u prints both sets of output (in whatever order you wish). Note that the program gives a zero score for missing assignments, such as dpd's unsubmitted midterm exam. You may assume that no student will have more than one score for each assignment.

The grading program uses hash tables to keep track of the grade information as it is read in. A hash table is a data structure which stores (key, value) pairs; given a key, a hash table can very quickly find the associated value. `/u/cs126/include/table.h` gives the specification for the hash table module you are to write:

```/* Creates a new hash table with "buckets" buckets. */
extern struct table *table_new(int buckets);

/* Returns the number of entries in "tbl". */
extern int table_size(struct table *tbl);

/* Adds "value" to "tbl" under "key", overwriting any previous value.
Copies "key" if necessary. */
extern void table_add(struct table *tbl, char *key, int value);

/* Returns the value listed in "tbl" under "key", or 0 if not found. */
extern int table_lookup(struct table *tbl, char *key);

/* Returns an array of pointers to the keys of "tbl". */
extern char **table_keys(struct table *tbl);
```

A hash table is implemented as an array of linked lists; each slot in the array is called a bucket. Initially each bucket contains an empty linked list. The table module includes a special function called the hash function; the hash function takes a key as an argument and returns an index into the hash table's array -- a number between 0 and `buckets` - 1. Following is the beginning of `table.c` (you can copy it from `/u/cs126/examples/table.c`); you should finish it by adding implementations of the functions declared in `table.h`.

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "misc.h"
#include "table.h"

struct table {
int buckets;
int size;
struct tablenode **array;
};

struct tablenode {
char *key;
int value;
struct tablenode *next;
};

static unsigned int strhash(char *s, int buckets)
{
unsigned int hashval;

for (hashval = 0; *s; s++) hashval = *s + 31 * hashval;
return hashval % buckets;
}

/* Implementations of table.h functions follow. */
/* ... */
```

`table_new` creates and returns a new hash table. Note that `table_new` needs to allocate (using `malloc`) the hash table's array in addition to the table structure itself.

To add a (key, value) pair to the table, `table_add` uses the hash function `strhash` to choose a bucket for the key. Then, if the bucket's linked list does not already contain a node for the key, `table_add` makes a new `tablenode` structure for the (key, value) pair and adds it to the bucket's linked list (using `strsave` to make a duplicate of the key string). If the linked list already contains a node for the key, then `table_add` overwrites the node's `value` field.

`table_lookup(tbl, key)` returns the value previously stored in `tbl` under `key`. It does this by finding the key's bucket (using the hash function), then searching for the key in the bucket's linked list. If it cannot find the key, `table_lookup` returns zero.

`table_keys(tbl)` creates (using `malloc`) an array containing all of the keys in `tbl`. `table_keys` doesn't duplicate the keys; the pointers in the returned array point to the same strings that the table's internal `tablenode` structures point to.

In addition to `table.c`, you should write `grade.c`, which contains `main`. `main` declares two hash tables, `useridtabl` and `assigntbl`, for storing (userid, sum) and (assign, sum) pairs respectively. As scores are read in from the standard input, they get added to the running sums in the two tables. At the end of the program, the sums are divided by the number of assignments (or userids) to calculate the averages. Following is a skeleton of `grade.c`, which you can copy from `/u/cs126/examples/grade.c`).

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "table.h"

#define TABLE_BUCKETS 59

int main(int argc, void *argv[])
{
struct table *useridtbl = table_new(TABLE_BUCKETS);
struct table *assigntbl = table_new(TABLE_BUCKETS);
char userid[100], assign[100];
int score, i, print_userids = 0, print_assigns = 0;

for (i = 1; i < argc; i++) {
if (strcmp(argv[i], "-u") == 0) print_userids = 1;
if (strcmp(argv[i], "-a") == 0) print_assigns = 1;
}

while (scanf("%s %s %d", userid, assign, &score) == 3) {
/* Increment userid's entry in useridtbl by score. */
/* Increment assign's entry in assigntbl by score. */
}

/* If "-u" appeared on the command line */
/* For each userid in useridtbl */
/* Print the average score for userid. */
/* If "-a" appeared on the command line */
/* Print the average score for assign. */
return 0;
}
```
You'll need to compile your program with the command line

`% /u/cs126/bin/lcc -n grade.c table.c`
Working versions of both files are supplied as `/u/cs126/lib/grade.o` and `/u/cs126/lib/table.o`, so you can test your code incrementally. For example, to test your `grade.c` with a known correct version of the hash table code, you can say:
`% /u/cs126/bin/lcc -n grade.c /u/cs126/lib/table.o`
Test your program with the data files `/u/cs126/data/grades1` and `/u/cs126/data/grades2`. The correct output (for both -a and -u, sorted with `sort` as above) is available in `/u/cs126/data/averages1` and `/u/cs126/data/averages2`.

`% /u/cs126/bin/submit 11 readme grade.c table.c`