Week 6: Algorithms

• What is an algorithm?
• Shuffling: stating the problem
• The Fisher-Yates shuffle
• Bottom-up Fisher-Yates
• Shuffling wrong
• Empirically testing shuffle implementations
• Searching
• Linear search
• Sortedness
• Testing for sortedness
• Binary search
• Understanding search algorithms
• Sorting algorithms
• Insertion sort: the “natural” sort
• Insertion sort with loops
• Selection sort
• Descending selection sort
• Quicksort
• Choosing the pivot element
• Quicksort with median pivot
• Merge sort
• Merging sorted lists