OPOL COMMUNITY COLLEGE
BSIT Department Learning Activity Package
LAP Code: IT 202 No. of Hours: 3 hours/meeting
LAP Subject Title: Data Structures and Algorithm
LAP-WEEK 01
INTRODUCTION TO DATA STRUCTURES and ALGORITHM
A. Topic Outline
Topic Learning Outcomes Activities Assignment
Introduction to Know the importance of 1. Knowledge
Data Structures algorithms in solving problem. Check Stacks ADT
and Algorithm. Differentiate algorithms from 2. Developmental and its
programs. Activity operation
What is Familiarize with abstract data 3. Laboratory
Algorithm? structures. Exercise
Interpret algorithm and 4. Assessment/
What are implement to program codes. Evaluation
abstract Create an algorithm base on a Activity
Datatypes? given problem.
Algorithm vs.
Program
B. Introductory Activity (10 minutes)
Knowledge Check
Instruction. Perform the sequence steps based on the given algorithm. Write your answers on a separate
document or use a yellow paper for your portfolio. (10 points)
Exercise 1: Finding the Midpoint.
(Could be performed by a human equipped with drawing instruments.)
Midpoint algorithm: To find the midpoint of a given straight-line segment AB:
1. Draw intersecting circles of equal radius, centered at A and B respectively.
2. Let C and D be the points where the circles intersect.
3. Draw a straight line between C and D.
4. Let E be the point where CD intersects AB.
5. Terminate with answer E.
C. Salient Concept
What is an algorithm?
An algorithm is a step-by-step procedure for solving a stated problem.
For example, consider the problem of multiplying two numbers. There are many possible algorithms
for solving this problem:
multiplication using a table (suitable only for small numbers)
1
OPOL COMMUNITY COLLEGE
BSIT Department Learning Activity Package
long multiplication
multiplication using logarithms
multiplication using a slide rule
binary fixed-point or floating-point multiplication (in a computer).
Example: GCDs
The greatest common divisor (GCD) of two positive integers is the largest integer that exactly
divides both.
E.g., the GCD of 77 and 21 is 7.
Euclid’s GCD algorithm:
To compute the GCD of positive integers m and n:
1. Set p to m, and set q to n.
2. Until q exactly divides p, repeat:
2.1. Set p to q, and set q to (p modulo q).
3. Terminate with answer q.
Defining Algorithm
- Definition: Algorithm is a step-by-step procedure, which defines a set of instructions to be executed
in a certain order to get the desired output. Algorithms are generally created independent of
underlying languages, i.e. an algorithm can be implemented in more than one programming language
Characteristics of an Algorithm
Input - An algorithm should have 0 or more well-defined inputs
Output - An algorithm should have 1 or more well-defined outputs, and should match the
desired output
Definiteness- clear and unambiguous
Finiteness- terminate after a finite number of steps
Feasibility − Should be feasible with the available resources.
Independent − An algorithm should have step-by-step directions, which should be
independent of any programming code
How to write an Algorithm?
There are no well-defined standards for writing algorithms. Rather, it is problem and resource
dependent. Algorithms are never written to support a particular programming code.
As we know that all programming languages share basic code constructs like loops (do, for, while),
flow-control (if-else), etc. These common constructs can be used to write an algorithm.
We write algorithms in a step-by-step manner, but it is not always the case. Algorithm writing is
a process and is executed after the problem domain is well-defined. That is, we should know the
problem domain, for which we are designing a solution.
2
OPOL COMMUNITY COLLEGE
BSIT Department Learning Activity Package
Example
Let's try to learn algorithm-writing by using an example.
Problem − Design an algorithm to add two numbers and display the result.
Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP
Algorithms tell the programmers how to code the program. Alternatively, the algorithm
can be written as:
Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP
In design and analysis of algorithms, usually the second method is used to describe an algorithm.
It makes it easy for the analyst to analyze the algorithm ignoring all unwanted definitions. He can
observe what operations are being used and how the process is flowing.
We design an algorithm to get a solution of a given problem. A problem can be solved in
more than one ways.
Hence, many solution algorithms can be derived for a given problem. The next step is to analyze
those proposed solution algorithms and implement the best suitable solution.
(source: [Link]
Algorithms vs. Programs
Algorithms:
can be performed by humans or machines
can be expressed in any suitable language
may be as abstract as we like.
Programs:
must be performed by machines
must be expressed in a programming language
must be detailed and specific.
3
OPOL COMMUNITY COLLEGE
BSIT Department Learning Activity Package
Example of Algorithm
If we wish to use the algorithm on a computer, we must first code it in a programming language.
There may be many ways of coding the algorithm, and there is a wide choice of programming
languages. But all the resulting programs are implementations of the same underlying algorithm.
Here we express our implementations in Java. (Alternatives would be Python, C++, etc.)
How to create programs
Requirements
Analysis: bottom-up vs. top-down
Design: data objects and operations
Refinement and Coding
Verification
o Program Proving
o Testing
o Debugging
Data Type vs. Abstract Data Type
Data Type
- A data type is a collection of objects and a set of operations that act on those objects.
Abstract Data Type
- An abstract data type(ADT) is a data type that is organized in such a way that the
specification of the objects and the operations on the objects is separated from the
representation of the objects and the implementation of the operations.
4
OPOL COMMUNITY COLLEGE
BSIT Department Learning Activity Package
Abstract Data Types (ADTs)
Data Structures
A data structure is a systematic way of organizing a collection of data.
A static data structure is one whose capacity is fixed at creation. E.g.: array.
A dynamic data structure is one whose capacity is variable, so it can expand or contract at any time.
E.g.: linked list, binary tree.
For each data structure we need algorithms for insertion, deletion, searching, etc.
Standard ADTs
What are the Standard ADTs? Stacks, Queues, Vectors, Lists, Trees, ect.
Why should we know Standard ADTs? Standard ADTs are great reusable components.
Can be effectively used in solving many real world
problems.
Often times programming requires adapting
algorithms which uses some of the standard ADTs.
What should we know about standard What operation they support?
ADTs? Complexity of supported operations.
Memory cost of operation.
5
OPOL COMMUNITY COLLEGE
BSIT Department Learning Activity Package
ADT Taxonomy
Linear ADTs – we call an ADT “Linear” if the following are true:
- there is a unique first element
- there is a unique last element
- every element has a unique predecessor (except 1st).
- every element has a unique successor (except last).
Non-Linear ADT – if one or more of the above is NOT true, the ADT is non-linear.
Selecting ADTs
Example:
(a) If organizing a tour route, where we have to add delete a city – use Link List.
(b) If managing a telephone directory that should provide short search time – use Sorted
Trees
D. Developmental Activities
The River IQ Game: (10 pts)
Write the sequence of moves that made you succeed with the game.
Note: You can try and play as many attempts as you want until you succeed.
E. Laboratory Exercise
Create a program to implement Euclid’s greatest common divisor algorithm. (20 pts)
Save your files using the following file format: <FamilyName_LabExer_GDC>
F. Evaluation/Assessment Activities
Instruction: Write your own algorithm to solve the following problem. (30 pts)
Problem: Ms. Dae Struck just finished checking the quarter exam of her 50 students. She would like
to arrange the exam paper based on the student scores from highest to lowest. Now, if you
are Ms. Struck, how will you arrange the exam paper?
Write your answers on a separate document or use a yellow paper for your portfolio.