Simplifying Algorithms with Variables and Indices
When writing algorithms, simplifying sequences of steps using variables and indices can lead to clearer and more concise explanations. By defining variables for elements and using indices to denote sequences, algorithms become easier to understand and manage. This approach helps in streamlining the algorithms, making them more efficient and less confusing.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
15-110: Principles of Computing Lecture 3: Algorithms and Abstractions August 30, 2020 Mohammad Hammoud Carnegie Mellon University in Qatar
Today Last session: Examples of algorithms Today s session: Abstractions Announcements: HW1 will be out today Quiz I grades will be out today
How to Simplify Sequences of Steps? You might have noticed that writing a sequence of steps in English (or in any natural language) can quickly become cumbersome The lines are too long and explaining that we need to compare a card with the next card which is on the right side of the card before requires a lot of thinking Consequently, we need to use a more constrained and less ambiguous language if we want to be really clear
Simplifying Sequences of Steps: Variables & Indices For this sake, we can use names (or variables) and indices in a way that is closer to math (and consequently to computing) Let us apply that to our program for finding the highest card in a deck We need to define the variables to use, their meanings, and their values (if any) Also, when we have a sequence of things, it is useful to denote it using indices, such as a0, a1, a2, ...an(this is a sequence with n + 1 elements)
Simplifying Sequences of Steps: Variables & Indices 1. Let c0, c1, ..., cn-1be the set of n cards 2. Let max = c0represent the highest card so far 3. Let i = 0 be the index of the last card we checked 4. Check if i < n: A. If yes: Check if ci+1> max a. If yes: max = ci+1; i = i + 1; go back to step 4 b. If no: i = i + 1; go back to step 4 B. If no: highest card is max A variable named max with c0 as a value assigned to it Try to rewrite some or all of the algorithms that we did last lecture using variables & indices and see how concise they become!
Simplifying Sequences of Steps: Repeat We can also identify when a sequence of steps is repeating, and for what values, and simply say: repeat this for all values... For example, in the previous algorithm, steps 4.A to 4.B are supposed to be executed for every i from 0 to n 1 Let us rewrite it using repeat"
Simplifying Sequences of Steps: Repeat 1. Input: Let c0, c1, ..., cn-1 be the set of n cards 2. Let max = c0 represent the highest card so far 3. Let i = 0 be the index of the last card we checked 4. Repeat for i = 0,1,2, ..., n 1: a. Check if ci+1 > max a. If yes: max = ci+1; 5. Output: Highest card is max Notes: Incrementing ieach time and going back to step 4 are now implicit in the repeat command The steps are now much closer to a program, thus it will be easier to type this in Python when the time comes!
Abstraction Let us consider again the problem of choosing snacks from a cafeteria given a certain budget and calorie intake The problem can be phrased as follows: You want to buy the highest-calorie snack from the below and pay a max of 15 QAR Item Price (QAR) Calories Objective: Maximize calories without execeeding a certain budget (constraint) Muffin 6 480 How Croissant 7 595 would you solve this? Chips 10 950 Hamburger 8 800 Chocolate 2 300 Fruit salad 5 200
Abstraction Hint: think about the calories per riyal Since it is a maximization problem, the higher the better In particular, you want the highest number of calories per each riyal (a greedy strategy) in order to obtain the highest-calorie snack with the 15QAR Item Price (QAR) Calories Calories/Riyal Muffin 6 480 480/6 = 80 5/10 of Chips 5/10 * 950 Cal 5 QAR Croissant 7 595 595/7 = 85 + + Chips 10 950 700/10 = 95 Hamburger 8 QAR + 800 Cal + Hamburger 8 800 800/8 = 100 Chocolate 2 300 300/2 = 150 2 QAR 300 Cal Chocolate Fruit salad 5 200 200/5 = 40 15 QAR 1,575 Cal
Abstraction This worked only because we assumed we can take fractions of items If this is not the case, this greedy strategy will not work! This problem is known as the 0 1 knapsack problem Item Price (QAR) Calories Calories/Riyal Muffin 6 480 480/6 = 80 Fruit Salad 200 Cal 5 QAR Croissant 7 595 595/7 = 85 + + Chips 10 950 700/10 = 95 Hamburger 8 QAR + 800 Cal + Hamburger 8 800 800/8 = 100 Chocolate 2 300 300/2 = 150 2 QAR 300 Cal Chocolate Fruit salad 5 200 200/5 = 40 15 QAR 1,300 Cal
Abstraction Here is another combination that has more calories, albeit spending the same amount of money (thus, the greedy approach did not give us the best answer) Solving this problem requires applying another algorithmic approach known as dynamic programming , which is beyond the scope of this class Item Price (QAR) Calories Calories/Riyal Muffin 6 480 480/6 = 80 Croissant 7 595 595/7 = 85 Chips 10 950 700/10 = 95 Croissant 7 QAR + 595 Cal + Hamburger 8 800 800/8 = 100 Chocolate 2 300 300/2 = 150 8 QAR 800 Cal Hamburger Fruit salad 5 200 200/5 = 40 15 QAR 1,395 Cal
Abstraction Let us consider another problem where we have a set of items with different weights and values Your job is to take the highest valuable load in a bag without exceeding a weight of 15Kg Objective: Maximize value without execeeding a certain weight (constraint) Item Weight (Kg) Value (QAR) Sceptre 4 10 How Shoes 1 1 would you solve this? Helmet 1 2 Armour 12 4 Dagger 2 2
Abstraction Do you think that this problem is similar to the snack problem? They are actually the same! If we can craft an algorithm for the snack problem, we can transform it (with minimal effort) into a solution for this problem The core of the two problems is: a. There is a set of items to choose from, with two associated values b. The answer consists of a subset of items such that one value is minimized/maximized and the other value adds up to a certain amount k c. The items cannot be split (i.e., non-fractional items)
So, What is Abstraction? Abstraction is the ability to overlook the unimportant details of a problem and focus only on the important core parts of it By doing this, we can transform the problem into something else, which we have a solution for
Example: Balancing Chemical Equations When we learn about chemical reactions, we often need to balance chemical equations such as this one: Al + O2 Al2O3 The goal is to assign coefficients for each molecule such that the number of atoms is the same on each side In school, we usually learn how to do this by trial and error If we give this problem a little thought, we will realize that there is a systematic way of finding solutions for it (i.e., NOT by trial and error)
Example: Balancing Chemical Equations The goal is to find the coefficients, so let us write them as variables in the equation: xAl + yO2 zAl2O3 The number of Al atoms on the left is x and on the right is 2z We want x = 2z, or x 2z = 0 Same holds for O, where we would want 2y = 3z, or 2y 3z = 0
Example: Balancing Chemical Equations The problem becomes finding x, y, z such that the following equations are satisfied: x 2z = 0 2y 3z = 0 What did we do? We transformed the problem of balancing chemical equations into a problem of solving a system of linear equations A computer does not know about chemical equations, but it knows a lot about linear equations There are many algorithms for solving this type of problem, so it is just a matter of choosing your favourite one!
Exercise: Binary Numbers Base-10 numbers (or regular numbers) can be represented as combinations of powers of 10 multiplied by coefficients 42 = 4 10 + 2 1 = 4 101 + 2 100 The coefficients range from 0 to 9; can you guess why? This idea can be applied to any natural number, not only base-10 ones The next most popular bases are 2 (or binary) and 16 (or hexadecimal)
Exercise: Binary Numbers Let us apply the same idea to a number in binary: 1010 1 23 + 0 22 + 1 21+ 0 20 8 + 2 10 This time the number on the left of is in base 2 and the numbers on the right are in base 10 Based on this, can you write an algorithm that transforms any binary number into its decimal representation (use variables to make your life easier)?
Algorithm: Binary to Decimal Numbers 1. Input: A binary number d0d1...dn 2. Let sum= 0 3. Let p= 1 4. Repeat for i = n, n 1, n 2, ..., 0: a. sum = sum + di p b. p = p 2 5. Output: sum
Next Class Moving to Python
References Notes on Principles of Computing by Giselle Reis: https://web2.qatar.cmu.edu/~mhhammou/15110-f20/references/ Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
