CS 371: Data Structures And Algorithms

Ursinus College, Spring 2021

As stated on the main page, there are two options for a final assessment, and I will provide more details about each one below

Option 1: Mock Coding Interview

A live coding interview, typically an hour in length, is a pretty standard part of a software engineering job these days. The focus is always on implementing algorithms, and this class will have covered the vast majority of the topics that are considered "fair game" for such an interview. The web site interviewing.io provides an excellent resource for this. You should spend some time looking at some of the sample interviews on this page to get an idea of how these go.

The interview we do will be somewhere between 30 and 45 minutes. I'll provide a rubric here as we get closer, but in essence, it is OK for you to make mistakes as you go along, as long as you recognize them and work to fix them. As a rule of thumb, the more talking you do about your thought process, the better.

Option 2: Geometric Algorithm Multimedia Expo

The annual Symposium on Computational Geometry (SOCG) always has a multimedia expo, where people are invited to submit short movies/skits/apps to make an algorithm "come alive." The focus of this conference is on "geometric algorithms," so basically geometry meets CS 371. Algorithms in this area have applications to computer graphics, robotics, video game design, city planning, map making, and beyond.

In this year's call, the official instructions are as follows:

The submission should be related to computational geometry, broadly
interpreted, but is otherwise unrestricted: for example, it can
illustrate a (new or existing) concept, technique or algorithm from
computational geometry, it can explain an application of computational
geometry, it can be meant for educational purposes or for entertainment
purposes, and so on.

The form of media is broad, including algorithm animations, interactive
software and games. To showcase the media after the event, for
submissions that are not videos, creation of an accompanying webpage
or video is encouraged (but not required).

Unlike the coding interview, students may actually work in groups on this project!. Students who go into enough depth with this work may submit their work to next year's conference! This would be particularly good for anyone who's considering applying to grad school. You can a history of all submissions since the 1990s on computational-geometry.org under Multimedia web proceedings

Videos/Skits

One of the videos in last year's multimedia expo was a video on how to make videos (very meta), which can serve as a practical guide for those who want to do a skit or an overview video.

Below are two examples of videos from the past two years

Web Apps / Games

For those who want to make an app, I'd highly recommend making a web demo using Javascript. For those who have not used Javascript, it is basically like Java meets Python, so it shouldn't take too long to learn. Here are a few examples from recent conferences

Spiroplot app
Dots and polygons
MatchTheNet
Geometric Models for Musical Audio Data
Scissors Congruence (cutting any two polygons with the same area into pieces that can be re-arranged into each other)
Geometric Spanner Algorithms Visualization
Interactive Geometric Algorithm Visualization in A Browser
Quickest Visibility Map Visualization

Ideas of Topics

Anything that combines skills from this class with geometry is fair game, but below are a few topics that would be great for this project

Segment Trees / KD Trees / BSP Trees

There are ideas similar to binary search trees that work for geometric objects. A segment tree is a binary tree that can be used to quickly look up whether a line segment exists in a collection of line segments. A KD-Tree is a tree that can be used to quickly find points in a point set. A BSP Tree is a tree that can be used to find any set of geometric objects more quickly.

Picture of a BSP tree, courtesy of Princeton computer graphics

Quick Hull

The quick hull algorithm is a very interesting algorithm for finding the convex hull of a set of points (you can see a demonstration of other convex hull algorithms in one of the videos above). In 2D, you can think of the convex hull as the points that a rubber band get stuck on after you snap it into place around the points. But the quick hull algorithm actually finds these points by starting on the inside and going out. It does not have as good theoretical guarantees as other convex hull algorithms, but it is very fast in practice and is widely used.

Polygon Ear Cutting

There is a strangely named algorithm called the "ear cutting algorithm" which can be used to divide any simple polygon (a polygon without holes or self-intersections) into triangles by chopping one external triangle (referred to as an "ear") off at a time until there is nothing left. I'd imagine that because of the name alone, some interesting skits could arise from this algorithm.

Linear Programming

There is a fundamental optimization problem in algorithms known as linear programming, which generally boils down to maximizing some linear function subject to a set of inequalities. It has an amazing geometric interpretation behind the scenes, and a breakthrough in computational complexity occurred when it was discovered that there's actually a polynomial time algorithm to solve it.

