Lecture (1)

Introduction

Dr. Wafaa Samy

ECE2103: Data Structure and Algorithms (Spring 2025-2026)

 Contents
• About the Course
oText Books
oAssessment Criteria
• Introduction
• Data Structure Overview
• Pointers
• Static and Dynamic Memory Allocation
2
 Text Books
• Handbook of Data Structures and Applications, Dinesh P. Mehta &
Sartaj Sahni, 2nd Ed., 2018.

• Data Structures and algorithms in C++, Mark A. Weiss, 4th Ed., 2013.

3
Lectures
Assessment Criteria
1 2 3 4 5 6 7th Week Exam 7 8 9 10 12th Week Exam 11 12 Project Final Exam

• 2nd to 6th Week – Activities 10

o 5th Week – Lab Quiz
• 7th Week – Exam 20

• 8th to 11th Week – Activities 5

o 10th Week – Lab Quiz
• 12th Week – Exam 15

• 13th to 14th Week – Activities 10

o Assignments & Activity Work
o 14th Week – Project Submission

• 16th Week – Final Exam 40

4
Programs are not just Algorithms
Programs = Algorithms + Data structures
• Data structure – A way of organizing and storing data to solve the problem at hand.
• It is mainly concerned with finding the best representation or organization of data in the
memory that leads to efficient processing.
o Examples: arrays, linked lists, stacks, queues, trees.
• Algorithm – Outline, the essence of a computational procedure, a series of precise step-
by-step instructions to produce to a specific outcome.
o Examples: binary search, merge sort, etc.
• Choice of data structure can affect the efficiency of an algorithm.
o For many problems, the ability to formulate an efficient algorithm depends on being able to
organize the data in an appropriate manner.
• Program – Implementation of an algorithm in some programming language. 5
 Data Structure Overview
• This course covers many data structures ranging from familiar arrays to more
complex structures such as trees and graphs.
• A data structure is a systematic way of organizing a collection of data.
o A static data structure is one whose capacity is fixed at creation (e.g. array).
o A dynamic data structure is one whose capacity is variable, so it can expand or
contract at any time (e.g. linked list).

• For each data structure, we need algorithms for insertion, deletion, searching,
etc. A data structure is a collection
o A data structure supports certain operations, each with a: of data values, the
relationships among them,
 Meaning: what does the operation do/return. and the functions or
 Performance: how efficient is the operation. operations that can be
applied to the data.
o Example: List with operations insert and delete. 6
 Data Structure Overview (Cont.)
Basic / Primitive Data Types are predefined set of data types in C / C++, as int, float, etc.

Derived Data Types are extensions from basic data types such as array, pointers, structs ,etc.

User-Defined Data Structures are those which are defined by the user (using both derived data types and
basic data types), as linked list, stack, etc.

• Linear Data Structure • Non-linear Data Structure

o Linked list o Tree
o Stack o Graph
o Queue
o Hash Table
7
 Data Representations
• In memory, every stored data item Primitive Data Types
occupies one or more contiguous
memory cells. Integers
• short 2 Bytes
• int 4 Bytes
Numbers
• The number of memory cells required • long 8 Bytes
to store a data item depends on its Floating-
• float 4 Bytes
type (char, int, double, etc.). point • double 8 Bytes
Numbers

Characters • char 1 Byte

8
 Example (1)
