Multi Data Collections Objectives The objective of Assignment 5 is for us to gai
ID: 3869033 • Letter: M
Question
Multi Data Collections
Objectives
The objective of Assignment 5 is for us to gain experience designing a software solution using multiple data organizations (i.e., data collections).
We shall also gain experience expressing the design of our multiple data organizations by drawing their underlying data structures.
To get an idea of what a multiple data organization may be, have a look at the Programming Problem 6 of Chapter 16 in our textbook and pay particular attention to its Figure 16.22.
Problem Statement
To ease students' task of transferring from one academic institution to another (for example, from Douglas College to SFU), a group of Canadian institutions created a Multi-Institution Student Transfer System.
This Multi-Institution Student Transfer System allows administrative staff in the Registrar's Office of a Canadian university/college to easily obtain information about student transfer applications.
The information kept by the Multi-Institution Student Transfer System is as follows.
For students:
student last name and first name,
student mailing address,
student email address,
name of the home institution (the institution from which the student is transferring),
student number from home institution,
name of transfer institution (the institution to which the student is transferring),
faculty to which the student is applying (e.g.: Science, Applied Science, etc...),
programs into which the student is applying (e.g.: Math Major and/or Physics Minor and/or etc...).
For institution:
institution name,
institution mailing address,
email address of the institution's Registrar's Office,
phone number of the institution's Registrar's Office,
a listing of all students information (see students above) transferring to this institution,
a listing of all students information (see students above) transferring from this institution.
Note that the information listed above can be used as data members for a class Student and a class Institution. We may also need to add more data members to these classes in order to satisfy the requirements listed below.
Requirements
This group of Canadian institutions has asked us to design this Multi-Institution Student Transfer System, keeping in mind their requirements.
When the Multi-Institution Student Transfer System start executing, it allows the administrative staff in the Registrar's Office of a Canadian university or college to identify an institution by entering a piece of information related to this institution. As the designer of this Multi-Institution Student Transfer System, we must select which information related to an institution the administrative staff is to enter (see a listing of information related to institution above). Once the administrative staff has identified the institution on which they wish to focus their inquiries (by entering a piece of information related to this institution), the Multi-Institution Student Transfer System then allows the administrative staff to do any of the following actions:
Display all the information related to this institution in O(1).
Display the number of students transferring to this institution in O(1).
Display the number of students transferring from this institution in O(1).
Modify some information related to this institution in O(1). Note that only the information related to this institution that is not used to identify this institution within the Multi-Institution Student Transfer System can be modified.
Display all students transferring to this institution, by ascending alphabetical sort order of the last name, in O(n) where n is the number of students transferring to this institution.
Display all students transferring from this institution, by descending numerical sort order of student number, in O(m) where m is the number of students transferring from this institution.
Insert a student transferring to this institution in O(log2 n) where n is the number of students transferring to this institution, using the student's last name.
Insert a student transferring from this institution in O(m) (worst case scenario) where m is the number of students transferring from this institution, using the student's student number.
Given a student's last name, modify all information related to this student transferring to this institution (except her/his last name) in O(1).
Given a student's last name, display all information related to a student transferring to this institution in O(1).
Given a student's student number, modify all information related to this student transferring from this institution (except her/his student number) in O(1).
Given a student's student number, display all information related to a student transferring from this institution in O(1).
Note: During the execution of the Multi-Institution Student Transfer System, removal of an institution and student objects are never performed.
What we are asked to do in this Assignment 5
We must design the multiple data organizations (i.e., data collections) (and their underlying data structures) that support the Multi-Institution Student Transfer System described above. Our design must satisfy all the given requirements above and their associated time efficiency.
We must clearly express our design by drawing the multiple data organizations i.e., data collections, we came up with along with their underlying data structures. The kind of drawing we are asked to do here is very akin to what we were asked to do in Assignment 2.
We must populate our drawing with a sufficient number of an institution and student objects to give a clear idea of the organization of our data. For example, we must sufficiently populate our drawing so as to illustrate whether our data is sorted, and if so, which data member is used as the search key. Note that we do not have to include values for all the data members of an object, just enough to give a clear idea. However, make sure we always include the values of the crucial data members, i.e., the ones used as search keys and indexing keys.
In our drawing, we must label our data collections and their underlying data structures clearly by writing their names (Sorted List, BST, SHSL list, etc...)
Let's feel free to add comments and explanations to our drawing if we feel they are necessary.
We are free to create our drawing by hand then scan it or create our drawing using a drawing software application. Let's name our drawing Data_Collections_and_Structures.pdf.
In general, we know that objects (instantiated from classes) must not be duplicated in memory. Why? Therefore, our drawing must not include duplicated objects of the institution and student classes.
We can assume ideal hashing, i.e., 1-1 mapping. In other words, we can assume that our hashing functions will never create collisions.
We can also assume that students have unique last names.
Lastly, in this assignment, we are not asked to implement the Multi-Institution Student Transfer System, i.e., we are not asked to write code.
Picture of fig16.2
FIGURE 16-22 A queue that points into a doubly linked binary search tree treePtr Smith.. Baker.. Wilson.. Able. Jones.. queuePtrExplanation / Answer
private String name;
private int id;
private int[] grades;
private int numGrades;
private int totalGrades;
// The constructor
// initializes the instance variables
// name, id, grades = new int[totalGrades], and numGrades = 0;
public Student (String name, int id, int totalGrades){
name = this.getName();
id = this.getId();
grades = new int[totalGrades];
numGrades= 0;
//System.out.println(name+" "+id+" "+grades[0]+" "+grades[1]+" "+grades[2]+" "+grades[3]+" "+grades[4]+" "+" "+totalGrades);
}
public String toString() {
String res = name + " " + id + " ";
for (int i=0; i < totalGrades; i++) {
res += " " + grades[i];
}
res += " score: " + new DecimalFormat("0.00").format(computeScore());
return res;
}
@Override
public int compareTo(StudentIF arg0) {
if (arg0 == null) {
return 1;
}
if (this.id > arg0.getId())
return 1;
else if (this.id < arg0.getId())
return -1;
else
return 0;
}
@Override
public String getName() {
return name;
}
@Override
public int getId() {
return id;
}
@Override
public double computeScore() {
double total = 0;
if (numGrades == 0) {
return total;
}
if (numGrades > grades.length) {
numGrades = grades.length;
}
for (int i = 0; i < numGrades; i++) {
total += grades[i];
}
return total / numGrades;
//return 0;
}
@Override
public boolean addGrade(int newGrade) {
if(numGrades<grades.length){
grades[numGrades] = newGrade;
numGrades++;
// System.out.println(grades[0]+" "+grades[1]+" "+grades[2]+" "+grades[3]+" "+grades[4]);
return true;
}
return false;
}
@Override
public boolean equals(StudentIF other) {
if (other.getId() == this.getId()) {
return true;
}
return false;
}
}
public class StudentLL implements StudentCollectionIF{
private String course;
private StudentLLNode head;
private int size;
private boolean debug; // you can set debug in main
// the client code provides the course name
public StudentLL(String course){
course = this.course;
}
public String toString(){
String res = "Course: " + course + " ";
for(StudentLLNode curr = head; curr !=null; curr=curr.getNext()){
StudentIF nS = curr.getStd();
res = res + nS + " ";
}
return res;
}
@Override
public boolean insort(StudentIF s) {
StudentLLNode curr = head;
if (s == null) {
return false;
}
if (head == null) {
StudentLLNode student = new StudentLLNode(s);
head = student;
size++;
//System.out.println("working");
return true;
} else {
if (curr.getStd().compareTo(s) == 0) {
//System.out.println("working");
return false;
}
while (curr.getNext() != null) {
if(s.compareTo(curr.getStd()) == 1){
//c
}
curr = curr.getNext();
}
//c
StudentLLNode student1 = new StudentLLNode(s);
curr.setNext(student1);
size++;
return true;
}
}
@Override
public boolean remove(StudentIF s) {
StudentLLNode current = head;
if(s == null){
return false;
}
if(s.getId() == (head.getStd().getId())){
//StudentLLNode top = head;
head = head.getNext();
size--;
return true;
}
else{
StudentLLNode previous, next;
previous = current;
current = current.getNext();
while(current != null){
next = current.getNext();
if(s.getId() == (current.getStd().getId())){
previous.setNext(next); //doesn't matter if next is null or not
size--;
return true;
}
previous = current;
current = next;
}
}
return false;
}
@Override
public int size() {
// TODO Auto-generated method stub
return size;
}
@Override
public double classAvg() {
//double total = 0.0;
//for (int i=0; i<this.size(); i++) {
// total += grades[i];
//}
//return total / grades.length;
return 10;
}
@Override
public double classTopScore() {
return 10;
}
}
struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;
Node * create_node(int value){
Node * temp = (Node *)malloc(sizeof(Node));
temp->value = value;
temp->right= NULL;
temp->left = NULL;
return temp;
}
Node * addNode(Node *node, int value){
if(node == NULL){
return create_node(value);
}
else{
if (node->value > value){
node->left = addNode(node->left, value);
}
else{
node->right = addNode(node->right, value);
}
}
return node;
}
void treeToList(Node *node){
Queue *queue = NULL;
Node * last = NULL;
if(node == NULL)
return ;
enqueue(&queue, node);
while(!isEmpty(queue)){
/* Take the first element and put
both left and right child on queue */
node = front(queue);
if(node->left)
enqueue(&queue, node->left);
if(node->right)
enqueue(&queue, node->right);
if(last != NULL)
last->right = node;
node->left = last;
last = node;
dequeue(&queue);
}
}
/* Driver program for the function written above */
int main(){
Node *root = NULL;
//Creating a binary tree
root = addNode(root,30);
root = addNode(root,20);
root = addNode(root,15);
root = addNode(root,25);
root = addNode(root,40);
root = addNode(root,37);
root = addNode(root,45);
treeToList(root);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.