際際滷

際際滷Share a Scribd company logo

CPP12 - Algorithms

Download as PPT, PDF
Michael Heron
Michael Heron

This is an introductory lecture on C++, suitable for first year computing students or those doing a conversion masters degree at postgraduate level.

1 of 23
Download to read offline
Algorithms Michael Heron
Introduction Yesterday we talked about maintainability. Today we talk about algorithms. Algorithms are implementation independent representations of common tasks in programming. Mostly these get represented in pseudo-code. We still need to turn them into actual working programs. All the steps needed are listed for our use.
Programming Tasks Often in programming we need to do certain well defined tasks. Rather than solve the problem for ourselves, we can look to see where people have made available algorithms to solve the problem for us. Implementing the algorithm into our own program requires understanding. We need to know how it all fits together.
Common Programming Tasks Arrays introduce two fertile areas for algorithms. Searching Sorting Arrays let us group together data according to a certain type. Ints, floats, chars, etc But the arrays we work with would often be better if we could do certain things easily.
Searching A common task for arrays is searching through to see if a particular value can be found. Various ways to do this. Various algorithms exist to provide ways in which this can be done. Linear search Binary search Not all algorithms are created equal
Efficiency Algorithms give us the process by which we arrive at a result, but they also give us another thing. A measure of efficiency. Algorithms are a fertile field of study for software developers. How much better is algorithm X compared to algorithm Y Much attention paid to how efficient they are. Particularly in terms of how they scale.
Scaling Scaling is the term we use to discuss how things change when we deal with bigger values. A piece of code that works for five values may not work well for ten A piece of code that works well for ten may not work as well for a million. We call this scaling up Many algorithms have problems doing this.
Sorting Arrays force no ordering onto elements. They go in the order we tell them to. We often require ordering to be applied. Otherwise we may as well not have an array for large data sets. Imagine a phone-book that wasnt in alphabetical order. How would you use it? The process of taking an unordered array and making it ordered is called sorting.
Sorting As with searching, many algorithms exist. Today well talk about one Bubble sort Sorting algorithms in particular have scaling problems. A result of combinatorial explosion Need a measure of how efficient they are for different sets of data.
Cases Algorithms get assessed on the following: Best case Worst case Average case Best case is when the circumstances are as amenable to processing as they can be. Worst case is when the circumstances are as bad for processing as they can be. Average case is the efficiency in the average case.
Searching Lets look at an example the linear search. For each item in the list: Check to see if the item you're looking for matches the item in the list. If it matches. Return the location where you found it (the index). If it does not match. Continue searching until you reach the end of the list. If we get here, we know the item does not exist in the list. Return -1. http://en.wikipedia.org/wiki/Linear_search
Linear Search intlinearSearch(int a[], intvalueToFind, int size) { for (inti=0; i<size; i++) { if (valueToFind == a[i]) { return i; } } return -1; } Code scales linearly. For 100 items, it has the following performance: Worst case 100 comparisons Best case 1 comparison Average case 50 comparisons
Binary Search If we had a sorted set of data, we would have a different situation. We could use a binary search. This allows us to cut out half of the entire array each time we search. This scales much better. We require many fewer comparisons to find the element in which we are interested.
Binary Search Start at midpoint. If desired value is at current point Return the current index. If desired value is in the top half of array Discard the bottom half Search again If desired value is in the bottom half of array Discard the top half Search again
Binary Search Code Int binarySearch(intsortedArray[], int first, int last, int key) { while (first <= last) { int mid = (first + last) / 2; if (key >sortedArray[mid]) first = mid + 1; else if (key <sortedArray[mid]) last = mid - 1; else return mid; } return -1; } http://www.uow.edu.au/~lukes/TEXTBOOK/notes- cpp/algorithms/searching/binarysearch.html
Binary Search Performance Binary searches scale better than linear searches. For each element, we half the size of the search space. For 1024 elements: Much better performance than associated linear search.
Sorting Binary searches only work on sorted data. We must ensure the data is sorted before we can apply it. May not be worth it for small data sets. Must sort the data before hand. Multiple ways to do this also. Again, different algorithms scale differently depending on the number of elements involved.
Bubble Sort Start at the beginning of the array Set our current position to the beginning. go through each element of the array from the beginning if our current element is greater than the next element swap them around Set the current position to be the next element Repeat until we reach the end. Wont look at the code for this sort. Elements bubble up into the right position based on the algorithm. Bad efficiency, with combinatorial explosion problem. Does however result in a fully sorted list.
Algorithms Algorithms give us the solution without the code. That means we dont need to worry about converting between different languages. We have a base level description we can use for actual implementation. They serve as a kind of shorthand jargon for people in the business. When you talk about a bubble sort, other programmers know what you mean.
Efficiency With the speed of modern processors, is efficiency really a big deal? Bigger processors have led to more ambitious programs. For very large sets of data, efficiency can be a real issue. Programs that take hours and hours to run are not uncommon. Some applications of programming so processor intensive that modern processors still cannot cope. Realistic 3D graphics as an example
Trade-Offs Programming is a process of trade-offs You can have perfect maintainability or perfect efficiency, you cant have both. Code that is very efficient usually has very low readability. Important to decide for yourself where the line lies for a given program. Safest to go for maintainability first.
Optimisation The process of turning slow running code into fast running code is called optimisation. Should be done only when there is a need. There exists in programming an informal guideline called the 80/20 rule Used in many contexts In this context: 80% of your CPUs time is spent in 20% of the code Hard to tell where critical code is Dont optimise first
Summary Efficiency often lies at the other end of the spectrum from maintainability. Code that runs fast is not often code that is easily maintained. Algorithms exist as a shorthand for approached to programming problems. Along with a way of measuring efficiency. Each program requires a different approach. No one answer.

