Congratulations on completing the mid-semester test! The following document is a guide to our grading. Note that though we include point breakdowns here, this was a guide to our tutors, and every code submission was unique, requiring individual analysis of a submission. Therefore, your grades may not exactly match what you assume you may have received.

However, we are human and make mistakes.  If you think we have accidentally awarded you too few points (or too many!) please submit a regrade request. All requests must be made at that link, do not email requests.

Contrary to the initial announcement on the LMS, we are extending the deadline for requests to Friday 23, April at 5PM Melbourne time.

The solutions provided here are modelled off student submissions, intended to illustrate the style that we would expect. While there may be more sophisticated approaches (included some in our internal solutions), these responses illustrated a strong understanding of the problem.

If you think your solution was close, or perhaps even the inspiration for these solutions—well done!

Some of our questions had multiple variants. If the code provided matched the incorrect variant, the rubric assigns a zero to that solution.

 

1   General Remarks

The MST had questions encompassing a range of difficulties. Question 1 was a good test to make sure you’re meeting the minimum standard for the class, whereas Question 2 was a good challenge question to test if you’ve mastered the material so far, with Question 3 somewhat in the middle.

Given the design of the test, we arranged to add an extra point to all scores.  The average before this change was approximately 56% with a standard deviation of 22%.

While the test overall had challenges, it was designed to show students the scope of what they could do with the tools they already had—even if that meant not getting everything right. By comparing your responses with the discussions here, you can understand what types of thinking you were missing, and not just what the exact solutions were.

We were pleased with how everyone fared, and hope it has left you with an opportunity to improve.

 

Question 1

This question was targeting your understanding of a few concepts:

• Iteration using loops

• Output using printf

• Basic use of variables and C syntax

Most students managed to get a majority of the points available for this question, and write relatively neat and concise code.

There were two variants of this question, requiring slightly different output.

Average score:    3/3

Std. dev:             0.70

Question Text: Variant 1

A k-half-Christmas-tree is represented by 2k lines, each of which has two more stars than the previous line, starting from two, with one letter ‘T’ at the top, and a new line after the tree.

For example, for k=2, the output should be:

T

**

****

******

********

For k=3, the output should be:

T

**

****

******

********

**********

************

...

 

Solution

1                  printf("T\n");  //  0.5  pt

2                  int  stars  =  0;  //  0.5pt  for  all  variable  declaration  and  initialisation

