Topic 1: Computational thinking Flashcards
Decomposition
breaking down problems and solutions into smaller parts
Abstraction
the process of removing or hiding unnecessary details (so you can focus on the important poins)
Algorithms
a step-by-step procedure for solving a problem or carrying out a task.
Reason for decomposing problems
to reduce the size of the problem
Subprogram
block of code that performs a specific task
Pre-existing subprograms in python
- print()
- len()
- random.randint()
- math.floor()
Subprograms are useful to:
- break down a complex program into less complicated parts
- make program logic clearer
- make it easier to maintain code
- code can be used as many times as needed, avoiding repetition
- be stored in libraries and reuse them in other programs
- enable a team of programmers to work together at the same time
2 ways subprograms speeds up program development
1) the programmer can use pre-existing subprograms so that they can use them to perform common tasks
2) a group of programmers can work in different subprograms because different subprograms can be allocated to different programmers.
Algorithms : flowcharts
Be able to draw flowcharts
Algorithms: selection
used to choose between two or more options
Selection in flowcharts
Diamond symbol; has 2 output arrows, one for yes and the other for no.
Selection in python
If… elif… else… statement
Algorithms : repetition
the process of repeating a set of instructions until there is a desired outcome
2 types of repetition
Condition-controlled repetition
Count-controlled repetition
Condition-controlled repetition
when the number of times a loop is executed is not known before the loop is started
Count-controlled repetition
when the number of times a loop is executed is known before the loop is started
Condition controlled in python
while statement
Count- controlled in python
for…in range() statement
Reason why loops do not need dedicated symbol in flowcharts
In a selection symbol (rhombus), you can have an arrow pointing at the begining of the choice, therefore that creates autmatically a loop
Reason why loops do not need dedicated symbol in flowcharts
In a selection symbol (Diamond), you can have an arrow pointing at the begining of the choice, therefore that creates autmatically a loop
Algorithms: iteration
Repeating a set of instructions for every item in a data list.
2 features in a flowchart that indicate iteration is used
- A data list
- A backward pointing arrow to a selection symbol
Arrays
data structure that can store multiple elements from the SAME DATA TYPE
2D arrays
[[…],[…],[…]]
Record
- a collection of data objects
- can be of DIFFERENT DATA TYPES
How are elements called in a record
a field
Arithmetic operators
used to perform calculations
Relational operators
used to compare different items of data
Examples of arithmetic operators:
+, -, *, /, %, // (returns integer part of division), **(exponentiation powers of)
Examples of relational operators:
==, !=, <, <=, >, >=
Difference between (%) and (//)
%(Modulus) returns the remainder after the division, whereas //(integer division) returns the integer part after division
AND operator
Overall statement is true if ALL individual statements are true
OR operator
Overall statement is true if ANY OF THE individual statements are true
NOT operator
used to reverse the logical state
TRACE TABLES
Page 12,13 R.Guide
Types of errors that can be found in algorithms
Syntax error
Runtime error
Logic error
Logic error
- Hardest to detect
- will produce an incorrect or unexpected result
Linear search
it is sequential starting at the begining and moves through item by item
Problem of linear search
Uses raw computing power
It is not an efficient method
- search starts at the begining
- until item found
- or reaches the end
Describe in words an algorithm for carrying out a linear search (6 marks)
1) If the length of list is 0, stop
2) Start at the beginning of the list.
3) Compare the list item with the search criterion.
4) If they are the same, then stop.
5) If they are not the same, then move to the next item.
6) Repeat steps 3 to 5 until the end of the list is reached
Binary search
compares the search item with the median item in a list, repeatedly splitting the list in half until the item is found or there are no more items left to search
Describe the stages of applying binary search to find 17:
3,5,9,14,17,21,27,31,35,37,39,40,42
Step 1: The median is 27 but is higher than search item
Step 2: The sub-list to the left is used: 3,5,9,14,17,21
Step 3: The median is 9 but is too low. The sub-list 14,17,21 is used.
Step 4: The median is 17 which is the search item.
Binary search requirement
needs to be sorted: alphabetically or numerically
Bubble sort ———
Page 17 in revision guide
Merge sort
is an algorithm that breaks a list into its components and then builds it up again IN the correct ORDER
Describe how data is sorted into ascending order using the merge sort algorithm
The list is divided into two repeatedly
- until each list has only one item.
The lists are then progressively merged
- with the items in ascending order.
Merge sort vs Bubble sort
For large numbers of items, a merge sort is far more efficient than a bubble sort as the problem is broken down into smaller and smaller problems, which are easier to solve
Choose Linear search when:
- unsorted list
- a short list
- a list that is not going to be searched very often
Choose Binary search when:
- a long list
- a list that will be searched often
Advantages of linear search:
- Linear search algorithms are simple
Advantages of Binary search:
- Divide and conquer (breaks the list into smaller lists and performs the same operation on each).
- Binary searches execute quickly
Disadvantages of linear search:
- Brute force (tries out every possibility until a solution is found or all possibilities are exhausted
Disadvantages of binary search:
- Initial list must be sorted
- Binary search algorithms are complex and user recursion (that is, where a function calls itself).
Choose bubble sort for:
- a list with a smaller number of items
Choose Merge sort for:
- a long list
Advantages of bubble sort:
- A simple algorithm to code
- No extra storage used to make copies of data.
Advantages of merge sort:
- Divide and conquer approach
- Longer lists add only a little bit more execution time
Disadvantages of bubble sort
- brute force
- longer lists use much more time to sort
Disadvantages of merge sort:
- uses additional memory for copies of lists.
- The splitting phase must happen, even for very short lists
- Complex algorithm, usually involving recursion.
Trace tables vs Truth tables
Truth tables are used for AND, OR, NOT whereas trace tables are used for showing how a program works.
