Introduction to Computational Topology

COSC 49.09, Fall 2020

Main | Schedule | Homeworks | About

Instructor

Hsien-Chih Chang (hsien-chih.chang@dartmouth.edu)

Lectures

Zoom
Mon Wed 4p–5:50p (Eastern Time)

Office Hours

Zoom
Fri 4p-5p, Mon 9a-10a (Eastern Time)

Discussion

Slack

Links

Canvas | Syllabus | Projects | Notes for COVID-19

Announcements

Nov 16

• This is the last lecture of the term. Thank you all for joining me to learn about computational topology! I hope the materials have been interesting and you learned something to take away with you.
• The final project presentations will be held on the finals week, which is two weeks from now. Here is the link to the signup form for final project presentation. Please fill it up by the end of the week.
  • Choose a date between 12/2 (Wed) and 12/4 (Fri).
  • Choose a 30-min time slot in the afternoons, from 1pm to 5pm.
  Let me know if none of the time slots work for you!

Nov 11

A newer version of Homework 3 has been uploaded (again). As pointed out by a student, there was an error in the erratum of Problem 3 (and also the announcements on Nov 4 below). A k-simplex has k+1 nodes, corresponding to the k+1 shortest paths that share a common intersection. In particular, intersection of two shortest paths corresponds to a 1-simplex. I apologize for the confusion.

Nov 4

A new version of Homework 3 has been uploaded. As pointed out by a student, there was an error in Problem 3. The shortest path complex contains not only the 2-simplices (edges) representing intersections of two shortest paths, it also contains all the k-simplices corresponding to higher-order intersections: construct one k-simplex for every k shortest paths that share a common intersection.

Nov 1

All project proposals have be reviewed and approved. I attached some comments to each of your submissions; all the comments and suggestions are meant to be what they are — suggestions — and you are not required to incorporate them to your project if you don't think they are a good fit. All the project proposals can be found and downloaded on Canvas.

Oct 28

Let's cancel the lecture today.  I will record the lecture on Zoom tonight, and post it on the course webpage; also I'll let you know when I start to record so you can jump in if you happen to be free tonight.  I apologize for the short notice.

Oct 26

• It's now half way pass the term, and I'm sure many of you are low in energy and pretty stressed right now.  (Me, too!)  So I decided that we should take a break from formal lectures today.  Instead, since you are now thinking about a good final project to work on, let's chat about how to (start to) do research!  We will resume normal lectures on Wednesday.
  • Research is a very different experience than studying for a course.  We will work together on a toy (but real) problem and I'll show you how to start thinking about a problem and search for references, how to filter information, how to write down thoughts and ask yourself questions, and things like that.  You know, research.  There is no "knowledge" to be taught today, just demonstrating my personal method towards working on a real frontier problem.
  • No prerequisites are assumed!  So I encourage all of you to join and we can tackle this problem together.  (Think about it as live-stream coding, but with research.)  Who knows we might get somewhere!
• I prepared a midterm feedback form, and would really appreciate your feed back on what works for the course and what not. If you have time please take 5 mins to fill it out; thank you for your time!

Oct 23

Homework 3 is out, due by 11/13 (Friday three weeks from now).

• This will be the last homework set of the term. Since there are three questions, you will have three weeks to think about them instead of two. I strongly encourage you to start early! Ideally, you only have to think about one problem each week.
• If you feel stressed and confused about the course material, come talk to me. Also, remember that the homework problems are designed to stretch your ability and put you out of your comfort zone, so they are difficult and even frustrating by design. This does not mean that you are doing bad for the course.
• In fact, look back to Homework 0 and see if you can figure out what topology concepts we are using in Problem 3 and 4. I hope you feel accomplished and learned something new since the start of the term.

Oct 22

So it was brought to my attention that there is a solution to Problem 2 in Homework 2 without using topology (well, at least not the ones we learned in this class).

• Take it as an extra credit problem: the solution I have in mind only requires you to perform one breadth-first search during the preprocessing time assuming the input graph is connected.
• You are not required to solve this challenging version of the problem to get full credit; any algorithm with linear preprocessing time and constant query time works.

Oct 20

