DATA STRUCTURES AND
ALGORITHMS
SCS 3102
George William
Kasaazi
Course Objectives
Learning Outcomes
Assessment
Module 1: Introduction
What is Data?
What is a Data Structure?
What is an Algorithm?
The Relationship between Data Structures and
Algorithms
Measuring Efficiency: Time and Space
Complexity
Characteristics of a Good Algorithm
Overview of Algorithmic Problem-
Solving
Why are Data Structures and Algorithms
Important?
The Building Blocks - Primitives &
Memory in C++
The C++ Memory Model
Primitive Data Types
Typical
Type Description Example
Size
int Integers (whole numbers) 4 bytes int age = 21;
char Single characters 1 byte char initial = 'J';
bool Boolean (true or false) 1 byte bool isFinished = false;
Single-precision floating
float 4 bytes float price = 15.99f;
point
Double-precision floating
double 8 bytes double pi = 3.14159;
point
#include <iostream>
int main() {
std::cout << "Size of an int is: " << sizeof(int) << " bytes" << std::endl;
}
The Most Important "Primitive":
Pointers
Pointers in Action
#include <iostream>
int main() {
// 1. A normal variable 'age' on the stack
int age = 21;
// 2. A pointer 'age_ptr' that stores the memory address of 'age'
int* age_ptr = &age;
// Displaying the addresses and values
std::cout << "Value of age: " << age << std::endl;
std::cout << "Address of age: " << &age << std::endl;
std::cout << "Value of age_ptr (it's an address): " << age_ptr <<
std::endl;
// 3. To get the value at the address, we dereference the pointer
std::cout << "Value pointed to by age_ptr: " << *age_ptr << std::endl;
// Prints 21
// We can also change the original value through the pointer
*age_ptr = 22;
std::cout << "New value of age: " << age << std::endl; // Prints 22
return 0;
}
Creating Custom Types
Why Primitives Aren't Enough
The struct (Structure)
#include <iostream>
#include <string>
// Define a new type called Student
struct Student {
int id;
std::string name;
double average_mark;
};
int main() {
// Create a variable of our new type
Student s1;
// Access and assign members using the dot (.) operator
[Link] = 1234;
[Link] = "Aisha";
s1.average_mark = 88.5;
std::cout << "Student: " << [Link] << ", ID: " << [Link] <<
std::endl;
return 0;
} struct is simple and often used for Plain Old Data (POD) containers.
The class and Object-Oriented
Programming
Building a Student Class
#include <iostream> void setMark(double mark) {
#include <string> if (mark >= 0 && mark <= 100)
class Student { {
private: // Why put the data here? average_mark = mark;
int id; }
std::string name; }
double average_mark; void display() {
public: // public functions. Why? std::cout << "ID: " << id <<
Student(int student_id, ", Name: " << name << ", Mark: " <<
std::string student_name) { average_mark << std::endl;
id = student_id; }
name = student_name; };
average_mark = 0.0; int main() {
std::cout << "Student " << Student s1(1234, "Aisha");
name << " created." << std::endl; [Link](88.5);
} [Link]();
return 0;
What is an Abstract Data Type (ADT)?
ADT Example: The List
Concrete Implementations of
the List ADT
Practice Questions for Module 1
Practice Questions for Module 1 …
Practical Coding Exercises
Employee Record:
Define a struct named Employee that contains the following
members: employeeID (int), name (string), and hourlyWage (double).
In your main function, create an Employee variable, assign values to its members,
and then print them to the console.
Car Class:
Create a class named Car.
It should have the following private member variables: make (string, e.g.,
"Toyota"), model (string, e.g., "Camry"), and currentSpeed (int).
It should have a public constructor that accepts the make and model and
initializes currentSpeed to 0.
It should have the following public methods:
accelerate(int amount): Increases currentSpeed by amount.
brake(int amount): Decreases currentSpeed by amount, but not below 0.
displayStatus(): Prints the car's make, model, and current speed.
In your main function, create a Car object, accelerate it, brake, and display its
status.