Week 10 Laboratory Exercises

Objectives

  • Become familiar with the environment used for the final exam
  • practice coding under exam conditions

Activities To Be Completed

The following is a list of all the activities available to complete this week...

Worth one mark in total:

  • exam_q1_season
  • exam_list_count_last
  • Prac Exam Q1
  • Prac Exam Q2

Worth half a mark in total:

  • exam_list_delete_last
  • padding_left
  • Prac Exam Q4

Worth half a mark in total:

  • nested_divisions
  • knight_moves

For your interest, but not for marks:

MyExperience

The first 10 minutes of the lab is set aside for you to complete the myExperience survey for COMP1511. Your answers are confidential and you should not show them to your tutor.

Take-Home Exam Practice

The first three lab exercises must be completed and submitted using the instructions for submission of the exam (the questions themselves will have these instructions).

This section of the lab will not be run under full exam conditions or time limits but it will be a good chance for you to familiarise yourself with how the questions will be structured as well as how auto testing and submission works.

Remember that in the exam you are allowed to look up resources, but you are not allowed to communicate with anyone (inside or outside the course) about the exam. If you like, you can try these exercises with those restrictions so that you have some familiarity with the format.

Practice Exam Part 1

Part 1 of the exam is a series of short questions that don't involve you writing code, but instead you interpreting code or understanding some key concepts.

You will be answering part 1 by editing a text file that you can test and submit. The test will only tell you if your answers are understood, not if they're correct.

The real exam will have more part 1 questions!

Your answers for part 1 questions in today's practice exam will not be marked.

Practice Exam Part 2

The first three of this week's lab exercises are the Part 2 questions for the practice exam.

Part 2 answers are entered into the file specified by each question, autotested using the 1511 autotest-pracexam command, and submitted using the "give" command. The questions include submission instructions.

We are not enforcing exam conditions but try to do the questions under simulated exam conditions.

If you can't complete the questions, you can talk to your tutors.

Your answers will be automarked in the usual way for lab exercises.

Accessing the Prac Exam Environment

To access the Prac Exam, go to: https://cgi.cse.unsw.edu.au/~cs1511/21T3/prac_exam/papers/.

You will be asked to enter your zID and zPass. You will then be taken to your personal exam paper.

In the final exam, this paper will be personalized to you.

Returning to normal lab work

The remaining lab exercises are completed the usual way. The challenge exercises are a q7-like and q8-like question.

Exercise
(●◌◌)
:

Practice Exam Q1 - Count the number of small values in an 2D array

In this task, you will be helping a gardener determine how many trees they can plant during spring.

You have been given array_seasons.c, which contains a function seasons.

You have also been given the definition of a struct tree, which tells you, for a particular tree, in what season you should plant it, and how many you have.

struct tree {​​
  int number; // TODO: we should call this "count" or "amount"
  char season;
};

The function seasons is given an array of treestructs, where each struct contains:

  • int number, which tells you how many trees there to be planted.
  • char season, which tells you which season the trees can be planted. 's' is for summer; 'a' is for autumn; w is for winter; p is for spring.

Add code to the function seasons, so that it returns the total number of trees that can be planted in spring:

For example, if the array of tree structs contains the following:

{​​
   { 3, 'p'},
   { 4, 's'},  
   {14, 'p'},
   { 5, 'a'},
   {24, 'w'},
   { 1, 'p'},
   { 4, 's'},
}

Your function should return the struct {​​18, 'p'}​​, because there are a total of 18 trees that can be planted in spring ‘p’.

Testing

array_seasons.c also contains a simple main function which allows you to test your seasons function.

Your seasons function will be called directly in marking.

The main function is only to let you test your seasons function

You can change the test array of structs in main to test seasons with other values.

Any changes you make to the main function will be ignored in marking.

