2.1 Flashcards
What is computational thinking?
- Thought processes involved in formulating a problem and expressing its solutions in such a computer can effectively carry out
What is abstraction?
- Removes unnecessary details
- To reduce the complexity when problem solving
What is decomposition?
- Breaking complex problem down into smaller more manageable parts
What are the advantages of decomposition?
- Makes the overall problem easier to solve
- Different people can work on different parts of a problem, reducing development time
- Program components can be reused
What is the algorithmic thinking approach?
- Identifying the individual steps needed to get to a solution
What are structure diagrams?
- Illustrate decomposition
- To understand a problem to code
- Lowest level nodes achieve a single task
What does an oval with flat sides represent?
Terminal (e.g. start/end)
What does a rhombus represent?
Input/Output
What does a parallelogram represent?
Decision
What does a line/arrow represent?
Program flow (leading onto one thing, sometimes yes/no label)
What does a medium rectangle in a big rectangle (with short side touching) represent?
Sub routine
What does a rectangle represent?
Process (something is initialised/calculated)
What are syntax errors?
- Break the grammatical rules of the language
- Stop it from being run
What are logic errors?
- Produce unexpected output
- Won’t stop program running
What are trace tables?
- Each line writing out the current state of each variable
- Noting down every output
- Each variable has own column
- New row every time state of variable changes
- Excellent way to track down logical errors
Describe a binary search?
- Calculate mid point
- If item is lower than mid point, repeat on left side including mp
- If item is greater than mid point, repeat on right side including mp
- Repeat until item is found/no items left to check
- Requires data set to be in order
What is a linear search?
- Starting from beginning
- Check if the item is the one to be found
- Repeat for the next item and check all items in order until item is found/no items left
- Does not require to be in order
- Very inefficient
What is a bubble sort?
- Sorts unordered list of items
- Compares each item with next and swaps when out of order
- Finishes when no more swaps need to be made
- Inefficient but easy to implement
- Time taken is related to the square of the number of items
What is a merge sort?
- Very efficient divide and conquer method for large data sets
- Repeatedly split the list in half until each list only contains only a single item
- Adjacent lists are combined together, compared, then put into the correct order into the new list
- Repeated until one continuous list is created
What is an insertion sort?
- Make the 1st item sorted list
- Start from the 2nd item and take one item at a time
- Compare the item to the items in the sorted list
- Insert in the correct position
- Repeat until there are no more items in the unsorted list