---

Lab-1: Basic C Programming

Due: 10/8 11pm

The goal of this lab is to get your hands dirty doing some basic C programming and debugging. There are two components to this lab. First, you write a series of simple C functions in programs whose skeleton code are already provided for you. Next, you write complete C programs by yourself from the scratch.

Mini-exercises: Part1-8 (100 points)

Obtain and update your lab files by doing:

$ cd cso18-labs
$ git fetch upstream
$ git merge upstream/master

For the series of mini-exercises on C, you shall complete the files part1.c, part2.c, ..., part8.c, found in subdirectory mini/

It is recommended that you complete and test each exercise individually. For example, suppose you have completed the exercise in part1.c. Test by typing the following:

$ make
$ build/part1
variable should be 5, actually is 3!
Aborted

From the above error message, you can see that it did not pass the test. Debug and try again. Complete and test each part individually before moving on to the next one.

Once you've passed the tests for all 8 exercises in mini/, you can double check your test-passing status by typing:

$ ./grade-lab
basic [part1.c]: 
  set_to_five: OK
  array_sum: OK
bubble sort [part2.c]: 
  swap: OK
  bubble_sort: OK
prime sieves [part3.c]: 
  initialize_array: OK
  mark_multiples: OK
  prime_number_sieves: OK
  find_smallest_divisor: OK
point structure [part4.c]: 
  set_point: OK
  point_dist: OK
linked list [part5.c]: 
  list_insert: OK
  list_end: OK
  list_size: OK
  list_find: OK
  list_remove: OK
bitwise operators [part6.c]: 
  get_exponent_field: OK
  clear_msb: OK
  bit_at_index: OK
binary tree [part7.c]: 
  preorder_traveral: OK
  inorder_traversal: OK
  inorder_traversal_with_dup: OK
split string [part8.c]: 
  easy_string_split: OK
  harder_string_split: OK
Score: 100/100

The above shows the example output of a successful full test.

Saving changes while you are working on Lab1

You should frequently save your work to protect against laptop failures and other unforeseen troubles. You save the changes by first "committing" them to your local lab repo and then "pushing" those changes to the repo stored on github.com

$ git commit -am "saving lab1 changes"
$ git push origin

The `-a` flag (as in the command `git commit -am ...`) tells git to add the changes you've made to existing files to the current commit. If you do not provide this flag, the changes you made to the existing files will not be committed. After you've pushed your changes with git push, they are safely stored on github.com. Even if your laptop catches on fire in the future, those pushed changes can still be retrieved. However, you must remember that git commit by itself does not save your changes on github.com (it only saves your changes locally). So, don't forget to type that git push origin.

Debugging the lab

Below are some advice on how to debug common problems encountered in doing this lab:

• Remember to recompile changed code. Whenever you've changed a file, always type make to re-compile before executing again.
• Write your own simple test code. Don't rely solely on the lab's testing infrastructure (i.e. ./grade-lab) to test the correctness of your code. Except for part7, we do not distribute the source of the test code (hence you will only see cso18-labs/clab/mini/static/part1_harness.o and not cso18-labs/clab/mini/static/part1_harness.c). This makes it hard to debug. So you should write your own tester.

  Let's say you want to test the array_sum function in file part1.c. To write your own test code, create a file (e.g. called test-part1.c) with a main function that invokes array_sum in various ways to test its correctness.

  An example test-part1.c might look something like this.

  Compile your test code by typing:

  $ gcc -std=gnu99 test_part1.c part1.c
  

• Read part7_harness.c test code. For part7, we distribute the source of the tester code in part7_harness.c. It'll be very helpful for debugging if you read this file.
• Learn to use gdb. It is absolutely essential that you learn to use gdb. This tool is a must for helping you handle ``segmentation fault'', which you'll see a lot when doing labs. Let's say you have a segfault on part1. Invoke gdb by typing:

  $ gdb build/part1
  (gdb) bt
  

  bt is the gdb command to print the stack trace which tells you where the problematic execution occurs and how the program got there. Recitation 2 has covered the use of gdb. There are also many tutorials online on gdb.

Write standalone C programs from scratch

In this second component of the lab, we provide no crutches (no skeleton code, no Makefile, no grading testers) to make you get comfortable with the overall experience of writing C programs and testing them on UNIX. You are to write one standard alone C program from scratch.

Standalone C program: Averaging columns in a *.csv file (25 points)

Put all your files for this exercise in cso18-labs/clab/scratch/avgcsv directory.

Write a C program that parses a *.csv file print out the average of each column. The input csv file has a set of columns separated by the ';' character. Each columns contains a whole or fractional number.

