Assignment 7: Peak, Scripts, Inversion

Deadline

2 November 2018 (Friday), 23:59pm

Prerequisites

• You are able to access the CS1010 programming environment.
• You are familiar with basic UNIX CLI and using terminal-based editor vim.
• You have gone through Exercise 1 and have already set up your .gitconfig.
• You are familiar with the steps of accepting, downloading, and submitting your exercise and assignment.
• You are familiar with the directory structure and the common files included in your assignment skeleton.

Learning Outcomes

• Be comfortable writing C programs that involve arithmetic operations, long, double, bool, and char types, conditional if/else statements, loops with while/for/do-while statements, arrays (including 2D arrays), strings, pointers, and dynamic memory allocation.
• Be comfortable designing algorithms related to solve computational problems related to searching and sorting, within the given big-O time efficiency bound.
• Be comfortable breaking down a problem into smaller subproblems which can be resolved using functions, including reusing existing functions written for other programs (with a tweak), writing a function that calls itself, designing what should the inputs and return values/types of a function be.
• Be able to analyze the problem and come up with solutions to problems that are efficient, through eliminating redundant and repetitive work.

Setup

• Click on this link to accept the assignment.
• Login to one of the hosts of CS1010 programming environment
• Run:

~cs1010/get-as07

• You should see the folder as07-<github id> in your home directory with the assignment skeleton inside.

Solving The Assignments

• Edit the files peak.c,scripts.c,inversion.c to solve the corresponding question as described below.
• You should break down the problem into smaller subproblems, and write one function for each of the subproblem to solve the problem.
• To compile and run tests with the sample inputs and outputs:

make

• A minimal set of test cases are given in the inputs and outputs subdirectory. You can use cat or less to look at the content of these test cases. You should add more test cases or edit the given ones to extensively test your programs.

Submission

When you are ready, run the following command to submit:

~cs1010/submit-as07

The C files given will be uploaded to GitHub. You can submit multiple times, but only the last submission will be graded.

Editing Your Files in Multiple Locations

You should edit your code only on the CS1010 PE hosts. If you choose to edit your code in other places, such as directly on Github or in a second location (such as your own laptop), you need to be comfortable with various git command to synchronize your code across the different locations, possibly needing to resolve synchronization conflicts.

Only the C files listed above will be submitted. You can create additional C files for testing different solutions, but eventually, you must put your solution into the corresponding C file provided as the skeleton.

Identifying Yourself

In every C file that you submit to CS1010, you need to identify yourself by writing your name and tutorial group. Marks will be deducted if you fail to do so. You need to edit the line:

@author XXXX (Group YYYY)

and change it to something like:

@author Sarah J. Connor (Group 09)

Grading

This assignment contributes towards 3% 4% of your final grade. The total mark for this assignment is 30 40 marks. There are five marking criteria: design, efficiency, correctness, documentation, and style.

• Design: 2 marks. You should break down your program into smaller functions, each one performs a single coherent task or solves a well-defined subproblem. You should avoid repetitive code that can be factored out as a function. Writing everything in a single long function main or cutting-and-pasting code would likely cause you to loose mark for this criteria.
• Efficiency: See the question for the breakdown and marking criteria for efficiency.
• Correctness: The rest of the marks are allocated to correctness. Note that passing the tests does not guarantee that your code is correct. Correctness here is defined in the broad sense of using the various programming constructs in C (type, function, variable, loops, arrays, pointers, conditionals, arithmetic expressions, logical expressions) properly, not just producing the correct output and bug-free.
• Style: Marks are no longer allocated for style, but we will deduct up to 2 marks if you have a serious violation of the style guideline. Please refer to the CS1010 C Style Guide and follow the recommended guideline.
• Documentation: Marks are no longer allocated for documentation, but we will deduct up to 2 marks if you do not document the functions in your code properly. Please refer to the documentation and follow the recommended format. We have added the compilation flag -Wdocumentation to help you identify documentation errors. You need to explain the purpose of every file, function, and parameter. Logic in your code that is not obvious should be explained as well.

We reserve the right to penalize students for using banned C syntax in the assignments. In addition, each grader at his or her own discretion can penalize students for repeating mistakes / bad practices from the student's past assignments (even if it was just a warning with no marks deducted in the earlier assignments).

Question 1: Peak (10 marks)

John helped his professor, Professor Reese, to conduct a topographic survey of a piece of land. He walked in a straight line, noting down the elevation of the land at every centimeter. After he is done, he passed the data to Professor Reese. The professor then asked him, "what is the peak elevation of the land?" John did not know the answer! He could write a program to scan through the millions of data points he collected, but he knew that, since you have taken CS1010, you can do a better job. So, John asked for your help.

You first clarify the problem with John: "What is a peak?" To which John explained that a peak is a location that is strictly higher than the surrounding locations. You then asked: "Is it guaranteed that there is exactly one peak?" John then explained the pattern in the data: the elevation always either remains the same or increases as he walks. After he passed the peak, the elevation always either remains the same, or decreases. But he cannot remember if he ever encountered a peak -- it might be possible that the elevations data is always non-decreasing, or non-increasing, or there is a flat plateau where there are multiple highest locations with the same elevation. So, a peak might not exist. But if there is a peak, it is guaranteed that there is exactly one peak.

"Please, can you help me solve it in $O(log n)$ time?" John pleaded. "Piece of cake!" You said.

Write a program peak that reads from the standard input the following:

• An integer $n$ ($n \ge 3$), followed by
• $n$ integers, each representing the elevation of a location surveyed by John

Then, prints, to the standard output, the index of the location of the peak if it exists, or no peak if a peak does not exist. The first elevation has an index of 0.

