Calculating Final Grades
| COS 126 Calculating Final Grades | Due: Wed. 4/30, 11:59pm |
/u/cs126/data/grades1 contains the following data:
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:% 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
Your program can print the output lines in any order; the pipeline above uses the Unix% a.out -u < /u/cs126/data/grades1 | sort dpd 55.333332 ret 89.333336 rs 77.333336
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:
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.% a.out -a < /u/cs126/data/grades1 | sort hw1 87.000000 hw2 84.000000 mid1 51.000000
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
Working versions of both files are supplied as% /u/cs126/bin/lcc -n grade.c table.c
/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:
Test your program with the data files% /u/cs126/bin/lcc -n grade.c /u/cs126/lib/table.o
/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.
Turn in your code and your documentation with the command
% /u/cs126/bin/submit 11 readme grade.c table.c