Data Structures & Algorithms
SECTION 1: Basic Concepts and Notations, Arrays and Recursion
OBJECTIVES: At the end of the section, the student is expected to be able to
1. explain the basic concepts of data structure and an algorithm and their role in the
problem solving process of a computer
2. explain the close relationship between the structuring of data and synthesis of
algorithms
ESP: Given n courses, prepare a schedule of examinations for the n course subject to
the following conditions:
(a) examinations for courses with common students must be assigned
different time slots (or, equivalently no student should be made to take
more than one exam at a time, i.e. no conflicts)
(b) examinations must be scheduled using the minimum number of time
slots feasible
To put the task at hand in perspective, let us think in terms of domains.
Raw Data Processed Data Storage Processing
(input) (output) Medium Units
List Bits : Add
of : : Subtract
courses : Bytes : Multiply
: Schedule of : Divide
List of : examinations Words : Compare
students : :
enrolled in : Etc. : Etc.
each course :
PROBLEM DOMAIN MACHINE DOMAIN
Figure 1. A Problem to Solve and a Computer on which to Solve the Problem
Two tasks to be addressed in the solution domain
1. the structuring of higher level data representations (lists, trees, graphs, tables, etc)
from the basic information structures available at the level of the machine (bits,
bytes, words, etc.) that will faithfully represent the information (raw and processed
data) at the problem domain
2. the synthesis of algorithms( for searching, sorting, traversal, etc.) from the basic
operations provided at the level of the machine (addition, subtraction, comparison,
Section 1 Page 1 of 6
Jennifer Laraya-Llovido
Data Structures & Algorithms
etc) to manipulate these higher-level data representations so that we obtain the
desired results
Data Structures Algorithms
Lists Searching
Trees Sorting
Tables Memory Management
PROBLEM MACHINE
DOMAIN Graphs Traversal DOMAIN
Etc. Etc.
SOLUTION DOMAIN
Figure 2. What CS 15 is all about (and more)
What is a Data Structure?
1. Data Type – refers to the kind of data that variables may hold or take on in a
programming language, and for which operations are automatically provided. For
example:
a. PASCAL: integer, real, Boolean and character
b. C: character, integer, floating point, double floating point
c. FORTRAN: integer, real, complex, logical and character
d. LISP: list or S-expression
2. Abstract Data Type or ADT – is a set of data elements with a set of operations
defined on the data elements.
3. Data Structure – the implementation, using a specific programming language, of
an ADT in terms of language data types or other data structures such that
operations on the data structure are expressible in terms of directly executable
procedures.
Section 1 Page 2 of 6
Jennifer Laraya-Llovido
Data Structures & Algorithms
What is an algorithm?
An algorithm is a finite set of instructions which, if followed will accomplish a particular
task.
5 Important Properties of Algorithms
1. Finiteness – an algorithm must terminate after a finite number of steps
2. Definiteness – each step of an algorithm must be precisely defined
3. Input- an algorithm has 0 or more input quantities from a set called the domain of
the algorithm
4. Output- an algorithm has 1 or more output quantities which generate a set called
the range of the algorithm
5. Effectiveness – all of the operations to be performed are sufficiently basic that they
can in principle be done exactly and in finite time by a person using only pencil and
paper.
Example1: How to become a city mayor algorithm
Step 1. Run for public office.
Step 2. Campaign.
Step 3. Get elected.
Is how to become city mayor algorithm in fact an algorithm?
Are the five properties satisfied?
Example 2: How to make a trained dog to roll over algorithm
Step 1. Feed the dog a biscuit.
Step 2. Command the dog to roll over.
Step 3. Feed the dog a biscuit.
Is how to make a trained dog to roll over algorithm in fact an algorithm?
Are the five properties satisfied?
Example 3: Euclid’s Algorithm for finding the greatest common divisor of two
positive
integers m and n.
Step 1: Divide m by n and let r be the remainder
Step 2: If r is zero, stop; GCD = n
Step 3: Set m ← n, n ← r and go back to step 1
Is Euclid’s algorithm in fact an algorithm? Are the five properties satisfied?
Let m = 708 and n = 135.
Loop 1: Step 1. 708/135 = 5 remainder 33
Step 2. remainder is not zero, continue
Step 3. m ←135, n ← 33
Loop 2: Step 1. 135/33 = 4 remainder 3
Step 2. remainder is not zero, continue
Section 1 Page 3 of 6
Jennifer Laraya-Llovido
Data Structures & Algorithms
Step 3. m ←33, n ← 3
Loop 3: Step 1. 33/3 = 11 remainder 0
Step 2. remainder is zero, stop; GCD = 3
Methods of Accessing the Elements of a Data Structure
To be able to perform any kind of operation on the elements of a data structure, we must
be able to access such elements. There are two methods to accomplish this:
1. the computed address method
The computed address method is used to access the elements of a structure
that is pre-allocated and essentially static.
2. the link-addressing method
The link-addressing method is a mechanism for manipulating dynamic structures
which change in shape and size at run time.
A node is a sequence of one or more contiguous addressable units. The
address of a node is the address of its leftmost addressable unit, say α. Since a
node has no name, we refer to it by its address. Thus we call the node shown
below as node α.
A node is usually divided into named segments called fields. Node α has two
fields named INFO and LINK. The content of the INFO field is the string ‘CS’
while that of the LINK field is the integer 1000. To access these values, we use
the notation INFO(α) and LIN(α), respectively.
INFO(α) = ‘CS’ INFO LINK
LINK(α) = 1000 α CS 1000
Now, consider the nodes shown below. Can you deduce an underlying
structure?
INFO LINK
3000 : CS 1000
1000 : IT 4000
4000 : BS Λ
When a field in this instance, the LINK field of a node contains the address of
another node, we say that the LINK field of the former contains a pointer to the
latter. Such a relationship can be graphically represented by an arrow emanating
from the former and directed to the latter node. Hence, an equivalent way of
representing the linked nodes shown above is as the linked list shown below:
Section 1 Page 4 of 6
Jennifer Laraya-Llovido
Data Structures & Algorithms
INFO LINK
α
CS IT BS Λ
The value 3000 is assigned to the pointer variable α which then effectively
becomes the pointer to the list. It is easy to see that the following relations are
true for this list.
INFO (α) = ‘CS’
INFO(LINK(α)) = ‘IT’
INFO(LINK(LINK(α))) = ‘BS’
What is the result of executing the following instructions on the list?
β ← LINK(α)
LINK(α) ← LINK(β)
LINK(β) ← Λ
Putting it all together: formulating a solution to the ESP
C01 RDA ALB NAC EDF BMG VLJ IVL LGM EGN KSO EST VIV
C02 MCA EDF SLF ADG BCG AAI RRK LGM RLM JGP LRQ WAR KLS DDY
C03 ABC BBD GCF ADG AKL BCL MIN JGP RSQ DBU IEY RAW ESZ
C04 ANA JCA CAB NAC GCF GLH VLJ LLM MAN PEP PQQ ERR SET MAV REW
C05 BBC EDD HSE ELG ISH JEI EMJ RRK TPL RER EPS AVU CDW ELY
C06 ALA MCA ABB BCF GLH AKL HGN RON JGP ALQ EPR ABT KEV YEZ
C07 CDC ISH ABI DHJ ESM FBM RMN PEP VIR JLS LOT MAV TEX
C08 AAA HLA BBD WRE ECG HLH DHJ RON TSO PQQ MBT REW BAX TRY BDZ
C09 MCA JCA BCF EGG AAI XTK CSM HLO RSP RER APR JET DBU WWW
C10 RDA BBB CLC ECG MNH EMJ JOK ARM NFM EGN RCN RSP LEQ YIR AVU
C11 ADB WDB BKC CLC SDE UKF BMG HRH BTK LGM QJP EPS KLS BST YNZ
Figure 3. Class lists for 11 courses
Section 1 Page 5 of 6
Jennifer Laraya-Llovido
Data Structures & Algorithms
CO4
CO1
CO2
CO3
C11
CO6
CO7
CO5
CO9
C1O CO8
Figure 4. Graph representing the class lists of Figure 3.
1. A vertex of the graph represents a course.
2. Two vertices (courses) are connected by an edge if one or more students are taking
both courses. (Such vertices are said to be adjacent.)
Algorithm: Approximate graph coloring
Step 1. Select an uncolored vertex and color it with a new color
Step 2. For each remaining uncolored vertex, i.e. u, determine if u is connected
by an edge to some vertex already with the new color; if it is not, color vertex u
with the new color
Step 3. If there are still uncolored vertices, go to step 1; else stop.
Color Vertices
Red C01, C03, C05
Green C02, C04, C10
Blue C06, C07, C11
Orange C08, C09
Figure 5. A summary of results using graph coloring
Section 1 Page 6 of 6
Jennifer Laraya-Llovido