3                  for  (int  j  =  0;  j  <=  2  *  k;  j++) 4                  {  //  0.5  pt  for  the  outer  loop

5                          for  (int  i  =  0;  i  <  stars;  i++)

6                          {                             //  1  pt  for  the  inner  loop,  including  update  of  "stars"    or    2*i

7                                  printf("*");  //  0.5  pt  for  the  prints,  including  "\n" 8                          }

9                          printf("\n");

10                        stars  +=  2; 11                }

Question Text: Variant 2

A k-half-Christmas-tree is represented by k lines, each of which has two more stars than the previous line, starting from two, with two letter ’L’s at the bottom, and a new line after the tree.

For example, for k=3, the output should be:

**

****

******

LL

For k=4, the output should be:

**

****

******

********

LL

...

 

Solution

1                  int  stars  =  0;  //  0.5pt  for  all  variable  declaration  and  initialisation

2                  for  (int  j  =  0;  j  <=  k;  j++)

3                  {  //  0.5  pt  for  the  outer  loop

4                          for  (int  i  =  0;  i  <  stars;  i++)

5                          {                             //  1  pt  for  the  inner  loop,  including  update  of  "stars"

6                                  printf("*");  //  0.5  pt  for  the  prints,  including  "\n" 7                          }

8                          printf("\n");

9                          stars  +=  2; 10                  }

11                  printf("LL\n");  //  0.5  pt

 

Question 2

This question was a riff on isprime, and was designed to test if you could pull together both algorithmic thinking and C programming applied to a multi-stage problem.

The key to solving this problem was to realize that it could be broken down into a series of much simpler steps—this is the process of abstraction we aim to teach in the course.

1. To compute secret_math you need to call secret twice with two different inputs

2. To compute secret and find the i-th k-secret number you need a way to check if a given number is secret, then loop through all the numbers until you find i of them that are secret

3. To check if a number is secret you need to loop through all of its possible divisors and check: (a) If the number is actually a divisor

(b) If the divisor is prime using isprime

(c) If the divisor is less than k

After breaking down the problem like this, it becomes much more manageable and it is possible to realize it requires very few lines of code!

Note that what we call k-secret numbers here in reality are called B-smooth numbers, and have applications in cryp- tography and number theory.

The most common mistakes was failing to break down the problem into smaller steps.  This also led to challenges understanding a worded representation of a function with two numerical parameters (i and k).

To do better on a similar problem, a student would be adivsed to go through each task the program needs to complete, and break those into subtasks.

Average score:     1/3

Std. dev:             1.04

Question Text

Given a number N, in cryptography and number theory, we often check if the factors of N that are prime are less than or equal to K. If yes, we will call N a K-secret number.

Note that 1 is always the first K-secret number given any K.

For example, The factors of 11 are 1, 11. Both 1 and 11 are prime, while 11 is not less than or equal to 7. Therefore 11 is not 7-secret.

The factors of 144 are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144. Of these, 2, and 3 are prime. Both 2 and 3 are less than 7, so 144 is 7-secret.

The initial sequence of 7-secret numbers is: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, ...

Write a function

secret_math(int  i,  int  j,  int K1,  int K2)

that prints out the sum/product (variant 1/variant 2) of the i-th K1-secret number and j-th K2-secret number. You may want to write a supporting function int  secret(int  i,  int K) that returns the i-th K-secret number. Example: secret_math(5,  2,  3,  7)

Should return: 8 Because the 5-th 3-secret number is 6 and the 2nd 7-secret number is 2, and 6+2 = 8.

You may assume that the function int isprime(int n) has been provided and returns 1 if a number is prime and 0 otherwise.

You may also assume that i, j, K1, K2  > 0

 

Solution

An alternate solution (not depicted) was to save all the k-secret values into an array and pick out the i-th one. While this works, it is inefficient as there is not reason to keep all the smaller k-secret numbers.

1         int  secret_math_variant1(int  i,  int  j,  int  K1,  int  K2) 2         {

3                  return  secret(i,  K1)  *  secret(j,  K2);  //  0.5  point  for  knowing  to  use  the  function ,→        twice  with  the  right  operator  in  between

4          }

5

6         int  secret_math_variant2(int  i,  int  j,  int  K1,  int  K2) 7         {

8                  return  secret(i,  K1)  +  secret(j,  K2);  //  0.5  point  for  knowing  to  use  the  function ,→        twice  with  the  right  operator  in  between

9          }

10

11         int  secret(int  i,  int  K) 12         {

13                  int  count  =  0;

14                  for  (int  num  =  1;;  num++) 15                  {

16                          if  (is_number_k_secret(num,  K)) 17                          {

18                                   //  1  point  for  having  a  loop  that  breaks  after  finding  the  i-th  K-secret  number 19                                   count++;

20                                   if  (count  ==  i)

21                                           return  num;

22                        }

23                }

24         }

25

26          //  the  loop  below must  loop  to  <=  num  else  it might miss  num  >  K  if  num  is  prime.

27          //  -1.5  if  the  below  is  missing  in  its  entirety  or  is  largely  incorrect

28          int  is_number_k_secret(int  num,  int  K) 29          {

30                  int  any_prime_factors_above_K  =  0;

31                  for  (int  divisor  =  1;  divisor  <=  num;  divisor++)     32                  {  //  0.5  for  having  the  for  loop  over  the  divisors

33                          if  (num  %  divisor  ==  0) 34                          {

35                                   if  (is_prime(divisor)  &&  divisor  >  K)

36                                   {  //  0.5  points  for  checking  is_prime,  0.5  points  for  divisor  >  K

37                                           return  0; 38                                   }

39                          }

40                          return  1; 41                  }

42          }

Question 3

This question was meant to be a chance to demonstrate an understanding of the basics of accessing and setting array elements. It also tested if a student understood that a char in C holds an underlying numerical value, and that the two

are interchangeable. Thus including numerical values in the array was a minor trap for the unwary. One of the most common errors was failing to do the swap requested in the question.

A stylistic oddity we saw among a few submission was the failure to use all three conditionals in a single combined statement (as below). Doing the check in one line would here not be inappropriate.

 

Average score: Std. dev:

 

Solution

1.24/3

1.14

1         int  find_bby(char  rooms[],  int  n) 2         {

3                          int  door_index  =  -1;

4                          int  bby_index  =  -1;

5                          for  (int  i  =  0;  i  <  (n  -  2);  i++)  //  0.5  points  for  loop 6                          {

7                                           if  (rooms[i]  ==  3  &&  rooms[i  +  1]  ==  8  &&  rooms[i  +  2]  ==  3) 8                                           {  //  0.5  points  for  finding  383  (numeric)

9                                                            door_index  =  i;

10                                           }

11

12                                       if  (rooms[i]  ==  'b'  &&  rooms[i  +  1]  ==  'b'  &&  rooms[i  +  2]  ==  'y') 13                                       {  //  0.5  points  for  finding  bby

14                                                           bby_index  =  i; 15                                           }

16                          }

17

18                          //  validate

19                          if  (door_index  ==  -1  ||  bby_index  ==  -1) 20                          {

21                                      return  -1;  //  0.5  correct  return  condition  (need  both  this  and  the  one  below) 22                        }

23

24                          //  swap    //  1pt  correct  swap

25                          rooms[door_index]  =  'b' ;

26                          rooms[door_index  +  1]  =  'b' ;

27                          rooms[door_index  +  2]  =  'y' ;

28

29                          rooms[bby_index]  =  3;

30                          rooms[bby_index  +  1]  =  8;

31                          rooms[bby_index  +  2]  =  3;

32                       return  1;  //  0.5  correct  return  condition  (need  both  this  and  the  one  above) 33         }

 

Question 4

The true/false questions were designed to test basic conceptual understandings and were in general handled well by students.

Short descriptions of the answers and distractors follows.

• C is an imperative programming language—meaning that the language uses sequences of statements that change a programs state. This was discussed in the intro to C.

• While big-O notation describes the asymptotic complexity of an algorithm, it doesn’t actually tell you how long a specific instance of a problem will take to solve