BEST代写-线上编程学术专家

Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

C语言代写 | CS211: Programming Assignment 1

C语言代写 | CS211: Programming Assignment 1

这个作业是介绍C语言的链接、编译等入门知识

CS211: Programming Assignment 1:
Intro to C Programming
1 Array Sorting
You have to write a program named first that will read an array from a file and sort the given array. You
will return the array sorted with all odd numbers in ascending order at the front followed by all even
numbers in descending order. You can use any sorting algorithm you know or wish to use. However, you
cannot use the library sort functions. You should write your own sort function.
1.1 Input Format
Your program will take a file name as an input. The first line in the file provides the total number of
values in the array. The second line will contain a list of numbers separated by tabs. For example a
sample input file “example_file.txt” is:
6
25 10 1 99 4 2
example_file.txt
1.2 Output Format
Your output will be a sorted list of numbers, odd numbers in ascending order and then even numbers
in descending order, each separated by tabs.
Command Line
$ ./first example_file.txt
1 25 99 10 4 2
1.3 Things to Note
• We will not give you improperly formatted files. You can assume all your input files will be in proper
format as above.
• Hint: It may be helpful to move all odd numbers to the front of an array first and then sort them.
1
2 Hash Table
In this part, you will implement a hash table containing integers. The hash table has 10,000 buckets. An
important part of a hash table is collision resolution. In this assignment, we want you to use chaining with
a linked list to handle a collision. This means that if there is a collision at a particular bucket then you
will maintain a linked list of all values stored at that bucket. For more information about chaining, see
http://research.cs.vt.edu/AVresearch/hashing/openhash.php
A hash table can be implemented in many ways in C. You must find a simple way to implement a hash
table structure where you have easy access to the buckets through the hash function. As a reminder, a hash
table is a structure that has a number of buckets for elements to ”hash” into. You will determine where
the element falls in the table using a hash function we describe below.
You must not do a linear search of the 10,000 element array. We will not award any credit for O(n) time
implementation of searches or insertions in the common case.
For this problem, you will be using the following hash function: key modulo the number of buckets.
2.1 Input Format
This program takes a file name as argument from the command line. The file contains successive lines of
input. Each line contains a character, either ‘i’ or ‘s’, followed by a tab and then an integer. For each line
that starts with ‘i’, your program should insert that number in the hash table if it is not present. If the line
starts with a ‘s’, your program should search the hash table for that value.
i 10
i 12
s 10
i 10
s 5
example_file.txt
2.2 Output Format
For each line in the input file, your program should print the status/result of that operation. For an insert,
the program should print “inserted” if the value is inserted or “duplicate” if the value is already present.
For a search, the program should print ”present” or “absent” based on the outcome of the search. You can
assume that the program inputs will have proper structure.
Command Line
$ ./second example_file.txt
inserted
inserted
present
duplicate
absent
2
3 Bit Function
In this exercise, you have to write a program that will read a number followed by a series of bit operations
from a file and perform the given operations sequentially on the number. The operations are as follows:
• set(x, n, v): sets the nth bit of the number x to v
• comp(x, n, v): sets the value of the nth bit of x to its complement (1 if 0 and 0 if 1)
• get(x, n, v): returns the value of the nth bit of the number x.
The least significant bit (LSB) is considered to be index 0.
For this exercise, you must use logical operations to implement the three functions. You are not allowed
to use any arithmetic operations or math library functions.
3.1 Input Format
Your program will take the file name as input. The first line in the file provides the value of the number x
to be manipulated. This number should be considered an unsigned short. The following lines will contain
the operations to manipulate the number. To simplify parsing, the format of the operations will always be
the command name followed by 2 numbers, separated by tabs. For the set(x, n, v) command, the value
of the second input number (v) will always be either 0 or 1. For the comp(x, n) and get(x, n) commands
the value of the second input number will always be 0 and can be ignored. Note that the changes to x are
cumulative, rather than each instruction operating independently on the original x.
5 # x =5
get 0 0 # get (x , 0) , ignoring second value (0)
comp 0 0 # comp (x , 0) , ignoring second value (0)
set 1 1 # set (x ,1 ,1)
example_file.txt
3.2 Output Format
Your output for comp and set commands will be the resulting value of the number x after each operation,
each on a new line. For get commands, the output should be the requested bit’s value.
Command Line
$ ./third example_file.txt
1
4
6
3
4 One-Shot Learning
In this exercise, 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 + w1x1 + w2x2 + w3x3 + w4x4 (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 N ∗ (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 data as a
N × 1 matrix, which we call Y :





y0
y1
.
.
.
yn





Similarly, we can represent the weights for each attributes as a (K + 1) × 1 matrix, which we call W:





w0
w1
.
.
.
wn





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 , W
are matrices as described above.
XW = Y
Using the training data, we can learn the weights using the below equation:
W = (XT X)
−1XT Y
4
where XT
is the transpose of the matrix X and (XT X)
−1
is the inverse of the matrix XT X.
Your main task in this part of the assignment is 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 inverse 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 assignment. The algorithm you are implementing is known as linear regression with least
square error as the error measure. The matrix (XT X)
−1XT
is also known as the pseudo-inverse of matrix
X. If you are curious, you can learn more about this algorithm at

4.1 Computering the Inverse using Gause-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 Gauss-Jordan elimination, which is described below. If you compute
inverse using any other method, you will risk losing all points for this part.
Inverse of a square matrix A is another square matrix B, since AB = BA = I, where I is the identity
matrix.
4.1.1 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’s 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 os A is:


1 2 4 1 0 0
1 6 7 0 1 0
1 3 2 0 0 1


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 more complex Gauss-Jordan elimination method,
you are allowed to swap the rows. For simplicity, we do not allow you to swap the rows.
5
Let’s see this method with the above augmented matrix Aaug. Again, our goal is to transform A part of
Aaug into an identity matrix. Since Aaug[1][0] 6= 0, we will subtract the first row from the second row to
make Aaug[1][0] = 0. Hence, we perform the operation R1 = R1 − R0 where R1 and R0 represent the
second and first row of the augmented matrix:


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 after this operation 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 after this operation 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 resulting
matrix 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 :


1 2 4 1 0 0
0 1 3
4 −
1
4
1
4
0
0 0 1 3
11
1
11 −
4
11


So far we have moved down the matrix and zero’ed the lower triangle matrix to 0’s and the diagonals of
the original matrix A to 1’s. Now, we will move up the matrix and transform the upper triangle portion of
the original matrix A to 0.
As a first step of this phase, we want to make Aaug[1][2] = 0. Hence, we perform the operation R1 =
R1 −
3
4 × R2 :


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:


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:


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


6
At this time, the A part of the augmented matrix is an identity matrix. The inverse of A matrix is the right
half of the augmented matrix, which originally was the identity matrix:


9
11 −
8
11
10
11

5
11
2
11
3
11
3
11
1
11 −
4
11


Your program must implement how to compute the inverse of a matrix using Gaussian-Jordan elmination
in order to perform one-shot learning.
4.2 Input Format
4.2.1 Training Data
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 double precision
value in the line represents the price of the house. The remaining K double precision values represent the
values for the attributes of the house.
4
7
21900.000000 ,3.000000 ,1.000000 ,1180.000000 ,1955.000000
538000.000000 ,3.000000 ,2.250000 ,2570.000000 ,1951.000000
180000.000000 ,2.000000 ,1.000000 ,770.000000 ,1933.000000
604000.000000 ,4.000000 ,3.000000 ,1960.000000 ,1965.000000
510000.000000 ,3.000000 ,2.000000 ,1680.000000 ,1987.000000
1230000.000000 ,4.000000 ,4.500000 ,5420.000000 ,2001.000000
257500.000000 ,3.000000 ,2.250000 ,1715.000000 ,1995.000000
train1.txt
In the example above, there are 4 attributes and 7 training data examples. Each example has the price of
the house followed by the values for the attributes. To illustrate, consider the training example below:
221900.000000, 3.000000, 1.000000, 1180.000000, 1955.000000
The price of the house is 221900.000000. The first attribute has value 3.000000, the second attribute has
value 1.000000, the third attribute has value 1180.000000, and the fourth attribute has value 1955.000000.
4.2.2 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.
2
3.000000 ,2.500000 ,3560.000000 ,1965.000000
2.000000 ,1.000000 ,1160.000000 ,1942.000000
test1.txt
7
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.
4.3 Output Format
Your program for this part will be executed as follows:
$./fourth <train-data-file-name> <test-data-file-name>
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) using (EQ1).
A sample output of the execution when you execute your program is shown below:
Command Line
$ ./fourth train.txt test1.txt
737861
203060
Submission
Submission Folder Structure
All files must be included in the pa1 folder. The pa1 directory in your tar file must contain 9 subdirectories, one each for each of the parts. The name of the directories should be named first through fourth (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).
pa1
first
first.c
first.h (if used)
Makefile
second
second.c
second.h (if used)
Makefile
third
third.c
third.h (if used)
Makefile
fourth
fourth.c
fourth.h (if used)
Makefile

bestdaixie

评论已关闭。