More Related Content

CPP12 - Algorithms

  • 2. Introduction Yesterday we talked about maintainability. Today we talk about algorithms. Algorithms are implementation independent representations of common tasks in programming. Mostly these get represented in pseudo-code. We still need to turn them into actual working programs. All the steps needed are listed for our use.
  • 3. Programming Tasks Often in programming we need to do certain well defined tasks. Rather than solve the problem for ourselves, we can look to see where people have made available algorithms to solve the problem for us. Implementing the algorithm into our own program requires understanding. We need to know how it all fits together.
  • 4. Common Programming Tasks Arrays introduce two fertile areas for algorithms. Searching Sorting Arrays let us group together data according to a certain type. Ints, floats, chars, etc But the arrays we work with would often be better if we could do certain things easily.
  • 5. Searching A common task for arrays is searching through to see if a particular value can be found. Various ways to do this. Various algorithms exist to provide ways in which this can be done. Linear search Binary search Not all algorithms are created equal
  • 6. Efficiency Algorithms give us the process by which we arrive at a result, but they also give us another thing. A measure of efficiency. Algorithms are a fertile field of study for software developers. How much better is algorithm X compared to algorithm Y Much attention paid to how efficient they are. Particularly in terms of how they scale.
  • 7. Scaling Scaling is the term we use to discuss how things change when we deal with bigger values. A piece of code that works for five values may not work well for ten A piece of code that works well for ten may not work as well for a million. We call this scaling up Many algorithms have problems doing this.
  • 8. Sorting Arrays force no ordering onto elements. They go in the order we tell them to. We often require ordering to be applied. Otherwise we may as well not have an array for large data sets. Imagine a phone-book that wasnt in alphabetical order. How would you use it? The process of taking an unordered array and making it ordered is called sorting.
  • 9. Sorting As with searching, many algorithms exist. Today well talk about one Bubble sort Sorting algorithms in particular have scaling problems. A result of combinatorial explosion Need a measure of how efficient they are for different sets of data.
  • 10. Cases Algorithms get assessed on the following: Best case Worst case Average case Best case is when the circumstances are as amenable to processing as they can be. Worst case is when the circumstances are as bad for processing as they can be. Average case is the efficiency in the average case.
  • 11. Searching Lets look at an example the linear search. For each item in the list: Check to see if the item you're looking for matches the item in the list. If it matches. Return the location where you found it (the index). If it does not match. Continue searching until you reach the end of the list. If we get here, we know the item does not exist in the list. Return -1. http://en.wikipedia.org/wiki/Linear_search
  • 12. Linear Search intlinearSearch(int a[], intvalueToFind, int size) { for (inti=0; i<size; i++) { if (valueToFind == a[i]) { return i; } } return -1; } Code scales linearly. For 100 items, it has the following performance: Worst case 100 comparisons Best case 1 comparison Average case 50 comparisons
  • 13. Binary Search If we had a sorted set of data, we would have a different situation. We could use a binary search. This allows us to cut out half of the entire array each time we search. This scales much better. We require many fewer comparisons to find the element in which we are interested.
  • 14. Binary Search Start at midpoint. If desired value is at current point Return the current index. If desired value is in the top half of array Discard the bottom half Search again If desired value is in the bottom half of array Discard the top half Search again
  • 15. Binary Search Code Int binarySearch(intsortedArray[], int first, int last, int key) { while (first <= last) { int mid = (first + last) / 2; if (key >sortedArray[mid]) first = mid + 1; else if (key <sortedArray[mid]) last = mid - 1; else return mid; } return -1; } http://www.uow.edu.au/~lukes/TEXTBOOK/notes- cpp/algorithms/searching/binarysearch.html
  • 16. Binary Search Performance Binary searches scale better than linear searches. For each element, we half the size of the search space. For 1024 elements: Much better performance than associated linear search.
  • 17. Sorting Binary searches only work on sorted data. We must ensure the data is sorted before we can apply it. May not be worth it for small data sets. Must sort the data before hand. Multiple ways to do this also. Again, different algorithms scale differently depending on the number of elements involved.
  • 18. Bubble Sort Start at the beginning of the array Set our current position to the beginning. go through each element of the array from the beginning if our current element is greater than the next element swap them around Set the current position to be the next element Repeat until we reach the end. Wont look at the code for this sort. Elements bubble up into the right position based on the algorithm. Bad efficiency, with combinatorial explosion problem. Does however result in a fully sorted list.
  • 19. Algorithms Algorithms give us the solution without the code. That means we dont need to worry about converting between different languages. We have a base level description we can use for actual implementation. They serve as a kind of shorthand jargon for people in the business. When you talk about a bubble sort, other programmers know what you mean.
  • 20. Efficiency With the speed of modern processors, is efficiency really a big deal? Bigger processors have led to more ambitious programs. For very large sets of data, efficiency can be a real issue. Programs that take hours and hours to run are not uncommon. Some applications of programming so processor intensive that modern processors still cannot cope. Realistic 3D graphics as an example
  • 21. Trade-Offs Programming is a process of trade-offs You can have perfect maintainability or perfect efficiency, you cant have both. Code that is very efficient usually has very low readability. Important to decide for yourself where the line lies for a given program. Safest to go for maintainability first.
  • 22. Optimisation The process of turning slow running code into fast running code is called optimisation. Should be done only when there is a need. There exists in programming an informal guideline called the 80/20 rule Used in many contexts In this context: 80% of your CPUs time is spent in 20% of the code Hard to tell where critical code is Dont optimise first
  • 23. Summary Efficiency often lies at the other end of the spectrum from maintainability. Code that runs fast is not often code that is easily maintained. Algorithms exist as a shorthand for approached to programming problems. Along with a way of measuring efficiency. Each program requires a different approach. No one answer.