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