Alpha Shapes

3D range scanners take a 3D picture of an environment and return a bunch of point samples in 3D space. But what they're really sampling is some surface. One way to turn these points into a surface is by connecting them with triangles into a so-called triangle mesh. There is an elegant geometric construction known as alpha shapes which can be used to figure out which triangles (or line segments in 2D) to introduce to connect points. Interestingly, alpha shapes can be computed with the help of convex hulls, so this group may have something in common with the quick hull group.

Picture courtesy of Teichmann and Capps

Hamiltonian Paths in Triangle Meshes

A hamiltonian path is a path in a graph that visits every vertex exactly once. One can think of it as a path one would trace out with a pencil that touches every node without visiting any node twice and without lifting the pencil. Below is an example in a graph with six vertices, courtesy of Wikipedia

Unfortunately, there is no polynomial time algorithm to find a Hamiltonian path in a graph, unless P = NP (we will discuss this more in CS 373: theory of computation). However, there are special kinds of graphs for which it is possible to find Hamiltonian paths. For example, it is possible to modify a triangle mesh so that its "dual graph" contains a Hamiltonian cycle, which is even stronger than a Hamiltonian path, since it also ends up where it started off. The result is that it is possible to trace a "space filling curve" on the surface of a 3D shape without lifting a pencil, ending at the same place that the pencil started, as shown below

Example hamiltonian paths on meshes, courtesy of Q Xing et. al.

For this project, students should definitely create an app. It is particularly well-suited for students who have taken computer graphics. The most difficult part of implementation is doing a perfect matching. The easiest way to accomplish this is by implementing the Blossom algorithm.

Hamiltonian Cycles in The Space of Binary Trees under Rotation

As shown in this paper, it is possible to enumerate all possible binary trees with a fixed number of leaves by starting with a tree with every branch to the left and performing one rotation at a time, eventually ending up back at the tree with every branch on the left. This has a very interesting geometric interpretation of a hamiltonian cycle on the associahedron.

On the course web page, I show an animation that visits all possible binary trees, but there is sometimes more than one rotation in between adjacent frames

Students should create a program that creates a similar animation visiting all possible binary trees with a fixed number of nodes, but which only has rotations between adjacent trees. Students should read this paper and study its implementation details.

Onions

Given a set of N points in the plane, it is possible to build an efficient data structure to query the K points that are to the right of any line in O(log(N) + k) time with a data structure called an onion and a version of binary search on steriods called fractional cascading. An onion is a series of convex hulls that are peeled back from outer to inner layer, as shown in the image below (courtesy of wikipedia)

I could imagine a ridiculous multimedia video where someone was peeling an onion while explaining this

Dynamic Time Warping / Discrete Frechet Distance

It would certainly be possible to create a skit about dynamic time warping where two people have to hop along some trajectory while minimizing the sum of ropes that they use to connect each other. There's a similar problem known as the Discrete Frechet Distance which is incredibly similar to DTW, but which tries to minimize the maximum distance between any two points on a warping path, rather than the sum of all distances. A "decision version" of this problem could be to choose a rope of a certain length and see if that rope is long enough for people to hold onto the two ends of that rope while jumping from one point to the next.

Iterative Closest Points

There's a really neat algorithm to align 3D shapes that "snaps one of them into place" on top of the other one. Click here to view an assignment I made in the past that explains this concept. An animation is below, courtesy of a former student Nina Sun. This is a project that's particularly well-suited for a web demo.

Duality of Points And Lines

Click here to view some slides on this topic.

Grading Rubric

65%	Technical refinement: How much did the project mature over the time you worked on it? How close are you to the final goal that you had? Did you meet all of the specifications that we set together?
10%	Clarity: How clear is your video or app to a general audience that hasn't necessarily taken this class?
15%	Aesthetics And Code Quality: If you made an app or a video, are they smooth and polished for the viewer / interactor? Is your code readable and in good style?
10%	Making It Your Own: How much did you do to refine this project and to make it your own? Did you put any unique twists on it that weren't suggested by the instructor?