CS1302: 2026-02-10
INTRODUCTION TO DISCRETE FOURIER TRANSFORMS

Usual Preparation

  1. Open Qunicy (with code if you have some)
  2. Open rustpad.io/#CS1302
  3. And I'll start a Google Meet.

Continued Array Examples: array-demo.cpp

Our Projects

  1. Cael's Music visualizer: uses a sound playing library, arrays, open-ended music visualizers, and perhaps Fourier transformations for a more advanced verseion.
  2. Luke's Lunar lander: uses colors, a bmp background, discrete Newtonian physics, keyboard and mouse input
  3. Carter's Newtonian starship: uses colors, more animation, discrete Newtonian physics

Michael's Exploration of the Discrete Fourier Transform

  1. Warning: I am just now learning most of this myself. Probably no need to take notes. Please just absorb what is absorbable and ask lots of questions.

    Fourier Transform Pairs from Allen D. Elster's MRI Questions
  2. The basic idea of a Fourier transform
  3. Discrete Fourier transforms (DFT)
  4. The straight-forward algorithm to compute a DFT of n samples is O(n²).
  5. The Fast Fourier transform (FFT): A O(n log n) algorithm for computing DFTs
  6. Both the signal and its transform are complex-valued.
  7. My experiments with the DFT in Excel: dft.xlsx
    (requires you to activate Excel's Data Analysis Toolpak)
  8. Using a DFT in our sound library:
    Frequency Spectrum Bands from LANDR Blog

Future Work

  1. Continue with your projects until you are satisfied.
  2. Continuing indexing items from this list of stories discussed in Worlds Enough and Time by Gary Westfahl; or from this other list of stories discussed in Time Machines by Paul Nahin. NOTE: Before choosing a story, click on the More Details list and ensure that it doesn't yet have a Librarian listed at the bottom. (It should have me listed as the Curator. When you've selected a story, let me know and I'll help you find it in an online library. Also send me your individual choice of your librarian name, login name, and password for the ITTDB.
  3. Read what interests you from the new books. Try to find a project (in any subject area) that you might enjoy or even feel passionate about. Computer science, math, quantum physics, time travel. Start exploring it on your own with the idea that you'll present some of it to us sometime in March.