Skip to content

Exercise 4: ID, Grade, Index, Max

This is a programming exercise for you to solve on your own. You can submit but it will not be graded. Test cases are provided for the exercises so that you can test and check on your own if your code is correct. Feel free to discuss your solution with your peers or your TAs.

Prerequisite

Learning Outcomes

  • Be comfortable writing correct C programs that involve if, else, loops, logical statements, and arrays.
  • Be able to decompose a more complex problem into smaller subproblems and write functions to solve the sub-problems.

Setup

~cs1010/get-ex04
  • You should see a new subdirectory ex04-<githubid> in your current working directory, where githubid is your GitHub ID.
  • Inside that directory, you should see a bunch of files:
    • id.c, grade.c, index.c and max.c are the most important files. They are the skeleton C code that you should edit to solve the exercise.
    • inputs and outputs are subdirectories that contain test inputs and test outputs. We use the same convention as Exercise 1 so you should be familiar with them.
    • Makefile: This is the configuration for the tool make that we use to automate the compilation and testing of the programs.
    • test.sh: This is a bash script for testing your code.

Solving The Assignments

  • Edit the .c files on the PE hosts to solve the corresponding question as described below.
  • You can assume that all test inputs are valid inputs.
  • To compile and run the given tests with the sample inputs and outputs, run on the command line,
make

This will compile all your C files and if there is no error, run the test scripts.

Submission

When you are ready, run the following command while you are in the exercise directory:

~cs1010/submit-ex04

The .c files will be uploaded to GitHub. You can submit multiple times. As an exercise is not graded, submitting your code only serves the purpose of archiving your work for backup purposes.


Question 1: ID

Your NUS student id has a letter at the end. This letter is called a check code and is a form of redundancy check used for detecting errors, especially when your student id is manually entered into a software application.

Your check code is calculated by:

  • Sum up the digits in your student id. Let the sum be N.
  • Divide N by 13, and take the remainder. Let the remainder be R
  • Look up the table below:
Remainder Check Code
0 Y
1 X
2 W
3 U
4 R
5 N
6 M
7 L
8 J
9 H
10 E
11 A
12 B

Write a program that reads in an integer containing the digits of a student's id from the standard input. Print out the check code to the standard output.

You should practice using an array to solve this problem instead of using a long if-else statement.

ooiwt@pe116:~/ex04-ooiwt$ ./studentid
1933091
Y
ooiwt@pe116:~/ex04-ooiwt$ ./studentid
3364497
E
ooiwt@pe116:~/ex04-ooiwt$ ./studentid
0123456
J

Addendum: Some students choose to store the check code in an array of char values instead of an array of strings. Storing the check code as char is indeed more appropriate, but I have not mentioned how to print a char to the standard output. There is no cs1010_print_char in the CS1010 I/O library. One way to print a char variable is to use putchar() function. The example below print A.

#include <stdio.h>

int main() {
  char c = 'A';
  putchar(c);
}

Question 2: Grade

In a mirror universe, there is an evil version of your professor who is especially tough on his CS1010 students. He uses the following grading scheme to decide the letter grade to give out.

Marks Letter Grade
100 A+
99 A
98 A-
96-97 B+
91-95 B
86-90 B-
81-85 C+
71-80 C
61-70 D+
51-60 D
0 -50 F

Write a program called grade that reads in an integer corresponding to the marks given to a student. Print out the letter grade given by the evil professor.

You should practice using an array to solve this problem instead of using a long if-else statement as done in Unit 8.

ooiwt@pe116:~/ex04-ooiwt$ ./grade
100
A+
ooiwt@pe116:~/ex04-ooiwt$ ./grade
99
A
ooiwt@pe116:~/ex04-ooiwt$ ./grade
50
F
ooiwt@pe116:~/ex04-ooiwt$ ./grade
87
B-

Question 3: Index

Write a program index that finds a given number from a list of n integers L.

The program should read the following from the standard inputs in order:

  • The first number is a positive integer n
  • The next n numbers corresponds to the list of integers l_0, l_1, ... l_{n-1} in L.
  • The next number is a positive integer k
  • The next k numbers are integers corresponds to a list of queries q_0, q_1, .. q_k

For each query, the program should print (on a new line) the position of the integer in the list, or "not found" if the query cannot be found. To be more precise, for each i, if q_i == l_j for some j, print j. If q_i appears multiple times in L, print the smallest j. If q_i is not in L, then print "not found".

ooiwt@pe116:~/ex04-ooiwt$ cat input
5
-5 3 1 8 -5
3
1 4 -5
ooiwt@pe116:~/ex04-ooiwt$ ./index < input
2
not found
0

Line 1 of the input file input tells the program that there are five integers to read. The next five integers should be read in as the list. The next integer (Line 3) is 3. The next three integers should be read in as queries. The first query is 1, which can be found at position 2 (we start counting from 0). The next query is 4, which is not found in the list. Finally, the last query is -5, which can be found at position 0 and 4, but we return only the one at position 0.

Question 4: Max

Write a program max that finds the maximum value from a list of n integers L.

Instead of doing this with a loop, you should solve this question with recursion. Write a function

long max(const long list[], long start, long end)
{
}

that calls itself and return the maximum value among the array elements list[start] .. list[end - 1]. It should split the input list into two halves (roughly), find the maximum of the left half, find the maximum of the right half, and return the larger of these two maximums.

In the function definition above, the keyword const (short for constant) is used to annotate that the array list is meant to remain unchanged.

The program should read the following from the standard inputs:

  • The first number is a positive integer n
  • The next n numbers correspond to the list of integers L.

and print to the largest value among the inputs to the standard output.

ooiwt@pe116:~/ex04-ooiwt$ cat input
5
-5 3 1 8 2
ooiwt@pe116:~/ex04-ooiwt$ ./max < input
8