Comp 318 - Algorithms (Spring 2026)

Introductory Information

• Syllabus.
• Canvas page.
• Mathematical Preliminaries

In-Class Examples/Links

Algorithm Analysis (Ch. 2)

• bin.cpp - converting a decimal integer to binary recursively.
• tower.cpp - Tower of Hanoi problem, the classic recursive problem.
• fact.cpp - recursive factorial problem and empirical analysis.
• fib.cpp - comparing performance of computing Fibonacci numbers recursively and iteratively.
• fibgraph.jpg - graph of empirical results of running fib.cpp.

Brute Force Algorithms (sorting and more) (Ch. 3)

• Class 2/26/26 - start of Chapter 3.
• Suite of data structure visualizations - collection in a Java jar file.
• sorting.mp4 - video of sorting routines in action. Sorry this is so small.
• sorting.cpp - suite of sorting routines in C++.

Decrease-n-Conquer (Ch. 4)

• Lomuto Partitioning

Divide-n-Conquer (Ch. 5)

• Quickhull. In our version, we sorted the input points; this is purported to produce the convex hull in a counter-clockwise order, which is desirable for many applications. It is not the sole driver of the time complexity, though. In general, the algorithm runs in O (n lg n) with a worst case complexity of O (n²). However...
  • • The Quickhull Algorithm for Convex Hulls - an often-cited paper by Barber et al. This is an extension of the original algorithm so that it works for any n dimensional space, with the performance with planar (2D) input being as described above. Interestingly, the authors calculate the performance (Big O) only through empirical methods. It also does not sort the points.
  • • A lower bound for the Quickhull convex hull algorithm... - paper from March 2025. Apparently, we still don't really understand the run-time complexity of Quickhull. This says it's O(nh), where h is the number of points in the convex hull.
• Wikipedia's entry on Karatsuba multiplication
• Carl Burch's implementation of Karatsuba multiplication
• YouTube video of Quicksort. You won't be disappointed.

Projects/Homework

• a4.pdf - project A4 specifications. Starter code is here.
• a3.pdf - project A3 specifications.
  • • a3.h
  • • METAL - Map-based Educational Tools for Algorithm Learning.
  • • HDX - METAL's Highway Data Examiner.
• hw3.pdf - homework 3.
• a2.pdf - project A2 specifications.
  • • mt257.dem.grd - small sample DEM file.
  • • franconia.dem.grd - larger sample DEM file.
• hw2.pdf - homework 2.