1 - Fundamentals of Algorithms Flashcards
Not to screw up
What is an algorithm
A series of instructions that describes how to solve a specific problem or perform a specific task
What is decomposition
Breaking down a problem down into smaller ‘sub-problems’
Advantages of decomposition
- Smaller problems are easier to solve than larger problems
- Each ‘sub-problem’ can be developed separately, making planning and working to a timescale easier
- ‘Sub-problems’ are easier to distribute among a team than one large problem
Inputs, Initialisation, processing, outputs
Inputs - what data enters the system and how?
Initialisation - What variables are needed and what are their initial values?
Processing - What processes (calculations, sorts, etc.) are carried out on the inputs?
Outputs - What data leaves the system and in what format?
Abstraction
Hiding the layers of complexity within a system, in order to focus on one specific layer of complexity
Common methods of defining algorithms
- Pseudocode
- Flowcharts
Pseudocode
A cross between English and a generic-looking programming language. While pseudocode would not compile, a competent programmer could convert it to code that would compile
Flow Chart
A means of defining an algorithm using shapes and arrows. Within each shape, an action is taking place or a decision is being made. The direction of arrows indicates which action or decision comes next
Flow charts are easier understood than pseudocode to someone who is not a programmer
Oval
This is the terminator. One is used to mark the start and another is used to mark the end. They are not used elsewhere
Arrow
Shows which instruction should take place next
Diamond
A decision. It asks a question and each arrow leaving must have a possible answer
Square/ rectangle
This is a process. Each one contains a single instruction. so complex tasks usually incorporate several processes
Parallelogram
This shape represents data that is entered into the system or output from it. Basically input or output
Sequence
A sequence is when instructions in an algorithm each need to be executed only once, and in the order in which they are written
Selection
Selection is when one sequence of instructions or another, but not both, is executed. The sequence that is executed will depend on what happened in earlier instructions.
Iteration
Iteration takes place when one or more instructions are executed more than once. Iteration is also known as repetition. Iteration is taking place when a program code (or pseudocode) contains the words LOOP, FOR, WHILE, or REPEAT.
Trace tables
Interpreting an algorithm works best when you do so one line at a time, as a computer would. A trace table can and should be used to keep track of variables that change throughout the algorithm.
Efficiency
A measure to compare two different algorithms that solve the same problem. A more efficient algorithm is a better choice. Efficiency can be measured in a number of different ways, the main type is TIME efficiency. An algorithm that can be executed in 20 instructions is more efficient than one that takes 30 instructions
Searching
Determining whether a specific piece of data exists within a data structure. If it does exist, a search algorithm will reveal its location
Linear search
A search algorithm that begins at one end of a data structure, checking each data item in turn until the required item is found, or the end of the structure is reached
Binary search
A search algorithm that begins in the middle of a data structure, eliminating half of the remaining data with each pass. Binary searches are only appropriate when performed upon a sorted data structure. (Meaning that data is already ordered)
Comparing searches
A binary search is more efficient that a linear search since it will, on average, find a search term more quickly than a linear search. However, binary searches do not work on unsorted data, so efficiency is not the only consideration
Sorting
Putting data into order, whether that be numerical order, alphabetical order or chronological order, ascending (A-Z) or descending (Z-A)
Bubble sort
Passes through the data, and swaps data that are not ascending
Keeps passing through until one lass pass proves that the data is sorted
A bubble sort only ends when a complete pass has yielded no changes or when n-1 (n being the number of elements to be sorted) passes have taken place
Merge sort
Unsorted data is split into individual units
Then paired with the smaller number first
Then merged into 4’s in ascending order
Keeps merging until the whole data set is merged in ascending order
Bubble sort vs Merge sort
Bubble sort:
Adv
- Straightforward to program
- Does not use much extra memory space while the sort is in progress
Dis
- Can take a very long time with a large set of data to sort
Merge sort Adv - More efficient in terms of time Dis - More complex to program - Requires lots of memory space as it runs
