Week 10 Laboratory Exercises
Objectives
- Become familiar with the environment used for the final exam
- practice coding under exam conditions
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/21T1/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.
Because the deadline for this lab has passed, we have moved all the questions to be regular lab questions. While the prac exam site works, the submission commands have been disabled.
Submit them following the below instructions instead.
Returning to normal lab work
The remaining lab exercises are completed the usual way.
Exercise — individual:
Practice Exam Q1 - Count the number of small values in an 2D array
// Return the maximum sum of a row in the 2D array.
int max_row_sum(int array[TEST_ARRAY_SIZE][TEST_ARRAY_SIZE], int side_length) {
// PUT YOUR CODE HERE (you must change the next line!)
return 42;
}
For example if the array is a 3 height by 3 width array
6, 7, 8, 1, 1, 9, 3, 2, 8
Your function should return 21 because:
6 + 7 + 8 == 21 1 + 1 + 9 == 11 3 + 2 + 8 == 13
As you can see, the largest row sum is 21.
Testing
array_2d_max_row_sum.c also contains a simple main function which allows you to test your max_row_sum function.Your max_row_sum function will be called directly in marking. The main function is only to let you test your max_row_sum function
Assumptions/Restrictions/Clarifications.
max_row_sum should return a single integer.max_row_sum should not change the array it is given.
max_row_sum should not call scanf (or getchar or fgets).
max_row_sum can assume the array contains at least one integer.
max_row_sum function should not print anything. It should not call printf.
Your submitted file may contain a main function. It will not be tested or marked.
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_array_2d_max_row_sum
When you are finished working on this exercise,
you must
submit your work by running give:
give cs1511 lab10_exam_array_2d_max_row_sum prac_q1.c
You must run give
before Monday 26 April 20:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Exercise — individual:
Practice Exam Q2 - Count the number of even numbers in a linked list
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/21T1/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.
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 must
submit your work by running give:
give cs1511 lab10_exam_list_count_last prac_q2.c
You must run give
before Monday 26 April 20:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Exercise — individual:
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/21T1/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;
}
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/21T1/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 deletesdelete_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.
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 must
submit your work by running give:
give cs1511 lab10_exam_list_delete_last prac_q4.c
You must run give
before Monday 26 April 20:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Exercise — in pairs:
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/21T1/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".
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
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.
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 26 April 20:00
to obtain the marks for this lab exercise.
Reflection #4
Don't forget that before the assigment is due (i.e. 8pm on Friday) you will need to complete Reflection #4
Find the instructions for the reflection here.
Follow the instructions here to copy the blog template and create a blog.
You will need to use the blog template to complete this exercise!
Challenge Exercise — individual:
Hard Challenge - Knight Moves, Final Question from a previous exam
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
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 must
submit your work by running give:
give cs1511 lab10_knight_moves knight_moves.c
You must run give
before Monday 26 April 20:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Submission
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