Assignment 6: Permutation 1 2 3

Deadline

26 October, 2018 (Friday), 23:59pm New time

Prerequisite

• 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 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.
• (new) 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-as06

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

Solving The Assignments

• Edit the files permutate1.c, permutate2.c, permutate3.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.
• (new) You should solve each problem using the most straightforward algorithm that you can think of first. Make sure that it runs correctly before trying to improve the efficiency of the algorithm.
• 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-as06

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 Sheldon Cooper (Group 09)

Grading

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

• (new) Efficiency: For each question, some marks are allocated for efficiency. See the question for the breakdown and marking criteria for efficiency.
• Documentation: For each question, two marks are allocated for documentation. Please refer to the documentation and follow the recommended format. 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.
• 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.

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: Permutation 1 (6 marks)

Write a program permutation1, that, given two list of numbers, $L_1$ and $L_2$, checks if $L_2$ is a permutation of $L_1$. We say one list is a permutation of another, if the two lists contain exactly the same numbers, but possibly in different order. For instance, the list 1 3 4 9 10 10 is a permutation of 10 9 10 3 1 4, since they contain the same numbers in different order.

Your program should read, from the standard input,

• a positive integer $n$,
• a list $L_1$, consists of $n$ integer values
• a list $L_2$, consists of $n$ integer values

and print, to the standard output, YES if $L_2$ is a permutation of $L_1$, and NO otherwise. Your solution must take no more than $O(n^2)$ time.

The grading criteria for this question is:

	Marks
Documentation	2
Correctness	3
Efficiency	1

A solution that takes longer than $O(n^2)$ will receive 0 marks for efficiency. Furthermore, your solution needs to be correct to receive marks for efficiency.

Question 2: Permutation 2 (10 marks)

Write a program permutation2, that, given two strings, consists of alphabets 'a' to 'z', $S_1$ and $S_2$, checks if $S_2$ is a permutation of $S_1$. We say a string is a permutation of another, if the two strings contain exactly the same alphabets, but possibly in different order. For instance, nus is a permutation of sun.

Your program should read, from the standard input,

• a string $S_1$, consists of $n$ lowercase alphabets (a to z)
• a string $S_2$, consists of $n$ lowercase alphabets (a to z)

and print, to the standard output, YES if $S_2$ is a permutation of $S_1$, and NO otherwise.

Your solution must take no more than $O(n)$ time.

The grading criteria for this question is:

	Marks
Documentation	2
Correctness	3
Efficiency	5

A solution that takes longer than $O(n)$ will receive 0 marks for efficiency. Furthermore, your solution needs to be correct to receive marks for efficiency.

Question 3: Permutation 3 (14 marks)

Write a program permutation3, that, given two strings, consists of alphabets 'a' to 'z', $S_1$ and $S_2$, checks if S_2 $S_1$ is a permutation of some substring of S_1 $S_2$. A substring of length $k$ is a consecutive sequence of $k$ characters from a string.

For instance, nus is a permutation of a substring of suntec, since suntec contains sun. ntu is also a permutation of a substring of suntec, since suntec contains unt. smu is not a permutation of any substring of suntec.

Your program should read, from the standard input,

• a string $S_1$, consists of $k$ characters, chosen from a to z
• a string $S_2$, consists of $n$ characters, chosen from a to z

and print, to the standard output, YES if $S_1$ is a permutation of some substring of length $k$ from $S_2$, and NO otherwise.

The grading criteria for this question is:

	Marks
Documentation	2
Correctness	5
Efficiency	7

Your solution needs to be correct to receive marks for efficiency. The efficiency marks are given as follows:

• $O(nk^2)$ solution: 2 marks
• $O(nk)$ solution: 4 marks
• $O(n+k)$ solution: 7 marks

Hint

Avoid repetitive work!