Assignment 3 – C Programming

• The following 4 problems will be available as Assignment 3 on the online judging
system available at http://intranet.csc.liv.ac.uk/JudgeOnline2/
• You need to write a valid C program that solves each of these problems – it must
read the input, as specified in the problem description then print the solution to the given
problem for that input.
• Input is read from the standard input, in the same way that you read input from the
keyboard as shown in lectures (e.g., using scanf). Output is also printed to the standard output, as
you have seen (e.g., using printf).
• When you are satisfied that your programs work correctly, you must submit them
through the departmental submission system, as described below.
• You must also include a brief report describing your solutions to the problems. This
should be up to one side of A4 paper (although there is no penalty for a longer report) and should
give a description of how each of your solutions works. This should include describing the
algorithm used to reach the solution, describing your use of any C language features (that were not
discussed in lectures), identifying any resources that you have used to help you solve the problems
and describing any joint work you may have down with other students.
• This assignment is worth 40% of the total mark for COMP281
• 40% of the marks will be awarded for programs that correctly solve the
problem for all test cases. All problems are weighted equally and each counts for 20% of this
total.
• 50% of the marks will be awarded depending on the style, comments and
efficiency of the solution. All problems are weighted equally and each counts for 20% of this
total.
• 10% of the marks will be awarded for the quality and depth of the
accompanying report
• See separate marking guidelines for more details.
Submission Instructions
• Name each of your c files with the problem number; i.e., 1046.c, 1048.c,
1049.c, and 1050.c. Place all four of your C files and your report (in .pdf format) into a
single zip file.
• Submit this zip file using the departmental submission system at
http://www.csc.liv.ac.uk/cgi-bin/submit.pl
Only the file submitted through this link will be marked
• The deadline for this assignment is March 18th,
4:00pm
• Penalties for late submission apply in accordance with departmental policy as
set out in the student handbook, which can be found at:
http://www.csc.liv.ac.uk/student/ugpdfhandbook.pdf
Problem 1046
Title: Sum of Adjacent Numbers
Description
In the 3x3 grid below, the greatest sum of two adjacent numbers in any direction (up, down, left, right, or
diagonally) is 22+23=45.
21 22 23
20 10 11
17 16 15
Input n and m. 1<=n<=100. 1<=m<=n. Then input a n x n grid. All integers in the grid are from 0 to 1000.
Output the greatest sum of m adjacent numbers in any direction (along straight line only).
You are required to use malloc to dynamically allocate just enough space for storing the grid.
Input
n, m, and then followed by a n x n grid
Output
The greatest sum of m adjacent numbers in any direction
Sample Input
3 2
21 22 23
20 00 11
17 06 15
Sample Output
45
Problem 1048
Title: Sort and Search for Dates
Description
Input n (1<=n<=10000) and then followed by n lines. Each line corresponds to a valid date, consisting of
one string ("January", "February", ..., or "December"), one integer between 1 and 31, and one two digit
integer representing the year (from 90 to 99, and then from 00 to 12). You do not have to worry about date
validation. All dates in the input are valid dates.
Please use structures to store the dates. Please use malloc to dynamically allocate just enough space for n
structures. You are asked to sort the dates chronologically using the built-in qsort function. Please output the
sorted list, one date per line, from most recent to oldest date. Please also use the built-in bsearch function to
allow for a user query to check whether a specific date is in the list, and output either "Yes" or "No".
Input
n and then followed by n dates.
Output
sorted list of dates, and whether a date input by the user (e.g. January 1 00) is in the list
Sample Input
10
January 1 01
January 1 00
February 28 99
July 17 12
September 10 12
July 1 00
June 30 90
August 25 06
May 27 08
October 1 03
January 1 00
Sample Output
September 10 12
July 17 12
May 27 08
August 25 06
October 1 03
January 1 01
July 1 00
January 1 00
February 28 99
June 30 90
Yes
Problem 1049
Title: Priority Queue
Description
A priority queue is an abstract data type, which is like a regular queue, but additionally, each element is
associated with a "priority value". In this problem, the queue elements are integers from 10000 to 19999, the
priority values are integers from 1 to 10 (10 corresponds to the highest priority).
The input consists of a list of operations, one operation per line. A sample input looks like the following:
Insert 10000 2
Insert 10000 2
Insert 10000 3
Insert 19444 9
Pop
Insert 10331 3
Pop
Pop
Pop
Pop
Pop
The operations are defined as follows:
• Insert x y: Add element x (10000<=x<=19999) to the queue with an associated priority value y
(1<=y<=10). The queue allows duplicate elements. In the above example, we inserted 10000 three
times. After these three insertions, there are two elements of value 10000 and priority 2 in the queue,
and there is one element of value 10000 and priority 3 in the queue. You don't need to check the
validity of the input. That is, if an input line says "Insert x y", then x is guaranteed to be between
10000 and 19999, and y is guaranteed to be between 1 and 10.
• Pop: Identify the element with the highest priority from the queue, output the element, and remove it
from the queue. If the queue is empty, then output -1 (the queue remains empty). If there are multiple
queue elements sharing the same highest priority value, then we remove and output the element that
has the highest priority value and joined the queue the earliest.
For the above sample input, the sample output should be:
19444
10000
10331
10000
10000
-1
Explanation of the example: At the moment of the first "Pop", 19444 has the highest priority value 9. At the
moment of the second "Pop", both 10331 and 10000 share the highest priority value 3. We remove and
output 10000 because it joined the queue earlier. At the moment of the third "Pop", 10331 has the highest
priority value 3. Finally, at the moment of the sixth "Pop", the queue is empty.
A priority queue can be implemented using a variety of methods. Your mark for this problem depends on the
efficiency of your implementation.
Time efficiency: The time efficiency of your implementation is judged based on the speed of insert and pop
when there are a huge number of elements in the queue.
Memory efficiency: The memory consumption of your queue should be dynamically adjusted based on the
number of elements in it.
Input
A list of operations, one per line
Output
Corresponding output
Sample Input
Insert 10000 2
Insert 10000 2
Insert 10000 3
Insert 19444 9
Pop
Insert 10331 3
Pop
Pop
Pop
Pop
Pop
Sample Output
19444
10000
10331
10000
10000
-1
Problem 1050
Title: Flight Travel Planner
Description
You are working for a travel agency and are asked to write a computer program that can provide travel
advice between cities based on a given map. The first line of the input of the program contains one integer n.
n (2<=n<=10000) is the number of cities on the map. The second line of the input also contains an integer,
m, (2<=m<=10000), which indicates the number of connections that will follow in the input below. Then,
starting from the third line of the input, each line contains two integers from 1 to n, i.e. the connections
between the cities. If a line says "a b", then it means that there is direct flight between city a and city b.
There will be m of such connections. The last line also contains a pair of cities, say "c d", which will
represent a query: "is there a connecting flight between c and d?"
Here is one sample input:
6
7
6 4
3 4
5 4
3 2
5 2
5 1
2 1
1 6
For this flight network, there exists at least one route between every pair of cities. For example, between city
5 and 6, there exists a route with 1 stop at city 4.
Given the input and the query, answer whether there is a route between cities c and d (note that this
connection can be indirect). The output should be "Yes" or "No".
Let x be the total number of lines of the input. We know for sure that x is much smaller than n square. Your
implementation should take this into consideration (for the purpose of saving memory).
For example, let us consider the case with n=10000 and x=10000 (so x is much less than n square). One easy
way to represent a graph in memory is to use a n by n matrix. If the element in the i-th row and the j-th
column equals 1, then that means node i and j are directly connected (0 means not directly connected). The
memory consumption of the matrix representation is at least n square over 2 bits (each element only needs 1
bit; also, we only need to store half of the matrix due to symmetry). When n=10000, n square over 2 bits is
just too much. You should find better ways to represent graphs in memory.
Input
Flight network
Output
Yes or No
Sample Input
6
7
6 4
3 4
5 4
3 2
5 2
5 1
2 1
1 6
Sample Output
Yes
Sample Input 2
5
3
4 3
3 2
5 1
1 4
Sample Output 2
No