1. Try something (guess and check)
2. Go through all the possibilities
3. Divide the problem into several sub problems or steps
4. Use of formulas/equations
5. Discover a structure or pattern
6. Make a model
7. Brute force
8. Divide-and-conquer (D&C)
Try something (guess and check)
• Just try something to solve the problem and afterwards you check your answer.
- e.g., “How many coins do you need to get 5.20 Euro if you have 3 times as many 20
cent coins as 5 cent coins?”.
Go through all the possibilities
• Only suitable if the number of possibilities is limited.
- e.g., “How can measure exactly 15 minutes with these two hourglasses (7 minutes
and 11 minutes)?”. > no waste of time
Divide the problem into several sub problems or steps
• Sometimes a problem looks complex, but dividing it into steps it will make it easy.
• If you combine a few of these approaches the problem will be clear and solvable:
- Simplify
- Divide
- Back reasoning
- Exclude
• e.g., “Is the number Alex had in mind odd or even?”.
• In the last step, you should check General reasoning: “if x = even, then result is odd” and
“if x = odd, then the result is even”.
1
,Computational Thinking Summary
Use of formulas/equations
• Use X and/or Y
• Faster and more efficient than “Try something (guess and check)”
• e.g., “How many coins do you have?”
• Sequences and series:
&
Discover a structure or pattern
• Note that there is a pattern that repeats always after a certain amount of steps
• e.g., “What is the last digit of 777?”
Make a model
• Translate the text into a model (schematic representation)
• e.g., “Determine how far the slab in total has moved forward, if the rollers have made exactly
one rotation”
Brute force
• A simple approach to solve problems
• Uses computing power to solve problems with a computer without the use of algorithms or
heuristics to speed up the calculation
• Is used if no algorithm is know that is faster or more efficient which leads to a solution
• Just do it!
• Linear search
• Bubble sort
Divide-and-conquer (D&C)
• A general technique to design algorithms (design strategy)
• Only suited for parallel computations in which each subproblem can be solved simultaneously
by its own processor
• Binary search
• Merge sort
• Quick sort
1. Divide the problem into a number of small sub-problems of the same type and ideally
about the same size (divide)
2. Solve each sub-problem (recursively) (conquer)
3. Combine all these solutions into a solution to the original problem (combine)
2
, Computational Thinking Summary
Lecture 2: From algorithm to flowchart, recursion, pseudocode
From algorithm to flowchart
What is a flowchart?
• A graphical representation (diagram/chart) of an algorithm or process
• Consists of
- Data (shown in different plains)
- Arrows (connect the plains)
• Symbols of a flowchart
Why?
• An algorithm description (spoken language or pseudocode) can not be entered directly into a
computer > the algorithm has to be converted into a computer program
• Processes or programs
- To analyse
- To design
- To maintain
- To document
• Important in problem analysis and in finding an efficient solution
Recursion
• Recursion is a technique where a method or function calls itself
• Not a program statement, but just a technique
• Factorials
- Factorials call themselves until 0! is reached
- The function F! (x), stops itself to call in F! (0) = 1 and the value is returned to the
calling function
- In general F! (N) = N * (N – 1)
3
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper TR19. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €6,65. Je zit daarna nergens aan vast.