Data Structures – Week #1
Introduction
Goals
We will learn methods of how to
(explicit goal) organize or structure large
amounts of data in the main memory (MM)
considering efficiency; i.e,
memory space and
execution time
(implicit goal) gain additional experience on
what data structures to use for solving what kind of
problems
programming
October 1, 2021 Borahan Tümer, Ph.D. 2
Goals continued…1
Explicit Goal
We look for answers to the following question:
“How do we store data in MM such that
1. execution time grows as slow as possible with the
growing size of input data, and
2. data uses up minimum memory space?”
October 1, 2021 Borahan Tümer, Ph.D. 3
Goals continued…2
As a tool to calculate the execution time of algorithms, we
will learn the basic principles of algorithm analysis.
To efficiently structure data in MM, we will thoroughly
discuss the
static, (arrays)
dynamic (structures using pointers)
ways of memory allocations, two fundemantal
implementation tools for data structures.
October 1, 2021 Borahan Tümer, Ph.D. 4
Representation of Main Memory
October 1, 2021 Borahan Tümer, Ph.D. 5
Examples for efficient vs. inefficient
data structures
8-Queen problem
1D array vs. 2D array representation results in saving
memory space
Search for proper spot (square) using horse moves save
time over square-by-square search
Fibonacci series: A lookup table avoids redundant
recursive calls and saves time
October 1, 2021 Borahan Tümer, Ph.D. 6
Examples for efficient vs. inefficient
data structures
8-Queen problem (4-queen and 5-queen versions)
x x
x x
x x
x x
x x
x x
x x
x x
x x
October 1, 2021 Borahan Tümer, Ph.D. 7
Examples for efficient vs. inefficient
data structures
8-Queen problem (4-q and 5-q versions)
int a[4][4];
x …. inefficient:
x a[0][1]=1; more memory
x a[1][3]=1; space (16 bytes
a[2][0]=1; for 4-q version)
x
a[3][2]=1; required
x int a[5];
x …. efficient:
a[0]=0; less memory
x
a[1]=2; space (5 bytes
x a[2]=4; for 5-q version)
x a[3]=1; required
a[4]=3;
October 1, 2021 Borahan Tümer, Ph.D. 8
Math Review
Exponents
a b xa a b
x x x
a b
; b
x ; ( x a )b x ab ;
x
Logarithms
log z y
y x a log x y a, y 0; log x y , z 0;
log z x
1
log xy log x log y; log log x; log x a a log x
x
October 1, 2021 Borahan Tümer, Ph.D. 9
Math Review
Arithmetic Series: Series where the variable of
summation is the base.
k 1
k (k 1) (k 1)(k 2)
i 1
i
2
k 1
2
;
k (k 1) 2(k 1) (k 1)(k 2)
2 2 2
October 1, 2021 Borahan Tümer, Ph.D. 10
Math Review
Geometric Series: Series at which the variable of
summation is the exponent.
n
1 a n 1 n
a n 1 1
i 0
a
i
1 a
, 0 a 1;
i 0
a i
a 1
, a N {1};
n
1
lim a , 0 a 1;
i
n i 0 1 a
n
1
s lim a i 1 a a 2 a 3 a 4 ... ;
n i 0 1 a
n
a
as lim a a i a a 2 a 3 a 4 ... ;
n i 0 1 a
s as s (1 a ) 1
October 1, 2021 Borahan Tümer, Ph.D. 11
Math Review
Geometric Series…cont’d
An example to using above formulas to calculate
another geometric series
i
s 2
i 1
i
;
1 2 3 i
s 2 3 i
2 2 2 2
2 3 4 i
2s 1 2 3 i 1
2 2 2 2
1 1 1 1
s 2s s 1 2 3 i
2 2 2 2
1
s i 2;
i 0 2
October 1, 2021 Borahan Tümer, Ph.D. 12
Math Review
Proofs
Proof by Induction
Steps
1. Prove the base case (k=1)
2. Assume hypothesis holds for k=n
3. Prove hypothesis for k=n+1
Proof by counterexample
Prove the hypothesis wrong by an example
Proof by contradiction ( A B ~ B ~ A )
Assume hypothesis is wrong,
Try to prove this
See the contradictory result
October 1, 2021 Borahan Tümer, Ph.D. 13
Math Review
Proof examples (Proofs… cont’d)
Proof by Induction
Hypothesis
n
n( n 1)
i
i 1 2
Steps 1
1. Prove true for n=1:
i 1
i 1
k
k ( k 1)
2. Assume true for n=k: i
i 1 2
3. Prove true for n=k+1: k 1
k (k 1) (k 1)(k 2)
i
i 1 2
k 1
2
;
k (k 1) 2(k 1) (k 1)(k 2)
2 2 2
October 1, 2021 Borahan Tümer, Ph.D. 14
Arrays
Static data structures that
represent contiguous memory locations holding data
of the same type
provide direct access to data they hold
have a constant size determined up front (at the
beginning of) the run time
October 1, 2021 Borahan Tümer, Ph.D. 15
Arrays… cont’d
An integer array example in C
int arr[12]; //12 integers
October 1, 2021 Borahan Tümer, Ph.D. 16
Multidimensional Arrays
To represent data with multiple dimensions,
multidimensional array may be employed.
Multidimensional arrays are structures specified
with
the data value, and
as many indices as the dimensions of array
Example:
int arr2D[r][c];
October 1, 2021 Borahan Tümer, Ph.D. 17
Multidimensional Arrays
m[0][0] m[0][1] m[0][2] m[0][c 1]
m[1][0] m [1 ][1] m [1][ 2] m [1][ c 1]
m[2][0] m[2][1] m[2][2] m[2][c 1]
m[r 1][0] m[r 1][1] m[r 1][2] m[r 1][c 1]
•m: a two dimensional (2D) array with r rows and c columns
•Row-major representation: 2D array is implemented row-by-row.
•Column-major representation: 2D array is implemented column-first.
•In row-major rep., m[i][j] is the entry of the above matrix m at i+1st row and
j+1st column. “i” and “j” are row and column indices, respectively.
• How many elements? n = r*c elements
October 1, 2021 Borahan Tümer, Ph.D. 18
Row-major Implementation
Question: How can we store the matrix in a
1D array in a row-major fashion or how can
we map the 2D array m to a 1D array a?
October 1, 2021 Borahan Tümer, Ph.D. 19
Row-major Implementation
Question: How can we store the matrix in a 1D array
in a row-major fashion or how can we map the 2D
array m to a 1D array a? elements after the
l-1 elements before the matrix representation matrix representation
a ... m[0][0] ... m[0][c-1] ... m[r-1][0] ... m[r-1][c-1] ...
index: k → k=l k=l+c-1 k=l+(r-1)c+0 k=l+(r-1)c+c-1
in general what is k in terms of l, i, j and c so we know m[i][j]=a[k]?
October 1, 2021 Borahan Tümer, Ph.D. 20
Row-major Implementation
Question: How can we store the matrix in a 1D array
in a row-major fashion or how can we map the 2D
array m to a 1D array a?
l elements
a ... m[0][0] ... m[0][c-1] ... m[r-1][0] ... m[r-1][c-1] ...
index: k → k=l k=l+c-1 k=l+(r-1)c+0 k=l+(r-1)c+c-1
In general, m[i][j] is placed at a[k] where k=l+ic+j.
Hence, m[i][j] = a[l+ic+j].
October 1, 2021 Borahan Tümer, Ph.D. 21
Implementation Details of Arrays
1. Array names are pointers that point to the first
byte of the first element of the array.
a) double vect[row_limit];// vect is a pointer!!!
2. Arrays may be efficiently passed to functions
using their name and their size where
a) the name specifies the beginning address of the
array
b) the size states the bounds of the index values.
3. Arrays can only be copied element by element.
October 1, 2021 Borahan Tümer, Ph.D. 22
Implementation Details… cont’d
#define maxrow …;
#define maxcol …;
…
int main()
{
int minirow;
double min;
double probability_matrix[maxrow][maxcol];
… ; //probability matrix initialized!!!
min=minrow(probability_matrix,maxrow,maxcol,&minirow);
…
return 0;
}
October 1, 2021 Borahan Tümer, Ph.D. 23
Implementation Details… cont’d
double minrow(double darr[][maxcol], int xpos, int ypos, int *ind)
{// finds minimum of sum of rows of the matrix and returns the sum
// and the row index with minimum sum.
double mn;
…
mn=<a large number>;
for (i=0; i<=xpos; i++) {
sum=0;
for (j=0; j<=ypos; j++)
sum+=darr[i][j];
if (mn > sum) { mn=sum; *ind=i; } // call by reference!!!
}
return mn;
}
October 1, 2021 Borahan Tümer, Ph.D. 24
Records (Structures)
As opposed to arrays in which we keep data of
the same type, we keep related data of various
types in a record.
Records are used to encapsulate (keep together)
related data.
Records are composite, and hence, user-defined
data types.
In C, records are formed using the reserved word
“struct.”
October 1, 2021 Borahan Tümer, Ph.D. 25
Struct
We declare as an example a student record
called “stdType”.
We declare first the data types required for
individual fields of the record stdType, and
then the record stdType itself.
October 1, 2021 Borahan Tümer, Ph.D. 26
Struct… Example
enum genderType = {female, male}; // enumerated type declared…
typedef enum genderType genderType; // name of enumerated type shortened…
struct instrType {
… //left for you as exercise!!!
}
typedef struct instrType instrType;
struct classType {// fields (attributes in OOP) of a course declared…
char classCode[8];
char className[60];
instrType instructor;
struct classtype *clsptr;
}
typedef struct classType classType; // name of structure shortened…
October 1, 2021 Borahan Tümer, Ph.D. 27
Struct… Example continues
struct stdType {
char id[8]; //key
//personal info
char name[15];
char surname[25];
genderType gender; //enumerated type
…
//student info
classType current_classes[10]; //...or class_type *cur_clsptr
classType classes_taken[50]; //...or class_type *taken_clsptr
float grade;
unsigned int credits_earned;
…
//next record’s first byte’s address
struct stdType *sptr; //address of next student record
}
October 1, 2021 Borahan Tümer, Ph.D. 28
Memory Issues
Arrays can be used within records.
Ex: classType current_classes[10]; // from previous slide
Each element of an array can be a record.
stdType students[1000];
Using an array of classType for keeping taken classes
wastes memory space (Why?)
Any alternatives?
How will we keep student records in MM?
In an array?
Advantages?
Disadvantages?
October 1, 2021 Borahan Tümer, Ph.D. 29
Array Representation
Advantages
1. Direct access (i.e., faster execution)
Disadvantages
1. Not suitable for changing number of student records
• The higher the extent of memory waste the smaller the number of
student records required to store than that at the initial case.
• The (constant) size of array requires extension which is impossible for
static arrays in case the number exceeds the bounds of the array.
The other alternative is pointers that provide dynamic memory allocation
October 1, 2021 Borahan Tümer, Ph.D. 30
Pointers
Pointers are variables that hold memory addresses.
Declaration of a pointer is based on the type of
data of which the pointer holds the memory
address.
Ex: stdtype *stdptr;
October 1, 2021 Borahan Tümer, Ph.D. 31
Linked List Representation
header
Std #1 Std #2 Std #3 Std #n
Memory heap
Std Std
2 n
header
Std
Std
3
1
Value of header=2E450
header=?
October 1, 2021 Borahan Tümer, Ph.D. 32
Dynamic Memory Allocation
header=(*stdtype) malloc(sizeof(stdtype));
//Copy the info of first student to node pointed to by header
s =(*stdtype) malloc(sizeof(stdtype));
//Copy info of second student to node pointed to by header
Header->sptr=s;
...
October 1, 2021 Borahan Tümer, Ph.D. 33
Arrays vs. Pointers
Static data structures Dynamic data structures
Represented by an index Represented by a record of
and associated value information and address
of next node
Consecutive memory cells
Randomly located in heap
Direct access (+) (cause for need to keep
Constant size (-) address of next node)
Memory not released Sequential access (-)
during runtime (-) Flexible size (+)
Memory space allocatable
and releasable during
runtime (+)
October 1, 2021 Borahan Tümer, Ph.D. 34