Assignment 2

Assignment 2 is now available! You can view the document here. This assignment will be due at 11:00 pm on Feb 4th. The submission guidelines are identical to the previous assignment. Electronic submissions are preferred (cc’ing both kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu), but if you wish to submit a physical document, do so in class or at 215 Smith Hall. Smith Hall locks to the public at 5:00 pm, so plan accordingly.

The document linked above has several questions inline, numbered as Exercises 12-17. You DO NOT need to complete problems 13 and 16; they involve material we have not yet covered. Also, there are some sections of text that might not recognize yet, such as a discussion of the Laplace-Beltrami operator and some use of exterior calculus. Don’t worry about these for now — they are not necessary to solve the problems, and we will be covering them in class in the upcoming weeks.

At the end of the document there is a coding assignment asking you to implement several of the quantities defined in the preceding text. A corresponding code skeleton is now present in the course repository, which you should download and modify. Note that the core library has also been updated, so you will need to re-download (or git pull, if you’re using git) the entire repository. The skeleton in Assignment2.py contains empty methods in which you will implement your solution, all of your modifications must be between the lines which say BEGIN YOUR CODE and END YOUR CODE. To submit the coding portion, email us your modified copy of the file Assignment2.py along with your written submission. There are some additional questions at the conclusion of the coding section, include your responses in the written submission.

To keep things simple, we will only be considering meshes without boundary for this assignment. There is a collection of such meshes in the Assignment2/Boundaryless_Meshes/ directory on which to test your code.

To investigate your code, run it as we did with the test assignment. Pressing ‘h’ will print (to your terminal) a list of commands supported by the program. Clicking on the mesh will print useful information about faces/edges/vertices.

Finally, on Tuesday (1/26) in class, I will be leading a workshop with a quick introduction to computing with meshes and a guide to using the course library. It is highly recommended that you attend! Please refrain from asking me any questions about the codebase until after that workshop.

Reading 3 – Topological Data Analysis

tda

Up until now, we’ve focused mainly on low-level concepts and definitions—for our next reading, we’ll take a high-level look at some very cool, contemporary algorithmic tools that leverage simplicial topology to make sense of large data sets in high dimensions. These tools fall under the broad heading of topological data analysis (TDA). One particular tool that’s received a lot of buzz in recent years (both within computer science as well as in applications in material science, imaging, biology, etc.) is persistent homology. The following video provides an excellent introduction, and should be mostly understandable based on what you’ve already learned in class:

Introduction to Persistent Homology (video)

Your reading assignment between now and February 2nd is to find one paper or survey on persistent homology that piques your interest (could be theory, could be applications) and summarize it to whatever degree you feel capable. Don’t worry if a lot of the terminology still seems alien—an important skill in reading academic papers is being able to extract the key idea without decoding every little detail and definition. If you find this subject interesting, you might consider doing your course project on TDA. More broadly, the emerging field of computational topology spans a broad range of beautiful and fascinating topics that could make good course projects.

Here are some pointers to get you started with persistent homology:

You might also try to give a rough summary of the different types of complexes that show up in topological data analysis (e.g., Vietoris-Rips, Čech, Witness, …).

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Tuesday, February 2nd including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / interesting / incomplete / not addressed.

Reading 2 – Topology

TopologyExamples

“Point set topology is a disease from which the human race will soon recover.”

—Henri Poincaré, father of modern topology

The goal of your second reading assignment is to make sure you understand at least the basic definition of each object we discussed in the last lecture, namely:

Topological Space
Metric / Metric Topology
Equivalence Relation / Quotient Topology

You may of course use whatever literature you like, since these definitions are all fairly standard. You should also read the Wikipedia page on topology, which gives a nice overview of its history and applications.

Submission: As usual, please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Thursday, January 21st including the string DDGSpring2016 in your subject line.  Your email for readings should always include:

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / incomplete / not addressed.

To test your own understanding, your email summary should answer the following two questions:

  1. Treating the black dots as points, and the blue blobs as subsets, which of the collections A–F is a topological space? Note that a blob with no points in it is the empty set.
  2. Two points \(x\) and \(y\) are “separated by neighborhoods” if there is a set \(U\) containing \(x\) and a set \(V\) containing \(y\) such that \(U \cap V = \emptyset\). Suppose we define an equivalence relation \(x \sim y\) where \(x\) is equivalent to \(y\) if and only if \(x\) and \(y\) cannot be separated. Again referencing the picture above, what then is quotient topology \(E/\!\sim\)? (Hint: this topology has a special name!)

Reading 1 – The Simplicial Complex

ddg_simplices

For your first reading assignment, your goal will be understand of the idea of a simplicial complex—or one of its many generalizations, if you’re already familiar with this idea (see below).  Simplicial complexes are the basis of many of the algorithms we’ll study in this class—and for a vast array of algorithms used in mesh processing, scientific computing, and Hollywood.  They are also one common way to discretize topological spaces, which are the starting point for our study of geometry in the smooth setting.

We will discuss this concept further in class, so don’t worry if you’re utterly confused!  Also, please feel free to discuss and ask questions here, by posting in the comments.

