2019-03-19
1
Lecture 8-2 Introduction to Algorithms – Problem-solving techniques
Objectives –algorithm
After completing this unit, you should be able to
Understand basic problem-solving techniques
Understand the top-down design process in the algorithm
development
Apply top-down design to develop simple algorithms
Understand the test cases and develop test cases
2019-03-19 2
Problem-solving steps
Four steps to solve the problems (George Polya) 1. understand the problem (problem statement)
• You should spend time on studying the problem to understand what is the input, and expected output
• Develop the test cases: a set of input representatives and their output 2. devise a plan (algorithm development)
3. carry out your plan (language implementation)
4. examine the solution (test results and analysis)
• Use the test cases to test your solution
• If solution is not correct, you need to repeat the steps
2019-03-19
3
Problem-solving technique
1. Try to solve the problem with small problem sizes and generalize the solution to any problem size
2. Top-down design approach
this is a commonly used approach in problem-solving:
Refine the algorithm steps successively so that the all steps are simple and do-able
1) Break a problem into smaller sub-problems. The sub-problems may be further divided into sub- sub-problems
2) Solve the smaller sub-problems
3) Combine the solutions to get the solution
3. Use flow chart or/and pseudo-code to represent the algorithm
2019-03-19 4
Top-down design video
• Watch the video clip about top-down design https://www.youtube.com/watch?v=QsKkG9gWxF4 (5min)
2019-03-19
5
Example 1: course grading
• In a course exam, there are 4 questions and each question has 25 marks (or points). If a student earns a total marks greater than 50, the student is passed. Develop an algorithm to determine if a student is passing or failing in the exam.
2019-03-19
6
•
1)
Example 1 course grading
We follow the steps in solution solving: understand the problem
we need to find what are input and what are expected output input: marks earned in 4 questions.
output: If total of marks is greater than 50, output “pass”, otherwise “fail”
test cases: 15, 20, 18, 13. total marks: 66, “pass” 10, 15, 8, 17. total marks: 50, “fail” 10, 10, 20, 8. total marks: 48, “fail”
2019-03-19
7
•
2)
Example 1 course grading
We follow the steps in solution solving: Devise a plan (develop an algorithm)
we apply top-down design approach
step 1: get input
step 2: compute total marks
step 3: if total marks greater than 50 then
output “pass” else
output “fail”
2019-03-19
8
•
2)
Example 1 course grading
We follow the steps in solution solving: Devise a plan (develop an algorithm)
we apply top-down design approach
step 1: get input
step 2: compute total marks
step 3: if total marks greater than 50 then
output “pass” else
output “fail” Refine step1:
step 1.1 get input marks1 from question 1 step 1.2 get input marks2 from question 2 step 1.3 get input marks3 from question 3 step 1.4 get input marks4 from question 4
2019-03-19
9
•
2)
Example 1 course grading
We follow the steps in solution solving: Devise a plan (develop an algorithm)
we apply top-down design approach
step 1: get input
step 2: compute total marks
step 3: if total marks greater than 50 then
output “pass” else
output “fail” Refine step2:
step 2.1 set total to the sum of mark1, mark2, mark3 and mark4
Step 3 is already clear and simple
2019-03-19
10
Example 1
2) Devise a plan (develop an algorithm) Computer algorithm
START
IN mark1
IN mark2
IN mark3
IN mark4
total = mark1 + mark2 + mark3 + mark4 IF total > 50 THEN
OUT “pass” ELSE
OUT “fail” ENDIF
STOP
Note: we use a single input for 4 marks in flowchart
course grading
START
IN mark1,mark2, mark3,mark4
total= mark1+mark2+mark3+ mark4
N
OUT “fail”
total> 50
Y
OUT “pass”
2019-03-19
11
STOP
Example 1 course grading
3) 4)
For these cases, we follow the flowchart
the output are correct
15, 20, 18, 13. total marks: 66, “pass” (green line) 10, 15, 8, 17. total marks: 50, “fail” (yellow line) 10, 10, 20, 8. total marks: 48, “fail” (red line)
START
carry out your plan
we do not implement it in C at the moment
IN mark1,mark2, mark3,mark4
Examine the solution
apply the test cases to check if solution is right total= mark1+mark2+mark3+ mark4
N
OUT “fail”
total> 50
Y
OUT “pass”
2019-03-19
12
STOP
A complete example
• You can find a complete more complicated example – How to develop a solution in C to print a pyramid
2019-03-19 13
Summary
• Algorithm is a fundamental aspect in computer science
• Pseudo-code and flow chart are commonly used to
represent the algorithms
• Top-down design approach makes it easier to solve a problem
• 4 steps are commonly used in the solution development
2019-03-19 14