Computer Science & Information Systems Data Structures

Question

1. Problem Statement

In this Problem, you have to write an application in C that keeps track of student records in a university.

At a university, there is a need to store all the details of graduating students. For this exercise, let us consider that the CGPA of the student is stored against the student id.

The students ID has the following format <YYYYAAADDDD> where

YYYY - represents the year in which this student joined the university

AAA - a three letter (alphabet) representing degree program

DDDD - a four digit number representing the students roll number

For instance, an ID can be of the form 2008CSE1223 corresponding to a student who joined the university in the year 2008 in the CSE department with the roll number 1223. The university offers a 4 year graduate degree program in CSE (Computer Science and Engineering), MEC (Mechanical Engineering), ECE (Electronics and Communication Engineering) and ARC (Architecture).

In the year 2008 the first batch of 20 students were admitted to the university. Now in the year 2018, 200 students were admitted across all departments. Consider the input with a random list of students per year and their corresponding CGPA (maximum of 5.0 point CGPA).

The university now wants to use the details of all its past students to:

a.   Identify and commemorate their alumni on the 10th year anniversary of the University. For this they will need to get a list of all students who scored over x CGPA.

b.   Extend a new course offering to selected students who have secured a CGPA between a specified range. For this they will need to get a list of all students who secured between CGPA x to CGPA y in the past five years.

c.    Identify the maximum and average CGPA per department.

Design a hash table, which uses student Id as the key to hash elements into the hash table. Generate necessary hash table definitions needed and provide a design document (1 page) detailing clearly the design and the details of considerations while making this design and the reasons for the specific choice of hash function.

Design a hash function HashId() which accepts the student-ID as a parameter and returns the hash value. You are only allowed to use basic arithmetic and logic operations in implementing this hash function.

Create / populate the hash table from the list of student ID and the corresponding CGPA.

Functions:

1.   def initializeHash(self): This function creates an empty hash table and points to null.

2.   def insertStudentRec(StudentHashRecords, studentId, CGPA): This function inserts the student id and corresponding CPGA into the hash table. The inputs contains the student ID and overall graduating CGPA (decimal value with a maximum of 5.0 points).

3.   def hallOfFame(StudentHashRecords, CGPA): This function prints the list of all students who have a CGPA greater than the CGPA passed to the function. The input can be identified with the tag mentioned below

hallOfFame: 4.5

Output format:

---------- hall of fame ----------

Input: 4.5

Total eligible students: 2

Qualified students:

2008CSE1225 / 4.5

2008CSE1226 / 4.8

-------------------------------------

Sample input

2008CSE1223 / 3.5

2008CSE1224 / 3.9

2008CSE1225 / 4.5

2008CSE1226 / 4.8

2008CSE1227 / 4.1

2008MEC1001 / 4.2

           Sample o/p

---------- hall of fame ----------

Input: 4.5

Total eligible students: 2

Qualified students:

2008CSE1225 / 4.5

2008CSE1226 / 4.8

Perform an analysis of functions 2 and 3 and give the running time in terms of input size n.

Instructions

1.     Implement the problem statement in c language. Make use of virtual labs for the same.

2.     Adhere to the data structures as indicated in the problem statement

3.     Ensure that operations throw appropriate messages when their capacity is empty or full.

4.     Write appropriate comments in the code.

5.     Run time analysis should be provided in asymptotic notations and not timestamp based runtimes in sec or milliseconds.

Deliverables

1.     Source code in .c files

2.     Asymptotic analysis of functions

3.     Create "how to use/run" text file which will have sequence of commands to compile and run your code.

4.     Create a document with screen shots displaying outputs for different methods.

Evaluation

a.      The assignment carries 15 percent weightage

b.     Grading will depend on

§ Fully executable code with all functionality

§ Well-structured and commented code

§ Accuracy of the run time analysis

The strict deadline of this assignment is 17^th June 2021

Answer 1

I got some source code for you but it's too big to list here..

either shoot me an email or we upload to the cloud...

Here is my suggestion for the hash table:

1st you need the data structure:

typedef struct _TStudentRec

{

int studentNum;

float studentGPA;

} * TStudentRec;

then you build the methods for the linked list

struct _TStudentListNode

{

struct _TStudentRec studentRec;

struct _TStudentListNode * next;

) * TStudentListNode;

Typedef struct _TStudentList

{

TStudentListNode first;

TStudentListNode next;

int count;

} * TStudentList;

StudentList_init();

StudentList_push();

StudentList_ToArray();

StudentList_FromArray();

typedef struct _TStudentHash

{

struct _TStudentList [4]; // one for each department : CSE, ESE, ARC, etc

} * TStudentHash

finally:

struct _TStudentHash[15]; // one for each year: 2008,2009,...2021,2022

Array is indexed by subtracting 2008 from the year. For example, student graduating

in 2014 shall be at index 2014-2008=6, which is the 7th hash table

You then index by the department: 0=CSE, 1=ESE, 2=ARC,etc.

You may use the following code fragments to parse the buffer containing the student record:

char * trim(char *str)

{

char *end;

// Trims leading space

while(isspace((unsigned char)*str)) str++;

if(*str == 0) // All spaces?

return str;

// Trims trailing space

end = str + strlen(str) - 1;

while(end > str && isspace((unsigned char)*end)) end--;

// Writes new null terminator character

end[1] = '\0';

return str;

}

//converts GPA from format XXX to X.XX; ex. "345" --> 3.45

