Important: Please read Lab Guidelines before you continue.
This lab consists of 3 exercises. The best 2 out of 3 exercises will be used to determine your attempt mark.
The main objective of this lab is on the use of arrays to solve problems.
The maximum number of submissions for each exercise is 12.
If you have any questions on the task statements, you may post your queries on the relevant IVLE discussion forum. However, do not post your programs (partial or complete) on the forum before the deadline!
Important notes applicable to all exercises here:
This is an extension of an earlier lab Nanotable 0. Now with arrays, our Nanotable program can be enhanced. Tables of data can be stored as arrays.
Nanotable1 has the following features (new features highlighted in !!):
Sample runs using interactive input (user's input shown in blue). Note that the first two lines (in green below) are commands issued to compile and run your program on UNIX.
You would need to use the -lm option in gcc if you use some math function in your program.
Sample run #1: (insert, sum, ave)
$ gcc -Wall -lm nanotable1.c -o nanotable1 $ nanotable1 Welcome to Nanotable! Type "help" for more information... Waiting for command... insert Please input the student's ID... 1 Please input the student's score... 90 Waiting for command... insert Please input the student's ID... 2 Please input the student's score... 80 Waiting for command... insert Please input the student's ID... 5 Please input the student's score... 100 Waiting for command... sum The sum of score is 270 Waiting for command... ave The average of score is 90 exit See you!
Sample run #2: (insert, rank)
Welcome to Nanotable! Type "help" for more information... Waiting for command... insert Please input the student's ID... 1 Please input the student's score... 90 Waiting for command... insert Please input the student's ID... 2 Please input the student's score... 80 Waiting for command... insert Please input the student's ID... 3 Please input the student's score... 80 Waiting for command... rank Please input the rank (1 - 3)... 5 Invalid rank: 5 Please input the rank (1 - 3)... 1 ID: 2, Score: 80 Waiting for command... rank Please input the rank (1 - 3)... 2 ID: 3, Score: 80 Waiting for command... rank Please input the rank (1 - 3)... 3 ID: 1, Score: 90 Waiting for command... exit See you!
Sample run #3: (insert, init, sum)
Welcome to Nanotable! Type "help" for more information... Waiting for command... insert Please input the student's ID... 1 Please input the student's score... 100 Waiting for command... sum The sum of score is 100 Waiting for command... init Initializing table... Waiting for command... sum The table is empty Waiting for command... exit See you!
The time here is an estimate of how much time we expect you to spend on this exercise. If you need to spend way more time than this, it is an indication that some help might be needed.
Given a list, a k-interval subsequence is a sublist where each element in the subsequence is k positions away from the next element in the subsequence.
For example, Figure 1a shows a list with 5 elements {-2, 3, -3, -1, 6}. Figure 1b shows the two 2-interval subsequences {-2, -3, 6} and {3, -1}. Figure 1c shows the three 3-interval subsequences {-2, -1}, {3, 6}, and {-3}. In general, there are k k-interval subsequences derivable from a list. You should have noticed that the 1-interval subsequence is the list itself.
Your task is to find the maximum sum of a k-interval subsequence among all k-interval subsequences. You are to report the solution subsequence: its sum, its interval k, and its starting position.
For the above example, all the k-interval subsequences and their respective sums are listed below:
Hence, the solution is the 3-interval subsequence starting at position 1 with a sum of 9.
There might be more than one subsequence with the maximum sum. For example, given the list {1, 5, 5 -6, -2, -2}, there are two subsequences with the maximum sum of 5:
You should report the former as its value of k (the interval) is smaller.
A skeleton program is given. You are to complete the given function
void sum_subsequence(int arr[], int size, int ans[])
You are NOT to change the function header given above, or marks will be deducted.
As the task is to find 3 values: the maximum sum, the interval, and the starting position, the ideal approach is to use address parameters or structure. However, we have not covered either of these topics yet. Hence, for the moment, we will use a 3-element integer array ans to hold the values, which are incidentally all integers (hence we can use an array):
You may assume that there is at least one element and at most 10 elements in the list.
Sample runs using interactive input (user's input shown in blue; output shown in bold purple). Note that the first two lines (in green below) are commands issued to compile and run your program on UNIX.
$ gcc -Wall subsequence.c -o subsequence $ subsequence Enter number of elements: 1 Enter 1 element: 123 Max sum 123 of 1-interval subsequence starting at position 0.
Second sample run:
$ subsequence Enter number of elements: 5 Enter 5 elements: -2 3 -3 -1 6 Max sum 9 of 3-interval subsequence starting at position 1.
Third sample run:
$ subsequence Enter number of elements: 6 Enter 6 elements: 1 5 5 -6 -2 -2 Max sum 5 of 4-interval subsequence starting at position 2.
The time here is an estimate of how much time we expect you to spend on this exercise. If you need to spend way more time than this, it is an indication that some help might be needed.
This exercise is tedious to code. Please brace yourself for long hours of preparation, coding and testing!
In the far far land of Maruku, there lives a population of optimistic frogs. Overly optimistic actually. Their life philosophy revolves around the idea of being forward looking. They believe that there is only one way in life, which is to move forward. Frogs who turn back are condemned in the society.
One fine day, two clans of frogs meet at the bridge of Marukunan River. The problem is, they are on different ends trying to cross the bridge. A nearby tourist commented, "Oh no, there's no way they can cross the bridge!" while another shouted, "Use your forward thinking to leap across all obstacles!".
The frogs stood there for a long time, thinking of a way to cross the bridge without dishonoring their family until a CS1010 student came by and said "Oh, I think they can cross it alright. It's just a matter of how many jumps will they need to take."
Figure 2. Frogs on the bridge
Write a program frogs.c to simulate a way for the frogs to cross the bridge. To simulate this, you are to write an integer array to represent the bridge and each element will represent the one frog or an empty space.
Each frog can only jump into the space in front of it, or jump over one frog into the space after that frog.
Your program should take in the length of a bridge (array), and the frogs and space (1, 0 or -1) at each position of the bridge. The user will then be able to move a frog to jump to the empty space directly in front of it OR to jump over a frog to the empty space behind the latter.
Figure 3-1. A frog can jump into empty space in front of it
Figure 3-2. A frog can jump over the frog in front of it to the empty space behind the latter
Figure 3-3. A frog can only jump into an empty space
Figure 3-4. A frog cannot jump so far!
Figure 3-5. A frog cannot jump backwards
Finally, your program should output when the game has ended. A game has ended if there is no possible jumps or all the frogs have successfully crossed the bridge. If they are successful, your program should output the number of jumps the frogs took to cross.
Figure 4-1. The frogs are stuck! Game over.
Figure 4-2. All the frogs have crossed the river!
You can be assured that the length of the bridge will not exceed 1000 and there is only one empty space on the bridge.
Sample run using interactive input (user's input shown in blue; output shown in bold purple). Note that the first two lines (in green below) are commands issued to compile and run your program on UNIX.
Initialising the array:
$ gcc -Wall frogs.c -o frogs $ frogs Please enter the length of the bridge: 7 Please insert frog at position 0: 1 Please insert frog at position 1: 1 Please insert frog at position 2: 1 Please insert frog at position 3: 0 Please insert frog at position 4: -1 Please insert frog at position 5: -1 Please insert frog at position 6: -1
The above inputs represents Figure 2.
Write a function to print out the current state of bridge and its positions:
Position: 0 1 2 3 4 5 6 Bridge: 1 1 1 0 -1 -1 -1
Sample run (move frog)#1:
Move the frog at position: 2 Position: 0 1 2 3 4 5 6 Bridge: 1 1 0 1 -1 -1 -1
Frog at position 2 can jump into the empty space at position 3.
Sample run (move frog)#2:
Move the frog at position: 4 Position: 0 1 2 3 4 5 6 Bridge: 1 1 -1 1 0 -1 -1
Frog at position 4 can jump over frog at position 3 to the empty space in position 2.
Sample run (move frog)#3:
Move the frog at position: 1 Invalid move!
Frog at position 1 can only jump to the right, but there is no empty space.
Sample run (move frog)#4:
Move the frog at position: 4 Invalid move!
Position 4 is empty, therefore it's an invalid move.
The program comes to an end when all frogs have crossed the bridge or when there is no more possible moves. Sample outcome #1:
Position: 0 1 2 3 4 5 6 Bridge: -1 -1 -1 0 1 1 1 Congratulations! The frogs took 15 jumps to cross the bridge!
Sample outcome #2:
Position: 0 1 2 3 4 5 6 Bridge: 1 1 -1 1 -1 -1 0 Oh no! It seems like the two clans of frogs are stuck!
The time here is an estimate of how much time we expect you to spend on this exercise. If you need to spend way more time than this, it is an indication that some help might be needed.
The deadline for submitting all programs is 11 October 2017, Wednesday, 5pm. Late submission will NOT be accepted.