9. Fast Fourier Transform

Thu Nov 12

Our goal for this week will be to take the code for a naive Fourier transform and team together to optimize through recursive divide-and-conquer, taking key insight from the Cooley-Tukey Fast Fourier Transform algorithm. Here is my derivation of the math behind the very clever Cooley-Tukey decomposition, this math forms the basis for how to rework the code.

Pre To-do

I'd like to ask each of you to put in a little prep work to come with a basic understanding of the Fourier transform. I've been hunting down introductory resources and can highly recommend these two:

Fourier transform visualized through periodic motion is a popular approach in Youtube videos. I am not sure these work as an introduction all on their own, but after getting the gist of things from the sites above, these animations can reinforce your understanding and are mesmerizing to watch:

Later followup

I found many good analytic resources, but most dive straight into the math and rarely surface for air. If you're intrigued to learn more, exploring these heftier resources could be a project for winter break.

8. Data compression

Thu Nov 05

For today's meeting, I'm planning to give a quick introduction to the Lempel-Ziv-Welch compression algorithm and then quickly move us into breakouts so we can get coding. If we hunker down and apply the power of teamwork, we may be able to pull off a complete LZW encoder-decoder, which would be a cool accomplishment! We can then compare/contrast Huffman to LZW in terms of effectiveness, performance, ease of implementation, and so on.

7. Simulation and Visualization

Thu Oct 29

We'll explore how to generate results via simulation and consider how data visualization can aid our understanding of a simulated process. The simulation algorithms we will look at belong to the family of "Monte Carlo" methods that use repeated random trials or statistical sampling. We will use the GWindow class of Stanford's CS106B library for simple drawing

6. Sorting

Thu Oct 22

We'll get a head start on CS106B by doing our own exploration of sorting in advance of Friday's lecture. The competition to be "the" standard sort for language/library is stiff. What does it take to be "The One"? Let's take a deep dive into Quicksort, one of the most celebrated of all sorting algorithms.

5. Super-charging recursion

Thu Oct 15

Recursion is a powerful and elegant problem-solving technique, but the exhaustive nature of certain recursive algorithms can come with a high cost in runtime performance. Let's look at techniques for paring down those costs by trading space for time and accepting approximation in place of exactness.

4. Fractals

Thu Oct 08

Pre To-do

Students who followed up with me after last week were clamoring for "more code!", so I plan to move in direction of more hands-on activities where we can. For this week, we'll be playing with code that riffs on the classic Sierpinski fractal and exposes intriguing and surprising connections from fractals to other parts of mathematics, including chaos and dynamic systems, iterated function systems, cellular automata, number theory, binary/ternary number representation, space-filling curves, and more. It is all quite magical!

Here are some wonderful background resources. If you have some time to check into these in advance, please do!

I'll have some sample code prepped that will get us started and you'll have a chance to work more closely on the code in small groups in breakouts. If you are able to, please update your Zoom to version >= 5.3. ("Check for Updates" in Zoom menu). The 5.3 version adds a few convenience features, one of which is the ability to self-select a breakout room.

3. Search engines, Google's Page Rank algorithm

Thu Oct 01

Pre To-do

Here are some resources to check out in advance of this Thursday's meeting. I'm not asking you to read all of these, but please do try to get the gist of the basic ideas underpinning Page Rank (Wikipedia page is a good start). If you're eager to go deeper, the original epic Brin/Page papers are quite accessible. To be an informed citizen and consumer of search it behooves us to know some of the ways those results can be distorted, I picked a few press articles to give a taste.

If you know of other good resources, please share on Ed!

2. Binary search

Thu Sep 24

Pre To-do

  • We will be using Ed Workspaces for collaborative coding; be sure you are signed up for 106M Ed forum.
  • Familiarize yourself with basics of Stanford Vector class
  • Review the CS106B Guide to Testing

For this week's meeting, I'm asking you to not read up on binary search in advance. Just come with a "clean mind" and we'll explore together. I will post reference links after the meeting for follow up.


Here are references on binary search. Some of these are excerpts from books available in the Stanford Library digital collection. Click the link, authenticate with your Stanford sunet, and find link to full book in section labeled "Available online".

Follow-up excursions

We got to just the tip of the iceberg this week. Let's keep the discussion going! Below are some further exercises and questions to consider. If you get a chance to try some out, please share your results on Ed and we can all learn from each other and offer feedback.

  • Refine algorithm into its cleanest, clearest form
    • should low/high be inclusive or exclusive?
    • how should low/high change each iteration? what invariant is being maintained?
    • is it necessary to ensure low/high always stay within bounds?

      To ponder: if low and high are in bounds at start of loop, then mid is in bounds. Updating bound low=mid or high=mid thus guarantees low/high to stay in bounds. But including mid in the remainder to search is not quite right, and as we saw in class, when low was already mid, this does not advance and gets stuck in infinite loop. Updating bound to mid+1 and mid-1 seems correct. But in some cases this can cause low/high to go out of bounds. When does this happen? Would this cause a problem? Why or why not?

    • what is correct stopping condition?
    • some argue that the cleanest form is for the loop to test for match and return early, but always run loop down to range of single element. If that final element is the target, return index, otherwise, not present. Try rewriting into that form, do you agree that is it cleaner? Why or why not?
    • how should duplicate elements be handled?
      • as-is returns index of a match, but not necessarily first/last.
      • if specification is to return index of first match, how could you change to do so?
      • does this version still run in logarithmic time? if not, how could you make it so?
      • what if requirement were to return the count of matching elements?
  • Confirm the correctness of your algorithm
    • could be proof via pre/post conditions, invariants
    • and/or rigorous test suite
      • what mix of whitebox/blackbox/fuzz constitutes "rigorous" coverage?
  • Performance studies using TIME_OPERATION
    • confirm that binary search is operating in logarithmic time
    • determine cost of a recursive implementation versus iterative
    • compute "payback horizon"
      • how many searches to hit break even where savings of binary vs linear search offsets costs of one-time sort?

1. Meet & Greet

Thu Sep 17

Pre To-do

Nothing to prep, just bring yourself and your enthusiasm. Zoom details. We will use our first meeting to introduce ourselves and brainstorm our plans for the seminar. Look over the list of possible topics.

Post meeting

Everyone please join the Ed forum and weigh in with your topic interests.

Thank you all for coming today and sharing your stories! We had two dozen attend, almost all first year or transfer students. An awesome journey awaits you at Stanford, I'm happy to be a part of welcoming you!