Exploring Algorithmic Concepts and Applications

BIT 1003- Presentation 4

An problems An algorithm problems. . algorithm is is a a method method for for solving solving a a class class of of While algorithms, solving While algorithms, the solving a a particular computer computer scientists term applies type of scientists applies to of problem think to any problem. . think a a lot method of lot about about the term particular type any method of e e. .g g. . The procedure, for The repair procedure, which for replacing repair manual which could replacing the manual for could also the brake for your also be pads. . your car be called car will called an will describe an algorithm, describe a a algorithm, brake pads 2

In mathematics, a famously successful and useful algorithm is Euclid s algorithm for finding the greatest common divisor (GCD) of two numbers. The GCD is the largest integer that will evenly divide the two numbers in question. Euclid described his algorithm about 300 BCE. 3

Repeat: If B is zero, the GCD is A. Otherwise: find the remainder R when dividing A by B replace the value of A with the value of B replace the value of B with the value of R 4

GCD(372, 84) Find GCD(84, 36) because 372/84 > remainder 36 Find GCD(36, 12) because 84/36 > remainder 12 Find GCD(12, 0) because 36/12 > remainder 0; Solved! GCD = 12 5

In computer science, algorithms are usually represented as pseudocode. Pseudocode programming language that it can represent the tasks the computer must perform in executing the algorithm. is close enough to a real Pseudocode particular language. is also independent of any 6

Function ! = means not equal Function name name and and arguments arguments GCD ( a, b ) GCD ( a, b ) While b ! = 0 { { indentation shows what to do while b ! = 0 set r = a modulo b ( = remainder a/b) r <-- a modulo b a <-- b b <-- r set a = original b set b = r (i.e., the remainder) border of the while repetition } } when b = 0, return value of a as the GCD return a 7

To illustrate how different algorithms can have different performance characteristics, we will discuss a variety of algorithms that computer scientists have developed to solve common problems in computing. 8

Suppose one is provided with a list of people in the class, and one is asked to look up the name Hasan Cemal. A algorithm that one can use. With simply compares each name in the list to the name for which we are searching. The search ends when the algorithm finds a matching name, or when the algorithm has inspected all names in the list. sequential search is a brute brute force force a sequential search, the algorithm 9

// indicates a comment list_of_names[3] is the third name in the list 10

If we know how long each statement takes to execute, and we know how many names are in the list, we can calculate the time required for the algorithm to execute. However, the important thing to know about an algorithm is usually not how long it will take to solve any particular problem. The important thing to know is how taken size how the will vary the time vary as time as the taken to size of to solve of the solve the the problem the problem problem changes problem will changes. the 11

If the list is twice as long, approximately twice as many comparisons will be necessary. If approximately comparisons will be necessary. In that case, the time devoted to the statements executed only once will become insignificant with respect to the execution time overall. The algorithm list the list is a million million times times as as long, many a The algorithm grows list being running running time in proportion searched. . time of of the the sequential to the sequential the size search of the search grows in proportion to size of the being searched 12

We say that the order of growth of the sequential search algorithm is n. The notation for this is T(n). We also say that an algorithm whose order of growth is within some constant factor of T(n) has a theta of NL say. The sequential search has a theta of n. The size of the problem is n, the length of the list being searched. 13

We say the sequential search algorithm is (n) because in the average case, and the worst case, its performance slows in proportion to n, the length of the list. 14

Programmers have designed many algorithms for sorting functionality frequently. One sorting algorithm is called the insertion sort, and it works in a manner similar to a card player organizing his hand. Each time the algorithm reads a number (card), it places the number in its sorted position among the numbers (cards) it has already sorted. numbers, because one needs this 15

Another algorithm for sorting numbers uses recursion detail shortly, to divide the problem into many smaller problems before recombining the elements of the full solution. recursion, a technique we will discuss in more Merge_sort_animation2.gif 16

Earlier algorithm and found its performance to be (n). One can search much more efficiently if one knows the list is in order to start with. The improvement in efficiency is akin to the improved usefulness of a telephone book when the entries are sorted by alphabetical order. In fact, for most communities, a telephone book where the entries were not sorted alphabetically would be unthinkably inefficient! we discussed the sequential search 17

18

The algorithms discussed so far all have an order of polynomial equation in n. A polynomial in n means the sum of some number of terms, where each term consists of n raised to coefficient. For instance, the insertion sort order of growth is (n2/2 - n/2). When an algorithm has an order of growth that is greater polynomial scientists refer to the algorithm as intractable. growth that can be described by some some power and multiplied by a than can be expressed n, by computer some equation in then 19

The salesman needs to visit each of several cities, and wants to do so without visiting any city more than once. In the interest of efficiency, the salesman wants to minimize the length of the trip. 20

Germany [1] 14! / 2 = 43,589,145,600 21

A factorial order of growth is even more extreme than an exponential order of growth. For example, there are about 3.6 million permutations of 10 cities, but more than 2 trillion billion permutations of 20. If the computer can compute the distance for a million permutations a second, the TSP problem will take 1.8 seconds for 10 cities, but tens of thousands of years for 20 cities. 22

As an example, consider a sorting task. Suppose you need to sort a million numbers (social security numbers, for example). You have the choice of using your current computer with a merge sort program, or of buying a new computer, which is 10 times faster, but which uses an insertion sort. 23

The insertion sort on the new computer will require on the order of (106)2, or a million million cycles, while the merge sort will require on the order of 106(lg 106), or 106(6), or 6 million cycles. Even when it runs on your old computer, the merge sort will still run four orders of magnitude faster machine. If it takes 20 seconds to run the merge sort on your old machine, it will take over 27 hours to run the insertion sort on the new machine! than the insertion sort on the new 24

Algorithm important technology. design should be considered A better algorithm can make the difference between being able to solve the problem or not. A better algorithm can make a much greater difference than any near-term improvement in hardware speed. 25

An algorithm is a specific procedure for accomplishing some job. Much of computer science has to do with finding or creating better algorithms for solving computational problems. We usually describe computational algorithms using pseudocode. We characterize the performance of algorithms using the term order of growth or theta. The order of growth of an algorithm tells us, in a simplified way, how the running time of the algorithm will vary with problems of different sizes. We provided examples of algorithms whose orders of growth were (lg n), n, n(lg n), n2, 2n and n!. Algorithm development should be considered an important part of computing technology. In fact, a better algorithm for an important task may improvement in computing hardware speed. be much more impactful than any foreseeable near-term 26

2.1 2.9 27