This is your last take home lab exercise. All take home labs are automatically graded by the CourseMarker and do not count as part of the continuous assessment grades. However, to better prepare yourself for the sit-in labs (which constitutes 5% weightage of the course each) you are strongly encouraged to attempt all questions.
In general, you should use the standard I/O using
scanf for input and
printf for output in your
programs, unless otherwise stated.
If you have any questions, you may post your queries in the IVLE forum. You
should take note that your program output should exactly match the
output given in the sample run.
There is no deadline for your take home labs. However you are encouraged to practice them as early as possible.
In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It works efficiently for the smaller primes (below 10 million). It was created by Eratosthenes, an ancient Greek mathematician. (Wikipedia)
The idea behind this method is to use a preprocessing step to first identify all prime numbers up to a maximum number n. After which multiple queries is a simple matter of array lookup. In your program, in the interest of memory, the maximum number you would implement is 10,000 (otherwise you would be out of memory). The algorithm works as follows:
While the algorithm seems complicated, the idea is quite simple:
Once the algorithm is complete, if we want to find out if n is prime, we simply look at A[n]. If A[n] is 1, than n is prime, otherwise it is not prime.
You should terminate each output with a new line character ("\n").
Your input consist of multiple lines of numbers which takes on a value either between 2 to 10,000 (inclusive) or 0. The last input is always a 0 and you may terminate your program once you read in the input 0. Your output is a line which can be either "prime" or "not prime" which follows immediately after every input. There is no output when the input is 0.
Sample run using interactive input (user's input shown in blue; output shown in bold purple):
| 92 not prime 93 not prime 94 not prime 95 not prime 96 not prime 97 prime 98 not prime 99 not prime 100 not prime 101 prime 102 not prime 0 |
Your program should be coded in a single file called "Sieve.c"
Submit your program through CourseMarker.
You have learnt that due to memory limitations, all data types have a maximum range. For example on many systems short (having 16 bits) has a value range of -32,767 to 32,767 and int (having 32 bits) has a value range of -2,147,483,648 to 2,147,483,647.
When dealing with large numbers, we can use the float or double data types which has a maximum value with an exponent of 308. However the number may not be exact and is a close approximation of the actual value if the exact number has multiple digits.
Many serious mathematical computations require very exact computations. The truncation of even a single digit may cause a system to fail (e.g. time coordination in space shuttle launches, banking applications), and in this case using floating point values may not be sufficient.
In this exercise, you are to write a program that can perform simple computations with very large numbers up to 1000 digits. Each very large number is always a positive number. The idea to do so is very simple, you will use an array of size 1000, with each slot storing a single digit. It is up to you in your implementation how you want to store the number (starting from the left end, or starting from the right end).
The exercise will be broken into multiple parts detailed below. You are to complete all parts.
You are not allowed to use string or character functions. Therefore you are not to include string.h and ctype.h.
Part 1 Reading in the input
The first line of the input are two numbers (separated by a space) n and m which denotes the number of digits in the first and second number (in that order). Both n and m must be <= 1000.
The second line has exactly n digits which represents the first large number.
The third line has exactly m digits which represents the second large number.
The forth line is a single character denoting the operator which can be any of the following:
You will perform the respective mathematical operations on the first and second large numbers indicated by the character. The mathematical operation is always n operator m, for example if the operator is '+', then we do n + m.
Part 2 add
Write a function add which takes in two arguments p and q which are very large numbers and output a very large number containing the sum of p and q (i.e. p + q). Both p and q are are always positive numbers.
Think of how your perform addition of two numbers. See the notes section of this document.
The outcome of an addition will never exceed 1000 digits.
Part 3 minus
Write a function minus which takes in two arguments p and q which are very large numbers output a very large number containing the subtraction of p by q (i.e. p - q). You may assume that p is always larger then q and that both are always positive numbers.
The outcome of a subtraction will always be a positive number.
This would simply be a modification of the previous part.
Part 4 output
Finally you are to output the computation in a new line.
Sample run using interactive input (user's input shown in blue; output shown in bold purple):
| 20 20 12345678901234567890 12345678901234567890 + 24691357802469135780 |
Another sample run:
| 20 20 24691357802469135780 12345678901234567890 - 12345678901234567890 |
Your program should be coded in a single file called "BigNumbers.c"
Submit your program through CourseMarker.
Remember to clear the buffer before reading the character! Do not use fflush but instead consume the newline character using scanf with the character specifier.
We revisit primary school mathematics in this exercise. Recall how you did simple mathematical operations to add, subtract, multiply and divide using carry overs?
E.g
1 1 1 1
1 2 3 4 5 6 7 8
+ 1 2 3 4 5 6 7 8
-------------------------------------
2 4 6 9 1 3 5 6
In
Computer
Architecture, a cache is a collection of data duplicating some original
values in the computer memory, where the original data is expensive to fetch
(owing to longer access time) compared to the cost of reading the cache. In
other words, a cache is a temporary storage area where frequently accessed data
can be stored for rapid access.
An analogy of a cache would be a librarian. When requested for some books, a
librarian would have to walk to the shelves to pick up the books. However, for
frequently requested books, the librarian may put them into a bag she carries so
that she can quickly produce them on request.
A computer typically has multiple levels of memory caches. However, to keep
things simple (as we always do), we will only consider a computer with 1 level
of cache to supplement the main memory. The main memory is equivalent to the
library shelves, while the cache is like the librarian's bag.
When we look up the cache for some data and find it there, it is called a cache
hit. Otherwise, it is called a cache miss. A cache hit requires only 20
nanoseconds. However in the event of a cache miss, since we have to copy the
data from the main memory into the cache before we can read it from the cache,
it would require 100 nanoseconds.
We assume the cache is initially empty. When the cache is full and we need to
bring in some data from the main memory into the cache, we have to decide which
existing item in the cache is to be replaced by the incoming item. We shall
replace the least recently used item in the cache in this case.
We shall use an example below to illustrate the states of a cache. We assume
that the cache can hold 8 items.
Initial state of the cache
Cache:
[1][5][9][8][2][7][12][13]
Timestamp: [0][7][4][1][5][6][ 3][ 2]
Current time : 8
The cache array contains the items in each slot of the cache. The timestamp
array denotes the last time a particular item was used. For example, item "1"
(at index 0) was used at the 0th unit of time, and item "5" was used at the 7th
unit of time, and so on. The current time is 8 now. If now the operating system
(OS) requests for item "1", we see that there is a cache hit, and consequently,
item 1 can be retrieved from the cache in 20 nanoseconds. We also update the
timestamp of item "1" to 8 and increase the current time by 1 unit. See the new
state of the cache below.
Cache after retrieving item 1.
Cache:
[1][5][9][8][2][7][12][13]
Timestamp: [8][7][4][1][5][6][ 3][ 2]
Current time : 9
Now (at time 9), if the OS requests for item "14", we see that there is a cache
miss. In this case, the OS has to fetch the data from the memory and put it into
the cache which takes 100ns. Since the cache is already full, we replace the
LEAST RECENTLY USED item with the newly retrieved item from the memory. In this
case the least recently used item is item 8 with a timestamp of 1. See the new
state of cache below.
Cache after retrieving item 14.
Cache:
[1][5][9][14][2][7][12][13]
Timestamp: [8][7][4][ 9][5][6][ 3][ 2]
Current time : 10
In this exercise, we want to simulate memory access on a cache with 8 slots, and
a main memory of arbitrary large size. You may assume that all requested items
are in the main memory and the initial state of the cache is all empty. The
input is a series of positive numbers which represent the items required, with the last input being a
-1. Your output should be a statement
denoting the total time required for all operations. Recall that a cache hit
takes 20ns, and a cache miss takes 100ns.
The following is always true about this exercise:
| 19 21 3 10 7 -1 Total time: 500ns. |
Another sample run
| 100 300 200 300 100 -1 Total time: 340ns. |
Your program should be coded in a single file called "Cache.c"
Submit your program through CourseMarker.
Scrat, a sabre-toothed squirrel of Ice Age fame, needs to carry his acorn
through a hilly valley and he needs your help. Being of small brain, he is not
able to find the best path through the valley. The "best path" is defined to be
the path that minimizes his total walking effort (remember that he still needs
to guard his acorn jealously!). To simplify our problem, we will find a good
path which is not necessarily the best or shortest path.Scrat's world is modeled by an NxN matrix, and Scrat's task is to walk from point (0, 0) to point (N-1, N-1). Each entry of the matrix contains a number between 0 (inclusive) to 100 (not inclusive), which represent the level of walking difficulty (0 = easiest, 99 = hardest). Your task is to write a program that automatically finds a good path through Scrat's world, so that he can minimize his walking effort and maximize his efforts to guard his acorn.
Your program should begin by asking the user for the size N (2 <= N <= 25) of the world (Scrat's world is always square), and then fill the entries with random integer values between 0 (inclusive) and 100 (not inclusive). The function int_rand to generate the random numbers has been given to you. So suppose that the user wants a 4x4 world, and your program generated the following matrix, where (0,0) is the top left hand corner and (0,3) is the top right hand corner:
To generate the world, you should generate the numbers from the topmost row, from left to right to the last row, from left to right. So the matrix below generates 25 17 99 99 75 ... in that order. You should note that the coordinate system used in this lab is different from the one used in previous labs.
| 25 | 17 | 99 | 99 |
| 75 | 99 | 15 | 99 |
| 99 | 99 | 99 | 22 |
| 99 | 99 | 99 | 80 |
Your program should now print his path in terms of (row, column) coordinates, and print out his total walking effort. So in the example above, your program would print out this (please follow the sample output precisely):
Scrat should walk from: (0, 0) to (0, 1) (0, 1) to (1, 2) (1, 2) to (2, 3) (2, 3) to (3, 3) His walking effort is 159.
Note that in order for your program to be correct, it must start from (0, 0) and end at (N-1, N-1), regardless of the cost at (N-1, N-1). Scrat's movements are also restricted: At each point, he can only either go right (e.g. from (0, 0) to (0, 1)), down (e.g. from (0, 0) to (1, 0)), or diagonally bottom right (e.g. from (0, 0) to (1, 1)); you are to choose the square with the least cost. In the event of a tie (i,e right, diagonally bottom right and/or bottom tiles have the same cost), Scrat will always try to move in this priority: diagonally bottom right first, then right, then down.
The input consist of only two numbers. The first number is n denoting the size of the world (which is n by n). The second number is a positive integer which denotes the seed.
The output is 1 + n + 1 + k + 1 lines. The output is as follows:
To print the world in the nice formatted output, you should use the specifier "%-3i ", (note the space after i) as such:
printf("%-3i ", m[i][j]);
Sample run using interactive input (user's input shown in blue; output shown in bold purple). The left panel is the sample run, the right panel shows a brief explanation.
| 4 1 Scrat's world: 51 17 30 53 94 17 70 22 49 12 8 38 27 36 98 53 Scrat should walk from: (0, 0) to (1, 1) (1, 1) to (2, 2) (2, 2) to (2, 3) (2, 3) to (3, 3) His total walking distance is: 167 |
Choose diagonal 17 because, we approach our endpoint faster Scrat isn't very smart, so he chose to walk to the nearest square at (2,3) instead of heading directly to (3, 3) |
Another sample run
| 5 0 Scrat's world: 0 65 30 67 10 51 48 60 36 25 37 82 17 29 64 78 98 80 46 53 62 24 70 71 97 Scrat should walk from: (0, 0) to (1, 1) (1, 1) to (2, 2) (2, 2) to (2, 3) (2, 3) to (3, 3) (3, 3) to (3, 4) (3, 4) to (4, 4) His total walking distance is: 290 |
Your program should be coded in a single file called "Scrat.c"
Submit your program through CourseMarker.