Summary
Computational Thinking Summary
- Course
- Institution
Computational Thinking Summary
[Show more]
Seller
Follow
TR19
Content preview
Computational Thinking SummaryLecture 1: Solution strategies
How do we approach a problem?
Solution strategies
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller TR19. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.34. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
83100 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now