Why the auxiliary lab?

Many of you are still struggling with C, as evidenced in the midterm performance. We provide this lab to help you get more C programming practice and (potentially) improve your grade if you have done poorly in the midterm. If you have done well in the midterm and are pretty comfortable with C, you need not complete this lab.

Like other labs, this lab counts for 7% of your total grade. However, this 7% comes out of the 25% midterm grade percentage. In other words, there are two ways of computing the final grade:

We use the higher score of the two as your actual final grade.

C exercises

There are four C exercises in this lab. We provide no clutches (no skeleton code and no Makefile) to make you get comfortable with the overall experience of writing C programs on UNIX.

Exercise 1: Prime generating integers

Please do Prime Generating Integers from Project Euler. Write a C program called prime.c that outputs the desired result.

Exercise 2: Bouncy number

Please do the bouncy number problem from Project Euler. Write a C program called bouncy.c that takes a command line argument representing the desired percentage, which is a number between 0 and 100. The program prints out the least number for which the proportion of bouncy numbers has the desired percentage.

Exercise 3: Large sum

Please do the Large Sum problem from Project Euler. Write a C program called sum.c that outputs the desired ten digits of the large sum.

Hint: How should your program obtain the input of the given one-hundred 50-digit numbers? There are two ways.

  1. You may include the given one-hundred 50-digit numbers as a constant in your program, e.g. by declaring char numbers[1000][51] = {"37107287533902102798797998220837590246510135740250", ..., };. Make sure you learn the necessary editor tricks so that you do not spend a lot of manual efforts formatting the given numbers.
  2. You may save the given one-hundred numbers in a text file (one number per line) and have your program read a given input text file. You need to use fopen, fgets, fclose to open a file, read its contents line by line, and close the file when you are done. Type man fopen or man fgets to learn how to use these C library functions. If you have the K&R book, please read Chapter 7 to learn how to do input/output in C.

Exercise 4: Find the ten most frequent words

Write a C program called wordcount.c to find the ten most frequently used words in the Bible. You should download and use this textfile of King James's bible.

In order to count the words, your program needs to transform the given textfile into a collection of words. First, you need to split the textfile into words. Each word refers to a consecutive sequence of alpha-numeric characters. Words are separated by one or more non-alphanumeric characters. Second, you need to ``normalize`` the words by turning any uppercase letters into a lower case one.

To count the occurances of words, there are several strategies.

  1. You can implement a hash table to store the mapping from each word (C strings) to its occurance counter. C's standard library does not have hash tables nor dictionary, so you'll have to implement your own. After you've counted all the words, you'll need to sort them by their occurance counters.
  2. You can sort all words first. For sorting, you can implement your own function (e.g. midterm problem 2 implements bubble sort), or use the library function qsort (type man qsort to learn how to use it). You can then sum consecutive identical words in the sorted list to count them. Last, you need to sort words by their occurance counts.

How to check your answer

We are running an answer-checking server. To check your programs' answer against out, please download submit.py and my.info files. Fill out the information in the my.info file. To check your prime problem (Exercise 1) solution, run 
$ python submit.py prime
To check your bouncy solution, run 
$ python submit.py bouncy

Submission

Please create a gzipped, tar file called lab0.tar.gz that contains all the *.c *.h files that you wrote for this lab, as well as a Makefile for creating and running the four executables. Write your Makefile in a way such that if one types make run-ex1, the program for the first exercise is executed and it outputs the desired answer. Similiarly, if one types make run-ex2, the program for the second exercise is executed and it outputs the desired answer, and so forth.

Note that we did not give you an existing Makefile on purpose. Review tutorial 1 to learn how to write a Makefile.

Also, learn how to use tar command. You can do man tar, googling, or consult the Makefile from previous labs to learn how to create a gzipped, tar file.

Submit your lab0.tar.gz here.