float GPA_unpack(char * strGPA3, char * strGPA4)

{

strGPA4[0] = strGPA3[0];

strGPA4[1] = '.';

strGPA4[2] = strGPA3[1];

strGPA4[3] = strGPA3[2];

strGPA4[4] = 0;

return(atof(strGPA4));

}

//converts GPA to 3 bytes; ex 3.45 --> "345"

void GPA_pack( float gpa, char * strGPA3)

{

char strGPA4[4];

memset(strGPA4,0,4);

sprintf(strGPA4,"%0.2f",gpa);

strGPA3[0] = strGPA4[0];

strGPA3[1] = strGPA4[2];

strGPA3[2] = strGPA4[3];

}

ParseStudentRec(TStudentRec studentRec, char * inbuff)

{

char dataBuff[5];

char * studentRecBuff = trim(inbuff);

char studentID[STUDENT_ID_LENGTH];

float gpa;

memset(studentID,0,STUDENT_ID_LENGTH);

//parses student id

strcpy(studentID,trim(strtok(studentRecBuff,"/")));

//graduation year

memset(dataBuff,0,5);

memcpy(dataBuff,studentID,4);

studentRec->year = (char) (atoi(dataBuff)-BASE_YEAR);

//department

memset(dataBuff,0,5);

memcpy(dataBuff,studentID+4,3);

if (strncmp(dataBuff,"CSE",3)==0)

{

studentRec->dept = DEPARTMENT_CSE;

}

else if (strncmp(dataBuff,"MEC",3)==0)

{

studentRec->dept = DEPARTMENT_MEC;

}

else if (strncmp(dataBuff,"ECE",3)==0)

{

studentRec->dept = DEPARTMENT_ECE;

}

else if (strncmp(dataBuff,"ARC",3)==0)

{

studentRec->dept=DEPARTMENT_ARC;

}

else

{

studentRec->dept = DEPARTMENT_NONE;

}

//student #

memset(dataBuff,0,5);

memcpy(dataBuff,studentID+7,4);

studentRec->studentNum= atoi(dataBuff);

//GPA

gpa = atof(strtok(NULL,"/"));

GPA_pack(gpa,studentRec->GPA);

}

DumpStudentRec(TStudentRec studentRec)

{

char GPA[5];

printf(" year = %d \n",studentRec->year+BASE_YEAR);

printf(" dept = %c \n",studentRec->dept);

printf(" student # = %d \n",studentRec->studentNum);

GPA[0] = studentRec->GPA[0];

GPA[1] = '.';

GPA[2] = studentRec->GPA[1];

GPA[3] = studentRec->GPA[2];

GPA[4] = 0;

printf(" GPA = %s \n",GPA);

}

GetStudentRecGPA(TStudentRec studentRec,TStudentGPA studentGPA)

{

char gpaBuff[5];

studentGPA->studentGPA = GPA_unpack(studentRec->GPA,gpaBuff);

studentGPA->studentNum = studentRec->studentNum;

}

int CompareByGPA(const void * rec1, const void * rec2)

{

TStudentGPA studentRecPtr1 = (TStudentGPA)rec1;

TStudentGPA studentRecPtr2 = (TStudentGPA)rec2;

int iReturn=0;

if (studentRecPtr1->studentGPA != studentRecPtr2->studentGPA)

{

iReturn = (studentRecPtr1->studentGPA > studentRecPtr2->studentGPA) ? 1 : -1;

}

return(iReturn);

}

int CompareByNum(const void * rec1, const void * rec2)

{

TStudentGPA studentRecPtr1 = (TStudentGPA)rec1;

TStudentGPA studentRecPtr2 = (TStudentGPA)rec2;

return(studentRecPtr1->studentNum - studentRecPtr2->studentNum);

}

StudentList_Init(TStudentList studentList)

{

studentList->first = studentList->last = NULL;

studentList->count=0;

}

StudentList_Push(TStudentList studentList, TStudentGPA studentRecGPA)

{

TStudentListNode newStudentListNode = (TStudentListNode)malloc(STUDENT_LIST_NODE_SIZE);

memcpy(&newStudentListNode->studentGPA,studentRecGPA,STUDENT_GPA_SIZE);

newStudentListNode->next = NULL;

if (studentList->count==0)

{

studentList->first = studentList->last = newStudentListNode;

}

else

{

studentList->last->next = newStudentListNode;

studentList->last = studentList->last->next;

}

studentList->count++;

}

//transfers student records from list to array; list is destroyed

StudentList_ToArray(TStudentList studentList, TStudentGPA arrayStudentGPA, int * n)

{

int iLoop;

TStudentListNode cur= studentList->first;

*n = studentList->count;

for (iLoop=0; iLoop<studentList->count; iLoop++)

{

studentList->first = studentList->first->next;

memcpy(&arrayStudentGPA[iLoop],&cur->studentGPA,STUDENT_GPA_SIZE);

free(cur);

cur = studentList->first;

}

studentList->count=0;

studentList->first = studentList->last=NULL;

}

//transfers student records from array to list; array is destroyed

StudentList_FromArray(TStudentList studentList, TStudentGPA arrayStudentGPA, int * n)

{

int count = *n;

int iLoop;

StudentList_Init(studentList);

for (iLoop=0; iLoop<count; iLoop++)

{

StudentList_Push(studentList,&arrayStudentGPA[iLoop]);

}

free(arrayStudentGPA);

arrayStudentGPA=NULL;

}