Assumptions/Restrictions/Clarifications.

  • You mut not change the arguments that seasons takes.
  • seasons must return a struct tree.
  • You must not change the definition of struct tree.
  • You must not modify the array of trees that seasons is passed.
  • seasons should not call scanf, getchar or fgets.
  • seasons should not call printf, putchar or any other function which prints something.
  • You can assume, that you will always be given at least one tree that can be planted in spring.
  • Your submitted file may contain a main function. It will not be tested or marked.
  • You may define extra functions and call them.
You can run an automated code style checker using the following command:
1511 style prac_q1.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest exam_q1_season

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab10_exam_q1_season prac_q1.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 22 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●◌◌)
:

Practice Exam Q2 - Count the number of even numbers in a linked list

Note list_count_last.c uses the following familiar data type:
struct node {
    struct node *next;
    int          data;
};
count_last is given one argument, head, which is the pointer to the first node in a linked list. You are guaranteed the list will not be empty.

Add code to count_last so that its returns the number of values which are the same as the last value in the list.

For example if the linked list contains these 8 values:

16, 12, 8, 12, 13, 19, 21, 12

count_last should return 3, because 12 is the last value, and 12 occurs 3 times in the list (including the last number).

Testing

list_count_last.c also contains a main function which allows you to test your count_last function.

This main function:

  • converts the command-line arguments to a linked list
  • assigns a pointer to the first node in the linked list to head
  • calls count_last(head)
  • prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your count_last function will be called directly in marking. The main function is only to let you test your count_last function

Here is how you use main function allows you to test count_last:

cp -n /web/cs1511/21T3/activities/exam_list_count_last/list_count_last.c .
dcc list_count_last.c -o list_count_last
./list_count_last 16 12 8 12 13 19 21 12
3
./list_count_last 2 4 6 2 4 6
2
./list_count_last 3 5 7 11 13 15 17 19 23 29
1
./list_count_last 2 2 2 3 2
4

Assumptions/Restrictions/Clarifications.

count_last will never receive a linked list with no nodes. That is, the head will never be NULL

count_last should return a single integer.

count_last should not change the linked list it is given. Your function should not change the next or data fields of list nodes.

count_last should not use arrays.

count_last should not call malloc.

count_last should not call scanf (or getchar or fgets).

count_last should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style prac_q2.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest exam_list_count_last

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab10_exam_list_count_last prac_q2.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 22 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●●◌)
:

Practice Exam Q4 - Count the number of times the same number is in the same position in a pair of linked lists

Download exam_list_delete_last.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/exam_list_delete_last/exam_list_delete_last.c .

Your task is to add code to this function in exam_list_delete_last.c:

//
// Delete the last node in list.
// The deleted node is freed.
// The head of the list is returned.
//
struct node *delete_last(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;
}
Note list_delete_last.c uses the following familiar data type:
struct node {
    struct node *next;
    int          data;
};
delete_last is given one argument, head, which is the pointer to the first node in a linked list.

Add code to delete_last so that it deletes the last node from list.

delete_last should return a pointer to the new list.

If the list is now empty delete_last should return NULL.

delete_last should call free to free the memory of the node it deletes.

For example if the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

delete_last should return a pointer to a list with these elements:

16, 7, 8, 12, 13, 19, 21

Testing

list_delete_last.c also contains a main function which allows you to test your delete_last function.

This main function:

  • converts the command-line arguments to a linked list
  • assigns a pointer to the first node in the linked list to head
  • calls delete_last(head)
  • prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your delete_last function will be called directly in marking. The main function is only to let you test your delete_last function

cp -n /web/cs1511/21T3/activities/exam_list_delete_last/list_delete_last.c .
dcc list_delete_last.c -o list_delete_last
./list_delete_last 16 7 8 12 13 19 21 12
[16, 7, 8, 12, 13, 19, 21]
./list_delete_last 2 4 6 2 4 6
[2, 4, 6, 2, 4]
./list_delete_last 42
[]
./list_delete_last
[]

Assumptions/Restrictions/Clarifications.

