Solving Problems and Finding Solutions Through Algorithms
Explore the concept of algorithms and problem-solving methods in daily and professional life, illustrated with examples ranging from choosing a meal to creating schedules for courses. Understand the importance of constraints, available knowledge, and requirements when seeking solutions. Learn how to approach problems at a high level by considering various factors and constraints. Delve into the process of problem-solving by understanding the problem, its context, and potential solutions.
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 1: What Are Algorithms? July 31, 2022 Mohammad Hammoud and Eduardo Feo Flushing Carnegie Mellon University in Qatar
We Encounter Problems Every Day In our daily and professional lives we are often faced with problems to solve Can you state a problem (any problem) that you ve encountered recently and had to find a solution for? Was the problem hard to think through? How did you come up with a solution for it? Was your solution acceptable, good, or the best that can be achieved? Problems can be as small as choosing a meal at a restaurant, or as complicated as making a schedule for all CMU courses (or even harder)
What to Consider When Trying to Find Solutions When trying to find a solution, you need to consider a number of aspects beforehand Constraints: Maybe you have only 20QAR to spend on a meal; what meal will you choose? Available Knowledge: You want to eat the healthiest meal, but nutritional facts are only available for a few of them and not all Requirements: Do you aim for a solution, a good solution, or the best solution?
Getting to Solving a Problem When will you be in a position to solve a problem? When you understand the problem its constraints its context (or the information that can be leveraged) what consists of a solution
Let us Approach a Problem at a High-Level Imagine you want to make a schedule for all CMU courses Some information to consider for each course: Time frame (first half, second half, full semester) Frequency (the number of times it will be taught every week) Lecture duration Type of the classroom Instructor(s) Some constraints: Limited number of classrooms Some courses may not overlap (e.g., students need to take them all or one instructor teaches two courses, etc.,) Is there always a perfect solution to this problem?
Let us Approach a Problem at a High-Level If you are given enough time, you can probably figure out a schedule (say, for 3, 5, or whatever number of courses) How will the difficulty of the problem vary when varying the numbers of courses, students, classroom types, etc.,? Can you state, step-by-step, how you came up with your schedule? Can you generalize your solution to any number of courses? Computers can help you solve this problem easily and quickly!
So, What is this Course About? This course is about learning how to: Go from a problem to a solution Then from a solution to an algorithm that describes your solution Then from an algorithm to a program that a computer can run to quickly (or efficiently) solve the problem How to find solutions Problem Algorithm Program
What is an Algorithm? An algorithm is a sequence of steps (instructions) for computing an answer (output) for a problem (input) For example, we might need to sort a sequence of numbers into a nondecreasing order Here is how we can define this sorting problem: Input: A sequence of n numbers (say, a1, a2, a3, , an) Output: A reordering of the numbers (say, a3, a2, an, , a1)such that a3 <= a2 <= an <= . <= a1
What is an Algorithm? An algorithm is a sequence of steps (instructions) for computing an answer (output) for a problem (input) For example, we might need to sort a sequence of numbers into nondecreasing order Here is how we can define this sorting problem: Input (an example or instance): (14, 2, 1, 87, 36, 14, 7, 99, 5) Output: (1, 2, 5, 7, 14, 14, 36, 87, 99)
Correct Algorithms An algorithm is said to be correct if, for every input instance, it halts with the correct output We say that a correct algorithm solves the given problem An incorrect algorithm might not halt at all on some input instances, or it might halt with an incorrect answer Good algorithms compute the correct solutions, do so efficiently (no useless steps), and are easy to understand and modify
Example: How to Compute Ages? You know today s date, and your friend tells you they were born on 16/04/1998 Can you calculate their age? Of course! Please write down your algorithm on a piece of paper
Example: How to Compute Ages? The sequence of steps (i.e., algorithm) that you have written down are more or less as follows: 1. Subtract the current year from the birthday year 2. Check if the current month is greater than the birthday month a. If yes: the solution is the number computed on step 1 b. If no: check if the current month is equal to the birthday month i. If yes: check if the current day is greater than or equal to the birthday day A. If yes: the solution is the number computed on step 1 B. If no: the solution is the number computed in step 1 minus 1 ii. If no: the solution is the number computed on step 1 minus 1
Example: How to Draw a Shape? Can you write a sequence of steps for a person to draw a square? What about a house? Or, a boat? For a square: 1. Draw a straightline from left to right of 5cm length 2. Turn 90 clockwise 3. Draw a straightline from top to bottom of 5cm length 4. Turn 90 clockwise 5. Draw a straightline from right to left of 5cm length 6. Turn 90 clockwise 7. Draw a straightline from bottom to top of 5cm length
Next Class More algorithms as examples
References Notes on Principles of Computing by Giselle Reis: https://web2.qatar.cmu.edu/~mhhammou/15110- f22/references/What-is-an-Algorithm.pdf Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