A new version of Homework 2 has been uploaded, emphasizing that in Problem 2, the starting and ending positions of the cube and corresponding color labels are given after the preprocessing. Which means you don't have time to look at the whole input map again after a position pair is given.

Oct 19

We had several instable connections and/or voice quality problems to Gather.Town; let's switch to Zoom permanently for future office hours.

Oct 17

It is time to think about your Final Project! The project proposal is due by 10/30 (Friday).

• Unlike previous homeworks, each person has to submit the project proposal individually.
• You should submit your proposal through Canvas.
• You are strongly encouraged to come talk to me and brainstorm on what do you like to do for your project! See the Projects page for ideas.

Oct 10

Homework 2 is out, due by 10/23 (Friday two weeks from now).

• There is one problem that asks you to watch an one-hour long video. Make sure to start earlier!

Oct 7

We will have our make-up office hour today at 3pm at Gather.Town.

Oct 5

The office hour today at 9am has been canceled due to emergencies. I will try to make up for it this week.

Oct 2

A new version of Homework 1 has been uploaded, with some errors fixed:

• The signing for the planar curve in Figure 1 is corrected. (LaTeX ate double minus signs in \texttt mode.)
• In problem 2(c), we assume the minimal bigon is not empty (otherwise we can remove it using a 2->0 move) and all empty loops have been removed using 1->0 moves.

Sep 25

Homework 1 is out, due by 10/9 (Friday two weeks from now).

• You are allowed to form a group up to three people; please feel free to use the Groups page on Canvas to form groups and look for group members.
• Some problems are marked with stars. Star problems do not have a deadline; feel free to submit solutions to them at any time. Problems marked with a really big star are open (as far as I can tell), but it doesn't necessarily mean they are hard. Like all research problems, they are all easy in hindsight once you found the solutions. Spend as much as time as you are willing to invest based on your own interest.

Sep 21

I am very sorry that I missed the 9am-10am office hour today. Now I'm on Gather.Town; come if you want to join us!

Sep 14

• We will have our first lecture today starting at 4pm.  The zoom link can be found here. To enter the meeting room you need a passcode, which I have attached in a separate Canvas announcement. Some of you are currently outside of US and might have a hard time joining us during lecture hours.  Rest assure that there is no attendance requirements and all the lecture recordings will be uploaded and shared with you.  I will host an extra office hour for those of you who cannot join the one on Friday. See you all soon!
• The recording of today's lecture (and of all the future lectures) is up, and can be found on the Schedule page. If you experience problems watching the videos please let me know. (Personally I recommend you to watch them in 1.5x speed as I tend to talk too slowly during live lectures.)
• An extra office hour will be held on Monday 9am to 10am (Eastern Time); hopefully this will cover the needs of those who are currently on the other side of the Earth. Let me know if you would like to join the office hours but neither time works for you.

Sep 9

Homework 0 is out, due by 9/18 (next Friday). All the homeworks should be submitted through Canvas.

• Homework 0 is designed to make sure that you have the necessary skills and math maturity for the course. If you find the problems to be way too challenging beyond the realm of fun, come talk to me and we can figure out together if this is the right class for you.
• Make sure to read all the policies regarding collaborations, submissions, and grading on the homework page.
• Most importantly, have fun! There is no reason to take an optional graduate-level course if you are not having fun.

If you are now in a different time zone other than the EDT, and in particular if you cannot make it to the lectures, please let me know immediately. We will talk about the logistics of the course on the first day of lecture, and make a decision about the weights between synchronous/asynchronous components afterwards, but I do want to get the inputs from those of you who cannot join the lectures.

Sep 7

Hello, welcome to COSC 49.09! This is the webpage for the upcoming course on computational topology. I'm still preparing for the course; please bear with me! If you see any broken links please do let me know. A few announcements:

• If you still want to enroll but cannot add yourself on Banner, please send a mail to me; I can remove the enrollment limit for you.
• We will (tentatively) be using Canvas for discussions and homework submissions. Due to unexpectedly large number of enrollments (woooo topology (click)?), we might need more tools to handle discussions and such.
• There will be a Homework 0 coming up on the first day of the class. The goal is to give everyone a sense of what background knowledge is assumed for the course. Stay tuned!