delete_last should call free to free the memory for the node it deletes

delete_first should not change the data fields of list nodes.

delete_last should not use arrays.

delete_last should not call malloc.

delete_last should not call scanf (or getchar or fgets).

delete_last should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style prac_q4.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest exam_list_delete_last

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab10_exam_list_delete_last prac_q4.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 22 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●●◌)
:

Padding (moving all elements) a character list

Download padding_left.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/padding_left/padding_left.c .

Your task is to add code to this function in padding_left.c:

// Given a list of characters, move each character
// along one, putting "pad_character" in the first place,
// and ignoring the last character.
//
// Given the list 'c' 'e' 'l' 'l' 'o'; calling left_pad
// once with pad_character = 'x' results in the list:
// 'x' 'c' 'e' 'l' 'l'. Calling it again with pad_character = 'e'
// results in the list: 'e' 'x' 'c' 'e' 'l'
//
// Note that you can't malloc, or modify the lists' nodes
// You can only move data around the list.
void pad_left(struct character_node *characters, char pad_character) {
    // TODO: COMPLETE THIS FUNCTION
}

padding_left is written using the following structs that cannot be changed:

// A node in a linked list of characters.
struct character_node {
    char data;
    struct character_node *next;
};

The character_node struct holds a character, as part of a linked list of characters.

pad_left is given a pointer to a character_node, which is the first element in a list of characters. It is also given a character to "pad" with.

When you "pad" a character list, you iterate over the list and "push" every character along one. This means that the second character becomes whatever the first character was. The third becomes whatever the second was, and so on. The first character becomes pad_character, and what was previously the last character is "forgotten".

Note: You should not be creating new nodes in this exercise. You only need to move characters between nodes, you should not use malloc at all.

For example if a list of characters called characters looks like this:

abcdef

Then the following function is called:

pad_left(characters, 't');

The list characters would be:

tabcde
Hint: You will need to use multiple temporary character variables to complete this exercise!

Examples

dcc padding_left.c -o padding_left
./padding_left lights
a
alight
m
maligh
>
>malig
>
>>mali

dcc padding_left.c -o padding_left
./padding_left cello
x
xcell
e
excel

Assumptions/Restrictions/Clarifications.

struct character_node cannot be edited. It must be used as is.

The string_to_characters, print_characters, and free_characters functions will help you test and run your program. They cannot be edited and must be used as it is. You should not use them yourself in pad_left

pad_left cannot return a new head, so you cannot add to the head of the list. You should complete this task solely by moving around data - you will not need to malloc yourself.

Your submitted file may contain a main function. It will not be tested or marked.

You can run an automated code style checker using the following command:
1511 style padding_left.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest padding_left

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab10_padding_left padding_left.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 22 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●●●)
:

Solving a Nested Division Expression (old Exam q7)

Write a C program nested_divisions.c which takes in lines of input that will contain division expressions, then solves them.

An example of how your program should look is shown below.

Please enter a division expression: 1/2
0.500000
Please enter a division expression: (10/3)/5
0.666667
Please enter a division expression: (100/4)/(8/(4/2))
6.250000
Please enter a division expression: 
$

An expression is defined as having 3 components.

  1. dividend
  2. division sign ('/')
  3. divisor

Said expression will appear in the format dividend/divisor

The crux of this problem is that each dividend and divisor can contain a division expression themselves.

Take (80/2)/(10/3) as an example. The dividend is 80/2 and the divisor is 10/3. It is evident here that both of these are expressions within themselves. This type of nesting can occur multiple times and needs to be solved for.

The above example is easy to handle in your head, but more complex expressions might require you to draw them out to see what is going on. An example drawing below evaluating (10/((50/3)/5))/(5/2) is provided.

Division Example

Please enter a division expression: (10/((50/3)/5))/(5/2)
1.200000
Please enter a division expression: 
$

