COS 126
Calculating 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 */
    /* For each assign in assigntbl */
      /* 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.

Submitting Your Program

Turn in your code and your documentation with the command

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