Programming Project You are a programming intern at the alumni relations office.
ID: 3548924 • Letter: P
Question
Programming Project
You are a programming intern at the alumni relations office. Having heard you are taking CS 20B, your boss has come to ask for your help with a task.
Quite often she needs to process files containing records for students attending UC schools and find those who are SMC alumni. She needs you to write a program that takes in a file containing UC student records and another file containing SMC alumni records and writes out to a file all the SMC alumni who are attending UC schools, ordered by ID. This sounds like a very simple task and you immediately agree to work on it. She warns you that the files are pretty large - a few hundred thousand student records. You inform her that with today's computers having processors of a few GHz this task is a piece of cake and can be computed in an instant.
Part 1:
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 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 comparing it for equality (based on ID) with every student in the SMC students array. 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, you sort it by ID and print it 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,
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. You remember to sort the array in which you are searching, or the binary search algorithm will not work correctly. We will use the Java library sort and binary search for this. Your data structures are an array and a sorted array. 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, you sort it by ID and print it to a file.
Part 4 (Extra Credit - 10 points):
Does it affect the performance which array we do the binary search on for Part 3?
If yes, please explain why. If no, please explain why not. Be as specific as you can. Provide your (commented out) text answer (and run times, if you wish) in the SMCAlumniFinder.java file clearly marked Part 4.
Hints:
It is always a good idea to test each little piece after you complete it. Trying to debug a whole
program is hard and very time consuming.
Whenever you work with a large data set it is much easier to first work on a small data set to
ensure your program functions correctly. Once you are confident that it produces the correct result you can move to the larger data sets. To help get you started, two small sample input files and the expected output have been provided.
Deliverables:
Since this is the first project, the design and most of the work has been done for you. You
should write the Student class and fill out the missing code in the provided program.
You should submit a zip file named project1_first_last.zip (where first and last are your first and last name) containing:
Student.java SMCAlumniFinder.java output.txt smc_grads_at_uc_2.txt
Grading:
Student.java
the class
overriding the equals method overriding the toString method implementing comparable
SMCAlumniFinder.java readStudentsFromFile writeStudentsToFile findCommonStudents1 findCommonStudents2
// a copy of the program output containing ONLY the timing printouts // or .._1 if you do not get _2 working
10 points 10 points 5 points 10 points
10 points 5 points 25 points 25 points
Explanation / Answer
Code with comments
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;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.