Lecture of algorithms and problem solving

Algorithms

1. Algorithms Discrete Structures Riphah International university lahore

2. Algorithms What is an algorithm? An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.

3. Algorithms Properties of algorithms: Input from a specified set, Output from a specified set (solution), Definiteness of every step in the computation, Correctness of output for every possible input, Finiteness of the number of calculation steps, Effectiveness of each calculation step and Generality for a class of problems.

4. Pseudocode An algorithm can also be described using a computer language. Understanding an algorithm is complicated and difficult. Algorithm can be translated into any programming language. As many programming languages are in common use, so instead of using a particular computer language to specify algorithms, a form of Pseudocode, will be used in this book. Pseudocode provides an intermediate step between an English language description of an algorithm and an implementation of this algorithm in a programming language.

5. Pseudocode Algorithm 1: Finding the Maximum Element in a Finite Sequence. procedure max(a 1 , a 2 , . . . , a n : integers) max := a 1 for i := 2 to n if max < a i then max := a i return max { max is the largest element}

6. Pseudocode 3 , 4 , 8 , 1 , 6 , 7 , 15 , 5 , 8 , 2 i a i max     3 2 (a 2 ) 4 (3<4) 4 3 (a 3 ) 8 (4<8) 8 4 (a 4 ) 1 (8<1) 8 5 (a 5 ) 6 (8<6) 8 6 (a 6 ) 7 (8<7) 8 7 (a 7 ) 15 (8<15) 15 8 (a 8 ) 5 (15<5)15 9 (a 9 ) 8 (15<8)15 10 (a 10 ) 2 (15<2) 15

7. Linear Search: It is also called sequential search. It searches an element sequentially by comparing the searching element with each element in the list one by one. procedure linear search ( x : integer, a 1 , a 2 , . . . , a n : distinct integers) i := 1 while ( i ≤ n and x ≠ a i ) i := i + 1 if i ≤ n then location := i else location := 0 return location { location is the subscript of the term that equals x , or is 0 if x is not found}

8. Linear Search:

9. Linear Search:

10. Linear Search:

11. Binary Search: Binary Search algorithm is used to search an element from a list of elements. This algorithm can be used when the list has terms occurring in increasing order. It proceeds by comparing the element to be located to the middle term of the list. The list is then split into two smaller sub lists of same size, or one of these smaller lists has one fewer term than other. The search continues by restricting the search to the appropriate sub lists based on the comparison of the element to be located and the middle term.

12. Binary Search: procedure binary search ( x : integer, a 1 , a 2 , . . . , a n : increasing integers) i := 1{ i is left endpoint of search interval} j := n { j is right endpoint of search interval} while i < j m := if x > a m then i := m + 1 else j := m if x = a i then location := i else location := 0 return location { location is the subscript i of the term a i equal to x , or 0 if x is not found}  

13. Binary Search:

14. Binary Search:

15. Binary Search:

16. Sorting Sorting is putting the elements into a list in which the elements are in increasing order.

17. Bubble Sort: The bubble sort is one of the simplest sorting algorithms, but not one of the most efficient. It puts a list into increasing order by successively comparing adjacent elements, interchanging them if they are in the wrong order. To carry out the bubble sort, we perform the basic operation that is, interchanging a larger element with a smaller one following it, starting at the beginning of the list, for full pass. We iterate this procedure until the sort is complete.

18. Bubble Sort: procedure bubblesort (a 1 , . . . , a n : real numbers with n ≥ 2) for i := 1 to n − 1 for j := 1 to n − i if a j > a j +1 then interchange a j and a j +1 { a 1 , . . . , a n is in increasing order}

19. Bubble Sort:

20. Bubble Sort:

21. Bubble Sort:

22. Insertion Sort: Insertion Sort is a simple sorting algorithm, but it is usually not the most efficient. To sort a list with n elements, the insertion sort begins with the second element. This second element is compared with the first element and inserted before the first element if it is smaller than the first element and after the first element if it is greater than the first element. At this point, the first two elements are in correct order. The third element is then compared with the first element, and if it is larger than the first element, it is compared with the second element, it is inserted into the correct position among the first three elements and so on.

23. Insertion Sort: procedure insertion sort(a 1 , a 2 , . . . , a n : real numbers with n ≥ 2) for j := 2 to n i := 1 while a j > a i i := i + 1 m := a j for k := 0 to j − i − 1 a j − k := a j − k −1 a i := m { a 1 , . . . , a n is in increasing order}

24. Insertion Sort:

25. Insertion Sort: