CS 240: Lecture 27 – AVL Trees
Dear students: Last time we introduced a special case of binary trees in which the left descendents are all less than their root and all the right descendents are greater. Such a tree holds the binary search in its bones. The binary search is fast, right? We like that. To get that speed, we need […]
CS 240: Lecture 26 – Binary Search Trees
Dear students: Fall break is over. Just four more weeks to the next one. And then two more weeks of the semester after that. Then finals. Then whew. In the weeks that we have left we’ll be talking about trees, dictionaries, hashing, and graphs. The good news is that these are all useful tools. The […]
CS 240: Lecture 25 – Expression Tree Lab
Dear students: Today we will devote our entire time together to a lab on expression trees. 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. […]
CS 240: Lecture 24 – Binary Trees
Dear students: We put the sorts behind us. Of course, nothing ever goes away in software development. We just put layers on top of it. Most of the time, we concern ourselves only with the outermost layer of abstraction: what are the methods named and what parameters do they expect? This class is meant to […]
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 […]