1) Fundamentals of Algorithms Flashcards
What is abstraction?
Removing uncessary details so you can focus on the important parts
What are examples of abstraction?
Maps (focus on important details such as roads and landmarks)
Money
What is decomposition?
Breaking down a complex problem into smaller more manageable sub problems
What are advantages of decomposition?
Allows large teams to each solve a part of a problem
Allows seemingly impossible problems to be solved
What do structure charts visually represent?
Breaking down a large problem into smaller parts
What do the parts of structure charts respresent?
Each box- a smaller problem to be solved
Lines- which bigger problem the box is a part of
What is algorithmic thinking?
A way of solving problems by producing algorithms
What is an algorithm?
A reusable set of instructions to solve a given problem
How are algorithms written in computing?
Pseudocode
Flow diagrams
What is pseudocode?
A way to write algorithms using code like statements
What is pseudocode intended to be?
Readable
Easy to understand
What is the purpose of pseudocode?
Planning algorithms focusing on the logic and steps rather than specific syntax
What do arrows represent in flow diagrams?
The flow of control
What do ovals represent in flow diagrams?
Start and end of a program
What do rectangles represent in flow diagrams?
A process
What do parallelograms represent in flow diagrams?
An input or ouput
What do diamonds represent in flow diagrams?
A decision
What do you need to look out for to interpret algorithms?
Identifiers
Inputs and outputs
Output messages
Comments
What are comments?
Descriptions of code
What is the easiest way to identify an algorithm?
Comments
What are identifiers?
Names of variables, constants, subroutines
What are common mistakes of algorithms? (3)
Incorrect operators
Incorrect identifiers
Missing processes
What are common missing processes?
Lines of code being forgotten can lead to issues such as infinite loops
What are 2 methods of completing an algorithm?
Trace tables
Identifying the algorithm
What does each column of a trace table represent?
Each variable
What does completing an algorithm mean?
Stating the output of an algorithm
What is a search algorithm?
A set of instructions for finding a specific item of data within a data set
What is an effective search?
A search which will always find the solution or determine if the target is not present
What is an efficient search?
A search that will find the solution quickly regardless of its location within the data set
What are 2 examples of search algorithms?
Linear search
Binary search
What is a linear search?
Searching through a data set one piece of data at a time
What are pros and cons of a linear search?
Pros- very easy to implement
Cons- slower on a long list
What is an example of a divide-and-conquer search algorithm?
Binary search
What is a binary search?
When you split a data set in two repeatedly until you find the target
What are pros and cons of a binary search?
Pros- faster than a linear search on a large dataset
Cons- data must be sorted before searching
What is a sort algorithm?
A set of instructions to arrange a dataset into a particular order
What is an efficient sorting algorithm?
One which can sort a dataset in a short time
What are 2 examples of sorting algorithms?
Bubble sort
Merge sort
What is a bubble sort?
Comparing values in twos and swapping them if they are in the wrong order
What are pros and cons of a bubble sort?
Pros- easy to implement, does not use much memory
Cons- poor for efficiency
What is a merge sort?
Splitting lists ito lists of size one and merging each pair until there is only one list
What are pros and cons of a merge sort?
Pros- very efficient algorithm
Cons- can be slower for small lists, needs additional memory
