CSCI 535: Computational Topology, Spring 2020

This repository is for class materials for the Spring 2020 Computational Topology course, taught by Prof. Fasy (brittany.fasy@montana.edu.com).

Course Catalog Description: Provides an introduction to topological data analysis (TDA). This course will cover the topological, geometric, and algebraic tools used in TDA. Specific topics covered include persistent homology, Reeb graphs, and minimum homotopy area. Students will explore a data set of their choice in a course project, and learn how to apply the tools discussed in lecture.

This course assumes that you are familiar with the following topics: set theory, vector spaces, runtime analysis, and basic data structures. A student in this class should be familiar with proof techniques, including proof by induction and proof by contradiction. Although not necessary, a suggested prerequesite for this class is either M 461 (Topology), which is offered every other Fall (odd years), or CSCI 432 (Algorithms), which is offered every fall.

Course Outcomes and Objectives

By the end of this course, a student will be able to:

• Explain the basics in topology, as they apply to computing with data.
• Compute Betti number, topological persistence, homology cycles, Reeb graphs, Laplace spectra from data.
• Read recent research papers in the area of computational topology.
• Articulate, both orally and in writing, mathematical proofs.
• Demonstrate teamwork skills.
• Present and to critique applications of research in Topological Data Analysis (TDA).
• Recognize potential applications of TDA.

When and Where?

When? Tuesdays and Thursdays, 12:15-13:30

Where? Gains 043

How do I contact you?

• SLACK: The preferred method to ask questions relating to this class is using the #csci-535 channel on the CompTaG slack group. Please use this link to sign up for the Slack, and be sure to join the class channel.
• OFFICE HOURS: TBA (in Barnard 363).

What is in this repository?

The folders in this repository contain all materials for this class.

• lec_notes: Copies of lecture notes and board photos. (TODO: need a volunteer!)
• hw: homework assignments, as well as a LaTex template for your submissions.

In addition, the root directory has the following files:

• README.md: the course syllabus, including the schedule.

Note: If you want to learn more about Markdown, check out this tutorial.

Accessing this Repo

The repository is set as public, so you can access all course materials easily. I suggest creating a fork, so that you can use your fork to maintain your own materials for this class. See the resources section below for forking directions.

To clone this repo:

$ git clone https://bitbucket.org/msu-cs/csci-535-sp20.git

Grading

Your grade for this class will be determined by:

• 30% Homework
• 30% Group Project
• 33% 10-minute Quizzes
• 5% Literature Review (Grad) or Active Participation (Undergrad)
• 2% (n+1)st Assignment

Literature Review (due 20 March 2020)

For this assignment you are asked to write a short literature review or survey articale on a topology-related research topic of your choice. Your write-up should be about five pages (not including references), and should include at least five primary sources.

This lit review should be a descriptive summary of research relating to your topic, including potentially comparisons of different algorithms, hisotrical context (in which order were papers published, and how much time was in between them?). These articles are written individually, so if you are working on a project together, I suggest that you have different spins on the related research, so that this lit review can be helpful for making progress on your course project.

Class Policies

Policy on Class Attendance

Class attendance and participation is encouraged.

Policy on Homework

All assignments must be submitted by 23:59 on the due date. Late assignments will not be accepted.

Each homework will be graded on the following scale: incomplete (-1), low pass (+1), pass (+3), high pass (+5). Additional opportunities to earn points will also be made available throughout the semester. To pass this course, you must accumulate at least 20 homework points (grad) or 17 points (ugrad). Quizzes will be graded in the same way.

All submission should be typeset (in LaTex), and submitted as a PDF both in D2L and Gradescope. Each problem should be started on a fresh page. A recommended template will be provided.

Policy on Collaboration

Collaboration is encouraged on all aspects of the class, except where explicitly forbidden. Note:

• All collaboration (who and what) must be clearly indicated in writing on anything turned in.
• Homework may be solved collaboratively except as explicitly forbidden, but solutions must be written up independently. This is best done by writing your solutions when not in a group setting. Groups should be small enough that each member plays a significant role.

Classroom Etiquette

Except for note taking and group work requiring a computer, please keep electronic devices off during class, as they can be distractions to other students. Disruptions to the class will result in being asked to leave the lecture, and one half-point will be deducted from the final grade.

Withdrawing

After project groups are set, I will only support requests to withdraw from this course with a ``W" grade if extraordinary personal circumstances exist. If you are considering withdrawing from this class, discussing this with me (and your group) as early as possible is advised.

Special Needs Information

If you have a documented disability for which you are or may be requesting an accommodation(s), please contact me and Disabled Student Services within the first two weeks of class.

MSU Policies

Academic Integrity

The integrity of the academic process requires that credit be given where credit is due. Accordingly, it is academic misconduct to present the ideas or works of another as one's own work, or to permit another to present one's work without customary and proper acknowledgment of authorship. Students may collaborate with other students only as expressly permitted by the instructor. Students are responsible for the honest completion and representation of their work, the appropriate citation of sources and the respect and recognition of others' academic endeavors.

