What is an algorithm.pdf

COMP 1631 F2024 Reading file What is an algorithm? Algorithms are precise step-by-step...

COMP 1631 F2024 Reading file What is an algorithm? Algorithms are precise step-by-step plans to solve a problem. Algorithmic thinking is the skill involved in developing an algorithm. In a sense, algorithms are blueprints for writing code in a specific programming language. (Image source: https://www.youtube.com/watch?v=9qfY3k0wMQ8) An algorithm for converting a decimal number to a binary number: Vocab alert: A decimal number is a way of writing numbers with which you are likely the most familiar, where numbers are written in a base-10 system. For instance, in a decimal system, the number 465 means: 4 × 10 + 6 × 10 + 5 × 10 Each position as we move left is a unit base 10 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) times 10. But decimal numbers aren’t the only way to write numbers. We can also write numbers in a base-2 system, where each position, as we move left, is a unit base 2 (0, or 1) times 2. This number system is the binary number system. For instance, 465 in binary notation would be 111010001, i.e. 1×2 +1×2 +1×2 +0×2 +1×2 +0×2 +0×2 +0×2 +1×2 (Get a calculator and check that when you do the math above you get 465!) Test yourself: Decimal and binary aren’t the only base number systems. You can use any number you’d like (another one computers often use is hexadecimal, which is base-16). Try to write 465 in ternary, which is base-3. The units base 3 are 0, 1, and 2. Then check your solution on the last page. Underneath everything, at the very bottom level, computers are using binary numbers all the time, so being able to convert between base 10 and base 2 is important to know. So let’s see how to do it: COMP 1631 F2024 Reading file 1. Let 𝑛 be a decimal number 2. Let 𝑏 be the number, initially nothing, that becomes our answer. The binary number will be constructed from right to left. 3. Repeat the following steps until 𝑛 becomes 0: a) Divide 𝑛 by 2, letting the result be 𝑑 and the remainder be 𝑟. b) Append the remainder, 𝑟, as the left-most digit of 𝑏. c) Let 𝑑 be the new value of 𝑛. Get a sheet of paper, and follow the above algorithm with 465 to make sure you get the same answer as above. But a computer, sadly, does not understand English. We need to convert the above algorithm into a language the computer understands. A program that expresses the algorithm in Scratch (left) and in Python (right): Even though these both look very different, they do the same thing (convert a decimal number to binary) and are both implementations of the algorithm above. Algorithms are procedural abstractions Abstraction is a fundamental idea in programming and refers to the process of removing physical, spatial or temporal details or attributes in the study of objects or systems to focus attention on information of greater importance or relevance. In a sense, an algorithm is an abstract description of a computational procedure. We encounter algorithms in everyday life. For example, in the figure below, look at the route COMP 1631 F2024 Reading file from the Dunn Building to the Sackville Memorial Hospital specified by Google Maps. An example of some details that are abstracted away are the most scenic route or which route is better on a specific day of the week. What other details can you list that are abstracted away? Some other abstractions include recipes and furniture assembly instructions COMP 1631 F2024 Reading file (Image source Blueberry Grunt: https://ourbestbites.com/wprm_print/blueberry-grunt#) (Image source furniture assembly: https://manuals.plus/ikea/billy-oxberg-bookcase-with- door-manual) The recipe for blueberry grunt does not care what brand of flour you use, nor where the blueberries were grown, nor in which country you are baking the grunt. The assembly instructions do not care how old you are, what screwdriver or hammer you use, or in what room you assemble the furniture. These details are irrelevant to the examples above. Multiple Solutions to the Same Problem It is important to note that there may be multiple solutions to the same problem: not all algorithms are equal, and one computational approach may be preferable to another. For example, one algorithm may be more reliable or require fewer steps. A crucial aspect of learning how to program is understanding that different algorithms can get you to the same end goal: there are often multiple solutions to a problem. Just as Google Maps may suggest alternate routes, one may be preferable to another because of the estimated duration, construction delays, mode of travel (car, public transport, bicycle or on foot), distance travelled or time of day. The option you choose may adhere to one of these criteria, or it may be something personal, like the route that takes you past a friend's house or the local chocolate shop. Likewise, algorithmic solutions for writing code may have superficial differences or more significant ones, like completion time or memory resource allocation. Vocab alert: Completion time is how long it takes an algorithm to run from start to finish. For example, how long it takes you to clean your room (an algorithm) may vary greatly from how long it takes your mum to clean your room, even though, in the end, the room ends up the same level of clean (maybe…) Vocab alert: It takes space, both physical and/or virtual, for a computer to run a program or algorithm and, behind the scenes, your computer is always putting stuff that is being run or saved in specific places. Memory allocation is a computer hardware operation that assigns this space. Characteristics and Components of Algorithms Donald Knuth, one of the 20th century pioneers of computer science, defines the following characteristics of algorithms: COMP 1631 F2024 Reading file (Image source: https://www.azquotes.com/quote/964459) 1. Finiteness: An algorithm must always terminate after a finite number of steps 2. Definiteness: Each step of an algorithm must be precisely defined. Each case must rigorously and unambiguously specify the actions to be carried out. 3. Input: An algorithm has zero or more inputs, which are quantities given to it initially before the algorithm begins or dynamically as the algorithm runs. 4. Output: An algorithm generally has one or more outputs: products of the algorithm's execution that have a specified relation to the inputs. 5. Effectiveness: An algorithm is also generally expected to be effective, in the sense that its operation must all be sufficiently basic so that they can, in principle, be done precisely and in a finite length of time by someone using pencil and paper. So what is 465 in ternary? 465 in ternary is 122020, i.e. 1×3 +2×3 +2×3 +0×3 +2×3 +0×3 Did you get it right?