Homework 1

Computer Architecture I ShanghaiTech University

Task 1: Binary Search Trees in C

Note: All work related to Task 1 should be submitted in a directory named task1.


Implement a Binary Search Tree in C. See the header file bintree.h for further details.

Your submission should only include the source code for the binary search tree, bintree.c. You may wish to include a .gitignore file to help you ignore any other file in your working area. Any other file found will directly result in a grade of 0. We will NOT be using your copy of the header file or Makefile.

Compilation of the source code requires no errors or warnings and conformity to the C89 standard. The Makefile syntax is given below.

CFLAGS=-Wpedantic -Wall -Wextra -Werror -std=c89

bintree.o: bintree.c bintree.h
  ${CC} ${CFLAGS} bintree.c -o bintree.o

We will test your program using the functions declared in the header file provided as well as some other functions defined by us. The output of the individual test cases will NOT be given in gradebot and any failed attempts at retrieving the test cases or the program outputs will be seen as plagiarism.

We require that you will have one line with comments for every four non-blank lines. Comments have to be meaningful and in English.

No memory leaks are allowed. Memory leaks will be automatically detected and manually screened and will result in a decrease in your score after the deadline.

We will also impose a limit of 300 on your LoC (lines of code). Do not exceed this limit as we will deduct points for those who exceed this limit.

Consider Learning Before You Start

Task 2: Libraries

Note: All work related to Task 2 should be submitted in a directory named task2. For all tasks assume that bintree.h will be provided in the working directory and your bintree.c will be copied to the current working directory.

Task 2.1: Static Library


Write a shell script named staticlib.sh that when invoked, produces a static library named libtree.afrom the source files bintree.c and bintree.h.

Then create a static-linked executable statictree from libtree.a and test.c. Do not execute the program in the shell script.

Hint: use the command ar to create the static library. Then use the command ld to create the executable file.


Write a shell script named dynamiclib.sh that when invoked, produces a dynamic-linked library named libtree.so from bintree.c.

Then generate an executable named dynamictree using libtree.so as well as test.c. Do not execute the program in the shell script.



Clone the repository from gradebot.

git clone metastasis@gradebot.org:user/{username}/{courseID}/{homeworkID}

For specific fields {username}, {courseID} and {homeworkID}please refer to your gradebot account.

Use commands such as git commit, git stash as well as git checkout to constantly keep track of your programming history.

Check In

The directory tree of your submission should look like the following :

├── .gitignore
├── task1
│   └── bintree.c
└── task2
    ├── dynamiclib.sh
    └── staticlib.sh

To push the repository to gradebot for grading, if you used git clone to generate your local repository, use git push origin master. Otherwise, add the remote repository before pushing.

Last Modified: Feb. 16, 2017