Plagiarism will not be tolerated in this course. According to the Meriam-Webster dictionary, plagiarism is `the act of using another person's words or ideas without giving credit to that person.' Proper credit means describing all outside resources (conversations, websites, etc.), and explaining the extent to which the resource was used. Penalties for plagiarism at MSU include (but are not limited to) failing the assignment, failing the class, or having your degree revoked. This is serious, so do not plagiarize. Even inadvertent or unintentional misuse or appropriation of another's work (such as relying heavily on source material that is not expressly acknowledged) is considered plagiarism.

By participating in this class, you agree to abide by the Student Code of Conduct. This includes the following academic expectations:

• be prompt and regular in attending classes;
• be well-prepared for classes;
• submit required assignments in a timely manner;
• take exams when scheduled, unless rescheduled under 310.01;
• act in a respectful manner toward other students and the instructor and in a way that does not detract from the learning experience; and
• make and keep appointments when necessary to meet with the instructor.

MSU Drug and Alcohol Policies

Per the Code of Conduct for students, no student may come to class under the influence of drugs or alcohol, as that would not be Fostering a healthy, safe and productive campus and community. See Alcohol and Drug Policies Website for more information. In particular, note:

As a federally-funded institution, we must adhere to all federal laws when it comes to alcohol and drug use or distribution. This holds true for marijuana as well. Using or distributing marijuana on or off campus is a violation of our code of conduct even if a student has a medical card or comes from a state in which marijuana is legal or has been decriminalized.

As noted, the University's alcohol and drug policies apply off campus. Using drugs and/or alcohol and returning to your residence hall in a disruptive fashion- either via odor, noise, destruction, etc- can lead to residence life policy and alcohol or drug policy violations. Remember, not everyone wants to hear or smell you.

## Resources

### Technical Resources

- [Git Udacity
  Course](https://www.udacity.com/course/how-to-use-git-and-github--ud775)
- [Forking in Git](https://help.github.com/articles/fork-a-repo/)
- [Markdown](http://daringfireball.net/projects/markdown/)
- [More Markdown](https://www.markdowntutorial.com/)
- [Inkscape Can Tutorial](http://tavmjong.free.fr/INKSCAPE/MANUAL/html/SoupCan.html)
- [Plagiarism Tutorial](http://www.lib.usm.edu/legacy/plag/pretest_new.php)]
- [Ott's 10 Tips](http://www.ms.uky.edu/~kott/proof_help.pdf)
- [Big-O, Intuitive Explanation](https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/)

### Course Textbook(s) 

- [EH] Edelsbrunner and Harer, Computational Topology. AMS, 2010. 


## Schedule

### Week 1 (14,16 January)
- Topics: Introduction to Topology: Sets, Functions, Neighborhoods, and More!
- Reading: TBD 
- HW-1 assigned, due 1/21.
- 16 Jan: [Dr. David Millman](https://www.cs.montana.edu/dave/mySite/index.html) will discuss the point-in-pologyon and side-of-line

### Week 2 (21,23 January)
- Topics: Graphs and Connectivity: Properties and Algorithms 
- Reading: EH, Section I.1 

### Week 3 (28,30 January)
- Topics: Curves, Knots, and Links 
- Reading: EH, Chapter I 

### Week 4 (4,6 February)
- Topics: Surfaces and Orientability 
- Reading: EH, Chapter II

### Week 5 (11,13 February)
- Topics: Surfaces and Orientability (cont.)

### Week 6 (18,20 February)
- Topics: Complexes: Alpha, Vieotoris-Rips, Cech, and more! 
- Reading: EH, Chapter III 

### Week 7 (25,27 February)
- Topics: (Discrete) Morse Theory 
- Reading: TBD 

### Week 8 (3,5 March)
- Topics: Homology 
- Reading: EH, Chapter IV

### Week 9 (10,12 March)
- Topics: More Homology 
- Reading: EH, Chapter VII
- Literature Review Due! (13 March)

### Week 10 (17,19 March)
- *SPRING BREAK* 

### Week 11 (24,26 March)
- Topics: Back from Break Topology Review 
- 26 March - problem session

### Week 12 (30 March, 2 April)
- Topics: Cohomology and Other Dualities
- Reading: EH, Chapter V
- 26 March - problem session

### Week 13 (7,9 April)
- Topics: Persistent Homology & Stability
- Reading: EH, Chapters VII, VIII

### Week 14 (14,16 April)
- Topics: Reeb Graphs 
- Reading: EH, Section VI.4; TBA 

### Week 15 (21,23 April)
- Topics: Topological Descriptors & Statistics
- Reading: TBA

### Week 16 (28,30 April)
- Group Presentations 

### Finals Week
- 4 May 2020, 14:00-16:50 (TODO: Please Confirm)

--- 

This syllabus was created, using wording from previous courses that I have
taught, as well as David Millman's Spring 2018 Graphics course.  Thanks, Dr.
Millman!