computer since HW
Problem Solving and Algorithms
Chapter 7
Sections 7.1, 7.2, 7.7
and Chapter 6, section 6.5
1
Goals
Improve problem solving skills
Provide a high level overview of algorithms(revisited) and pseudo-code using examples and in class exercises
2
Problem Solving and Writing Programs
Think before your write
Write you before you code
Code using a specific language best suited to solve the problem at hand
3
Problem Solving and Algorithms
Solving problems is the core of computer science
Understand how a human solves a problem to write the algorithm
Understand how to translate this algorithm into something a computer can do
-Use tools such as pseudo-code
Write the specific syntax (code required by a language) to get the job done.
4
Problem Solving
Solve:
555 1001 2
5
Problem Solving: How to Solve It: A New Aspect of Mathematical Method by George Polya
1. Problem Definition
a. Write a detailed, concise, accurate description of the problem
-understand the goal and any constraints
* deliverable: problem definition statement
2. Devise a Plan to break the problem down into smaller, more manageable tasks
a. ask questions, consult resources
b. brainstorm with your team
c. refer back to the problem definition to stay on track
* deliverable: step by step solution to problem
6
Problem Solving: How to Solve It: A New Aspect of Mathematical Method by George Polya, cont.
3. Execute the Plan
a. check each step
b. can I prove that each step is correct and complete?
- test it, use test data
4. Evaluate your Solution
a. does it solve the problem
b. can it be done more efficiently
c. does it cause any other problems
DOCUMENT/SAVE YOUR WORK
7
When coding in a specific language, both logic and syntax must be correct
Syntax
Must conform to syntax rules of language
Variable names, data types
Termination characters
Selection and Loop formation
Logic
Give instructions in specific sequence
Do not omit important steps
Do not add extraneous steps
8
Algorithm, the first step
Algorithm
A set of unambiguous, ordered step by step instructions for solving a problem in a finite amount of time
some are learned – ex. solving math problems
some we figure out ourselves – ex. how to get to the university and back
others require written instructions – ex. recipe, assembly of Ikea furniture
Steps include:
Sequence- one task performed after the other
Selection –a decision (selection ) is made between 2 alternative choices such as if this then do this
Iteration- repetitive action such as repeat x times or repeat until a certain condition is met
9
Algorithm/Flowchart
10
5 minute table exercise
Write an algorithm to list the state or country where each of you were born
Do not include duplicates
Use 1 line for each state/country
Be prepared to share your problem solving process
11
Common Planning Tools
Pseudocode – sequentially listed, single lines of English-like statements to describe the steps to solve a software problem
Uses key words to indicate a common operation
This reflects the program logic not the syntax of a specific language
Closer to code than algorithm, but not the code
Flowchart - a pictorial representation of the steps to solve a problem
Uses standard symbols to indicate key operations (reference only)
12
3 major operations
Input (text, numbers, images, sound)
Process (calculations, formula, logic)
Output (results)
Problem: Write a program to double a given integer. Display the answer. Use pseudocode to outline the steps to solve the problem.
INPUT myNumber
PROCESS myAnswer = myNumber * 2
OUTPUT myAnswer
| Input | Process | Output |
| GET | CALCULATE | WRITE |
| READ | SET |
Pseudocode for Number Doubling
Variables – named memory locations for the purpose of storing values, the values stored may vary
Synonyms
13
Need to compute the total price to carpet any given room
Inputs?
Process (Formula)?
Output?
Pseudo-code:
-no grammar rules
-use key words to make description easier and more efficient
-no punctuation
-not case sensitive, but case may be used for readability
-language neutral
-one statement/line
-may use conditional statements like If Then Else and Iteration for repetitive tasks
This is sequential
14
Pseudocode example, Sequential
GET Length of room
GET Width of room
GET Price of carpet in square yards
CALCULATE Area using Area = Length x Width
CALCULATE totalPrice using totalPrice=Area x Price
WRITE totalPrice
Variables – named memory locations for the purpose of storing values, the values stored in the variables may vary
15
Pseudocode Example, Selection
Selection – direction of the program is dictated by choice or by comparing values
Give discount of 10 % if customer spends over $10,000.00
IF totalPrice > 10000 THEN
Calculate totalPrice *.9
ELSE
Calculate totalPrice
END
Where is this pseudocode inserted?
16
Write a Problem Description to solve the 555 1001 2 problem. Note that this is your table’s interpretation of how to solve this problem.
Write the pseudocode to solve the problem using your problem definition.
Deliverable: pseudocode on whiteboard
5 minute In Class Table Activity
17
Iteration Using the Number Doubling example
Iteration is a process where a set of instructions are repeated in a sequence a specified number of times or until a condition is met. When the first set of instructions is executed again, it is called an iteration or loop, use for repetitive processes
GET aNumber
while aNumber < 1000 Answer= aNumber * 2 PRINT aNumber
GET aNumber
end
aNumber < 1000 is the condition test (after while) loop is run only if the condition is true
loop
18
Possible Assignment
Write pseudocode for a particular case of your choosing. Refer to previous examples
Include a minimum of :
2 inputs
1 computation
1 selection structure (if then else)
1 output
Write the case problem description in English, Write the solution using pseudocode.
Upload HWPCinitials.docx to Pilot.
PRINT 1 copy WITHOUT the solution.
PRINT 1 copy WITH the solution.
BRING BOTH COPIES TO CLASS on due date
In Class, at your table, choose the “best” problem to pass to the next table.
Pass problem on to next table (1->2, etc)
Then each table reads problem and creates a psuedo-code if-then-else statement to satisfy problem.
If problem description is NOT CLEAR, it is sent back to originators
5 min
19
Logical Comparison Operators
When writing pseudocode and actual code, will need to use comparison operators
| Operator | Name of operator |
| < | less than |
| <= | less than or equal to |
| = | equal to |
| != | not equal to |
| >= | greater than or equal to |
| > | greater than |
20
Boolean Operators
| Operator | Explanation | Example |
| AND | AND returns TRUE if both operands are true and FALSE otherwise | |
| OR | OR returns TRUE if either operand is true and FALSE otherwise | |
| NOT | NOT returns TRUE if its operand is false and FALSE if its operand is true |
* operand specifies data that is to be operated on or manipulated
21
Must remember how to use truth tables
| 0 | 1 | |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
A value of 1 represents True
A value of 0 represents False
Both conditions must evaluate to true to return a true
AND
22
OR Operation- Truth Table
| 0 | 1 | |
| 0 | 0 | 1 |
| b | 1 | 1 |
A value of 1 represents True
A value of 0 represents False
If either condition evaluates to true , it returns a true
23
NOT Operator
| 0 | 1 |
| 1 | 0 |
A value of 1 represents True
A value of 0 represents False
A false value becomes true and a true value become false
24
Order of Operations
If there are multiple operations, the order of evaluation is:
1. The NOT (i.e. ! ) operator is applied First
2. Then the AND (i.e. && ) operator
3. And finally the OR (i.e.|| ) operator
Use parentheses to denote (i.e. force) the order of evaluation
Answer the questions below, based on the following expressions:
chocolate OR vanilla AND nuts
If you place the above order, will you give nuts on you sundae?
(chocolate OR vanilla) AND nuts
With the above order, will you always get nuts on your sundae?
25
NOT operator example and precedence
NOT
Unary operator-it takes a single operand and its outcome is the opposite of its operand
Example:
We are looking to eliminate teenagers from our study
Will this expression accomplish that?
! age > 12 AND age < 20
26
In Class Work-write your answers by table (7 minutes max)
Write an expression to: (use a Boolean operator)
1. Check that score is less than 0 or greater than 100, use parenthesis to show the order operations
2. Check that score is between 75 and 100 inclusive, use parenthesis to show the order operations
Place the parenthesis around the expression to show the default order of operations
3. X>1 AND x<100 OR x=300
4. What are the values of x?
27
Selection Statement If-Then-Else
IF condition is true
do this
ELSE (meaning the condition is FALSE)
do something else or do nothing
May Use with Multiple Conditions
IF condition is True, do this
ELSE IF this condition is True, do this
ELSE IF …
ELSE do this
28
Selection example
The age determines which statements are executed.
INPUT age
IF ( age < 12 )
Write "Pay children's rate"
Write "You get a free box of popcorn"
ELSE IF ( age < 65 )
Write "Pay regular rate"
ELSE
Write "Pay senior citizens rate"
29
Problem of finding the smallest of three given numbers using a nested If statement
IF (a < b) AND (a < c)
Result = a
ELSE IF (b < a) AND (b < c)
Result = b
ELSE
Result = c
30
Following Pseudo-code
Write "How many pairs of values are to be entered?“
Read numberOfPairs
Set numberRead to 0
WHILE (numberRead < numberOfPairs)
Write "Enter two values separated by a blank; press return"
Read number1
Read number2
IF(number1 < number2)
Print number1 + " " + number2 the + means next to(not add), “ “ is a blank
ELSE
Print number2 + " " number1
Increment numberRead increment means add 1
Problem: Read in x pair of positive numbers as specified by the user, then print each pair in numerical order. Output each pair of numbers.
Use for next slide
31
Walk Through-With your table, write the data values into the orange boxes using the pseudo-code on the previous page. Use your nearby whiteboard. Also write the output at the bottom.
Data Fill in values during each iteration
3
55 70
2 1
33 33
numberOfPairs
| numberRead | number1 | number2 |
What is the output?
32
Looping Statements Count-Controlled
Set sum to 0
Set count to 0
Set number to 1
Set limit to 3
While (count < limit)
Read number
Set sum to sum + number
Write "Sum is " + sum
Increment count
Increment number
Count keeps track of the number of times a task is completed
• initially the task hasn’t been done, and count is 0
• each time the task is completed, count increases by 1
Count Controlled - a loop that terminates when a counter reaches some limiting value
33
Event Controlled Loop Using Number Doubling Example
GET aNumber
while aNumber < 1000
Answer = aNumber * 2
Print aNumber
GET aNumber
end
Note the Boolean expression at the beginning of the loop (after while), looping continues while the condition evaluates to True
34
Case 1 Given the problem description, decompose the problem to list the inputs required, any formulas required and the final output. Then write the pseudo-code. Desk check your work. Turn in the pseudo-code only.
Employees earn a base salary and may earn a bonus if they sell more than$50,000 worth of a product during 1 month.
If the employee sells more than $50,000 worth of the product each month, they earn their salary plus a bonus of $1,000.
If they sell less than $50,000 worth of the product, no bonus is earned, but they still earn their salary.
Give the total amount earned.
35
Case 2 Given the problem description, decompose the problem to list the inputs required, any formulas required and the final output. Then write the pseudo-code. Desk check your work. Turn in the pseudo-code only.
Create a shipping charge program that will calculate the shipping charge for an item based on its weight.
If the item weighs less than 16 ounces, the shipping charge is a flat rate of 12.95. If the item weighs over 16 ounces, the shipping charge is the weight of the item minus 16 ounces multiplied by 30 % plus the flat rate.
Determine the charge, then output it.
36