1 Fundamentals Of Algorithms Flashcards
What is Abstraction?
Abstraction is the technique that simplifies a problem by removing unnecessary details so you can focus on the important parts that are relevant to the problem
What are two examples of Abstraction?
Maps and Money
How are Maps an example of Abstraction?
Maps are an example of Abstraction as they leave out irrelevant information and only leave key parts such as roads and landmarks
How is money an example of Abstraction?
Money is a type of Abstraction as it is just an abstract concept. Money has no value but represents the value of goods and services.
What is decomposition?
Decomposition is the breaking down of a complex problem into smaller, more manageable, sub-problems. Each sub-problem can be solved individually, before the sub-solutions are combined to solve the original problem
What are the advantages of Decomposition?
Decomposition allows large teams to work on a part of the problem and work on it.
Decomposition allows extremely hard problems to be solved easily by splitting it up into simple tasks
What are Hierarchy or Structure Charts?
Hierarchy or Structure Charts are used to visually represent breaking a large problem down into the smaller parts that make it up.
Each box represents a smaller problem to be solved.
Lines show which bigger problem the box is a part of.
What is Algorithmic thinking?
Algorithmic thinking is the way of solving problems by producing algorithms.
What is an algorithm?
An algorithm is a reusable set of instructions that solve a given problem
How do we represent algorithms in computing?
We mainly represent algorithms as Pseudocode or Flow diagrams
What is Pseudocode?
Pseudocode is a way to write out algorithms using code-like statements. It is intended to be readable and easy to understand.
What is the purpose of Pseudocode?
Pseudocode is used to plan algorithms, focusing on logic and steps rather than language specific syntax
Can Pseudocode be run on a computer?
No as it isn’t an actual programming language
What are flow diagrams?
Flow diagrams are used to visually represent the steps that make up an algorithm
What do the arrows in a flow diagram represent?
Arrows in a flow diagram represent the flow of control, or what to execute next.
What is an oval used for in a flow diagram?
An oval is used for the start and end of a process
What is a rectangle used for in a flow diagram?
A rectangle is used to represent a process
What is a parallelogram used for in a flow diagram?
A parallelogram is used to represent an input or an output
What is a diamond used for in a flow diagram?
A diamond is used to represent a decision.
How many arrows comes out of a decision?
Two
What are some tips for interpreting algorithms?
- Look out for Identifiers
- Identify Inputs and Outputs
- Examine Output Messages
- Look for comments
What are identifiers?
Identifiers are the names of constants, variables and subroutines. They give a strong clue about the purpose of an algorithm
How can you use output messages to help interpret algorithms?
Output messages often format the result of an algorithm in a human readable way.
How can you use comments to interpret algorithms?
Comments are descriptions of the code. Comments will often state the purpose of a given algorithm. They are often the clearest method to identify an algorithm.
What are some common mistakes that lead to the algorithm being incorrect?
- Incorrect operators
- Incorrect identifiers
- Missing Processes
What can be identifiers?
- Variable names
- Constant names
- Subroutine names
What could happen if there are missing processes?
If there are missing lines of code, there could be issues such as infinite loops where the code never ends
What is a trace table?
A trace table is a technique used to test algorithms or computer programs for logic errors that occur while the algorithm or program executes. The trace table simulates the flow of execution
Why should you use a trace table to complete an algorithm?
You can use the trace table to keep track of the value of each variable and carefully follow through the code till the end.
What does completing the algorithm ask you to do?
Completing the algorithm means you should state the output of the algorithm
What is the most common operator mistake?
> compared to >=
How do you draw a trace table?
First, you draw a table with one column per variable.
Then, you go through the algorithm line by line, updating values of the variables.
Finally, you read off the output from the table at the end of the algorithm
What is searching?
Searching is finding a certain value in a set of other values
What is search algorithm?
A search algorithm is a set of instructions for finding a specific item of data within a data set.
Why should computers be efficient in finding data?
Computer systems can store and process billions of pieces of data so it is vital that computers can find the information they need efficiently.
What is effective searching?
An effective search is one which will always either find the solution or determine that the target data is not present.
What is an efficient search?
An efficient search will find the solution quickly regardless of the location within the data set.
What are the two common search algorithms?
The two common search algorithms are Linear search and Binary search
How does a linear search work?
A linear search would work from one end to the other in a data set checking each piece of data to find the solution.
What is linear search in pseudocode?
for item in dataset . if item = target then . .return true . endif endfor return false
What are the pros and cons of linear searching?
Pro: Very easy to implement
Con: Slow on a long list
How does a binary search work?
You find the middle of then dataset. If the middle value is greater than the target then, repeat it on the first half of the dataset.
If the middle value is lesser than the target, then repeat on the second half of the dataset.
Keep repeating, until the middle value is the target. If it is the middle value, then we have found the target.
If not, stop repeating once the size of our dataset is zero.
What is binary search in pseudocode?
dataset = [.....] min = 0; max = len(dataset); while (min target then . . max = midpt - 1 . else if dataset[midpt] < target then . . min = midpt + 1 . endif endwhile return False
What are the pros and cons of binary search?
Pro: Faster than linear search on a large dataset.
Con: Dataset must be sorted before starting.
What are Sorting Algorithms?
Sorting algorithms are a set of instructions to arrange a dataset into a particular order.
What are the two Sorting algorithms required to learn?
Bubble sort and Merge Sort
What is an efficient sort?
An efficient sort algorithm is one which can sort a dataset in a short time.
How does bubble sorting work?
Compare the first two items of the dataset:
If they are in the wrong order, swap them.
Continue for the rest of the cards in the deck.
Repeat the whole process, until a pass with no swaps happens.
What is a bubble sort in pseudocode?
repeat .swapped = False .for i = 1 to n-1 . if A[i - 1] > A[i] then . .swap(A[i -1],A[i]) . .swapped = True . endif .endfor until NOT swapped
What are the pros and cons of bubble sort?
Pros: Easy to implement Does not use much memory Cons: Poor for efficiency
How does merge sort work?
Split the lists into lists of size one.
Merge each pair of sublists by comparing the first value of each list and putting the smaller value into the new list first.
Continue merging until there is only one list.
What are the Pros and Cons of merge sort?
Pros: A very efficient algorithm Cons: Can be slower for small lists Needs additional memory
When is it a bad time to use merge sort?
On a small list which is unlikely to grow
