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