Your executable file must be named avgcsv. It should take as argument the name of a csv file and outputs the average of each column (with 2 digits of precision), separated by ';'.

For example, suppose the contents of the example.csv are as follows:

$ cat example.csv   
10;25.5;56
22;10;100.4

Then, the expected output of the command ./avgcsv example.csv should be:

$ ./avgcsv example.csv
16.00;17.75;78.20

We expect you to write a Makefile to generate the avgcsv executable file from your source code. Recitation 1 teaches you how to write a Makefile.

We do not provide you with any tests and will test your program under a few *.csv files of our own choosing during grading time. You should write unit tests for your program. In particular, you should test the cases when the input csv file contains a large number of rows or a large number of columns. You can assume that you won't run out of memory storing all the floating points parsed from the file in the memory.

Once finished, add relevant source files and Makefile to your git repo by typing git add *.c *.h Makefile. Commit and push git commit -am "avgcsv"; git push origin

Note that whenever you add a new file in this directory, you need to manually tell git to ``track it'' with git add. Otherwise, the file will not be committed by git commit.

Some advice on doing this lab:

• Use either strtok_r from C library, or string_token you implemented in part8.c of minilab to split into columns. If you decide to use the former, read its documentation man strtok_r, and compile your program with gcc flag `gcc -std=gnu99`. If you decide to use the latter, include the header file with #include "../../mini/part8.h", and link your program with part8.o from the mini/ directory.
• Use printf(".2f", number) to print a number to the precision of 2 decimal points.
• Write good tests. In your unit tests, you should test with csv files with different rows and columns. Make sure you test cases when the input csv file contains a large number of rows or a large number of columns. You can assume that you won't run out of memory storing all the floating points parsed from the file in the memory.
• Pay attention to coding style. Do not write all your code in one giant main function. Break your program logic into several smaller functions.

Once you finished avgcsv, you may either elect to do the bonus exercise below, or proceed to hand in the lab.

Bonus exercise: Game of Life (25 points)

This is a bonus exercise, and thus not mandatory.

Put all your files for this exercise in cso18-labs/clab/scratch/gameoflife directory.

Write a C program to simulate the Conway's game of life.

In a game of life of size n by n, the universe is two dimensional and consists of n by n cells. Each cell is in one of two possible states, "live"/"dead" (or "populated"/"unpopulated"). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

• Any live cell with fewer than two live neighbours dies, as if caused by under-population.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any live cell with more than three live neighbours dies, as if by over-population.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. The rules continue to be applied repeatedly to create further generations.

What about boundary conditions? We treat the borders of the 2D world as if they wrap around. In a universe of n x n cells, let's refer to the top-left cell as in position (0,0) and the bottom right cell as in position (n-1,n-1). If borders wrap around, then the 8 neighbors of (i,j) are:

1. ((i+1)%n,j) right neighbor
2. ((i-1)%n,j) left neighbor
3. (i,(j+1)%n) top neighbor
4. (i,(j-1)%n) bottom neighbor
5. ((i+1)%n,(j+1)%n) topright neighbor
6. ((i-1)%n,(j+1)%n) topleft neighbor
7. ((i+1)%n,(j-1)%n) bottomright neighbor
8. ((i-1)%n,(j-1)%n) bottomleft neighbor

Your executable file must be named gameoflife. It should take two arguments. The first argument is the name of a seed pattern file. The second argument is the number of ticks to run for the simulation. The seed pattern file contains one line per row of the universe. If the cell is "dead", its position is marked with the '.' character. If the cell is "live", the position is marked with the 'x' character. The seed file also effectively specifies the size of the universe to simulate.

For example, the contents of an example seed file example_seed are as follows:

$ cat example_seed
.....
.....
.xxx.
.....
.....

Then, the expected output of the command ./gameoflife example_seed 1 should be:

$ ./gameoflife example_seed 1
.....
..x..
..x..
..x..
.....

The expected output of the command ./gameoflife example_seed 2 should be:

$ ./gameoflife example_seed 2
.....
.....
.xxx.
.....
.....

Like in exercise 1 and 2, you should write a Makefile to compile your program and write your own unit tests to check the correctness. During grading, we'll test your program using seed files of our own choosing. You may assume that the seed file used for testing contains a world of no more than 1000x1000

Once finished, add relevant source files and Makefile to your git repo by typing git add *.c *.h Makefile. Commit and push git commit -am "gameoflife"; git push origin

Handin Procedure

To handin your files, simply commit and push them to github.com

$ git commit -am "hand in lab1"
$ git push origin 

We will fetching your lab files from Github.com at the specified deadline and grade them.

---