Sistem Digital : Sum of Product ( SOP ) dan Product of Sum ( POS )

Algoritma dan Struktur Data : Algorithms, Making Pseudocode, dan Contoh Soal

Algorithms, Data Structure & Programs

Algorithm + Data Structure = Program [Niklaus Wirth]

Programming: Implement an algorithm into a suitable programming language, using a data structure supported by the programming language

Definition of Algorithms

Origin of the word "Algorithm": 9th Century Persian Mathematician, Abu Abdullah Muhammad ibn Musa Al-Khwarizmi

Algorithms: the very basic and (probably) the most important thing on the world of computer

Data Structure

Way in which data are stored for efficient search and retrieval. Data Structure is methods or formats for organizing data in a computer

Computational Problem

Computational problem is defined in terms of its input and output. An instance of the sorting problem {31, 41, 59, 26, 41, 58}. A correct algorithm halts with a correct output for every input instance

Example: Reduce a Fraction

1. Problem : Reduce a given fraction to its lowest terms 
2. Input : a pair of positive integers representing the numerator and denominator of a fraction 
3. Output : a pair of positive integers representing the numerator and denominator of the fraction in its lowest terms

Ideas

• Equivalent to finding GCD (greatest common Divisor) of the two numbers and divide both numbers with their GCD 
• Reduce the problem into finding GCD of 2 positive integers

Finding GCD

Steps :

1. Find r, the minimum value between a and b. 
2. If both a and b are divisible by r then r is the GCD of a and b. 
3. Otherwise decrement r. 
4. Go back to step 2. 

Usually, pseudocode is used to present an algorithm

Pseudocode

Pseudocode : a notation resembling a simplified programming language, used in program design. 

Why we need to use it ? 

• Code : used in communication between human and computer 
• Pseudocode : used in communication/discussion (about algorithm) between human and another human

Example

Pseudocode Conventions

• Use an uppercase letter for method’s name 
• "//" indicates the remainder of the line is a comment 
• Line number is used for easier reading 
• Use "=" for an assignment 
• Does not need to declare or initialize a variable 
• Allow multiple values to be returned in a single return statement 
• Multiple assignment : i = j = e
• Indentation: indicates block structure 
• To describe repetition: while, for, and repeat-until 
• To describe branching: if-else 
• To decrement the counter value: downto 
• To change loop counter by amount great than 1: by 
• Variables are local to the given procedure/method 
• Array access: [ ] 
• Compound data: objects and their attributes. 
• Attribute access: OBJECT_NAME.ATTRIBUTE 
• A return statement immediately transfers control back to the point of call in the calling procedure 
• error: indicates an error 
• Short circuiting 

Examples

Necesities

• Practical : You have to know a standard set of important algorithms for different areas of computing and build/practice your problem solving intuition.
• Theoretical : Study of algorithms is the cornerstone of computer science (informatics?) and its easier to study everything else after you master the basic.Exercises

Exercises

1. According to David Harel, what makes algorithms important in computer science ? 
2. Write 8 cases about the effects of bad algorithms ini real life ! 
3. Write the pseudocodes to solve these problems ! 
• Calculating the area of a circle ! 
• Calculating the distance of two points in 2D ! 
• Calculating the frequency of an integer x in an Array A. Array A contains n integers. 
• Calculating the result of matrix addition between Matices A and B! The dimension of A and B is m x n ! 
• Calculating the average value of every elements in the major diagonal of a n x n matrix
4. Write the pseudocode for these problems ! 
• Find the absolute value of an integer x ! 
• Checking if an integer n is odd or even. 

5. Euclid’s GCD

There might be several (different) algorithms to solve a same problem. Algorithm to find the GCD of two integers, created by Euclid:

1. Divide the number a by b, the remainder is r 
2. Replace a by b 
3. Replace b by r 
4. Continue until a can’t be more divided. In this case, a is the GCD

Discussion: This algorithm yield the same output. But, is it faster than the previous algorithm?
Task: Write the pseudocode of Euclid’s GCD algorithm!Eratosthenes’ Prime Number !

6. Eratosthenes' Prime Number

Finding all prime numbers up to a specified integer (n). Simple Algorithm created by Eratosthenes

1. Build a list of all the integers greater than one and less than or equal to n. 
2. Strike out the multiples of all primes less than or equal to the square root of n 
3. The numbers that are left are the primes. 

Task: Write the pseudocode of the algorithms of Eratothenes’ Prime Number !

Sumber

Slide ASD : Introduction dan Pseudocode

http://informatika.unpar.ac.id/