# CS/SE 7301.003.20F — Recent Advances in Computing — Computational Topology

Fall 2020
Mondays and Wednesdays 1:00pm–2:15pm
Live lectures: MS Teams. Link will be given in the "CS 7301.003 2208" team.
Recorded lectures: Posted in the Lectures channel of the "CS 7301.003 2208" team as soon as they are available.

## Instructor:

Kyle Fox
Office: ECSS 4.224 (all meetings will likely be online)
Phone: (972) 883-4168
Email: kyle.fox@utdallas.edu
Office Hours: Wednesdays 2:30pm–3:30pm and Thursdays 10:30am–11:30am via MS Teams (tentative). Additional or private office hours available by request. Please email Kyle directly.
Homepage: https://personal.utdallas.edu/~kyle.fox/

Course syllabus: (MS Word) (pdf)

## Announcements

• 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.

## Schedule and Homework

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.

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