Starting from:
$29
Assignment 2: One-Shot Learning and Sudoku
Programming Assignment 2: One-Shot Learning and Sudoku (100 points + 25 Extra credit points)
This assignment is designed to provide you some experience writing programs with the C programming language. There are three parts to this assignment. The third part is extra credit.
Part 1: One-Shot Learning (50 points)
In the first part, you will write a C program that implements simple “one-shot” machine learning algorithm for predicting house prices in your area. There is significant hype and excitement around artificial intelligence (AI) and machine learning. CS 211 students will get a glimpse of AI/ML by implementing a simple machine learning algorithm to predict house prices based on historical data. For example, the price of the house (y) can depend on certain attributes of the house: number of bedrooms (x1), total size of the house (x2), number of baths (x3), and the year the house was built (x4). Then, the price of the house can be computed by the following equation:
y = w0 + w1.x1 + w2.x2 + w3.x3 + w4.x4 (1) Given a house, we know the attributes of the house (i.e., x1, x2, x3, x4). However, we don’t know the weights for these attributes: w0, w1, w2, w3 and w4. The goal of the machine learning algorithm in our context is to learn the weights for the attributes of the house from lots of training data. Let’s say we have N examples in your training data set that provide the values of the attributes and the price. Let’s say there are K attributes. We can represent the attributes from all the examples in the training data as a Nx(K + 1) matrix as follows, which we call X:
[
1, x0,1, x0,2, x0,3, x0,4 1, x1,1, x1,2, x1,3, x1,4 1, x2,1, x2,2, x2,3, x2,4 1, x3,1, x3,2, x3,3, x3,4 .. 1, xn,1, xn,2, xn,3, xn,4
] where n is N −1. We can represent the prices of the house from the examples in the training dataas a Nx1 matrix, which we call Y .
[
y0 y1 .. yn
]
Similarly, we can represent the weights for each attribute as a (K + 1)x1 matrix, which we call W.
1
[
w0 w1 .. wk
]
The goal of our machine learning algorithm is to learn this matrix from the training data. Now in the matrix notation, entire learning process can be represented by the following equation, where X, Y , and W are matrices as described above.
X.W = Y (2)
Using the training data, we can learn the weights using the below equation:
W = (XT.X)−1.XT.Y (3) where XT is the transpose of the matrix X, (XT.X)−1 is the inverse of the matrix XT.X. Your main task in this part to implement a program to read the training data and learn the weights for each of the attributes. You have to implement functions to multiply matrices, transpose matrices, and compute the inverses of the matrix. You will use the learned weights to predict the house prices for the examples in the test data set.
Want to learn more about One-shot Learning? The theory behind this learning is not important for the purposes of this class. The algorithm you are implementing is known as linear regression with least square error as the error measure. The matrix ((XT.X)−1.XT) is also known as the pseudo-inverse of matrix X. If you are curious, you can learn more about this algorithm at https://www.youtube. com/watch?v=FIbVs5GbBlQ&hd=1.
Computing the Inverse using Gauss-Jordan Elimination
To compute the weights above, your program has to compute the inverse of matrix. There are numerous methods to compute the inverse of a matrix. We want you to implement a specific method for computing the inverse of a matrix known as Guass-Jordan elimination, which is described below. If you compute inverse using any other method, you will risk losing all points for this part. An inverse of a square matrix A is another square matrix B, such that A.B = B.A = I, where I is the identity matrix.
Gauss-Jordan Elimination for computing inverses
Below, we give a sketch of Gauss-Jordan elimination method. Given a matrix A whose inverse needs to be computed, you create a new matrix Aaug, which is called the augmented matrix of A, by concatenating identity matrix with A as shown below. Let say matrix A, whose inverse you want to compute is shown below:
[
1 2 4 1 6 7 1 3 2
]
The augmented matrix (Aaug) of A is:
[
1 2 4 1 0 0 1 6 7 0 1 0 1 3 2 0 0 1
]
2
The augmented matrix essentially has the original matrix and the identity matrix. Next, we perform row operations on the augmented matrix so that the original matrix part of the augmented matrix turns into an identity matrix. The valid row operations to compute the inverse (for this assignment) are: • You can divide the entire row by a constant • You can subtract a row by another row • You can subtract a row by another row multiplied by a constant However, you are not allowed to swap the rows. In the traditional Gauss-Jordan elimination method you are allowed to swap the rows. For simplicity, we do not allow you to swap the rows. Let’s see this method with the above augmented matrix Aaug. • Our goal is to transform A part of the augmented matrix into an identity matrix. Since Aaug[1][0]! = 0, we will subtract the first row from the second row because we want to make Aaug[1][0] = 0. Hence, we perform the operation R1 = R1 −R0, where R1 and R0 represents the second and first row of the augmented matrix. Augmented matrix Aaug after R1 = R1 −R0 [ 1 2 4 1 0 0 0 4 3 −1 1 0 1 3 2 0 0 1 ]
• Now we want to make Aaug[1][1] = 1. Hence, we perform the operation R1 = R1/4. The augmented matrix Aaug after R1 = R1/4 is: [ 1 2 4 1 0 0 0 1 3 4 −1 4 1 4 0 1 3 2 0 0 1 ]
• Next, we want to make Aaug[2][0] = 0. Hence, we perform the operation R2 = R2 − R0. The augmented matrix Aaug after R2 = R2 −R0 is: [ 1 2 4 1 0 0 0 1 3 4 −1 4 1 4 0 0 1 -2 -1 0 1 ]
• Next, we want to make Aaug[2][1] = 0. Hence, we perform the operation R2 = R2 − R1. The augmented matrix Aaug after R2 = R2 −R1 is: [ 1 2 4 1 0 0 0 1 3 4 −1 4 1 4 0 0 0 −11 4 −3 4 −1 4 1 ] • Now, we want to make Aaug[2,2] = 1, Hence, we perform the operation R3 = R3∗−4 11 . Then, Aaug is:
[
1 2 4 1 0 0 0 1 3 4 −1 4 1 4 0 0 0 1 3 11 1 11 −4 11
]
3
• Next, we want to make Aaug[1,2] = 0, Hence, we perform the operation R1 = R1 − 3 4 ∗R2. Then,A aug is:
[
1 2 4 1 0 0 0 1 0 −5 11 2 11 3 11 0 0 1 3 11 1 11 −4 11
]
• Next, we want to make Aaug[0,2] = 0, Hence, we perform the operation R0 = R0 −4∗R2. Then, Aaug is:
[
1 2 0 1 11 −4 11
16 11
0 1 0 −5 11
2 11
3 11
0 0 1 3 11
1 11 −4 11
]
• Next, we want to make Aaug[0,1] = 0, Hence, we perform the operation R0 = R0 −2∗R1. Then, Aaug is:
[
1 0 0 9 11 −8 11
10 11
0 1 0 −5 11
2 11
3 11
0 0 1 3 11
1 11 −4 11
]
• At this time, the A part of the augmented matrix is an identity matrix. Hence, the inverse of A matrix is:
[
9 11 −8 11
10 11
−5 11
2 11
3 11
3 11
1 11 −4 11
]
Your goal is to write a program to compute the inverse of a matrix to perform one-shot learning.
Input/Output specification
Usage interface
Your program for this part will be executed as follows:
./first <train-data-file-name <test-data-file-name
where <train-data-file-name is the name of the training data file with attributes and price of the house. You can assume that the training data file will exist and that it is well structured. The <test-data-file-name is the name of the test data file with attributes of the house. You have to predict the price of the house for each entry in the test data file.
Input specification
The input to the program will be a training data file and a test data file.
4
Structure of the training data file
The first line in the training file will be an integer that provides the number of attributes (K) in the training set. The second line in the training data file will be an integer (N) providing the number of training examples in the training data set. The next N lines represent the N training examples. Each line for the example will be a list of comma-separated double precision floating point values. The first K double precision values represent the values for the attributes of the house. The last double precision value in the line represents the price of the house. An example training data file (train1.txt) is shown below:
4 7 3.000000,1.000000,1180.000000,1955.000000,221900.000000 3.000000,2.250000,2570.000000,1951.000000,538000.000000 2.000000,1.000000,770.000000,1933.000000,180000.000000 4.000000,3.000000,1960.000000,1965.000000,604000.000000 3.000000,2.000000,1680.000000,1987.000000,510000.000000 4.000000,4.500000,5420.000000,2001.000000,1230000.000000 3.000000,2.250000,1715.000000,1995.000000,257500.000000
In the example above, there are 4 attributes and 7 training data examples. Each example has values for the attributes and last value is the price of the house. To illustrate, consider the training example below
3.000000,1.000000,1180.000000,1955.000000,221900.000000
The first attribute has value 3.000000, the second attribute has value 1.000000, third attribute has value 1180.000000, and the fourth attribute has value 1955.000000. The price of the house for these set of attributes is provided as the last value in the line: 221900.000000
Structure of the test data file
The first line in the training file will be an integer (M) that provides the number of test data points in the file. Each line will have K attributes. The value of K is defined in the training data file. Your goal is predict the price of house for each line in the test data file. The next M lines represent the M test points for which you have to predict the price of the house. Each line will be a list of comma-separated double precision floating point values. There will be K double precision values that represent the values for the attributes of the house. An example test data file (test1.txt) is shown below:
2 3.000000,2.500000,3560.000000,1965.000000 2.000000,1.000000,1160.000000,1942.000000
It indicates that you have to predict the price of the house using your training data for 2 houses. The attributes of each house is listed in the subsequent lines.
Output specification
Your program should print the price of the house for each line in the test data file. Your program should not produce any additional output. If the price of the house is a fractional value, then your program should round it to the nearest integer, which you can accomplish with the following printf statement:
printf("%0.0lf\n", value);
where value is the price of the house and its type is double in C. Your program should predict the price of the entry in the test data file by substituting the attributes and the weights (learned from the training data set) in Equation (1). A sample output of the execution when you execute your program as shown below,
5
./first train1.txt test1.txt
should be
737861 203060
Part 2: Sudoku (50 points)
In Part 2 of this assignment, you will write a C program that implements a simple Sudoku solver (in the third part you can implement a complex Sudoku solver for extra credit). Sudoku is a simple logic puzzle where the objective is to fill a 9x9 grid of cells with each cell containing a number from the set 1-9 while fulfilling the following constraints: • Each number is unique in its row and column. • Each number is unique in its subgrid where a subgrid is defined by cutting the 9x9 into 9 nonoverlapping 3x3 grids (top left, top, top right, left, middle, right, bottom left, bottom, bottom right). • Each row, column, and subgrid have all numbers from 1-9 present. A Sudoku is defined as solved when all of its cells in the 9x9 grid are filled with numbers with each cell satisfying the constraints above. A Sudoku is defined as unsolvable when there is no configuration where all the cells can be filled without breaking the constraints. A Sudoku will start partially completed with some numbers placed in the 9x9 grid. This will allow the solver to determine where to place new numbers in order to find the solution for the given Sudoku. For this part, we will only be looking at Sudoku grids with one unique solution. In this part, we will look at Sudoku grids wehre there will always be a cell that you can fill with 100% certanity with an unique according to the constraints described above.
Part 3: Extra Credit (25 points)
It is not always possible to fill at least one element with 100% certainity in each step for many Sudoku grids. Sometimes the next step to be taken cannot be known and instead, a guess must be taken in order to move forward, such as perhaps filling in a cell randomly. For extra credit on this assignment, you can implement an algorithm that solves these more complex Sudoku grids. A possible algorithm to do so would be to solve as much of the Sudoku as can be done so confidently. Once no more nodes can be filled with 100% certainty, continue by taking the first unsolved cell (let’s call this cell A) and filling it with a number that satisfies the constraints and continue solving as usual from there. If a solution is found, then you are done. Otherwise, if no moves can be taken and the board has not yet been filled than you must backtrack to the state where you guessed the value of cell A and either guess a new value for cell A or perhaps choose a new cell altogether. This is a simple backtracking algorithm. There are many algorithms to solve these complex Sudoku and it is entirely up to you to decide which to implement.
Input format for Part 2 and Part 3
Your program will read in the data from a file given to the program as an argument from the command line. The file format will be a 9x9 grid with each number in the same row separated by a tab. Blank cells will be represented with a ‘-’. An example Sudoku grid test1.text is given below:
6
- - - 5 8 2 - - - - 5 - - - 2 - 9 2 - 1 - 4 - - 5 5 - 8 - - 1 7 - - 3 - - - - - 2 - - 9 7 - - 1 - 3 4 - - 9 - 5 - 1 6 - - 1 - - - 9 - - 9 - 2 1 - - - A sample Sudoku grid test2.txt is given below: 1 - 3 - - - 8 4 1 - - - - - - 5 - 2 2 - - - - - 6 9 3 - - - 3 - 9 - - 4 - - - 4 - - - - 5 - - - - - - 3 - 6 - - - - - - - - 7 - - - - - - - - 8 3 2 - 4 5 6 7 8 You can assume that all inputs will be valid meaning the spacing will be correct and only the ‘-’ character and numbers 1-9 will be present in the test files. The preset numbers in the test may not satisfy the constraints of Sudoku as in the example test2.txt above resulting in an unsolvable Sudoku. Output format: For a Sudoku grid that has a solution, you should print out the 9x9 grid with each number in the same row separated by a tab and with each row on a new line. There should be no trailing spaces or tabs on any line of output. A sample execution is given below:
./second test1.txt
3 1 4 5 8 2 6 7 9 7 8 5 6 9 3 2 4 1 9 2 6 1 7 4 3 8 5 5 6 8 3 2 1 7 9 4 1 3 7 4 6 9 5 2 8 2 4 9 7 5 8 1 6 3 4 7 2 9 3 5 8 1 6 6 5 1 8 4 7 9 3 2 8 9 3 2 1 6 4 5 7
For a Sudoku grid that has no solution, your program should print “no-solution” and nothing else. For part 2, Sudoku grids that have a solution but cannot be found without guesses are considered unsolvable.
Structure of your submission folder
All files must be included in the pa2 folder. The pa2 directory in your tar file must contain 2 directories or 3 directories (if decide to do the extra credit part). The name of the directories should be named first through second or first through third (in lower case). Each directory should contain a c source file, a header file(if you use it), and a Makefile. For example, the subdirectory first will contain, first.c, first.h (if you create one), and Makefile (the names are case sensitive).
Hints and suggestions • You are allowed to use functions from standard libraries but you cannot use third-party libraries downloaded from the Internet (or from anywhere else). If you are unsure whether you can use something, ask us.
7
• We will compile and test your program on the iLab machines so you should make sure that your program compiles and runs correctly on these machines. You must compile all C code using the gcc compiler with the -Wall -Werror -fsanitize=address flags. • You should test your program with the autograder provided with the assignment.
Submission
You have to e-submit the assignment using Sakai. Your submission should be a tar file named pa2.tar. To create this file, put everything (three folders) that you are submitting into a directory named pa2. Then, cd into the directory containing pa2 (that is, pa2’s parent directory) and run the following command: tar cvf pa2.tar pa2
To check that you have correctly created the tar file, you should copy it (pa2.tar) into an empty directory and run the following command:
tar xvf pa2.tar
This should create a directory named pa2 in the (previously) empty directory.
Grading guidelines
The grading will be automatically graded using the autograder.
Automated grading phase
This phase will be based on programmatic checking of your program using the autograder. We will build a binary using the Makefile and source code that you submit, and then test the binary for correct functionality and efficiency against a set of inputs. • We should be able build your program by just running make. • Your program should follow the format specified above for both both the parts. • Your program should strictly follow the input and output specifications mentioned. Note: This is perhaps the most important guideline: failing to follow it might result in you losing all or most of your points for this assignment. Make sure your program’s output format is exactly as specified. Any deviation will cause the automated grader to mark your output as “incorrect”. REQUESTS FOR RE-EVALUATIONS OF PROGRAMS REJECTED DUE TO IMPROPER FORMAT WILL NOT BE ENTERTAINED. • We will check all solutions pair-wise from all sections of this course to detect cheating using moss software and related tools. If two submissions are found to be similar, they will instantly be awarded zero points and reported to office of student conduct. See Rutgers CS’s academic integrity policy at: https://www.cs.rutgers.edu/academic-integrity/introduction.
Autograder
We provide the AutoGrader to test your assignment. AutoGrader is provided as pa2 autograder.tar. Executing the following command will create the pa2 autograder folder.
tar xvf pa2_autograder.tar
There are two modes available for testing your assignment with the PA2 AutoGrader.
8
First mode
Testing when you are writing code with a pa2 folder
1. Lets say you have a pa2 folder with the directory structure as described in the assignment.
2. Copy the folder to the directory of the pa2 autograder
3. Run the pa2 autograder with the following command python pa2 autograder.py It will run the test cases and print your scores.
Second mode
This mode is to test your final submission (i.e, pa2.tar)
1. Copy pa2.tar to the pa2 autograder directory
2. Run the pa2 autograder.py with pa2.tar as the argument. The command line is:
python pa2 autograder.py pa2.tar
9
This assignment is designed to provide you some experience writing programs with the C programming language. There are three parts to this assignment. The third part is extra credit.
Part 1: One-Shot Learning (50 points)
In the first part, you will write a C program that implements simple “one-shot” machine learning algorithm for predicting house prices in your area. There is significant hype and excitement around artificial intelligence (AI) and machine learning. CS 211 students will get a glimpse of AI/ML by implementing a simple machine learning algorithm to predict house prices based on historical data. For example, the price of the house (y) can depend on certain attributes of the house: number of bedrooms (x1), total size of the house (x2), number of baths (x3), and the year the house was built (x4). Then, the price of the house can be computed by the following equation:
y = w0 + w1.x1 + w2.x2 + w3.x3 + w4.x4 (1) Given a house, we know the attributes of the house (i.e., x1, x2, x3, x4). However, we don’t know the weights for these attributes: w0, w1, w2, w3 and w4. The goal of the machine learning algorithm in our context is to learn the weights for the attributes of the house from lots of training data. Let’s say we have N examples in your training data set that provide the values of the attributes and the price. Let’s say there are K attributes. We can represent the attributes from all the examples in the training data as a Nx(K + 1) matrix as follows, which we call X:
[
1, x0,1, x0,2, x0,3, x0,4 1, x1,1, x1,2, x1,3, x1,4 1, x2,1, x2,2, x2,3, x2,4 1, x3,1, x3,2, x3,3, x3,4 .. 1, xn,1, xn,2, xn,3, xn,4
] where n is N −1. We can represent the prices of the house from the examples in the training dataas a Nx1 matrix, which we call Y .
[
y0 y1 .. yn
]
Similarly, we can represent the weights for each attribute as a (K + 1)x1 matrix, which we call W.
1
[
w0 w1 .. wk
]
The goal of our machine learning algorithm is to learn this matrix from the training data. Now in the matrix notation, entire learning process can be represented by the following equation, where X, Y , and W are matrices as described above.
X.W = Y (2)
Using the training data, we can learn the weights using the below equation:
W = (XT.X)−1.XT.Y (3) where XT is the transpose of the matrix X, (XT.X)−1 is the inverse of the matrix XT.X. Your main task in this part to implement a program to read the training data and learn the weights for each of the attributes. You have to implement functions to multiply matrices, transpose matrices, and compute the inverses of the matrix. You will use the learned weights to predict the house prices for the examples in the test data set.
Want to learn more about One-shot Learning? The theory behind this learning is not important for the purposes of this class. The algorithm you are implementing is known as linear regression with least square error as the error measure. The matrix ((XT.X)−1.XT) is also known as the pseudo-inverse of matrix X. If you are curious, you can learn more about this algorithm at https://www.youtube. com/watch?v=FIbVs5GbBlQ&hd=1.
Computing the Inverse using Gauss-Jordan Elimination
To compute the weights above, your program has to compute the inverse of matrix. There are numerous methods to compute the inverse of a matrix. We want you to implement a specific method for computing the inverse of a matrix known as Guass-Jordan elimination, which is described below. If you compute inverse using any other method, you will risk losing all points for this part. An inverse of a square matrix A is another square matrix B, such that A.B = B.A = I, where I is the identity matrix.
Gauss-Jordan Elimination for computing inverses
Below, we give a sketch of Gauss-Jordan elimination method. Given a matrix A whose inverse needs to be computed, you create a new matrix Aaug, which is called the augmented matrix of A, by concatenating identity matrix with A as shown below. Let say matrix A, whose inverse you want to compute is shown below:
[
1 2 4 1 6 7 1 3 2
]
The augmented matrix (Aaug) of A is:
[
1 2 4 1 0 0 1 6 7 0 1 0 1 3 2 0 0 1
]
2
The augmented matrix essentially has the original matrix and the identity matrix. Next, we perform row operations on the augmented matrix so that the original matrix part of the augmented matrix turns into an identity matrix. The valid row operations to compute the inverse (for this assignment) are: • You can divide the entire row by a constant • You can subtract a row by another row • You can subtract a row by another row multiplied by a constant However, you are not allowed to swap the rows. In the traditional Gauss-Jordan elimination method you are allowed to swap the rows. For simplicity, we do not allow you to swap the rows. Let’s see this method with the above augmented matrix Aaug. • Our goal is to transform A part of the augmented matrix into an identity matrix. Since Aaug[1][0]! = 0, we will subtract the first row from the second row because we want to make Aaug[1][0] = 0. Hence, we perform the operation R1 = R1 −R0, where R1 and R0 represents the second and first row of the augmented matrix. Augmented matrix Aaug after R1 = R1 −R0 [ 1 2 4 1 0 0 0 4 3 −1 1 0 1 3 2 0 0 1 ]
• Now we want to make Aaug[1][1] = 1. Hence, we perform the operation R1 = R1/4. The augmented matrix Aaug after R1 = R1/4 is: [ 1 2 4 1 0 0 0 1 3 4 −1 4 1 4 0 1 3 2 0 0 1 ]
• Next, we want to make Aaug[2][0] = 0. Hence, we perform the operation R2 = R2 − R0. The augmented matrix Aaug after R2 = R2 −R0 is: [ 1 2 4 1 0 0 0 1 3 4 −1 4 1 4 0 0 1 -2 -1 0 1 ]
• Next, we want to make Aaug[2][1] = 0. Hence, we perform the operation R2 = R2 − R1. The augmented matrix Aaug after R2 = R2 −R1 is: [ 1 2 4 1 0 0 0 1 3 4 −1 4 1 4 0 0 0 −11 4 −3 4 −1 4 1 ] • Now, we want to make Aaug[2,2] = 1, Hence, we perform the operation R3 = R3∗−4 11 . Then, Aaug is:
[
1 2 4 1 0 0 0 1 3 4 −1 4 1 4 0 0 0 1 3 11 1 11 −4 11
]
3
• Next, we want to make Aaug[1,2] = 0, Hence, we perform the operation R1 = R1 − 3 4 ∗R2. Then,A aug is:
[
1 2 4 1 0 0 0 1 0 −5 11 2 11 3 11 0 0 1 3 11 1 11 −4 11
]
• Next, we want to make Aaug[0,2] = 0, Hence, we perform the operation R0 = R0 −4∗R2. Then, Aaug is:
[
1 2 0 1 11 −4 11
16 11
0 1 0 −5 11
2 11
3 11
0 0 1 3 11
1 11 −4 11
]
• Next, we want to make Aaug[0,1] = 0, Hence, we perform the operation R0 = R0 −2∗R1. Then, Aaug is:
[
1 0 0 9 11 −8 11
10 11
0 1 0 −5 11
2 11
3 11
0 0 1 3 11
1 11 −4 11
]
• At this time, the A part of the augmented matrix is an identity matrix. Hence, the inverse of A matrix is:
[
9 11 −8 11
10 11
−5 11
2 11
3 11
3 11
1 11 −4 11
]
Your goal is to write a program to compute the inverse of a matrix to perform one-shot learning.
Input/Output specification
Usage interface
Your program for this part will be executed as follows:
./first <train-data-file-name <test-data-file-name
where <train-data-file-name is the name of the training data file with attributes and price of the house. You can assume that the training data file will exist and that it is well structured. The <test-data-file-name is the name of the test data file with attributes of the house. You have to predict the price of the house for each entry in the test data file.
Input specification
The input to the program will be a training data file and a test data file.
4
Structure of the training data file
The first line in the training file will be an integer that provides the number of attributes (K) in the training set. The second line in the training data file will be an integer (N) providing the number of training examples in the training data set. The next N lines represent the N training examples. Each line for the example will be a list of comma-separated double precision floating point values. The first K double precision values represent the values for the attributes of the house. The last double precision value in the line represents the price of the house. An example training data file (train1.txt) is shown below:
4 7 3.000000,1.000000,1180.000000,1955.000000,221900.000000 3.000000,2.250000,2570.000000,1951.000000,538000.000000 2.000000,1.000000,770.000000,1933.000000,180000.000000 4.000000,3.000000,1960.000000,1965.000000,604000.000000 3.000000,2.000000,1680.000000,1987.000000,510000.000000 4.000000,4.500000,5420.000000,2001.000000,1230000.000000 3.000000,2.250000,1715.000000,1995.000000,257500.000000
In the example above, there are 4 attributes and 7 training data examples. Each example has values for the attributes and last value is the price of the house. To illustrate, consider the training example below
3.000000,1.000000,1180.000000,1955.000000,221900.000000
The first attribute has value 3.000000, the second attribute has value 1.000000, third attribute has value 1180.000000, and the fourth attribute has value 1955.000000. The price of the house for these set of attributes is provided as the last value in the line: 221900.000000
Structure of the test data file
The first line in the training file will be an integer (M) that provides the number of test data points in the file. Each line will have K attributes. The value of K is defined in the training data file. Your goal is predict the price of house for each line in the test data file. The next M lines represent the M test points for which you have to predict the price of the house. Each line will be a list of comma-separated double precision floating point values. There will be K double precision values that represent the values for the attributes of the house. An example test data file (test1.txt) is shown below:
2 3.000000,2.500000,3560.000000,1965.000000 2.000000,1.000000,1160.000000,1942.000000
It indicates that you have to predict the price of the house using your training data for 2 houses. The attributes of each house is listed in the subsequent lines.
Output specification
Your program should print the price of the house for each line in the test data file. Your program should not produce any additional output. If the price of the house is a fractional value, then your program should round it to the nearest integer, which you can accomplish with the following printf statement:
printf("%0.0lf\n", value);
where value is the price of the house and its type is double in C. Your program should predict the price of the entry in the test data file by substituting the attributes and the weights (learned from the training data set) in Equation (1). A sample output of the execution when you execute your program as shown below,
5
./first train1.txt test1.txt
should be
737861 203060
Part 2: Sudoku (50 points)
In Part 2 of this assignment, you will write a C program that implements a simple Sudoku solver (in the third part you can implement a complex Sudoku solver for extra credit). Sudoku is a simple logic puzzle where the objective is to fill a 9x9 grid of cells with each cell containing a number from the set 1-9 while fulfilling the following constraints: • Each number is unique in its row and column. • Each number is unique in its subgrid where a subgrid is defined by cutting the 9x9 into 9 nonoverlapping 3x3 grids (top left, top, top right, left, middle, right, bottom left, bottom, bottom right). • Each row, column, and subgrid have all numbers from 1-9 present. A Sudoku is defined as solved when all of its cells in the 9x9 grid are filled with numbers with each cell satisfying the constraints above. A Sudoku is defined as unsolvable when there is no configuration where all the cells can be filled without breaking the constraints. A Sudoku will start partially completed with some numbers placed in the 9x9 grid. This will allow the solver to determine where to place new numbers in order to find the solution for the given Sudoku. For this part, we will only be looking at Sudoku grids with one unique solution. In this part, we will look at Sudoku grids wehre there will always be a cell that you can fill with 100% certanity with an unique according to the constraints described above.
Part 3: Extra Credit (25 points)
It is not always possible to fill at least one element with 100% certainity in each step for many Sudoku grids. Sometimes the next step to be taken cannot be known and instead, a guess must be taken in order to move forward, such as perhaps filling in a cell randomly. For extra credit on this assignment, you can implement an algorithm that solves these more complex Sudoku grids. A possible algorithm to do so would be to solve as much of the Sudoku as can be done so confidently. Once no more nodes can be filled with 100% certainty, continue by taking the first unsolved cell (let’s call this cell A) and filling it with a number that satisfies the constraints and continue solving as usual from there. If a solution is found, then you are done. Otherwise, if no moves can be taken and the board has not yet been filled than you must backtrack to the state where you guessed the value of cell A and either guess a new value for cell A or perhaps choose a new cell altogether. This is a simple backtracking algorithm. There are many algorithms to solve these complex Sudoku and it is entirely up to you to decide which to implement.
Input format for Part 2 and Part 3
Your program will read in the data from a file given to the program as an argument from the command line. The file format will be a 9x9 grid with each number in the same row separated by a tab. Blank cells will be represented with a ‘-’. An example Sudoku grid test1.text is given below:
6
- - - 5 8 2 - - - - 5 - - - 2 - 9 2 - 1 - 4 - - 5 5 - 8 - - 1 7 - - 3 - - - - - 2 - - 9 7 - - 1 - 3 4 - - 9 - 5 - 1 6 - - 1 - - - 9 - - 9 - 2 1 - - - A sample Sudoku grid test2.txt is given below: 1 - 3 - - - 8 4 1 - - - - - - 5 - 2 2 - - - - - 6 9 3 - - - 3 - 9 - - 4 - - - 4 - - - - 5 - - - - - - 3 - 6 - - - - - - - - 7 - - - - - - - - 8 3 2 - 4 5 6 7 8 You can assume that all inputs will be valid meaning the spacing will be correct and only the ‘-’ character and numbers 1-9 will be present in the test files. The preset numbers in the test may not satisfy the constraints of Sudoku as in the example test2.txt above resulting in an unsolvable Sudoku. Output format: For a Sudoku grid that has a solution, you should print out the 9x9 grid with each number in the same row separated by a tab and with each row on a new line. There should be no trailing spaces or tabs on any line of output. A sample execution is given below:
./second test1.txt
3 1 4 5 8 2 6 7 9 7 8 5 6 9 3 2 4 1 9 2 6 1 7 4 3 8 5 5 6 8 3 2 1 7 9 4 1 3 7 4 6 9 5 2 8 2 4 9 7 5 8 1 6 3 4 7 2 9 3 5 8 1 6 6 5 1 8 4 7 9 3 2 8 9 3 2 1 6 4 5 7
For a Sudoku grid that has no solution, your program should print “no-solution” and nothing else. For part 2, Sudoku grids that have a solution but cannot be found without guesses are considered unsolvable.
Structure of your submission folder
All files must be included in the pa2 folder. The pa2 directory in your tar file must contain 2 directories or 3 directories (if decide to do the extra credit part). The name of the directories should be named first through second or first through third (in lower case). Each directory should contain a c source file, a header file(if you use it), and a Makefile. For example, the subdirectory first will contain, first.c, first.h (if you create one), and Makefile (the names are case sensitive).
Hints and suggestions • You are allowed to use functions from standard libraries but you cannot use third-party libraries downloaded from the Internet (or from anywhere else). If you are unsure whether you can use something, ask us.
7
• We will compile and test your program on the iLab machines so you should make sure that your program compiles and runs correctly on these machines. You must compile all C code using the gcc compiler with the -Wall -Werror -fsanitize=address flags. • You should test your program with the autograder provided with the assignment.
Submission
You have to e-submit the assignment using Sakai. Your submission should be a tar file named pa2.tar. To create this file, put everything (three folders) that you are submitting into a directory named pa2. Then, cd into the directory containing pa2 (that is, pa2’s parent directory) and run the following command: tar cvf pa2.tar pa2
To check that you have correctly created the tar file, you should copy it (pa2.tar) into an empty directory and run the following command:
tar xvf pa2.tar
This should create a directory named pa2 in the (previously) empty directory.
Grading guidelines
The grading will be automatically graded using the autograder.
Automated grading phase
This phase will be based on programmatic checking of your program using the autograder. We will build a binary using the Makefile and source code that you submit, and then test the binary for correct functionality and efficiency against a set of inputs. • We should be able build your program by just running make. • Your program should follow the format specified above for both both the parts. • Your program should strictly follow the input and output specifications mentioned. Note: This is perhaps the most important guideline: failing to follow it might result in you losing all or most of your points for this assignment. Make sure your program’s output format is exactly as specified. Any deviation will cause the automated grader to mark your output as “incorrect”. REQUESTS FOR RE-EVALUATIONS OF PROGRAMS REJECTED DUE TO IMPROPER FORMAT WILL NOT BE ENTERTAINED. • We will check all solutions pair-wise from all sections of this course to detect cheating using moss software and related tools. If two submissions are found to be similar, they will instantly be awarded zero points and reported to office of student conduct. See Rutgers CS’s academic integrity policy at: https://www.cs.rutgers.edu/academic-integrity/introduction.
Autograder
We provide the AutoGrader to test your assignment. AutoGrader is provided as pa2 autograder.tar. Executing the following command will create the pa2 autograder folder.
tar xvf pa2_autograder.tar
There are two modes available for testing your assignment with the PA2 AutoGrader.
8
First mode
Testing when you are writing code with a pa2 folder
1. Lets say you have a pa2 folder with the directory structure as described in the assignment.
2. Copy the folder to the directory of the pa2 autograder
3. Run the pa2 autograder with the following command python pa2 autograder.py It will run the test cases and print your scores.
Second mode
This mode is to test your final submission (i.e, pa2.tar)
1. Copy pa2.tar to the pa2 autograder directory
2. Run the pa2 autograder.py with pa2.tar as the argument. The command line is:
python pa2 autograder.py pa2.tar
9
1 file (187.3KB)