#include <stdio.h>
int main()
{
short shortType;
int integerType;
long longType;
float floatType;
double doubleType;
char charType;
printf("Size of short: %d bytes\n“ , sizeof(shortType));
printf("Size of int: %d bytes\n“ , sizeof(integerType));
printf("Size of long: %d bytes\n“ , sizeof(longType)); In C language, printf() function is
printf("Size of float: %d bytes\n“ , sizeof(floatType)); used to print formatted output to the
printf("Size of double: %d bytes\n“ , sizeof(doubleType)); standard output stdout (which is
printf("Size of char: %d byte\n“ , sizeof(charType)); generally the console screen).
return 0;
9
}
 Address vs. Value
• Each memory cell has an address associated with it. Example: int xyz = 32;
• Each cell also stores some value.
xyz  variable
• Don’t confuse the address referring to a memory
location with the value stored in that location. 32  value

• Whenever we declare a variable, the system allocates 1024  address

memory location(s) to hold the value of the variable.
o Since every byte in memory has a unique address, 1024: 32 Value
this location will also have its own (unique)
xyz
address.
Address
101 102 103 104 105 ... Variable Name
... 23 42 ...
10
Data Representations (Cont.)

Derived Data Types

Arrays • Element size * # of elements.

• 4 Bytes (32 Address bits) or 8 Bytes

Pointers (64 Address bits).

• Depending on entire size for all

Structs members & memory alignment.
11
 Example (2)
#include<stdio.h>
struct Point
{
int x, y, z; // 12 bytes
};
int main()
{
int days[] = {1,2,3,4,5}; // 20 bytes
int *ptr = days; // either 4 or 8 bytes for 32-bits or 64-bits system
struct Point p;
printf("size of array is %d\n", sizeof(days));
printf("size of pointer ptr is %d\n", sizeof(ptr));
printf("size of p, instance for struct Point is %d",sizeof(p));
return 0;
12
}
What is a Pointer?

Example: int pointer, float pointer,…

13
 Example (3): Pointers
#include<stdio.h>
int main()
{
int X = 25;
int *Ptr;
Ptr = &X;
printf("%d\n", X); // equal to printf(“%d”, *Ptr);
*Ptr = *Ptr + 100; // 25 +100 = 125 (X = 125)
printf("Ptr = %x while *Ptr = %d", Ptr, *Ptr);
return 0;
}

Ptr X
0x22fe44 25
14
 T* v versus T *v
Note: Pointer variables must
always point to a data item of
the same type: int and float:
• have different sizes
float x; (often 4 bytes each, but
not guaranteed).
int *p; • have different memory
: representations.

p = &x; // ❌ wrong
• Multiple Variables in one Declaration: will result in wrong output.
Note: Never assign an
absolute address to a pointer
variable: That address:
• may not exist.
int *count; • may be protected.
• may belong to
count = 1268; another program.

15
 Example (4): Pointers – Passing Parameters
• As Input Parameter • As Output Parameter
void doubleValue (int *val)
char *findNull (char *str)
{
{
*val *= 2;
char *ptr = str;
}
while( *ptr != ‘\0’)
In main body: ptr++; text: H e l l o \0
int x = 30; ^ ^
return ptr; str returned pointer
doubleValue(&x); } • Stops when it reaches the null terminator '\0'.
• Returns a pointer to that null character. So it
printf(“%d”, x); // Print 60 returns: the address of the end of the string.
16
 Example (5): Structured Data – Pointer to
Structure
struct circle { double radius, area; };

circle *cirPtr; //Pointer cirPtr ?

myCircle
10
circle myCircle = {10, 314}; //initialize
314

cirPtr myCircle
cirPtr = &myCircle; 0x6ff0 10
314

// Accessing myCircle through cirPtr: myCircle

(*cirPtr).radius = 1; // equal to cirPtr->radius = 1; cirPtr 0x6ff0 1
3.14
(*cirPtr).area = 3.14; // equal to cirPtr->area = 3.14;
17
 Example (6): Pointers and Arrays
Element Value Address
x[0] 1 2500
• Consider the declaration: int x[5] = {1, 2, 3, 4, 5};
x[1] 2 2504
• Suppose that each integer requires 4 bytes. x[2] 3 2508
• Compiler allocates a contiguous storage of size 5x4 = 20 bytes. x[3] 4 2512
• Suppose the starting address of that storage is 2500. x[4] 5 2516
• The compiler also defines the array name as a constant pointer to the first element.
• If int *p is declared, then p = x; and p = &x[0]; are equivalent.
• We can access successive values of x by using p++ or p-- to move from one element to another.
• Relationship between p and x:
p = &x[0] = 2500
p+1 = &x[1] = 2504 In general, *(p+i) gives the
p+2 = &x[2] = 2508 value of x[i]
p+3 = &x[3] = 2512
p+4 = &x[4] = 2516
• C knows the type of each element in array x, so knows how many bytes to move the pointer to get
18
to the next element.
 Layout of a Process in Memory
• Process = Program in execution.
• The memory layout of a process is typically divided into multiple sections (parts)
including:
1. Text section: The program code (the executable code).
2. Data section containing global variables.
3. Heap section containing memory dynamically allocated during program run time.
4. Stack section containing temporary data when invoking functions.
• E.g. Function parameters, return addresses, local variables.
• For the stack:
 Each time a function is called, an activation record containing function parameters,
local variables, and the return address is pushed onto the stack.
 When control is returned from the function, the activation record is popped from
the stack.
• The sizes of the text and data sections are fixed, as their sizes do not change during
program run time.
• The stack and heap sections can shrink and grow dynamically during program execution.
• Similarly, the heap will grow as memory is dynamically allocated, and will shrink when
memory is returned to the system.
19
 Layout of a Process in Memory (Cont.)

(Data)
(Data)

20
MEMORY

21
 Memory Allocation
• Static memory allocation:
o Store variables in stack and it happens at compile time based on variable definitions.
o Access to those variables is very fast.
o The stack is reserved in a LIFO order (dependent with each other), the most recently
reserved block is always the next block to be freed. That is make stack simple to
keep track of its storage.

• Dynamic memory allocation:

o Allocation of memory storage (all available unused memory called the heap) for use
in a computer program during the runtime.
o Accessing this memory is a bit slower than stack.
o Element of the heap have no dependencies with each other and can always be
accessed randomly at any time, that is make heap much more complex to keep track
of which parts are allocated or free. 22
Example (7): Static Memory Allocation

y 90

x 65

• Variables inside { } exist only within that block.

• If a block doesn’t execute, its variables don’t exist at all. 23
Example (7): Static Memory Allocation (Cont.)

b 7
< a 5

y 90

x 65

24
Example (8): Static Memory Allocation

Square
x
SquareOfSum
x,y,z

main
a 4
b 8

Total
total ???144

25
 Dynamic Memory Allocation & De-allocation
Functions
• malloc
oAllocates requested number of bytes and returns a pointer to the
first byte of the allocated space.
• free
oFrees previously allocated space.
• realloc
oModifies the size of previously allocated space.
• We will only do malloc and free.

26
Dynamic Memory Allocation & De-allocation
• void *malloc(size_t size);
o void * a generic pointer type that can point to memory of any type.
o size_t a type defined by the standard library as the type returned by sizeof.

And returns a pointer to the

starting address of the block on
the heap, void pointer so we can
do casting to the type (*int). 27
 Example (9)
p
p = (int *) malloc(100 * sizeof(int)); 400 bytes of space

• A memory space equivalent to 100 times the size of an int bytes is reserved.
• The address of the first byte of the allocated memory is assigned to the pointer p of type
int.
• Note: malloc always allocates a block of contiguous bytes.
o The allocation can fail if sufficient contiguous memory space is not available.
o If it fails, malloc returns NULL.
if ((p = (int *) malloc(100 * sizeof(int))) == NULL)
{ printf (“\n Memory cannot be allocated”);
exit();
}
• Note: Be careful to allocate the correct number of bytes, Example:
int *i = (int *) malloc(1); //wrong as it allocates 1 byte, not 1 int. 28
 Dynamic Memory Allocation & DE-allocation
•C (Cont.) • C++:
// Single element // Single element
Int main(){ int main(){
int *X = (int *) malloc (sizeof (int)); int *X = new int;
*X=5 ; } *X=5 ; }

0x202 5 0x202
X

STACK HEAP

29
Releasing the Allocated Space: free
An allocated block can be
returned to the system for
future use by using the
free function.

Note that no size needs to

be mentioned for the
allocated block, the system
remembers it for each
pointer returned.

30
 Dynamic Memory Allocation & DE-allocation
•C (Cont.) • C++:
// Single element
// Single element
Int main(){
int main(){
int *X = (int *) malloc (sizeof (int));
int *X = new int;
*X=5 ;
*X=5 ;
free(X); }
delete X; }

// deletes the space that X

points to. 0x202 5 0x202
Note that the pointer X still X

exists in this example. That's a

named variable subject to STACK HEAP
scope and extent determined at
compile time. It can be reused. 31
 Pointers – Common Problems
• Dangling Pointers • Memory Leak
• Dereferencing a pointer after the • When losing the pointer to the
memory it refers to has been freed is memory region allocated, so that
called a “dangling pointer”. space is reserved but unreachable
• Behavior is undefined. Might: until the program terminates.
o appear to work. • Example:
o bogus data. int *a = (int*)malloc(10 * sizeof(int));
o program crash. int b[10];
• Example: a = b; /* 40 bytes in heap are lost*/
int *a = (int *) malloc(10 * sizeof(int));
free(a);
printf("%d\n", a[0]); /* Error */
32
Dynamic Memory Allocation & De-allocation
•C
(Cont.)
• C++:
// Single element // Single element
int *X = (int *) malloc (sizeof (int)); int *X = new int;
free(X); delete X;

// Multiple elements // Multiple elements

int *X_arr = (int *) malloc (sizeof(int)*10); int *X_arr = new int[10];
free(X_arr); delete[ ] X_arr;

33
 Problem with Arrays
• Example: Search for an element in an array of N elements.
• Sometimes:
o Amount of data cannot be predicted beforehand.
o Number of data items keeps changing during program execution.
• One Solution: find the maximum possible value of N and allocate an array of N
elements.
o Wasteful of memory space, as N may be much smaller in some executions.
o Example: maximum value of N may be 10,000, but a particular run may need to
search only among 100 elements.
 Using array of size 10,000 always wastes memory in most cases.
• Better Solution: Dynamic memory allocation.
o Know how much memory is needed after the program is run.
 Example: ask the user to enter from keyboard.
o Dynamically allocate only the amount of memory needed.
34
 Using the malloc’d Array
• Once the memory is allocated, it can be used with pointers, or with
array notation.
• Example:
int *p, n, i;
scanf(“%d”, &n); // Reading an integer input
p = (int *) malloc (n * sizeof(int));
for (i=0; i<n; ++i)
scanf(“%d”, &p[i]);

The n integers allocated can be accessed as *p, *(p+1), *(p+2),…,

*(p+n-1) or just as p[0], p[1], p[2], …,p[n-1]
35
Memory Layout of a C Program
Some few differences:
(1) The global data
section is divided into
different sections for
(a) initialized data and
(b) uninitialized data,
and (2) A separate
section is provided for
the argc and argv
parameters passed to
the main() function.

36
Example (10): Memory Allocation

37
 Example (10): Dynamic Memory Allocation
int x = 2;
int a[4];
int *b;
int main ()
{
b = (int *) malloc (4* sizeof(int));
b[0] = 10;
b[1] = 20;
}
Static memory allocation.
int arr[10];
Dynamic memory allocation.
int *ptr;
ptr = (int *) malloc (sizeof (int) * 10); 38
Exercises

39
Thank You
Dr. Wafaa Samy

[Link]@[Link]

40