Algorithms & Data Structures Review Sheet 1
Modern University Academic Year: 2021/2022
For Technology & Information Semester: Spring 2022
Faculty of Computers & AI Specialization: Level Tow
Course:CS231 Algorithms& Data Structures
Prof.\ Alaa Abd El-Raheem
T.A Dawad
CS231 Data Structure Review Sheet 1
1 Time Class
Define and implement a time class. Each object of this class represents a certain time of the day.
The hours, minutes and seconds are stored as integer numbers. The class includes a constructor,
the method normalize() that converts a time object such that its elements become in the correct
range (0<=hr<24, 0<=min<60, 0<=sec<60), the method advance(int h, int m, int s) to advance the
current time of an existing object, the method reset(int h, int m, int s) to reset the time of an
existing object and the method print(). Write an application program to demonstrate this class.
1.1 // Header File save as Time.h
#include<iostream>
class Time
{
private:
int second, minute, hour;
public:
Time(); // Default constructor
Time(int h, int m, int s); // Parametrized constructor
void reset(int h, int m, int s); // Changes time data
void print(); // Shows time data
void normalize(); // Adjusts time to be normal
void advance(int h, int m, int s); // Adds time to this time
};
1
Algorithms & Data Structures Review Sheet 1
1.2 // Implementation of the Time Class save as Time.cpp
#include<iostream>
#include"Time.h"
using namespace std;
Time::Time(){
second = 0;
minute = 0;
hour = 0;
}
Time::Time(int h, int m, int s){
hour = h;
minute = m;
second = s;
}
void Time::reset(int h, int m, int s){
hour = h;
minute = m;
second = s;
}
void Time::print(){
cout << hour << ":" << minute << ":" << second << endl;
}
void Time::normalize(){
minute = minute + second / 60;
second = second % 60;
hour = hour + minute / 60;
minute = minute % 60;
hour = hour % 24;
}
void Time::advance(int h, int m, int s){
second = second + s;
minute = minute + m;
hour = hour + h;
normalize();
}
2
Algorithms & Data Structures Review Sheet 1
1.3 // Time Main Function
#include<iostream>
#include"Time.h"
using namespace std;
void main(){
Time time;
time.reset(11, 121, 131);
cout << "The time before normalization: ";
time.print();
time.normalize();
cout << "The time after normalization: ";
time.print();
int h, m, s;
cout << "Enter time to add:" << endl;
cout << "Enter hours: ";
cin >> h;
cout << "Enter minutes: ";
cin >> m;
cout << "Enter seconds: ";
cin >> s;
time.advance(h, m, s);
cout << "The time after advancing: ";
time.print();
}
3
Algorithms & Data Structures Review Sheet 1
2 Date Class
Define and implement a date class. Each object of this class represents a certain date. The day,
month and year are stored as integer numbers. The class includes a constructor, the method
days() that convert a date object to days from the start of the current year, the method print() to
print the date in the form dd/mm/yyyy. Write an application program to demonstrate this class.
2.1 // Header File save as Date.h
#include<string>
using namespace std;
class Date {
private:
int day; // Day # (Range : 1-31)
int month; // Month # (Range : 1-12)
int year; // Year # (Range : 1901-2099)
public:
void set(int d, int m, int y); // Sets date data
bool leap(); // Checks if the year is leap
bool valid(); // Checks if the date is valid (numbers in range)
int yearDay(); // Returns day number in current year
int days(); // Returns days since 1/1/1901
string weekDay(); // Return weekday
void print(); // Shows date data (Weekday, Monthname day#, year#)
void add(int n); // Adds n days to this date
};
4
Algorithms & Data Structures Review Sheet 1
2.2 // Implementation of the Date Class save as Date.cpp
#include"Date.h"
#include<iostream>
#include<string>
using namespace std;
// Sets date data
void Date::set(int d, int m, int y) {
day = d;
month = m;
year = y;
}
// Checks if the year is leap
bool Date::leap(){
if (year % 4 == 0)
return true;
else
return false;
//return !(year%4);
}
// Checks if the date is valid (all numbers are in the specified range)
bool Date::valid(){
int month_days[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
if (leap())
month_days[2] = 29;
if (month < 1 || month > 12)
return false;
if (day < 1 || day > month_days[month])
return false;
if (year < 1901 || year > 2099)
return false;
return true;
}
// Returns day number in current year
int Date::yearDay(){
if (!valid())
return -1;
int sum_days[] = { 0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 };
int yearDay = sum_days[month] + day;
if (leap())
5
Algorithms & Data Structures Review Sheet 1
yearDay++;
return yearDay;
}
// Returns days since 1/1/1901
int Date::days(){
if (!valid())
return -1;
int years = year - 1901;
int days = years * 365.25 + yearDay();
return days;
}
// Return weekday, NOTE: 1/1/1901 was a tuesday
string Date::weekDay(){
if (!valid())
return "-1";
const char* weekdays[] = { "Monday", "Tuesday", "Wednesday", "Thursday", "Friday",
"Saturday", "Sunday" };
return weekdays[days() % 7];
}
// Shows date data (Weekday, Monthname day#, year#)
void Date::print() {
const char* month_name[] = { "", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep",
"Oct", "Nov", "Dec" };
if (!valid())
cout << "Invalid Date!" << endl;
else cout << weekDay() << ", " << month_name[month] << " " << day << " " << year <<
endl;
}
6
Algorithms & Data Structures Review Sheet 1
// Adds n days to this date
void Date::add(int num)
{
int month_days[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
day += num;
while (day > month_days[month]){
if (leap())
month_days[2] = 29;
else
month_days[2] = 28;
day -= month_days[month];
month++;
if (month > 12){
month = 1;
year++;
}
}
}
2.3 // Date Main Function
#include"Date.h"
#include<iostream>
#include<string>
using namespace std;
void main(){
Date date;
int day, month, year, n;
cout << "Enter day: ";
cin >> day;
cout << "Enter month: ";
cin >> month;
cout << "Enter year: ";
cin >> year;
date.set(day, month, year);
cout << endl << "Full date: ";
date.print();
cout << "Year day: " << date.yearDay() << endl;
cout << "Days since 1901: " << date.days() << endl << endl;
cout << "Enter days to add: ";
cin >> n;
7
Algorithms & Data Structures Review Sheet 1
date.add(n);
cout << "Date after adding: ";
date.print();
}
8
Algorithms & Data Structures Review Sheet 1
3 Student Class
The student ADT is:
Private: Stud_ID, Stud_Name, Stud-Level, Stud_Scores.
Public Operations: Constructor, Set_Stud_Data, Print_Stud, GPA.
Write using C++ student class and its implementation, then demonstrate all the student
operations.
3.1 // Header File save as Student.h
#include <iostream>
#include <string>
using namespace std;
const int sub_n = 6;
class Student {
private:
int stud_id, stud_level;
string stud_name;
double stud_scores[sub_n];
public:
// Constructor
Student();
// Set student data
void set_stud_data(int id, string name, int level, double scores[]);
// Show student data
void print_stud();
// Calculate student GPA
double GPA();
};
3.2 // Implementation of the Student Class save as Student.cpp
#include <iostream>
#include <string>
#include "Student.h"
using namespace std;
Student::Student(){
stud_id = stud_level = 0;
stud_name = "";
for (int i = 0; i < sub_n; i++)
stud_scores[i] = 0;
}
9
Algorithms & Data Structures Review Sheet 1
void Student::set_stud_data(int id, string name, int level, double scores[]){
stud_id = id;
stud_level = level;
stud_name = name;
for (int i = 0; i < sub_n; i++)
stud_scores[i] = scores[i];
}
void Student::print_stud() {
cout << "Student ID : " << stud_id << endl
<< "Student Level: " << stud_level << endl
<< "Student Name: " << stud_name << endl;
for (int i = 0; i < sub_n; i++)
cout << "Score of subject #" << i + 1 << ": " << stud_scores[i] << endl;
cout << "Student GPA : " << GPA() << endl;
}
double Student::GPA(){
double sumGPA = 0;
for (int i = 0; i < sub_n; i++){
if (stud_scores[i] >= 90)
sumGPA += 4.0;
else if (stud_scores[i] >= 85)
sumGPA += 3.7;
else if (stud_scores[i] >= 80)
sumGPA += 3.4;
else if (stud_scores[i] >= 75)
sumGPA += 3.1;
else
sumGPA += 2;
}
return (sumGPA / sub_n);
}
3.3 // Student Main Function
#include <iostream>
#include <string>
#include "Student.h"
using namespace std;
void main(){
Student s1;
int id, level;
10
Algorithms & Data Structures Review Sheet 1
string name;
double scores[sub_n];
cout << "Enter data of student" << endl;
cout << "Enter ID: ";
cin >> id;
cout << "Enter name: ";
cin >> name;
cout << "Enter level: ";
cin >> level;
for (int i = 0; i < sub_n; i++) {
cout << "Enter grade of student #" << i + 1 << ": ";
cin >> scores[i];
}
s1.set_stud_data(id, name, level, scores);
s1.print_stud();
}
11
Algorithms & Data Structures Review Sheet 1
4 Employee Class
The employee ADT is:
Private: id, workingHours, hourRate.
Public Operations: Constructors, setData, basicSalary, overtime, taxes, netSalary, print.
Write using C++ employee class and its implementation, then demonstrate all the employee
operations.
4.1 // Header File save as Employee.h
class Employee {
private:
int id; //employee's ID
float workingHours; //how many hours they worked in a week
float hourRate; //how much they get paid per hour
public:
Employee(); //default no-arg constructor
Employee(int i, float wh, float hr); //parametrized constructor
void setData(int i, float wh, float hr);//set employee data
float basicSalary(); //returns employee's basic salary per week
float overTime(); //returns employee's overtime bonus per week
float taxes(); //returns employee's taxes per week
float netSalary(); //returns employee's net salary
void print(); //shows employee data
};
4.2 // Implementation of the Employee Class save Employee.cpp
#include "Employee.h"
#include<iostream>
using namespace std;
Employee::Employee() {
id = 0;
workingHours = 0;
hourRate = 0;
}
Employee::Employee(int i, float wh, float hr) {
id = i;
workingHours = wh;
hourRate = hr;
}
12
Algorithms & Data Structures Review Sheet 1
void Employee::setData(int i, float wh, float hr){
id = i;
workingHours = wh;
hourRate = hr;
}
13
Algorithms & Data Structures Review Sheet 1
//if an employee works over 40 hours, they get paid for 40 hours of work
//if they work under 40 hours, they get paid per hour
float Employee::basicSalary() {
if (workingHours > 40)
return 40 * hourRate;
else
return workingHours * hourRate;
}
//for every hour they work overtime (more than 40)
//they get paid 1.5 times their hour rate
float Employee::overTime() {
if (workingHours > 40)
return (workingHours - 40) * hourRate * 1.5;
else
return 0;
}
//if they get paid 0-1000, no taxes are deducted
//if they get paid 1000-2000, 5% taxes are deducted
//if they get paid over 2000, 10% takes are deducted
float Employee::taxes() {
float salary = basicSalary() + overTime();
if (salary <= 1000)
return 0;
else if (salary <= 2000)
return salary * 0.05;
else
return salary * 0.1;
}
float Employee::netSalary() {
return basicSalary() + overTime() - taxes();
}
void Employee::print(){
cout << "ID: " << id << endl
<< "Salary: " << basicSalary() << endl
<< "Overtime: " << overTime() << endl
<< "Taxes: " << taxes() << endl
<< "Net Salary: " << netSalary() << endl;
}
14
Algorithms & Data Structures Review Sheet 1
4.3 // Employee Main Function
#include"Employee.h"
#include <iostream>
using namespace std;
void main() {
Employee emp1;
emp1.setData(9292, 60, 30);
cout << "First employee data:" << endl;
emp1.print();
Employee emp2(19034, 45, 10);
cout << endl << "Second employee data:" << endl;
emp2.print();
}
15
Algorithms & Data Structures Review Sheet 1
5 Queue Class
Queue ADT defined as a sequence of items of the same data type, there are two pointers, one for
Queue Front and other for Queue Rear. The Queue policy is First In First Out (FIFO).
Write a C++ Queue class represent the above ADT Queue and Queue Class implementation.
Then, write a C++ program that uses a Queue objects and apply all operations on it.
5.1 // Header File save Queue.h
class Queue {
private:
int capacity; // queue capacity <= size
int size; // Size of storage array
int* data; // Pointer to dynamic array
int front; // Index of front element
int rear; // Insertion index
int count; // Number of queued items
public:
Queue(int queueSize); // Constructor
~Queue(); // Destructor
void enqueue(int x); // Insert item at rear end
void dequeue(); // Remove front item
void retrieve(); // Retrieve front item
int length(); // Number of items in queue
void setCapacity(int newcap); // Set capacity to newcap
bool empty(); // Check if queue is empty
bool full(); // Check if queue is full
};
5.2 // Implementation of the Queue Class Queue.cpp
#include "Queue.h"
#include<iostream>
using namespace std;
Queue::Queue(int queueSize) {
front = rear = 0;
capacity = size = queueSize;
count = 0;
if (queueSize > 0)
data = new int[queueSize];
else
data = 0;
}
16
Algorithms & Data Structures Review Sheet 1
Queue::~Queue() {
if (data)
delete[] data;
}
void Queue::enqueue(int x) {
if (full())
cout << "Queue is Full" << endl;
else{
data[rear] = x;
rear = (rear + 1) % size;
count++;
}
}
void Queue::dequeue() {
if (empty())
cout << "Queue is empty" << endl;
else{
cout << "Deqeue element : " << data[front] << endl;
front = (front + 1) % size;
count--;
}
}
void Queue::retrieve(){
if (empty())
cout << "Queue is empty" << endl;
else
cout << "Current element is " << data[front] << endl;
}
int Queue::length(){
return count;
}
bool Queue::full(){
return count >= capacity;
}
bool Queue::empty(){
return count == 0;
17
Algorithms & Data Structures Review Sheet 1
void Queue::setCapacity(int newcap) {
capacity = newcap;
if (newcap > size){
int* newdata = new int[newcap];
for (int i = 0; i < count; i++)
newdata[i] = data[(front + i) % size];
if (data) //this is testing whether storage is not null
delete[] data;
data = newdata; //both are pointing to same location
size = newcap; //set new size
front = 0; //front equal to zero
rear = count; //rear is now == count
}
}
18
Algorithms & Data Structures Review Sheet 1
5.3 // QUeue Main Function
#include<iostream>
#include"Queue.h"
using namespace std;
void main() {
Queue q(5);
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
// Testing new capacity function
q.setCapacity(6);
q.enqueue(10);
q.retrieve();
while (!q.empty())
q.dequeue();
}
19
