C programming

COMP281 Resit Assignment 3 – C Programming

• The following 4 problems will be available as Resit 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., 1052.c, 1048.c, 1074.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 August 17th, 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 1052 Title: Tree route in a triangle Description By starting at the top of a right-angled triangle (see example in the sample input) and moving to one of the adjacent numbers (vertically or diagonally) on the row below, one can compute the maximum sum of numbers over different routes. In the sample input for instance the maximum total from top to bottom is 3+7+4+9=23. Input n, followed by a triangle of level n. (The example triangle's level is 4.) Output the maximum total from top to bottom. Input n and then followed by a triangle of level n Output Maximum total from top to bottom Sample Input 4 3 7 4 2 4 6 8 5 9 3 Sample Output 23 Problem 1048 Title: Sort and Search for Dates II 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 date to oldest. 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, followed by a user query in format day month year (e.g. 1 1 00). Output sorted list of dates, and whether a date input by the user (e.g. 1 1 00 day month year) 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 1 1 00 Sample Output June 30 90 February 28 99 January 1 00 July 1 00 January 1 01 October 1 03 August 25 06 May 27 08 July 17 12 September 10 12 Yes Problem 1074 Title: 3D Minesweeper Description

Your program will be given the positions of mines in a 3 dimensional grid. It will then answer a user query indicating how many mines there are in a specific location in the grid. You will be given the size of the board and the positions of n mines on the board. There may be more than one mine in the same position. Your task is to print the number of mines in the grid at a specific location (given by coordinates). You should use calls to malloc to allocate enough memory to store a suitably sized grid. Input Three  integers,  x  y  z  in  the  first  line,  separated  by  spaces,  indicating  the  size  of  the  board  (x*y*z)   where 1 ≤ x ≤ 100,000, 1 ≤ y ≤ 100,000, and 1 ≤ z ≤ 100,000.   An  integer  n    in  the  second  line,  indicating  the  number  of  mines  (which  may  be  up  to  INT_MAX).    

3n  integers  in  the  third  line  that  describe  the  positions  of  the  mines,  in the format X1 Y1 Z1 X2 Y2 Z2 … Xn Yn Zn Followed by a query (position in the grid) in the format of Xq, Yq, Zq. The grid starts at position 1, so the valid positions for any coordinate Xi Yi Zi are described by 1 ≤ Xi ≤x  ,  1≤ Yi ≤y  ,  and1≤ Zi ≤z. There  will  be  enough  memory  available  to  store  the  whole  grid.    There  could  be  possibly  (very)  many  mines   in  the  same  position.   Output The number of mines in the location of the query. Sample Input 3 3 3 3 1 1 1 2 2 2 1 1 1 1 1 1 Sample Output 2 Problem 1050 Title: Flight Travel Planner II 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.

Here is one sample input:

6

7

6 4

3 4

5 4

3 2

5 2

5 1

2 1

For this example 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 answer whether there is a route between any two cities in the input (note that connections or routes 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 Sample Output Yes Sample Input 2 5 3 4 3 3 2 5 1 Sample Output 2 No