4 Programming Question (40 points) 4.1 Instructions You need to write the code b
ID: 3871519 • Letter: 4
Question
4 Programming Question (40 points) 4.1 Instructions You need to write the code by yourself. Your implementation must use C/C++ and your code must run on the Linux machine general.asu.edu. Please refer to the programming guide (available under the Assignments folder on Blackboard) for using the general.asu.edu server, as well as compiling and running C/C++ code under Linux For this question, you need to provide a Makefile that compiles your program to an executable named a2 that runs on the Linux machine general.asu.edu. Our TA will write a script to compile and run all student submissions; therefore, executing the command make in the Code folder must produce the executable a2 also located in the Code folder 4.2 Requirements In this question, you will write a serial program that executes a sequence of commands that operate on individual files. Valid commands include: . Start Name, where Name is a character string of maximum length 20 alphabetic characters representing the name of the data file (Name.txt). The structure of Name.txt is an integer N indicating the total number of data entries contained in this file, followed by N additional lines of integers (the actual data entries). This command first reads N from the file Name.txt, dynamically allocates an array of integers of size N (if it has not already been allocated), and then reads the remaining N data entries into the array. The commands that follow until the End command are to be applied to the resulting data array The output of the Start command is Processing data from: Name.txt End Name, which indicates the end of the processing for the data in file Name.txt. The Start and End commands will always come in pairs with matching names. Any memory dynamically allocated for Name must be freed on an End command. The output of the End command is End of processing data from: Name.txtExplanation / Answer
Project2.java
import java.io.FileNotFoundException;
import java.util.Scanner;
import name.Name;
public class Project2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input, command;
Name n1 = new Name();
try {
Scanner sc = new Scanner(System.in);
do {
System.out.println("Enter the command. "); /ac/ Take input from
// user
command = sc.next();
if (command.compareTo("Start") == 0) // If command is Start call
// Start function.
{
input = sc.next();
n1.start(input);
} else if (command.compareTo("InsertionSort") == 0) // If
// command
// is
// InsertionSort
// call
// InsertionSort
// function.
{
n1.insertionSort();
n1.reinitialise(n1.name); // reinitialise the array
} else if (command.compareTo("MergeSort") == 0) // If command is
// InsertionSort
// call
// InsertionSort
// function.
{
n1.mergeSort();
n1.reinitialise(n1.name); // reinitialise the array
} else if (command.compareTo("Select") == 0) // If command is
// Select call
// Select
// function.
{
input = sc.next();
int temp = n1.select(input);
} else if (command.compareTo("Average") == 0) // If command is
// Average call
// Average
// function.
{
n1.average();
} else if (command.compareTo("End") == 0) // If command is End
// call End
// function.
{
input = sc.next();
n1.end(input);
} else if (command.compareTo("Exit") == 0) // If command is Exit
// call Exit
// function.
{
n1.exit();
} else
System.out.println("Invalid command.");
} while (command.compareTo("Exit") != 0 && sc.hasNext());
sc.close();
} catch (FileNotFoundException e) {
System.out.println("File not found");
} catch (Exception e) {
e.printStackTrace();
}
}
}
Name.java
package name;
import java.io.BufferedReader;
import java.io.FileReader;
import sort.InsertionSort;
import sort.MergeSort;
public class Name {
int fitnessData[];
int size; // will store the size of array
int sort; // to check if array is sorted or not
public String name;
int endname;
int sortedData[]; // store sorted array
public Name() {
// TODO Auto-generated constructor stub
size = 0;
sort = 0;
name = "";
endname = 1;
}
public void reinitialise(String input) throws Exception {
sort = 1;
sortedData = new int[size];
for (int i = 0; i < size; i++) {
sortedData[i] = fitnessData[i]; // Store the sorted data
}
input = input.concat(".txt"); // append ".txt" to define the
// extension of file to be read
FileReader inputFile = new FileReader(input);
BufferedReader bufferReader = new BufferedReader(inputFile);
String line;
line = bufferReader.readLine();
if (line != null) {
endname = 0;
size = Integer.parseInt(line); // read total no of inputs
fitnessData = new int[size];// initialize array with the size
}
for (int i = 0; i < size; i++) {
line = bufferReader.readLine();
if (line != null) {
fitnessData[i] = Integer.parseInt(line);// store input
// values in the
// array
}
}
bufferReader.close();
}
public void start(String input) throws Exception {
if (endname == 0) {
System.out.println("Invalid Start "); // Give error for consequtive
// start
} else if (endname == 1) {
name = input;
input = input.concat(".txt"); // append ".txt" to define the
// extension of file to be read
FileReader inputFile = new FileReader(input);
BufferedReader bufferReader = new BufferedReader(inputFile);
String line;
System.out.println("Processing fitness data of: " + name);
line = bufferReader.readLine();
if (line != null) {
endname = 0;
size = Integer.parseInt(line); // read total no of inputs
fitnessData = new int[size];// initialize array with the size
}
for (int i = 0; i < size; i++) {
line = bufferReader.readLine();
if (line != null) {
fitnessData[i] = Integer.parseInt(line);// store input
// values in the
// array
}
}
bufferReader.close();
} else
System.out.println("Unable to open file. "); // gives error if file
// not
// found
}
public void end(String input) {
if (input.compareTo(name) == 0) {
System.out.println("End of processing fitness data for: " + name);
size = 0; // deallocating memory
sort = 0;
// fitnessData = null;
// sortedData = null;
name = "";
endname = 1;
} else {
System.out.println("Invalid End. "); // if user tries to end
// different name
}
}
public void insertionSort() {
InsertionSort is = new InsertionSort();
fitnessData = is.insertionSort(fitnessData);
}
public void mergeSort() {
MergeSort is = new MergeSort();
fitnessData = is.mergeSort(fitnessData, 0, fitnessData.length - 1);
is.printAns();
}
public int select(String input) {
if (sort == 0) // check if array is sorted
{
System.out.println("Unable to select from an unsorted array. "); // error
// if
// array
// is
// not
// sorted
} else {
int i;
if (input.compareTo("min") == 0) {
i = 0; // smallest value i.e. first data item
} else if (input.compareTo("max") == 0) {
i = size - 1; // largest value i.e. last data item
} else if (input.compareTo("median") == 0) {
if (size % 2 == 0) // if the array contains even numbers
{
i = size / 2;
float median = (sortedData[i] + sortedData[i - 1]);
System.out.println("Selecting item: " + median / 2); // median
// is
// mean
// (average)
// of
// the
// two
// middlemost
// numbers
return 0;
} else
i = size / 2; // if the array contains odd number
} else {
i = Integer.parseInt(input);
if (i < 1 || i > size) // check if input is greater than or less
// than size of array
{
System.out.println("Invalid input."); // prints error if
// input greater
// than size of
// array
return 0;
}
i--;
// cout<<i;
}
System.out.println("Selecting item: " + sortedData[i]);
return 0;
}
return 1;
}
public void average() {
float avg = 0;
for (int i = 0; i < size; i++) {
avg += fitnessData[i]; // sum of all elements in array
}
avg = avg / size; // divide by the total number of elements to get
// average
System.out.println("Average number of steps: " + avg);
}
public void exit() {
System.out.println("Program terminating.");
}
}
InsertionSort.java
package sort;
public class InsertionSort {
int compare, swap;
public InsertionSort() {
// TODO Auto-generated constructor stub
compare = 0;
swap = 0;
}
public int[] insertionSort(int data[]) {
int key;
for (int i = 1; i < data.length; i++) // Insertion Sort
{
key = data[i];
int j = i - 1;
while (j >= 0 && data[j] > key) {
compare++;
data[j + 1] = data[j];
j = j - 1;
swap++;// increment swap when we place the element in proper
// position
}
compare++; // increment compare when data[j]>key is false
data[j + 1] = key;
}
System.out.println("Number of comparisons made by insertion sort: "
+ compare);
System.out.println("Number of swaps made by insertion sort: " + swap);
return data;
}
}
MergeSort.java
package sort;
public class MergeSort {
int compare, swap;
public MergeSort() {
// TODO Auto-generated constructor stub
compare = 0;
swap = 0;
}
public int[] merge(int data[], int start, int mid, int end) {
int sortedList[] = new int[data.length];
for (int i = 0; i < data.length; i++) {
sortedList[i] = data[i]; // store array in temp file for reference
}
int i = start;
int j = mid + 1;
int z = start;
while (i <= mid && j <= end) {
compare++;
// swap++;
if (sortedList[i] <= sortedList[j]) {
data[z] = sortedList[i];
i++;
} else {
data[z] = sortedList[j];
j++;
swap++;
}
z++;
}
if (i <= mid) {
for (int k = z; k <= end; k++) {
data[k] = sortedList[i]; // If left array is not traveresed
// completely
i++;
}
} else if (j <= end) {
for (int k = z; k <= end; k++) {
data[k] = sortedList[j]; // If right array is not traveresed
// fully
j++;
}
}
return data;
}
public int[] mergeSort(int data[], int start, int end) {
int mid;
if (start < end) {
mid = ((start + end) / 2);
data = mergeSort(data, start, mid); // mergesort on Left part of
// array
data = mergeSort(data, mid + 1, end); // mergesort on Right part of
// array
data = merge(data, start, mid, end);
}
return data;
}
public void printAns() {
System.out.println("Number of comparisons made by insertion sort: "
+ compare);
System.out.println("Number of swaps made by insertion sort: " + swap);
}
}
MergeSort.java
package sort;
public class MergeSort {
int compare, swap;
public MergeSort() {
// TODO Auto-generated constructor stub
compare = 0;
swap = 0;
}
public int[] merge(int data[], int start, int mid, int end) {
int sortedList[] = new int[data.length];
for (int i = 0; i < data.length; i++) {
sortedList[i] = data[i]; // store array in temp file for reference
}
int i = start;
int j = mid + 1;
int z = start;
while (i <= mid && j <= end) {
compare++;
// swap++;
if (sortedList[i] <= sortedList[j]) {
data[z] = sortedList[i];
i++;
} else {
data[z] = sortedList[j];
j++;
swap++;
}
z++;
}
if (i <= mid) {
for (int k = z; k <= end; k++) {
data[k] = sortedList[i]; // If left array is not traveresed
// completely
i++;
}
} else if (j <= end) {
for (int k = z; k <= end; k++) {
data[k] = sortedList[j]; // If right array is not traveresed
// fully
j++;
}
}
return data;
}
public int[] mergeSort(int data[], int start, int end) {
int mid;
if (start < end) {
mid = ((start + end) / 2);
data = mergeSort(data, start, mid); // mergesort on Left part of
// array
data = mergeSort(data, mid + 1, end); // mergesort on Right part of
// array
data = merge(data, start, mid, end);
}
return data;
}
public void printAns() {
System.out.println("Number of comparisons made by insertion sort: "
+ compare);
System.out.println("Number of swaps made by insertion sort: " + swap);
}
}
input.txt
399
49051
73854
64619
20400
5988
3180
4887
3174
25189
7884
11756
9546
59912
74673
2238
14930
38099
71185
13704
4483
72218
21055
1654
46987
18561
1880
24927
23762
4211
16652
2360
11943
48071
28030
72418
2673
57030
22093
8162
31879
5303
3597
47538
46421
1146
20052
72360
1819
12828
59911
8215
67586
67017
12781
33759
15959
4772
2144
53267
4412
7843
1272
2164
3190
50793
942
15038
65606
15207
14939
14400
1732
1806
63834
21145
15486
2563
43247
18554
18571
13892
59708
43393
690
25053
4418
52231
56829
72378
19110
3263
2864
67559
51906
4902
4813
843
1576
3687
6689
1951
15398
2110
45719
70596
58864
17130
18537
1193
4155
22273
49241
16842
33704
13140
29623
7353
1774
64953
20655
3175
50760
953
9346
14741
10093
18175
60334
36855
46399
1636
4087
18748
66156
17058
1103
14036
57890
3513
16487
2443
21473
2618
57339
37199
58173
1613
10177
70325
74915
44497
58321
2233
4874
11152
8354
14645
19917
16635
66441
62348
60874
65578
24675
15088
34638
6460
55823
66875
1292
21411
1827
826
3672
4205
2352
64431
25367
13629
764
30984
59655
42566
23489
20177
4821
22132
38997
3596
24476
24487
4707
27406
13928
13616
41104
70800
3396
57591
24160
20724
1060
2981
14871
580
5879
5527
3338
39013
25320
19664
74934
58536
3682
62921
5247
57323
3205
49718
34734
9775
69717
27404
9587
527
1900
32684
3859
5017
22348
2736
9287
4255
17568
10273
3623
14267
4203
2101
9442
42550
4671
1676
7807
61423
24484
3602
17571
1469
42683
2293
3291
52000
12436
2990
14581
2572
40127
2486
39795
941
2421
9403
1105
36835
74615
67448
72744
5957
2049
8411
28192
70586
36085
73957
2185
21511
19645
21154
2139
60540
41321
60217
38788
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.