Your program should be somewhat flexible with brackets. As a result, an expression can be surrounded by as many pairs of brackets as it likes (without going over the max string size). Some examples of this are below.

Please enter a division expression: 80/2
40.000000
Please enter a division expression: ((((((((((80/2))))))))))
40.000000
Please enter a division expression: (10/30)/(5/3)
0.200000
Please enter a division expression: ((((10/30))))/((5/3))
0.200000
Note: You can still get high marks for this exercise if you do not handle these cases

Make sure you account for bracket ordering, as brackets will affect your final result, a simple example is below.

Please enter a division expression: 80/(2/2)
80.000000
Please enter a division expression: (80/2)/2
20.000000
Assumptions/Restrictions/Clarifications

  • The max string size given is 1024 characters long
  • You can assume only positive integers will be input (this also means no division by 0 can occur)
  • You can assume each opening bracket will have a corresponding closing bracket
  • You can assume input will always be valid
  • You can assume only numbers, brackets and division signs are in the input string. Importantly, there will be no spaces or decimal points.
  • If a dividend or divisor is an expression, it will always have brackets surrounding it
    • E.g. (10/3)/(5/2)
  • If a dividend or divisor is a number, it will never have brackets surrounding it
    • E.g. 5/2
You can run an automated code style checker using the following command:
1511 style nested_divisions.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest nested_divisions

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab10_nested_divisions nested_divisions.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 22 November 20:00 to obtain the marks for this lab exercise.

Exercise
(●●●)
:

Hard Challenge - Knight Moves (old Exam q8)

This question was taken from a past exam paper. It is an example of the hardest question at the end of the paper and it is usually expected that less than 5% of students can complete this question within the time constraints.

Write a C program knight_moves.c which prints sequences of moves which takes a knight from a specified square on a chessboard to another specified square on the chessboard.

A chessboard is an 8x8 square matrix. We label each square as below:

a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1

A knight makes an L-shaped move. It moves either two squares horizontally and one square vertically or two squares vertically and one square horizontally.

For example, a knight at d4 can move to one of eight squares: c2, e2, b3, b5, c6, e6, f3 or f5.

A move can not take a knight off the chessboard. Hence, a knight on square near the edge of the board will have fewer possible moves.

For example, a knight at a1 can move only to c2 and b3.

Write a C program which takes two arguments: a starting square and and a finishing square.

It should print a sequence of moves which take a knight from the starting square to the finishing square. This sequence of moves should be as short as possible.

In many cases there are multiple shortest sequences, your program must print all of the sequences in alphabetic order

For example:

dcc -o knight_moves knight_moves.c
./knight_moves d4 b3
d4 b3 
./knight_moves d4 a1
d4 b3 a1
d4 c2 a1
./knight_moves g2 b2
g2 e1 d3 b2
g2 e3 c4 b2
g2 e3 d1 b2
g2 f4 d3 b2

Assumptions/Restrictions/Clarifications

Your program must complete in 60 seconds when executed with dcc --valgrind

Your can assume there are two command-line arguments and they correctly identify squares on the board.

You can assume the starting and finishing squares are different.

No error checking required

You can run an automated code style checker using the following command:
1511 style knight_moves.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest knight_moves

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab10_knight_moves knight_moves.c

Note, even though this is a pair exercise, you both must run give from your own account before Monday 22 November 20:00 to obtain the marks for this lab exercise.

Submission

When you are finished each exercises make sure you submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember you have until Week 11 Monday 20:00 to submit your work.

You cannot obtain marks by e-mailing your code to tutors or lecturers.

You check the files you have submitted here.

Automarking will be run by the lecturer several days after the submission deadline, using test cases different to those autotest runs for you. (Hint: do your own testing as well as running autotest.)

After automarking is run by the lecturer you can view your results here. The resulting mark will also be available via give's web interface.

Lab Marks

When all components of a lab are automarked you should be able to view the the marks via give's web interface or by running this command on a CSE machine:

1511 classrun -sturec