Assignment 4: SelectionSort, Add, Mastermind

Deadline

12 October, 2018 (Friday), 6:00pm.

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, and strings.
• 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.

Setup

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

~cs1010/get-as04

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

Solving The Assignments

• Edit the files selectionsort.c, add.c, mastermind.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

• The 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 can add more test cases or edit the given ones if needed.

Submission

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

~cs1010/submit-as04

The files selectionsort.c, add.c, mastermind.c, 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 Jean Luc Picard (Group 9)

Grading

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

• 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.
• Style: For each question, two marks are allocated for style. Please refer to the CS1010 C Style Guide and follow the recommended guideline.
• 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, conditionals, arithmetic expressions, logical expressions) properly, not just producing the correct output and bug-free.

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: SelectionSort (10 marks)

You have implemented counting sort, a simple and fast sorting algorithm that works on integers with limited range. But if the range of possible values to be sorted is huge or unlimited, then, counting sort does not work so well, and we need a different kind of sorting algorithm.

In this question, you are asked to implement selection sort. The idea behind selection sort is simple, and we will illustrate with the sequence 15 23 16 4 42 8. To sort an array with $n$ values in increasing order, selection sort first finds the maximum value, then moves it into its proper place, that is, the last position. This move is achieved by swapping the value currently in the last position with the maximum value. For instance, for 15 23 16 4 42 8, 42 is the maximum value and 8 wrongly occupies the position reserved for the maximum value. After the first step, the array becomes 15 23 16 4 8 42.

We now focus on sorting the first $n-1$ values in the array (since the maximum is in place). To do this, we find the second largest value, and move it to the second last position. The array becomes 15 8 16 4 23 48 after this second step.

The algorithm continues, moving the third largest value into place, the fourth largest value into place, etc., until the array is sorted. The table below shows the evolution of the array.

Step	Array	Remarks
0	15 23 16 4 42 8	Input Array
1	15 23 16 4 8 42	Swap 42 and 8
2	15 8 16 4 23 42	Swap 23 and 8
3	15 8 4 16 23 42	Swap 16 and 4
4	4 8 15 16 23 42	Swap 15 and 4
5	4 8 15 16 23 42	8 happens to already be in position
6	4 8 15 16 23 42	4 must already be in position

Write a program selectionsort that, reads the following, from the standard input,

• $n$, the number of integers to sort
• followed by $n$ integers

into an array, and prints, to the standard output, $n - 1$ lines, each line showing the array after moving the largest or the next largest element into position.

You can assume that the input list of $n$ integers to be sorted are unique -- i.e., no repetition.

Sample Run

ooiwt@pe119:~/as04-skeleton$ ./selectionsort
6 15 23 16 4 42 8
15 23 16 4 8 42
15 8 16 4 23 42
15 8 4 16 23 42
4 8 15 16 23 42
4 8 15 16 23 42
ooiwt@pe119:~/as04-skeleton$ ./selectionsort
3 0 4 8
0 4 8
0 4 8
ooiwt@pe119:~/as04-skeleton$ ./selectionsort
5 1 3 5 4 2
1 3 2 4 5
1 3 2 4 5
1 2 3 4 5
1 2 3 4 5

Question 2: Add (15 marks)

In this question, you are asked to write a program that adds two non-negative numbers which can be arbitrarily large. The types provided by C can only represent a number up to a certain value. We have seen that long long int is not even big enough to represent 21!.

For this question, we will represent a number using an arbitrarily long string consisting of characters (of type char) '0' to '9' (note: not integer 0 to 9). C supports arithmetic operations on char values as well. To convert between the numerical value of a digit character, we can do the following:

• To convert from a digit character to its numerical value, we subtract the char '0'. For instance, '6' - '0' will give us the value 6.
• To convert from a numerical value of a digit to its character, we add the char '0'. For instance, 6 + '0' will give us the character '6'.

You can read a sequence of non-space characters from the standard input using cs1010_read_word, and print a sequence of characters (i.e., a string) to the standard output using cs1010_println_string.

Write a program add that reads from the standard input two non-negative numbers represented as strings consisting of digits '0' to '9', and prints to the standard output the sum of the two numbers.

You will likely need to use the C standard library function strlen, which returns you the number of characters in a string (excluding the terminating '\0'). Look up on how to use this function on your own.

Sample Run

ooiwt@pe119:~/as04-skeleton$ ./add
1
1
2
ooiwt@pe119:~/as04-skeleton$ ./add
7
8
15
ooiwt@pe119:~/as04-skeleton$ ./add
999999
1
1000000
ooiwt@pe119:~/as04-skeleton$ ./add
1400060514000605140006051400605
19330911933091193309119330911933091
19332311993605193914259336963333696

Question 3: Mastermind (15 marks)

Photo by flöschen, some right reserved

Mastermind is a board game played by two players, a coder and a codebreaker. The coder creates a code consists of four color pegs, chosen from pegs of six different colors (cyan, green, red, blue, purple, orange). Repetition of the same colors is allowed. The codebreaker's task is to guess the colors of the pegs and the order their appears in the code.

The game proceeds in rounds. In each round, the codebreaker tries to guess the code by specifying the colors and the order of the colors. The coder then provides feedback to the codebreaker, with two smaller pegs of black and white color. A black color peg is placed if the codebreaker guesses correctly a peg in both position and color. A white color peg is placed if the codebreaker guesses correctly a peg in color but not in the position. Based on the feedback, the codebreaker guesses again in the next round. In the actual board game, the codebreaker wins if he guesses correctly every color in the correct order. The coder wins if the codebreaker failed to guess correctly after 8 guesses.

Write a program called mastermind that simulates the Mastermind game. The program first reads in the code from the standard inputs. We denote the colors with their initials, c, g, r, b, p, o. Hence, the code is a 4-letter word. For instance, the code prob corresponds the pegs purple, red, orange, blue, in that order. It then reads in a sequence of guesses, each is a 4-letter word consists of the letter c, g, r, b, p, o. For each guess, the program prints out two numbers, the first is the number of pegs that are correct in both position and color. The second, is the number of pegs that are correct in color but not position. Note that we do not double count, so the total of these two numbers is at most 4.

For example, if the code is prob and the guess is borg, the program prints 0 3. Since none of the guesses is correct in both color and position. The three colors b, o, r, however, appear in the code, albeit in a different position. Suppose the guess is rrrr, the program prints 1 0. The third r is the guess appears in the correct position and correct color. There is no other r in the code, so the second number is 0. This example illustrates that we do not double count. We do not match the other rs in the guess to the r in the code, once the r in the code has been matched.

The program terminates when the guess is the same as the code.

Sample Run

ooiwt@pe119:~/as04-skeleton$ ./mastermind
prob
borg
0 3
rrrr
1 0
bbbb
1 0
oorr
0 2
prob
4 0
ooiwt@pe119:~/as04-skeleton$ ./mastermind
cccp
borg
0 0
prob
0 1
oooc
0 1
crrc
1 1
pcpc
1 2
cpcp
3 0
cccp
4 0