Week 2 : Algorithm Basics Introduction to Bioinformatics (LF:DSIB01) Panos Alexiou panagiotis.alexiou@ceitec.muni.cz Adobe Systems Basics of Algorithms •Definition of an algorithm • •Pseudocode Notation • •Exercise: The Coin Change Problem • •Brute force, Iterative, Recursive • •Big-O notation • 2 Adobe Systems What is an algorithm •A sequence of instructions one must perform to solve a well formulated problem •A step-by-step method of solving a problem •A set of instructions designed to perform a specific task • • 3 Sequence of instructions Step-by-step method Set of instructions Solve Perform Well formulated problem Specific task Adobe Systems 4 Sequence of instructions Step-by-step method Set of instructions Solve Perform Well formulated problem Specific task Adobe Systems Pseudocode Notation 5 Adobe Systems Pseudocode Notation 6 Adobe Systems Pseudocode Notation 7 Adobe Systems Pseudocode Notation 8 Adobe Systems Pseudocode Notation 9 Adobe Systems Pseudocode Notation 10 Adobe Systems Pseudocode vs Computer Code 11 If you were to build a machine that follows these instructions, you would need to make it specific to a particular kitchen and be tirelessly explicit in all the steps (e.g., how many times and how hard to stir the filling, with what kind of spoon, in what kind of bowl, etc.) This is exactly the difference between pseudocode (the abstract sequence of steps to solve a well-formulated computational problem) and computer code (a set of detailed instructions that one particular computer will be able to perform). Adobe Systems Pseudocode Exercise: Coin Change (Euro coins) 12 Convert an amount of money into the fewest number of coins Input: Amount of money (M) Output: the smallest number of 50c (a), 20c (b), 10c (c), 5c (d), 2c (e) and 1c (f) such that 50a+20b+10c+5d+2e+1f = M Try: M=60c; M=55c; M=40c Adobe Systems Pseudocode Exercise: Coin Change (Generalised) 13 Adobe Systems Pseudocode Exercise: Coin Change (US coins) 14 Try M = 40; c1=25, c2=10, c3=5, c4=1 NB: Division = “floor” Adobe Systems Pseudocode Exercise: Coin Change (US coins) 15 M = 40; c1=25, c2=20, c3=10, c4=5, c5=1 Discontinued 1875 for being too confusing NB: Division = “floor” Adobe Systems Pseudocode Exercise: Coin Change (US coins) 16 BetterChange 40= 1x25 + 1x10 + 1x5= 3 coins Incorrect! 40 = 2x20= 2 coins M = 40; c1=25, c2=20, c3=10, c4=5, c5=1 Discontinued 1875 for being too confusing NB: Division = “floor” Adobe Systems Pseudocode Exercise: Coin Change 17 Tries every combination Guaranteed to find optimal Slow Adobe Systems 18 Tries every combination Guaranteed to find optimal Slow Spoiler: (There is a better solution: Stay tuned for Week 4) Brute Force Algorithm Adobe Systems Recursive Algorithms 19 https://www.mathsisfun.com/games/towerofhanoi.html 1 disc = 1 move 2 discs = 3 moves (1-2, 1-3, 2-3) 3 discs = 7 moves (1-3, 1-2, 3-2, 1-3, 2-1, 2-3,1-3) … Adobe Systems Towers of Hanoi (3 disks) 20 https://www.mathsisfun.com/games/towerofhanoi.html More generally, to move a stack of size n from the left to the right peg, you first need to move a stack of size n − 1 from the left to the middle peg, and then from the middle peg to the right peg once you have moved the nth disk to the right peg. To move a stack of size n − 1 from the middle to the right, you first need to move a stack of size n − 2 from the middle to the left, then move the (n − 1)th disk to the right, and then move the stack of n − 2 from the left to the right peg, and so on. 7 moves (1-3, 1-2, 3-2, 1-3, 2-1, 2-3,1-3) Adobe Systems Towers of Hanoi: N disks 21 https://www.mathsisfun.com/games/towerofhanoi.html ? Adobe Systems Towers of Hanoi: N disks 22 https://www.mathsisfun.com/games/towerofhanoi.html Adobe Systems Towers of Hanoi: N disks 23 https://www.mathsisfun.com/games/towerofhanoi.html Adobe Systems Towers of Hanoi: 4 disks 24 https://www.mathsisfun.com/games/towerofhanoi.html Adobe Systems Towers of Hanoi: 4 disks 25 https://www.mathsisfun.com/games/towerofhanoi.html Adobe Systems Iterative Algorithms – Fibonacci Series 26 Adobe Systems Iterative Algorithms – Immortal Rabbits 27 A baby pair of rabbits takes the same time to mature as a mature pair of rabbits takes to produce a new pair. How many rabbits are there after N iterations? PS: rabbits cannot die! 1,1,sum of previous two, … Adobe Systems 28 Iterative: Fast (linear) Recursive: Slow (exponential) Iterative Algorithms vs Recursive Algorithms Adobe Systems 29 Recursive: Slow (exponential) Adobe Systems Algorithms •Brute force : Try Everything, slow but always correct • •Recursive : To Solve for n, first solve for n-1 • •Iterative : Loop on something, can be faster 30 Adobe Systems Fast vs Slow algorithms 31 •How many operations does an algorithm take as N increases? • •Is the relationship linear? Quadratic? Exponential? • •What is the upper limit of the running time of an algorithm as N increases? Adobe Systems Guess random number (up/down) 32 Simple search: For i in 1 to N If i == the number return i Binary search: Range-min = 1 Range-max = N While () i = middle number of range if i == the number; return I elsif i < number; Range-max=i; elsif i > number; Range-min=i; 1ms / check N = 100 Adobe Systems Guess random number (up/down) 33 ??? Guess ??? ~15 times faster Adobe Systems Guess random number (up/down) 34 ~450ms ? ~15 times faster ~15 times faster ? Adobe Systems Guess random number (up/down) 35 ~15 times faster Adobe Systems Guess random number (up/down) 36 Linear 1 ms/element O(n) Logarithmic 1 ms/log2(element) O(log n) (Worst case scenario) Adobe Systems 37 Adobe Systems Common Big-Os 38 https://www.freecodecamp.org/news/big-o-notation-simply-explained-with-illustrations-and-video-87d5 a71c0174/ "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" Adobe Systems Week 1 Summary 39 -I know what an algorithm is - -I can write pseudocode - -I understand -Brute force -Iterative -Recursive - -Big-O = how slow Adobe Systems Adobe Systems Adobe Systems Adobe Systems Adobe Systems Adobe Systems 40 www.ceitec.eu CEITEC @CEITEC_Brno Panos Alexiou panagiotis.alexiou@ceitec.muni.cz Thank you for your attention! 60 minutes lunch break. >