Topic 1 - Problem Solving
No description yet. This curated deck is ready for daily study.
Card preview (23)
What is an algorithm?
A set of instructions that perform a specific task.
What are algorithms used for?
Calculations, data processing and automated reasoning.
What are the 5 different representations of algorithms?
Flowcharts, Pseudocode, Structured English, Written descriptions and program code.
What are flowcharts?
Diagrams consisting of geometric shapes that help visualise a problem.
What is Pseudocode?
An informal description of a program or algorithm.
What is Structured English?
Similar to Pseudocode except symbols are often written out (e.g. ADD instead of +)
What is the purpose of algorithms?
To visualise the logical steps of a task.
What is a Quick Sort?
A quick and efficient algorithm used to put data into a particular order (often ascending/descending or rearranging letters of the alphabet)
What are the 4 steps to execute a Quick Sort algorithm?
• Select a pivot from the list • Write down all the items less than and bigger than the pivot, keeping the order, in a sub-list. • Write down the remaining items, keeping the order, in a sub-list. • Repeat steps 1-3 until all items are chosen as a pivot.
What is a Bubble Sort?
An algorithm that works by repeatedly stepping through a list, comparing each item with the following item, swapping them if necessary.
What is a Selection Sort?
An algorithm that splits the input list into two imaginary sub-lists: a sorted list and an unsorted list.
What are the steps to execute a Selection Sort algorithm?
• Swap the smallest element in the list with the first element in the list. • Repeat the process with the nth smallest element and replace it with the element in the nth position in the list. • Continue until the list is sorted.
What is a search algorithm?
Finds a specific item within a larger group.
How does a Linear Search algorithm work?
Checks every single item in the list until you find your search item, or fail to find it at all.
Why is a Linear Search algorithm not very efficient?
The time it takes is related to how long and where in the list the item is.
How does a Binary Search algorithm work?
Continually divides your list by two (hence BINARY), eliminating the part of the list that cannot have your item in it.
How does a Breadth First Search (BFS) work?
Works by visiting nodes closest to the starting point first.
How does a Depth First Search (DFS) work?
Works by visiting nodes as far into the graph as possible before backtracking to visit the previously unvisited nodes.
How is algorithmic efficiency measured?
In terms of time (how long it takes to run) and space (how much memory is required).
What are the factors that affect algorithmic efficiency?
• How well designed the data structures are • The software and hardware • The programming language and translator used
What is decomposition?
Breaking a problem down into smaller, more manageable sub-programs.
What are two advantages of decomposition?
• Different people can work on different sub-problems 2. Able to compute the solution in parallel
What are two disadvantages of decomposition?
• The problem must be understood well. 2. It can be difficult to combine the solutions