Listed below are some suggested readings (from “beginner” to “expert”).  For this first reading assignment, you are also free to search for references that you find easier or more interesting:

  • Simplicial Complex (up through & including “Closure, Star, and Link”) – Perhaps it seems lazy to send a link to the Wikipedia (which is the first result on Google), but then again, I wrote much of this page many years ago—and made the figures.  It would be a useful exercise to contrast with  Abstract Simplicial Complex.
  • Simplicial Complexes and Simplicial Complexes – two brief introductions, both by Herbert Edelsbrunner.
  • Cell Complexes – more advanced (and nicely illustrated) introduction by Jeff Erickson.
  • Algebraic Topology (pp. 102–104) – very nice (and free!) book by Allen Hatcher, who here discusses $\Delta$-complexes, a close cousin of simplicial complexes.  Those of you who want to go really deep might also take a look at pp. 5–10 on cell (CW) complexes, as well as an additional supplement on simplicial CW structures.

Finally:

  • A Survey of Efficient Structures for Digital Geometry Processing, Section 2.2 – I include this reference not because it is particularly good introduction to simplicial complexes—in fact, there are some errors!—but because it gives a rough sense of the kind of document you will write for your final project (albeit a bit different in focus).

Submission: Please send an email to kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu no later than 10:00 AM on Tuesday, January 19; please include the string DDGSpring2016 in your subject line, so that we can be sure we catch your submission.  Your email for readings should always include:

  1. a short (2-3 sentence) summary of what you read, and
  2. at least one question about something you found confusing / incomplete / not addressed.

For this particular reading, your summary should include a clear, concise definition for a simplicial complex, i.e., one that could be used to quickly communicate the idea to one of your peers without ambiguity.  For those of you already familiar with simplicial complexes, try to summarize the taxonomy of different complex types (simplicial complex, oriented simplicial complex, $\Delta$-complex, CW-complex, simplicial set, …).

Assignment 1 (Codebase)

As Keenan mentioned in class, the second component of getting started is downloading the codebase and getting a sample program to run. The codebase for this course is available at https://github.com/nmwsharp/DDGSpring2016.

The README displayed on that page contains some instructions for getting started and running a test program, as well as some other information. If you are an experienced programmer, feel free to ignore the instructions and do as you wish, there’s nothing especially unusual going on here (just get the test program working!).

To verify your success, please email me (nsharp@cs.cmu.edu) a screenshot of the window displaying the bunny by Jan 21. Don’t forget to include “DDGSpring2016” in the subject line.

There will surely be some hiccups getting started with this code, don’t hesitate to contact me with issues either via email or blog comments. I will also be holding an optional help session next Tuesday (Jan 19) around 5:00 so we can get things sorted out. If you aren’t available at that time and you would like to meet, let me know.

Assignment 1

A1 Assignment 1 has been released, and can be obtained by clicking on the image or on this link.  It will be due on January 21st at 11:00pm.  Solutions can be submitted either electronically (cc’ing both kmcrane@cs.cmu.edu and nsharp@cs.cmu.edu), or physically either in class or outside 215 Smith Hall.  (Note that Smith Hall is typically locked in the evening, so if you want to submit physically you should plan to do so a bit earlier!)  Solutions will be graded not only on correctness, but also on legibility and quality of exposition—part of our goal this term is to help you become better mathematical communicators; solving problems in a vacuum helps nobody.  We will take points off for terrible handwriting—for those of you who suffer from this affliction, we strongly suggest you use $\LaTeX$.  Please make sure to put both your name and your Andrew ID on your submission.

The coding portion of this assignment is forthcoming—basically you will just need to get the code skeleton up and running on your machine, and we will be glad to assist you (potentially in a recitation session).

If you don’t know where to get started with some of these proofs, just ask!  We are glad to provide further hints, suggestions, and guidance either here on the website, via email, or in person.  Office hours are still TBD, but let us know if you’d like to arrange an individual meeting.  Also, don’t be afraid to chat with your classmates—you will learn much more together than you will in isolation.

Good luck!

Assignment 0

Part of your course grade is determined by participation, which can include both in-class participation as well as discussion here on the course webpage.  Therefore, your first assignment is to:

  1. create an account, and
  2. leave a comment on this post containing your favorite mathematical formula (see below).
To make things interesting, your comment should include a description of your favorite mathematical formula typeset in $\LaTeX$.  If you don’t know how to use $\LaTeX$ this is a great opportunity to learn — a very basic introduction can be found here.  (And if you don’t have a favorite mathematical formula, this is a great time to pick one!)

Welcome to 15-458 / 15-858B! (Spring 2016)

Welcome to the website for 15-458/858B.  Here you’ll find course notes, lecture slides, and homework (see links on the right).

If you are a student in the class, register now by clicking here!

We strongly prefer that you register using your CMU email, but in any case you must not register with an address at hotmail.com, live.com, gmail.com, yahoo.com, aol.com, earthlink.net, as email from these domains will be filtered out by the host.

A few things to note:

  • You will be subscribed to receive email notification about new posts, comments, etc.
  • You can ask questions by leaving a comment on a post.  If you’re apprehensive about asking questions in public, feel free to register under a pseudonym.
  • Otherwise, please associate a picture to your profile by registering your email address at Gravatar.com—doing so will help us better recognize you in class!
  • You can include mathematical notation in your questions using standard $\LaTeX$ syntax.  For instance, when enclosed in a pair of dollar signs, an expression like dollar\int_M K dA = 2\pi\chidollar gets typeset as $\int_M K dA = 2\pi\chi$.
If you encounter any problems while trying to use the website, please contact the TA at nsharp@cs.cmu.edu.