COMPSCI4039
Week 10 – Algorithms
What is an algorithm?
Copyright By PowCoder代写 加微信 powcoder
• In a nutshell, an algorithm is a series of instructions.
• They are to be followed exactly in order to achieve something.
• You and I use algorithms in our daily lives (even if we aren’t aware)
• A recipe is a series of instructions to prepare food.
• This is an algorithm.
• Why? Because it is a series of instructions that you follow to achieve a result, something (hopefully) delicious.
• Even something mundane like making coffee… is an algorithm.
• Why? Because you follow a series of instructions to achieve a result. Coffee.
What is an algorithm?
• When we think about algorithms, we often think about computational algorithms (or algorithms that exist within some scientific discipline)
• Computing Science = the science of computation.
• Computation = the execution of a series of instructions. • A series of instructions = an algorithm.
• It is easy to make the natural association with algorithms and Computing Science.
• Because a major aspect of computing science is the study, creation and refinement of algorithms.
• But remember that algorithms can (and do) exist anywhere and are not exclusive concepts to computing science!
Application of algorithms
• Algorithms are often used to solve problems by providing a series of instructions to follow.
• Some examples are: • Data processing.
• Searching and sorting algorithms. • Recommendation algorithms.
• Matching algorithms.
• Shortest path algorithms.
The travelling salesman problem
• Famous computing science problem.
• There are several algorithms in existence that can solve this problem.
• Nearest Neighbor is the most common solution.
Image: Wikipedia
Expressing an algorithm
• There are two ways we can represent the nearest neighbour algorithm:
Verbose explanation:
Start at a random node n. While there are nodes not yet visited, let m be the node with the smallest distance from n. Set n to be m. Finally take the distance from n to the starting node.
Pseudocode:
let n be a random node s
while nodes_to_visit is not empty;
let m be shortest distance from n set n to be m
remove n from nodes_to_visit
set n to be s
Caveats of algorithms
• An algorithm is a concept that exists independently of software. • An algorithm is not a piece of software.
• A piece of software is not an algorithm.
• Algorithms allow us to express explicitly how we can go about solving problems in a step-by-step manner.
• But the problem must be solvable.
• I.e., there must be a way for us to arrive at a solution, by following a step-by-
step process.
• There are some famous problems that are not solvable. • Such as the halting problem discussed in the Turing thesis.
Algorithms vs programs
• Just to re-emphasise…
• An algorithm and a program are nothing alike.
• An algorithm is a series of logical steps.
• They can be expressed informally, or semi-formally with loose syntax.
• A program is a piece of software that implements an algorithm.
• It must be written in a formal way, with explicit syntax so it can be executed.
• A program will often implement an algorithm (or multiple) depending on the context of the program being created.
• But they are not by definition, algorithms.
Complexity
• Complexity is a way for us to express the amount of effort it takes to complete an algorithm.
• Because an algorithm is an explicit series of steps to be followed exactly, the way by which the instructions are expressed can lead to efficient, or inefficient solutions.
• For example, if a recipe had you cook every single ingredient separately, one at a time before combining them, then this will take you longer to complete than a recipe that tells you to combine everything and cook them together.
Complexity cont’d
• There are generally two ways to interpret complexity in an algorithm. • Complexity associated with understanding the algorithm (conceptual
complexity)
• Complexity associated with execution of the algorithm (time complexity)
• Computing science involves the study of algorithmic time complexity. • You will learn about this in ADS
• We use big O notation to express the time taken to follow an algorithm.
• Indicates the amount of work, or number of calculations required.
Big O notation
• Mathematical formula to express how many computations are required to follow an algorithm.
• For a given size of a problem n, we want to know how a function grows as n increases to determine the efficiency of an algorithm.
• Say if we wanted to sum the numbers stored in an array of size n.
• We would iterate over each value and perform a single addition operation involving that value. Therefore, if we have n elements in an array, we perform n operations.
• This is known as linear complexity O(n).
• The amount of work to do increases proportionally to the size of the problem.
Coming back to the travelling salesman problem
• The nearest neighbour algorithm is more efficient as a solution to this problem as we perform fewer operations. We simply calculate the shortest path from the current node and move there, so on until we finish.
• If we wanted to calculate the best solution, we would perform substantially more work as we would need to calculate all possible ways forward and compare each possibility before moving to the immediate next node.
• Therefore, complexity analysis is important in computing science.
• It allows us to compare multiple approaches to solving a problem and determine which one is better than the other, through the expression of mathematical formulae.
Visualising complexity
• We can see, in the event a problem has O(n) complexity, the linear relation between the size of the problem (x- axis) and the work required (y-axis)
• We want to avoid exponential complexity if possible and try to aim for logarithmic complexity whenever we can.
COMPSCI4039
Week 9 – Recursion
What is recursion?
“To understand recursion, you must first understand recursion…”
• Recursion is the act of using what we know about small problems, to solve larger problems.
• How many ancestors do you have?
• #ancestors(you) = #ancestors(mother) + #ancestors(father) + 2
Recursive approach
• The principle with recursive arguments is to take the solution to a small problem and scale it up to find the solution to a bigger problem.
• For example, if we wanted to sum all the numbers that are presented to us in some sequence:
• We could do this with or without recursion.
Without recursion
• Solving this problem is reasonable without recursion.
• We create a for loop, iterate over the numbers from 1 to some max
value, and sum the numbers as follows:
private static int printNumbers(int max) { int output = 0;
for (int i = 1; i <= max; i++)
output += i; return output;
With recursion
• With recursion the conceptualised solution is a little trickier to understand.
• We call the method multiple times; on each call we add the result of the computation from the next call to the value that will be returned by the current call:
private static int printNumbers(int max) { if (max == 1)
return 1; else
return max + printNumbers(max - 1); }
Recursion visualised
• The initial call to the method T will create another call to T with different values.
• Each call will perform some logic with the result of the nested call it makes.
• We use a stopping case to determine when to stop calling the method over and over.
• It won't stop otherwise!
(T is short for printNumbers)
Recursion visualised
• When we hit the stopping case, we start to return the values from the nested calls.
• This means we have call T(1) initially return its values to T(2), which returns its values to T(3) and so on...
• This allows us to calculate T(5) by having summing the results of all these individual function calls.
Why recursion?
• It allows us to simplify the expression of code when working with more complex problems.
• We will see this shortly.
• The advantage of recursion is that it can reduce the amount of work
required to perform a task, and therefore reduce its complexity.
• Another advantage is that recursive code is something that can handle any size of problem, we are programming a general solution.
• The disadvantage of recursion is there is increased conceptual difficulty in creating the solution.
2 important principles of recursion
• Every recursive call must simplify the computation in some way
• There must be special cases to handle the simplest computation
• The examples I have illustrated thus far were designed to showcase how recursion works but does not demonstrate the benefit of recursion.
• We need to look at more complex examples to see this.
• Permutations – will illustrate how we can simplify code.
• Binary Search – will illustrate how we can make search more efficient.
Permutations example
• Let's see how recursion can simplify code.
• Suppose I wanted to calculate all possible permutations of a string. • If I had the word 'bark', there would be 24 possible permutations:
bark, bakr, brak, brka, bkar, bkra, abrk, abkr, arbk, arkb, akbr, akrb, rbak, rbka, rabk, rakb, rkba, rkab, kbar, kbra, kabr, karb, krba, krab
Again, there is a recursive and a non-recursive way of solving this problem. Let's compare the two.
Non recursive approach
Let's have a look at some code
Problems with non-recursive approach
• We can see with the code example that there are a lot of for loops. • We need one for loop, for each letter in the String.
• This will work as a solution, but it is not nice to look at.
• There is a lot of repeated code, and expandability is an issue.
Q: If we wanted to make the string bigger, what will be required?
Non recursive approach
Let's have a look at the code again
The need for recursion
• The code does not scale well with the size of the problem.
• It is necessary to have as many loops as per the size of the string.
• If we wanted to calculate the permutations of a String that is 6, 7 or 8 characters long, we would have a lot of code to manage.
• This can be error prone and if we needed to refactor, will be a lot of work. (poor software engineering practice)
• Using recursion means we can create a general solution that can work with any size problem.
Recursive approach
Let's have a look at the code one more time...
Recursive approach
• We can see that it is much easier to read.
• We are able to simplify the expression of code.
• At the expense of conceptual difficulty.
• Recursion approaches can be challenging...
• As we use a lot of memory as Java calls and assigns variables multiple times. • Stack overflow problems occur when the JVM calls the method too often.
• Permutation algorithms are exponential in complexity.
• Your code will not perform well when calculating the permutations of "this_string_here_don't_wait_on_it"
Another problem, searching
• Recursion can be (and is) used to search data structures in Java.
• Without their use, we would have very inefficient sorting algorithms.
• Let's say I have the following sorted list
• If I wanted to search for a particular value v, our algorithm should return the index of the position of v if it is there, -1 otherwise.
• So far, we have been using linear search to achieve this.
Linear Search algorithm
• Depending on where the value is in the array, we may need to check all n positions.
• On average, we can estimate we would need to check roughly half (n/2)
• This grows much like linear complexity
Recursion for searching
• We can use recursion to search a sorted array.
• The principle is to check the 'middle' of the array. If we hit the item
we want, fantastic.
• Otherwise, we jump to the middle of the array to our left, or right depending on where the item should be located.
• We perform this step multiple times, until we either find the item, or can no longer find a 'middle' to jump to.
• This indicates that the element is not in the array, without us searching the entire array.
Binary Search algorithm
• With binary search we can reduce the number of checks we perform when searching for an item in an array.
• This in turn reduces the time complexity. It is much more efficient to search a sorted array like this than to use linear search.
• This only works for sorted arrays however, for unsorted arrays the method would not guarantee to provide a correct result.
Revisiting complexity
• Because we can skip so many elements when we search, we can approximately state that there are log n computations required.
• This is something that will be demonstrated to you in greater detail in ADS.
• Complexity is not something that will be examinable in this course.
• However, algorithms and recursion are examinable.
Final code example
Let's look at some code!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com