• In the following, you will find 5 problems that constitute Assignment 3. They will be also available on the online judging (OJ)

• 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.

o Even if the program is not correct, still submit whatever you have! You can still earn points if

certain parts of the code are done right.

• You must also include a brief report describing your solutions to the problems. This should be maximum 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) and identifying any resources that you have used to help you solve the problems.

• This assignment is worth 40% of the total mark for COMP281

• 50% 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

• 40% 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

• as for the first assignment, name each of your c files according to the problem number. That is, if a problem has number xxxx, than name that file xxxx.c. For instance, problem 1029 should be put in a file called 1029.c.
• Place all five of your C files and your report (in .pdf format) into a single zip file

• Before you submit your solutions, please first test them using the online judge. You are required to

include the “Result” and the “RunID” in your C code as comments. The OJ provides a RunID. RunIDs are not problem IDs.

• Example:

the problem is 10xx

The solution has been accepted by the OJ, and the runID is 2033. You add to your code: /* 2033 Accepted */ to 10xx.c

• Result is one of the following: Accepted, Wrong Answer, Presentation Error, Time Limit Exceeded, Memory Limit Exceeded, Output Limit Exceeded, Runtime Error, Compile Error

• Submit this zip file using the departmental submission system.
• Only the file submitted through this link will be marked.

• The deadline for this assignment March 17, 5pm.
• Penalties for late submission apply in accordance with departmental policy as set out in the student handbook.

1. Problem 1046

Title: Sum of Adjacent Numbers!

Description

In the 3×3 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 of the above directions (along straight line only). Keep in mind that there are 2 diagonal directions that you will need to check.

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

2. 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, the number of dates to sort,

• followed by n dates,

• followed by a user query in format day month year (e.g. “1 1 00” or “31 3 68”).

Output

• Sorted list of dates,

• followed by “Yes” or “No” to indicate whether the query 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

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

3. Problem 1053

Title: Stack Implementation

Description

In computer science, a stack is a last in, first out (LIFO) data structure. There are two fundamental operations, called push and pop. The push operation adds a new item to the top of the stack, or initializes the stack if it is empty. The pop operation removes an item from the top of the stack. You are asked to implement a stack using C. The stack elements should be stored in heap memory, using malloc, and freed when popped

Input

Each line of input specifies one operation. For the push operation, the format is “Push x”, where x is a positive integer. For the pop operation, the format is “Pop”.

Output

For operation “Push x”, the corresponding output line should be “x pushed”. For operation “Pop”, the corresponding output line should be “x popped”, where x is the item removed from the top of the stack (if the stack is empty, then the output should be “-1 popped”).

Sample Input

Push 10

Push 20

Push 30

Pop

Pop

Push 40

Pop

Pop

Pop

Sample Output

10 pushed

20 pushed

30 pushed

30 popped

20 popped

40 pushed

40 popped

10 popped -1 popped

Hint

Stacks are easily implemented making use of a linked list.

4. 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”. For 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

Brief explanation: 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

Hint

Again, regular queues are easily implemented using linked lists.

5. 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. 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

• 4

5 4

• 2

5 2

5 1

2 1

1 6

This sample input can be visualized as follows:

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

• 4

5 4

• 2

5 2

5 1

2 1

1 6

Sample Output

Yes
Place your order now for a similar paper and have exceptional work written by our team of experts to guarantee you A Results

Why Choose US

6+ years experience on custom writing
80% Return Client
Urgent 2 Hrs Delivery
Your Privacy Guaranteed
Unlimited Free Revisions