An $O(n)$ solution is trivial. You will get 0 marks if your solution simply scans through the array linearly looking for an elevation that is the peak. That is what John would do anyway! To get full marks for correctness and efficiency for this solution, your code should run in $O(log n)$ time when the input elevations are all distinct. Your code is allowed to take longer than $O(log n)$ if there are equal elevations in the input data, with the extreme case of $O(n)$ when all elevation values are the same (the land is completely flat).

Sample Run

ooiwt@pe119:~/as07-weitsang$ cat inputs/peak.1.in
5
1 3 5 4 2
ooiwt@pe119:~/as07-weitsang$ ./peak < inputs/peak.1.in
2
ooiwt@pe119:~/as07-weitsang$ cat inputs/peak.2.in
3
1 2 3
ooiwt@pe119:~/as07-weitsang$ ./peak < inputs/peak.2.in
no peak
ooiwt@pe119:~/as07-weitsang$ cat inputs/peak.3.in
4
-1 2 2 -1
ooiwt@pe119:~/as07-weitsang$ ./peak < inputs/peak.3.in
no peak

Question 2: Scripts (10 marks)

Professor Reese is teaching a huge class at the university. He finished grading a test and he asked John to help him enter the grades into IVLE grade book, in increasing order of the student id. John asked the professor, "Are the scripts sorted?", to which the professor answered, "Almost! The top portion of the pile is sorted in increasing order. The rest, in decreasing order." The professor then left after saying "Hasta la vista, baby," leaving John to wonder how to deal with the test scripts. John needed to sort the scripts in increasing order of the student id. So he messaged you to help him figure out an efficient algorithm to do this. "No problemo!", you said, "Can be done in $O(n)$!" You said. So you went ahead and wrote out the following program to show John how he can solve his problem in $O(n)$ time.

Write a program scripts that reads, from the standard input, the following:

• An integer $n$ ($n \ge 1$), followed by
• $n$ integers, each representing the student ids.

The student ids are unique, i.e., there is no duplicate in the inputs. The student ids from the inputs are arranged in such a way that, the first $k$ are in increasing order, the remaining $n - k$ are in decreasing order. $k$ is not given in the input, and $0 \le k \le n$.

Then, prints, to the standard output, the student ids in increasing order.

An $O(n^2)$ or $O(n log n)$ solution is trivial. You will get 0 marks for correctness and efficiency if your solution simply uses one of the existing sorting algorithms to sort the scripts. Note also that you cannot use counting sort here since a student id can be represented with an arbitrarily large integer (but still fit in a long).

Hint: Allocate an output array and populate it with integers taken either from the front or from the back of the input array depending on which one is larger.

Sample Run

ooiwt@pe119:~/as07-weitsang$ cat inputs/scripts.1.in
5 
1 3 5 4 2
ooiwt@pe119:~/as07-weitsang$ ./scripts < inputs/scripts.2.in
1 2 3 4 5
ooiwt@pe119:~/as07-weitsang$ cat inputs/scripts.2.in
3
1 20 300
ooiwt@pe119:~/as07-weitsang$ ./scripts < inputs/scripts.2.in
1 20 300
ooiwt@pe119:~/as07-weitsang$ cat inputs/scripts.3.in
1
-100
ooiwt@pe119:~/as07-weitsang$ ./scripts < inputs/scripts.3.in
-100

Question 3: Inversion (20 marks)

Professor Reese called John in the evening. "Mr. Connor, I told you that the pile of scripts is almost sorted. But I do not know what it means by almost actually. Can you help me figured out how to quantify that?" John is clueless as well. So he called you. "Ah, I learned this in CS1010 Assignment 3," you boasted, "we can count the number of inversions." You then go on to explain that an inversion is a pair of scripts that are out of order. A perfectly sorted pile of scripts would have zero inversion, and an inversely sorted pile of scripts would have $n \times (n-1)/2$ inversions. "Let me help you to do this, in $O(n)$ time!"

Write a program inversion that reads, from the standard input, the following:

• An integer $n$ ($n \ge 1$), followed by
• $n$ integers, each representing the student ids.

The student ids are unique, i.e., there is no duplicate in the inputs. The student ids from the inputs are arranged in such a way that, the first $k$ are in increasing order, the remaining $n - k$ are in decreasing order. $k$ is not given in the input, and $0 \le k \le n$.

You program should then prints, to the standard output, the number of inversions in the input.

You have already solved this problem in Assignment 3 in $O(n^2)$ time, so, an $O(n^2)$ solution would receive 0 marks. An $O(n log n)$ solution will get 10 marks for correctness and efficiency at most (Hint for $O(n log n)$ solution: binary search). To get full marks for correctness and efficiency, you need to produce an $O(n)$ solution (Hint for $O(n)$: sort).

Sample Run

ooiwt@pe119:~/as07-weitsang$ cat inputs/inversion.1.in
5 
1 3 5 4 2
ooiwt@pe119:~/as07-weitsang$ ./inversion < inputs/inversion.2.in
4
ooiwt@pe119:~/as07-weitsang$ cat inputs/inversion.2.in
3
1 20 300
ooiwt@pe119:~/as07-weitsang$ ./inversion < inputs/inversion.2.in
0
ooiwt@pe119:~/as07-weitsang$ cat inputs/inversion.3.in
1
-100
ooiwt@pe119:~/as07-weitsang$ ./inversion < inputs/inversion.3.in
0

Bug in Sample Output

If you retrieve the assignment before 8am Saturday morning, your sample output for inversion.1.out says 5, but it should be 4. The inversions are 5 4, 3 2, 5 2, and 4 2.