CC 104 - SG - 1.pdf

FM-AA-CIA-15 Rev. 0 10-July-2020 Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation MODULE TITLE BASIC CONCEPTS AND NOTATION MODULE OVERVIEW T...

FM-AA-CIA-15 Rev. 0 10-July-2020 Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation MODULE TITLE BASIC CONCEPTS AND NOTATION MODULE OVERVIEW This module aims to enable you to understand the concepts and properties of algorithm, the problem solving process, different mathematical functions that can be used to analyze an algorithm and measuring algorithm complexity using Big – Oh Notation. Problem solving and programming exercises were included in every section in order to test your understanding of the lesson. LEARNING OBJECTIVES By the end of this module you should be able to:  Define Algorithm  Explain the process of problem solving  Identify properties of algorithms  Use basic mathematical functions to analyse algorithms  Measure complexity of algorithms (Big – Oh Notation) LEARNING CONTENTS Unit 1: Algorithm and Properties of Algorithm Introduction The term algorithm is used in computer science to describe a finite, deterministic, and effective problem-solving method suitable for implementation as a computer program. It is a strictly defined finite sequence of well – defined statements that provides the solution to a problem or to a specific class of problems for any acceptable set of input values (if there are any inputs). The term “finite” means that the algorithm should reach an end point and cannot run forever. Unit learning outcomes By the end of this unit you should be able to:  Define what algorithm is  Differentiate the different properties of algorithms  Apply these properties to design an algorithm for a specific problem What is Algorithm? PANGASINAN STATE UNIVERSITY 1  FM-AA-CIA-15 Rev. 0 10-July-2020 Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation 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. The following demonstrates how algorithm is being applied in real world: The Algorithm for Making a Cup of Tea 1. Put the teabag in a cup 2. Fill the kettle with water 3. Boil the water in the kettle 4. Pour some of the boiled water into the cup 5. Add milk to the cup 6. Add sugar to the cup 7. Stir the tea 8. Drink the tea As you can see, there are certain steps that must be followed. These steps are in specific order, even though some of the steps could be rearranged. For example, steps 5 and 6 can be reversed. You will also notice that aside from the sequence of steps that must be performed, the entire process is finite and reach its end point which enable you to achieve your goal (in this case, making a cup of tea). Fundamental Properties of Algorithms  Finiteness - an algorithm must terminate after a finite number of steps  Definiteness - ensured if every step of an algorithm is precisely defined. For example, "divide by a number x" is not sufficient. The number x must be define precisely, say a positive integer.  Input - domain of the algorithm which could be zero or more quantities  Output - set of one or more resulting quantities; also called the range of the algorithm  Effectiveness - ensured if all the operations in the algorithm are sufficiently basic that they can, in principle, be done exactly and in finite time by a person using paper and pen PANGASINAN STATE UNIVERSITY 2  FM-AA-CIA-15 Rev. 0 10-July-2020 Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation CHECK YOUR UNDERSTANDING – Consider the following Java Code (Adopted from JEDI Teacher’s Manual for Data Structure and Algorithm). Analyse the code fragment below: public class Minimum { public static void main(String[] args) { int a[] = { 23, 45, 71, 12, 87, 66, 20, 33, 15, 69 }; int min = a; for (int i = 1; i < a.length; i++) { if (a[i] < min) min = a[i]; } System.out.println("The minimum value is: " + min); } } What does the program do? Identify and discuss the different properties that the algorithm possess. Unit 2: Problem Solving Process Introduction Programming is a problem-solving process, i.e., the problem is identified, the data to manipulate and work on is distinguished and the expected result is determined. It is implemented in a machine known as a computer and the operations provided by the machine is used to solve the given problem. Unit learning outcomes By the end of this unit you should be able to:  Understand the problem solving process  Design an algorithm for a specific problem The Problem Solving Process The problem solving process could be viewed in terms of domains – problem, machine and solution. Problem domain includes the input or the raw data to process, and the output or the processed data. For instance, in sorting a set of numbers, the raw data is set of numbers in the original order and the processed data is the sorted numbers. PANGASINAN STATE UNIVERSITY 3  FM-AA-CIA-15 Rev. 0 10-July-2020 Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation Source: JEDI Teacher’s Manual for Data Structures and Algorithm The machine domain consists of storage medium and processing unit. The storage medium – bits, bytes, words, etc – consists of serially arranged bits that are addressable as a unit. The processing units allow us to perform basic operations that include arithmetic, comparison and so on. Source: JEDI Teacher’s Manual for Data Structures and Algorithm Solution domain, on the other hand, links the problem and machine domains. It is at the solution domain where structuring of higher level data structures and synthesis of algorithms are of concern. Source: JEDI Teacher’s Manual for Data Structures and Algorithm 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. The common constructs across programming languages such as loops and other flow control can be used to write an algorithm. Writing an algorithm is a process that is only executed after the problem domain is well – defined. That is, we should know the problem domain, for which we are designing a solution. 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 PANGASINAN STATE UNIVERSITY 4  FM-AA-CIA-15 Rev. 0 10-July-2020 Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation 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. Alternately, the algorithm can be represented using a flow chart (which was discussed during your CC 102 class) or using a pseudocode. Step 1 − START ADD Step 2 − get values of a & b Step 3 − c ← a + b Step 4 − display c Step 5 − STOP 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. Source: https://www.tutorialspoint.com/data_stru ctures_algorithms/algorithms_basics.ht m CHECK YOUR UNDERSTANDING – Design an algorithm for the following using Pseudocode and Flowcharts 1. Show the algorithm for computing the velocity of the car. Having the following inputs: D1 – the starting point D2 – the ending point T – Time interval to reach D2 V = (D2 – D1) / T PANGASINAN STATE UNIVERSITY 5  FM-AA-CIA-15 Rev. 0 10-July-2020 Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation 2. Show the algorithm for computing the density of a given square. Use the following as your inputs: M – Mass of the object V – Volume of the square (S6) D=M/V - Density of the object 3. Compute the greatest common divisor of two nonnegative integers’ p and q as follows: If q is 0, the answer is p. If not, divide p by q and take the remainder r. The answer is the greatest common divisor of q and r. Unit 3: Mathematical Functions Introduction Mathematical functions are useful in the creation and analysis of algorithms. In this section, some of the most basic and most commonly used functions with their properties are listed. Unit learning outcomes By the end of this unit you should be able to:  Understand the mathematical functions in the creation and analysis of algorithms  Solve problems using the different mathematical functions  Discuss the different identities in relation to mathematical functions The Mathematical Functions  Floor of x (⎿x⏌) - greatest integer less than or equal to x, x is any real number o e.g.:  ⎣ 3.14 ⎦ = 3  ⎣ 1/2 ⎦ = 0  ⎣ -1/2 ⎦ = -1  Ceiling of x (⎾x⏋) - smallest integer greater than or equal to x, where x is any real number o e.g.:  ⎾3.14⏋= 4  ⎾1/2⏋= 1  ⎾-1/2⏋= 0  Modulo - given any two real numbers x and y, o x mod y = x if y = 0 o =x-y*⎣x/y⎦ if y 0 o e.g.:  10 mod 3 = 1  24 mod 8 = 0  -5 mod 7 = 2 Identities PANGASINAN STATE UNIVERSITY 6  FM-AA-CIA-15 Rev. 0 10-July-2020 Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation The following are the identities related to the mathematical functions defined above o ⎾x⏋= ⎿x⏌ if and only if x is an integer o ⎾x⏋ =⎿x⏌ + 1 if and only if x is not an integer o ⎣ - x ⎦ = -⎾x⏋ o ⎣ x ⎦ + ⎣ y ⎦ 1 microseconds count  count + 1 nn/2 O(n) Linear Sequential 1.00 seconds For i  1 to n Search sum  sum + i O(n Heapsort 19.93 seconds log2n) O(n2) Quadratic Insertion Sort 11.57 days For i  1 to n For j  i to n sum  sum + j O(n3) Cubic Floyd’s 317.10 Algorithm centuries O( 2n ) Exponential Eternity Operations on the O-Notation:  Rule for Sums - Suppose that T 1(n) = O(f(n)) and T 2(n) = O(g(n)). - Then, t(n) = T1(n) + T2(n) = O(max( f(n), g(n))).  Rule for Products - Suppose that T1(n) = O( f(n) ) and T2(n) = O( g(n) ). - Then, T(n) = T1(n) * T2(n) = O( f(n) * g(n) ). - For example, consider the algorithm below: for(int i=1; i