Write a java program to use binary search that takes in a file containing UC stu

Question

Write a java program to use binary search that takes in a file containing UC

student records and another file containing SMC alumni records and writes out to a file all the Pierce College

alumni who are attending UC schools, ordered by ID.

You think about the problem for a minute and you come up with a plan.

- You will create a Student class representing student records. It will have three data members

corresponding to the data contained in the student records file

int id;

String name;

String school;

- You will have no setters or getters in your Student class.

- You will override the equals method to consider two student objects as equal if they have the same ID.

- You will implement the comparable interface to allow sorting of student objects by ID.

- You will override the toString method to print the fields as they appear in the student records file.

The idea is that for every record you read from the file, you will create a Student object. You will store

the UC students into a student array and the SMC alumni into another student array. Parts 2 and 3

operate on these arrays.

Part 2:

Now that you have two arrays with one containing UC students and the other containing SMC

alumni, you plan to process the arrays and find the students who belong to both arrays. Your data

structures are these two arrays. Your algorithm will be: for each student in the UC students array you

try to find it in the SMC students array by doing a linear search on the SMC students array (comparing

for equality). If you do find it, that UC student is then stored in an array containing students who are

SMC alumni attending UC schools. Once you have the array of the common students, it is sorted by ID

and printed to a file. We will use the Java library sort for this.

Part 3:

After running your program from Part 2 and discovering that it takes ~ 5 - 10 minutes to

complete for the given input (much longer for larger files), you decide to really think about the problem

in order to find a solution that does not force your boss to go get a cup of coffee every time she needs

to run your program. It seems even those powerful processors in today's computers can't really save a

bad algorithm.

You remember from class that binary search is much more efficient than linear search for

finding an element in an array and decide to try it out. We will use the Java library binary search for

this. Your algorithm will be: for each student in the UC array you will binary search the sorted SMC

array. If the binary search finds the student, that UC student is stored in an array containing students

who are SMC alumni attending UC schools. Once you have the array of the common students, it is

sorted by ID and printed to a file. We will use the Java library sort for this.

***** You must use binary search on Arrays. Do not use ArrayList.

Explanation / Answer

Student.java:

public class Student implements Comparable<Student> {

//variables

private int id;

private String name;

private String school;

//Accessors and Mutators

public int getId() {

return id;

}

public void setId(int id) {

this.id = id;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public String getSchool() {

return school;

}

public void setSchool(String school) {

this.school = school;

}

//the equals method to consider two student objects as equal if they have the same ID.

@Override

public boolean equals(Object obj) {

if (this == obj)

return true;

if (obj == null)

return false;

if (getClass() != obj.getClass())

return false;

Student other = (Student) obj;

if (id != other.id)

return false;

return true;

}

//You will implement the comparable interface to allow sorting of student objects by ID.

@Override

public int compareTo(Student student) {

int anotherId = ((Student) student).getId();

//ascending order

return this.id - anotherId;

}

//You will override the toString method to print the fields as they appear in the student records file.

@Override

public String toString() {

return name+","+id+","+school;

}

}

SMCAlumniFinder.java:

import java.io.File;

import java.io.FileNotFoundException;

import java.io.FileWriter;

import java.io.IOException;

import java.util.Arrays;

import java.util.Scanner;

public class SMCAlumniFinder {

static Student[] readStudentsFromFile(String filename, int num) {

try {

Scanner in = new Scanner(new File(filename));

Student[] students = new Student[num];

int i = 0;

while (in.hasNextLine()) {

String line = in.nextLine();

Student student = new Student();

String[] lineSplit = line.split(",");

student.setName(lineSplit[0]);

student.setId(Integer.parseInt(lineSplit[1]));

student.setSchool(lineSplit[2]);

students[i] = student;

i++;

}

in.close();

return students;

} catch (FileNotFoundException e) {

e.printStackTrace();

return null;

}

}

static void writeStudentsToFile(Student[] students, String filename) {

FileWriter out = null;

try {

out = new FileWriter(filename);

for ( int i = 0; i < students.length; i++)

{

out.write(students[i].toString()+" ");

}

} catch (IOException e) {

e.printStackTrace();

}

finally{

//close resources

try {

out.close();

} catch (IOException e) {

e.printStackTrace();

}

}

}

static Student[] findCommonStudents1(Student[] group1, Student[] group2,

int numCommon) {

Student[] common = new Student[numCommon];

int k = 0;

for(int i=0;i<group1.length;i++){

for(int j=0;j<group2.length;j++){

Student student1 = new Student();

Student student2 = new Student();

student1 = group1[i];

int student1ID =student1.getId();

student2 = group2[j];

int student2ID =student2.getId();

if(student1ID == student2ID ){

common[k] =group1[i];

k++;

}

}

}

return common;

}

static Student[] findCommonStudents2(Student[] group1, Student[] group2,

int numCommon) {

Student[] common = new Student[numCommon];

Arrays.sort(group1);

Arrays.sort(group2);

int k=0;

Student student1 = new Student();

for (int j =0; j< group1.length; j++){

student1 = group1[j];

String school = group1[j].getSchool();

student1.setSchool("SMC");

int index = Arrays.binarySearch(group2, student1);

if(index >=0){

group2[index].setSchool(school);

common[k] = group2[index];

k++;

}  

}

return common;

}

public static void main(String[] args) {

    

/*Student[] uc = readStudentsFromFile("C:\eclipse\abc\sample_uc_students.txt", 10);

Student[] smc = readStudentsFromFile("C:\eclipse\abc\sample_smc_grads.txt", 5);

final int SMC_UC_GradsNumber = 2;*/

Student[] uc = readStudentsFromFile("uc_student.txt", 35);

Student[] smc = readStudentsFromFile("smc_grads.txt", 11);

final int SMC_UC_GradsNumber = 11;

long start, end;

start = System.currentTimeMillis();

Student[] common1 = findCommonStudents1(uc, smc, SMC_UC_GradsNumber);

end = System.currentTimeMillis();

System.out.println("Cross checking took " + (end - start) / 1000.0

+ " seconds.");

Arrays.sort(common1);

writeStudentsToFile(common1, "mc_grads_at_uc_1.txt");

start = System.currentTimeMillis();

Student[] common2 = findCommonStudents2(uc, smc, SMC_UC_GradsNumber);

end = System.currentTimeMillis();

System.out.println("Using binary search it took " + (end - start)

/ 1000.0 + " seconds.");

Arrays.sort(common2);

writeStudentsToFile(common2, "smc_grads_at_uc_2.txt");

}

}

Note: I cannot provide the output screenshots, as i dont have the input dataset with thousands of record. Include the proper input file to get required output.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.