June 4, 2021: Homework solutions have been removed in case we want to reuse any problems in future semesters.
December 12: Final grades have been submitted to Orion. I sincerely hope you've all had a great semester.
If you liked Computational Topology, you may be interested in signing up for Benjamin Raichel's course CS 6319 — Computational Geometry. You can find more information about the course here.
November 23: Final project reports can now be turned in via eLearning. The "official" due date is Wednesday, November 25th, but I am glad to offer extensions if requested. You must request an extension to turn in after November 25th. Unless there's extreme need, I'll make Tuesday, December 8th the latest you can extend the deadline.
November 16: Due to the compressed time frame and other difficulties we're facing this semester, we will not be doing project presentations. Your project grade will be based entirely on the report instead. Please remember that the report is officially due Wednesday, November 25th. However, I plan to be very lenient with deadline extensions. Please let me know if one is needed.
November 2: Homework 3 has been released. It is due Friday, November 20th by the end of the day. The LaTeX source files are also available.
October 27: Submitted project proposals are now available on eLearning. I'm expecting another to be submitted before tomorrow's class, so you may want to check tomorrow afternoon if you're not in a hurry to see what others have proposed.
October 15: Homework 2 solutions have been released.
October 12: The eLearning assignment for the project proposals is now available. Every student should submit their own one-to-two page proposal by Friday, October 23rd. Afterward, I will upload all proposals to eLearning so you can see what your classmates are interested in and plan to work together on the projects if you would like.
October 7: The hint to Problem 2 of Homework 2 has been updated to remove a minor inaccuracy. Please see the homework pdf for details.
October 2: The hint to Problem 1 of Homework 2 suggested a solution to a related problem. You may provide an algorithm for either the original or related problem for full credit. See the homework pdf for details.
September 25: Homework 2 has been released. It is due Friday, October 9th by the end of the day. The LaTeX source files are also available.
September 23: Homework 1 solutions have been released. Homework 2 will be released soon.
September 8: Unfortunately, Erickson has removed his lecture notes from times he taught a computational topology courses in the past. He is currently writing new notes for his latest iteration of his course, but they don't contain all the details of his past notes. I have removed links to his old notes and added links when appropriate to his latest version of his course. Future lectures will diverge fairly quickly from his material.
Homework 1 Problem 1(d) contained a direct reference to something from Erickson's notes that I did not show during a lecture. As that material is no longer available, everybody will receive 2 points automatically for that part.
September 4: Homework 1 has been released. It is due Friday, September 18th by the end of the day. If you would like to use LaTeX to write your solutions, you may want to start with the source files for the homework and this solutions template.
August 18: An assignment to fill out the prerequesite form has been posted to eLearning. Please fill out the form and submit it to eLearning by next Monday, August 24th. You can find instructions for filling out the form here. The course has no official prerequesites.
Hello all, and welcome to CS/SE 7301.003.20F — Recent Advances in Computing — Computational Topology. I'm Kyle, an assistant professor at UTD and your instructor for the course. Normally, I'd wait until seeing you in person before making any announcements, but this semester is of course exceptional.
This course will have regular lectures presented by myself and office hours where we can discuss class topics or homework problems. I plan to do live lectures and office hours through MS Teams, under the "CS 7301.003 2208" team. I will also post recorded lectures there in case you can't attend in person, and we can use it as a discussion space if you'd like. If you have a strong preference for a different platform, please let me know. The class is small enough that we may be able to move. I find eLearning to be very frustrating to use, however, so I'd prefer to keep as much off of eLearning as possible, all things being equal.
This course has a website at https://personal.utdallas.edu/~kyle.fox/courses/cs7301.003.20f/. I will post copies of every announcement and homework assignment on the website. The website will also contain the only copy of the (always changing) course schedule along with links to relevant readings and lecture notes I use for myself as a script. I keep old class websites around forever in case you want to read up on algorithms or computational geometry topics that I've taught before. The website is also the best resource for understanding course policies and getting general writing advice.
We'll also use eLearning as the way I email announcements to everybody, the place to submit homework and reports, and the place I put your grades.
I'm looking forward to a great semester with you all, and I'll see most of you this Monday, August 17th at 1pm in the Live Lectures meeting of MS Teams.
The schedule below will be updated with new subjects and recommended readings throughout the semester. Exact topics discussed in each lecture may change.
Shortly before or after each lecture, I will update the readings with my own notes/script. Use at your own risk! My notes likely have typos or maybe even a few bugs!
The notes from the first seven lectures contain content and figures from computational topology courses by Jeff Erickson.
| Date | Subject/Event | Reading | Notes |
|---|---|---|---|
| Mon, Aug. 17th | Administrivia, curves in the plane, Jordan curve theorem | Erickson 1; lecture notes | |
| Wed, Aug. 19th | Triangulations, Jordan-Schönflies Theorem | Erickson 1; lecture notes | |
| Mon, Aug. 24th | Abstract graphs, planar graphs and rotation systems, and duality | Erickson 2; lecture notes | Prerequesite form due (instructions) |
| Wed, Aug. 26th | Primal-dual correspondences, Euler's formula | Erickson 2; lecture notes | |
| Mon, Aug. 31st | Minimum spanning trees in planar graphs, straight-line embeddings via Schnyder Woods | Erickson 2; lecture notes | |
| Wed, Sept. 2nd | Path and cycle homotopy | Erickson 3; lecture notes | |
| Mon, Sept. 7th | No class; university closed for Labor Day | ||
| Wed, Sept. 9th | Homotopy testing | Erickson 3; lecture notes | |
| Mon, Sept. 14th | Planar graph separators | Klein and Mozes 5; Har-Peled and Nayyeri; Erickson scribbles; lecture notes | |
| Wed, Sept. 16th | Minimum s,t-cuts in planar graphs | Erickson scribbles; lecture notes | Homework 1 due Friday, September 18th (LaTeX source) (solutions template) (solutions) |
| Mon, Sept. 21st | Multiple-source shortest paths | Klein and Mozes 7; Erickson scribbles; lecture notes | |
| Wed, Sept. 23rd | Maximum flow in planar graphs | Klein and Mozes 10; Erickson scribbles; Erickson paper; lecture notes | |
| Mon, Sept. 28th | Finish maximum flows | Klein and Mozes 7; Erickson scribbles; lecture notes | |
| Wed, Sept. 30th | Surface maps | Erickson map scribbles; Erickson notes; lecture notes | |
| Mon, Oct. 5th | Non-orientable surfaces and boundary | Erickson map scribbles; More Erickson scribbles; Erickson notes; Tree-coforest and forest-cotree decompositions (Section 3); lecture notes | |
| Wed, Oct. 7th | Shortest non-trivial cycles | Erickson scribbles; in \(n \log \log n\) time (Section 3); lecture notes | Homework 2 due Friday, October 9th (LaTeX source) (solutions) |
| Mon, Oct. 12th | Minimum s,t-cuts in surface graphs | Erickson scribbles; minimum cuts paper; alternative signature proofs (Section 3); lecture notes | |
| Wed, Oct. 14th | More minimum cuts in surface graphs | minimum cuts paper; lecture notes | |
| Mon, Oct. 19th | Graph minors | Erickson notes; lecture notes | |
| Wed, Oct. 21st | Algorithms exploiting low treewidth | Erickson notes; lecture notes | Project proposals due Friday, October 23rd |
| Mon, Oct. 26th | Cell complex definitions | Erickson notes; Edelsbrunner notes; lecture notes | |
| Wed, Oct. 28th | Cell complex examples | Erickson notes; Edelsbrunner notes on AC and VR complexes, Delaunay complexes, and alpha complexes, lecture notes | |
| Mon, Nov. 2nd | Simplicial homology definitions | Erickson notes; lecture notes | |
| Wed, Nov. 4th | Euler-Poincaré formula, reduction algorithm for computing homology | Erickson notes (see the warning in my notes); lecture notes | |
| Mon, Nov. 9th | Persistent homology | Edelsbrunner notes; lecture notes | |
| Wed, Nov. 11th | Stability of persistent homology and bottleneck distance | Edelsbrunner notes; lecture notes | |
| Mon, Nov. 16th | Stability and curvature of cycles | Edelsbrunner notes; lecture notes | |
| Wed, Nov. 18th | Curvature of cycles continued, smooth functions | Edelsbrunner notes on curvature and smooth functions; lecture notes | Homework 3 due Friday, November 20th (LaTeX source) |
| Mon, Nov. 23th | Morse functions, Reeb graphs | Edelsbrunner notes on Morse functions, transversality (just to state Morse inequalities), and Reeb graphs; lecture notes | |
| Wed, Nov. 25th | Reeb graphs on manifolds, closing thoughts | Edelsbrunner notes; lecture notes | Project reports due |