Week 1 Introduction to Algorithm And Data Structure.ppt

SAVE OFFLINE

Algorithms and Data Structures Dr. Rand Kouatly [email protected]

University of Applied Sciences Europe Berlin 2019

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

1

Course Contents ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪

Introduction to Algorithms and Data Structures, Mathematics for Algorithms, Functions and Recursion, Sorting Problem, Divide and Conquer, Data Structure (Array, Stack, Queue, Linked List), Data Structure (Graphs, Trees), Searching Problem, Data Structure (Priority Queues, Binary Heaps), Data Structure (Hash Functions, Hash Table, Disjoin set), Dynamic Programming,

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

2

Definition In this course, we will look at: Algorithms for solving problems efficiently Data structures for efficiently storing, accessing, and modifying data

We will see that all data structures have trade-offs There is no ultimate data structure... The choice depends on our requirements The problem of big Data The problem of scalability

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

3

Definition ⚫

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time. problem

algorithm

input

“computer”

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

output 4

Definition ⚫

⚫

The algorithm is a step-by-step method of solving some problem. Algorithms typically have the following properties: ⚫

⚫ ⚫ ⚫

⚫

⚫

⚫

Input: The algorithm receives input. Output: The algorithm produces output. Precision: The steps are precisely stated. Determinism: The intermediate results of each step of execution Finiteness: The algorithm terminates; that is, it stop after finite number. Correctness: The output produced by the algorithm is correct. Generality: The algorithm applied to set of inputs.

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

5

Definition ⚫

Important points: – The non ambiguity requirement for each step of an algorithm cannot be compromised. – The range of inputs for which an algorithm works has to be specified carefully. – The same algorithm can be represented in several different ways. – Several algorithm for the same problem may exists. – Algorithms for the same problem can be based on very different ideas and solved the problem with dramatically different speed.

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

6

Definition For example: Finding the Maximum of Three Numbers. This algorithm finds the largest of the numbers a, b, and c.

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

7

Definition For example: Finding the Maximum of Three Numbers. This algorithm finds the largest of the numbers a, b, and c. Solution 1: if a > b, if a > if c > a if c > if b > a if b >

then c then then b then then c then

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

print (a is the largest)

print (c is the largest) print (b is the largest) 8

Definition For example: Finding the Maximum of Three Numbers. This algorithm finds the largest of the numbers a, b, and c. Solution 2:

x = a if b > x, then if c > x, then

x = b x = c Print (the largest is x)

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

9

Definition Fundamental data structures ⚫

List

⚫

Graph

➢

array

⚫

Tree

➢

linked list

⚫

Set and dictionary

⚫

Stack

⚫

Binary Tree

⚫

Queue

⚫

Heap

⚫

Priority Queue

⚫

Hash Tables

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

10

Algorithm Tasks There are two main tasks in the study of algorithms:

• Designing an algorithm: To solve a particular problem.

• Analyzing a given algorithm: Analyzing algorithms provides insights into designing new algorithms.

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

11

Algorithm Tasks

• Designing an algorithm: To solve a particular problem.

Is an art more than a science. There are basic techniques: - Searching techniques - Divide-and-conquer methods. - Greedy algorithms. - Dynamic programming.

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

12

Algorithm Tasks For example: Finding if the n is prime or not (Prime Number is the number that can be divided only by it self or 1 without a reminder) Example: n =17 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

The number 17 is prime number

Example: n =21 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

The number 21 is not prime number Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

13

Algorithm Tasks For example: Finding if the n is prime or not 1- for each number list p from 2 to n starting from i = 1 2- if i / p with no reminder the number is not prime then exit 3- increase i

4- repeat until i is equal to n 5- go step 2 6- print the number is prime Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

14

Algorithm Tasks For example: Finding the list of prime numbers that are less and equal to n. Example: n =23 2 2 2 2

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 3 5 7 9 11 13 15 17 19 21 23 3 5 7 11 13 17 19 23 3 5 7 11 13 17 19 23

