CS 240: Lecture 22 – Sort Review
Dear students: In today’s lab, we’ll work through a few exercises to investigate radix sort and review the five sorting algorithms we’ve discussed: Radix sort exercise Sort review There’s nothing to turn in. Ask lots of questions! TODO You have some work to do before the next class: Complete the second take of mastery quiz […]
CS 240: Lecture 21 – Quicksort and Radix Sort
Dear students: Today we’ll start by walking through the exercises that you started working on last time. We’ll calculate the best and worst case running times of quicksort and reason about why it’s still considered a good sort even though its worst case is no different than insertion sort or selection sort. During the remainder […]
CS 240: Lecture 21 – Quicksort
Dear students: Mergesort has some nice worst case running time, but have you check out quicksort? It too takes a recursive, divide-and-conquer approach to sorting. Here’s the overall algorithm: public static void quicksort(int[] items) { quicksort(items, 0, items.length – 1); } private static void quicksort(int[] items, int left, int right) { int pivotIndex = (left […]
CS 240: Lecture 20 – Recursion Lab
Dear students: Today we will devote our entire time together to solving some programming challenges on Leetcode using recursion. Complete these exercises in Java: 203. Remove Linked List Elements 206. Reverse Linked List 21. Merge Two Sorted Lists 24. Swap Nodes in Pairs 2. Add Two Numbers Find these problems by clicking on the Problems […]
CS 240: Lecture 19 – Mergesort
Dear students: Insertion sort and selection sort can be written in just a few lines of code, but the energy consumption of each of those lines is quite high. Both are $\Theta(n^2)$. Suppose you have a processor that runs at 3.5 gigahertz. That means its clock ticks many times per second. Let’s generously assume that […]
CS 240: Lecture 18 – Sorting
Dear students: Now that we have a new tool for analyzing recursive algorithms, we are ready to start looking at some of those algorithms. The fastest sorting algorithms are recursive. However, the fastest sorting algorithms are also complex. Rather than begin with them, we first look at some simpler but slower sorting algorithms. Tail Recursion […]
CS 240: Lecture 17 – Recurrence Lab
Dear students: Today we will devote our entire time together to a lab on recurrences. Follow these guidelines: Expand your general case out at least three levels to be certain of the pattern. Write your answers out cleanly on paper or screen. Triple-check your algebra. Ask lots of questions. There’s nothing to turn in. TODO […]
CS 240: Lecture 16 – Binary Search
Dear students: Even before computers, we humans collected massive amounts of data. We made dictionaries and phonebooks, for example. Finding an entry in our records can be difficult. One option is the sequential search, which looks like this: to search(target) for each record if record matches target return record return null In the worst case, […]
CS 240: Lecture 15 – Recurrence Relations
Dear students: This semester is moving right along. We started by discussing the need to gauge the expected running time of our code in a machine-independent way. Coming up with an exact number of operations is too hard. Instead we decided to focus only on the dominant terms of an algorithm’s cost function. The result […]
CS 240: Lecture 14 – Queue Lab
Dear students: Today we will devote our entire time together to a lab on queues. Follow these guidelines: You may work with one other person. If there’s an odd number of people, one group of three is permitted. Complete the lab using a single computer. Take turns at the keyboard. Talk to each other. When […]