Assignment 2 – C Programming

! The following 5 problems will be available as Assignment 2 on the online judging system available
at http://intranet.csc.liv.ac.uk/JudgeOnline/
! 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 done with other students.
! This assignment is worth 30% 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
• Name each of your c files according to the problem number; i.e.,
1029.c,1032.c,1041.c,1043.c and 1044.c. Place all five of your C files and your report
(in .pdf format) into a single zip file.
• All question have also been/will also be posted on www.csc.liv.ac.uk/JudgeOnline2
• 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.
o 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 */
o 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 at :
http://www.csc.liv.ac.uk/cgi-bin/submit.pl
The deadline for this assignment is Wednesday March 4th, 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 1029
Title: ROT R 3
Description
ROT R 3 ("Rotate Right by 3") is a simple substitution cipher to encode letters. Applying ROT R 3 to a
piece of text merely requires examining its alphabetic characters and replacing each one by the letter 3
places further or 'right' of it along in the alphabet, wrapping back to the beginning if necessary. A becomes
D, B becomes E, and so on up to W, which becomes Z, then the sequence continues at the beginning of the
alphabet: X becomes A, Y becomes B, and Z, becomes C. Only those letters, which occur in the English
alphabet, are affected; numbers, symbols, whitespace, and all other characters are left unchanged.
Input
One line of characters (ends with EOF)
Output
The result after applying ROT R 3 to the input
Sample Input
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!
Sample Output
DEFGHIJKLMNOPQRSTUVWXYZABCdefghijklmnopqrstuvwxyzabc!
Problem 1032
Title: String search
Description
Input three strings s1, s2, and s3 (one for each line). They may contain whitespaces. Output the number of
times s3 and s2 occur as a substring of s1.
For example, if the input strings are "hello world”, “europe” and "wor", then the output should be “0 1”. As
another example, if the input strings are "hello world hello”, “hello world” and "hel", then the output should
be “1 2”. If the input strings are "hello world”, “hello” and "helo", then the output should be “1 0”.
You are not allowed to use system functions defined in string.h.
Input
s1, s2 and s3.
Output
Two numbers.
Sample Input
Hello World! Hello
Hello
World
Sample Output
2 1
Problem 1041
Title: Dot Product of two matrices
Description
Input three positive integers n, m, and p. Then input two matrices. The first one is a n (rows) by m (columns)
matrix. The second one is a m (rows) by p (columns) matrix. Output the matrix product (should be n rows
by p columns). You are required to store the matrices in heap memory.
Input
n, m, p, and two matrices
Output
Product of these two matrices
Sample Input
4
3
2
14 9 3
2 11 15
0 12 17
5 2 3
12 25
9 10
8 5
Sample Output
273 455
243 235
244 205
102 160
Problem 1043
Title: Sort Strings
Description
Input n and then followed by n strings, one string per line. Subsequently this is followed by input m, and
then followed by m strings (one per line). Strings consist of lowercase English letters only. The maximum
string length is 100 (at most 99 letters, plus '\0'). However, most strings are very short. That is, you should
dynamically allocate just enough memory to store each string. You should also dynamically allocate just
enough space for storing n+m string pointers.
Please sort these n+m strings based on their lengths in descending order. String lengths are unique. There
will be no ties. Output the sorted list of strings.
Input
n and then followed by n strings. m and then followed by m strings.
Output
Sorted list, one string per line
Sample Input
5
abcdefghijk
abcde
a
abcdefgaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
zzzzzzzzzzzzzzzzzzzzzz
3
bb
cccc
hhhhhhhhhhhhhh
Sample Output
abcdefgaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
zzzzzzzzzzzzzzzzzzzzzz
hhhhhhhhhhhhhh
abcdefghijk
abcde
cccc
bb
a
Problem 1044
Title: 2 raised to the power of x
Description
2^x stands for 2 raised to the power of x. 2^4=16 and the sum of its digits is 1+6=7. 2^5=32 and the sum of
its digits is 3+2=5. Input x. x is a nonnegative integer that is at most 10000. Output the sum of the digits of
2^x.
Hint: Problem 1036 is a good start.
Input
x
Output
result (one integer)
Sample Input
4
Sample Output
7