The remining number are the list of the consecutive prime number of 23

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

15

Algorithm Tasks For example: Finding the list of prime numbers that are less and equal to n. 1- for each number list p from 2 to n save all the number in Array A

2- starting from the first number in the array A[0] 3- if A[1] = 0 go to to next number 4- repeat for all A[1] and eliminate all multiple of A[1] in the list by setting A[i] to 0 until i = n 5- Go to second number A[2] and go step 3 Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

16

What is an Algorithms Recipe, process, method, technique, procedure, routine,… with following requirements: ⚫ Finiteness: terminates after a finite number of steps ⚫ Definiteness: rigorously and unambiguously specified ⚫ Input: valid inputs are clearly specified ⚫ Output: can be proved to produce the correct output given a valid input ⚫ Effectiveness: steps are sufficiently simple and basic Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

17

What is an Algorithms Theoretical importance the core of computer science Practical importance

A practitioner’s toolkit of known algorithms Framework for designing and analyzing algorithms for new problems

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

18

Algorithm Tasks • Analyzing a given algorithm: In analysis is to assure: Correctness: given an algorithm for problem, does it solves the problem? Termination: Does the algorithm always stop after a finite number? Time analysis: How many instructions does the algorithm execute? Space analysis: How much memory does the algorithm need to execute? Does there exist a better algorithm? : Lower bounds : Optimality

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

19

Pseudo code for Algorithms Although ordinary languages is sometimes adequate to specify an algorithm computer scientists prefer pseudo code. ⚫

Pseudo code is so named because it resembles the actual code of computer languages such as C++ and Java. ⚫

There are several versions of Pseudo code, which must be concerned, uppercase and lowercase letters, special words,…. ⚫

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

20

Pseudo code for Algorithms For example: Finding the Maximum of Three Numbers. Input Parameters: a, b, c Output Parameter: x max(a,b,c,x) { x = a if (b > x) // if b is larger than x, update x x = b if (c > x) // if c is larger than x, update x x = c }

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

21

Pseudo code for Algorithms For example: Finding if n is prime number. Input: Integer n Output: primes true or flase for i ← 2 to n do if n % i = 0 //% computer the reminder of division prime = flase exit else i← i + 1 prime = true

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

22

Pseudo code for Algorithms For example: Finding the list of prime numbers that are less and equal to n. Input: Integer n ≥ 2 Output: List of primes less than or equal to n for p ← 2 to n do A[p] ← p for p ← 2 to n do if A[p] ≠ 0 //p hasn’t been previously eliminated from the list j←p*p while j ≤ n do A[j] ← 0 //mark element as eliminated j←j+p

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

23

Famous Algorithms ⚫ ⚫ ⚫ ⚫ ⚫ ⚫ ⚫

⚫ ⚫ ⚫

Sorting Searching Shortest paths in a graph Minimum spanning tree Primality testing Traveling salesman problem Knapsack problem Chess (n –Queen) Towers of Hanoi Program termination

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

24

The Present Many algorithms currently in use are not general, deterministic, or even finite. ⚫

An operating system, is a program that never terminates. ⚫

A finite program with input and output (Online algorithms). ⚫

Algorithms written for more than one processor, ore multiprocessors, are deterministic. ⚫

Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

25

The Future Quantum Computing ⚫ In Quantum computer, the fundamental unit of information is quamtum bit or qubit. ⚫ qubit like a bit, has values 0 and 1, but it can also exist in an intermediate state, ⚫ A quantum computer operates on qubits, ⚫ It can perform some computations more efficiently than a traditional one. DNA Computing ⚫ DNA (deoxyribonucleic acid) Computing bits (0 and 1) are replaced by bases A, C, G, and T. ⚫ A DNA computation begins by generating strand of DNA. Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

26

Thank you!

Any Questions? Dr. Rand Kouatly, Algorithms and Data Structures - University of Applied Siences Europe, 2019

27