teaching machines

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 […]

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, […]

1 2 3