fundamentals of algorithms Flashcards
understand and explain the term algorithm
an algorithm is a reusable set of instructions that solve a given problem
a computer program is an implementation of an algorithm
understand and explain the term decomposition
decomposition means breaking a problem into a number of sub problems, so that each sub problem accomplishes an identifiable task, which might itself be further subdivided
understand and explain the term abstraction
abstraction is the process of removing unnecessary detail from a problem
advantage and disadvantage of linear search algorithms
-Will perform fast searches of small to medium lists..
-The list does not need to sorted. Unlike a binary search, linear searching does not require an ordered list.
-Not affected by insertions and deletions. As the linear search does not require the list to be sorted, additional elements can be added and deleted. As other searching algorithms may have to reorder the list after insertions or deletions, this may sometimes mean a linear search will be more efficient
Slow searching of large lists. This speed disadvantage is why other search methods have been developed.
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 our 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
advantages of decomposition
decomposition allows large teams to work on a part of the problem and work on it
allows extremely hard problems to be solved easily by splitting it up into simple tasks
how do we represents algorithms in computing
we mainly represent algorithms as pseudocode or flow diagrams
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
the 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 come out of a decision
2
what are some tips to interpret 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 value 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
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
is 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 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
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 the values of 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’s 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
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
+ very easy to implement
- slow on a long list
how does a binary search work
you find the middle of the data set
if the middle value is greater than the target then repeat it on the first half of the data set
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 target we have found the target
if not, stop repeating once the size of our data set is 0
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
+ faster than linear search on a large data set
- dataset must b sorted before starting
what are sorting algorithms
sorting algorithms are a set of instructions to arrange a data set 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 data set in a short time
how does bubble sorting work
compare the first two items of the dataset
if they are wrong, 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
+ easy to implement
+does not use much memory
- poor for efficiency
how does merge sort work
split the lists into lists of size one
merge each pair of sublists by comparing the 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
+ a very efficient algorithm
- 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
