Department of Mathematics

CMSE 890-002: Fast and Memory Efficient Algorithms for Big Data

Instructor: Mark Iwen
Time and Place: MWF 11:30 am -- 12:20 pm via Zoom
Physical Office: C342 WH
Office Hours: Wed. and Fri. at 12:30 pm (Zoom link for these), Wed. at 4:00 pm (Zoom link for this), and by appointment

Topics covered will include fast linear Johnson-Lindenstrauss (JL) embeddings and their applications, small space algorithms for approximate counting problems, metric space embeddings and their applications, and randomized numerical linear algebra for large scale calculations.

Ethics, Fairness, Profiling, and Privacy:

The algorithmic techniques taught in this class can be used together with large datasets to do potentially unethical things. I am often disturbed by the ideas I myself have and hear about concerning the type of profiling and inference that fast methods applied to the large amounts of personal data available about each and every one of us online could potentially enable. I encourage all students who take this class to keep ethics, privacy, and fairness issues in mind at all times. If you are new to thinking about such issues I have a few recommended videos and articles to watch/read below to help get you started:

A video discussing surveillance capitalism and related issues See Thomas Strohmer's 1W-MINDS talk, April 30, 2020.
A few articles on China's social credit score system in Time, in The Atlantic, and in The Economist.
A couple articles about the NSA collection of US citizen's data in The Guardian and in Forbes.
An article about racism, algorithms, and machine learning in The New Republic.

These issues are complex and nuanced. Citizens of every country, state, and region must be vigilant, informed, and brave enough to ask questions if we want to make sure that technology remains a benefit to ourselves and society at large as opposed to a self-inflicted curse.

Course website for CMSE890-002:

The course website has the course schedule, the syllabus, and supplementary reading. Papers covered in class will be posted there.


This course has no textbook. Instead we will be covering material from several papers and book chapters during the semester. These resources are linked to on the Topics Covered page.


Exercises will be assigned in class most days. They will *not* be collected or checked other than as part of the final oral exam for the class (see below) if the student has not chosen to do a project.

Alternatively, students may elect to work on projects (approved in advance by the instructor) instead of completing the homework assignments. A written report on the project will then be required before the end of the semester which will be defended as part of the final oral exam. The written project report will count for all the homework assigned while the student was completing their optional and instructor approved research project.

Students are encouraged to work with their peers on homework assignments. Math is a collaborative discipline and two or three minds are often better than one. However, your final homework solutions must be written up individually in your own words and then kept to help you during the final oral exam. The solutions will be useless to you if you don't understand how they work!

Final Oral Exam:

Students must either meet with the instructor in person (if classes are in session, all parties wearing a mask, and staying socially distanced) or via zoom with the camera on. The instructor will then ask the student to solve several HW problems that were assigned in class, or else to discuss their project (if they chose to do one). The student's HW grade will be based on their participation in the exam, together with the quality of their solutions. The oral exam will be open notes -- it is expected that the student will consult their project report and/or personal homework solutions as part of the exam. In short, the purpose of this exam is to convince the instructor that the student completed ``most'' of the assigned homework (if they did not do a project), or else to describe their project, summarize their project's conclusions, as well as to answer instructor questions about their project.

The time and place (or link) for the final oral exam will be scheduled with the instructor individually, or in small groups. All exams should take place sometime between Dec. 7 and Dec. 18, 2020, and should be scheduled before Thanksgiving (Nov. 26). Each oral exam will be 30 minutes in duration for each student. The instructor reserves the right to waive this oral exam requirement, or to shorten its duration, for any student as necessary for scheduling purposes.

Feedback on the Course Notes:

Cullen Haselby will be writing up course notes in LaTeX and making his notes on each lecture available within a week of my having delivered it. You should read his notes when they become available and make sure that what we covered is correctly recorded and makes sense -- it will be a great way for you to cement your understanding of what we cover. In the process of reading his notes you will certainly see typos and have questions/comments that could improve the presentation.

In order to encourage you to give us feedback on the notes about typos, etc., you find while reading them, providing us feedback will determine part of your course grade. I will provide everyone in class with a link to a Google document where you can record your feedback, as well as a link to the most recent course notes. Every student should make at least 3 entries in the Google document giving feedback on the most recent version of the notes over the course of the semester. Of course, the more comments the better. The instructor reserves the right to consider additional comments above 3 made by any student as additional credit toward the class participation portion of that student's course grade.

Class Participation:

Please ask questions, answer questions, make constructive comments, and generally "show your face" by attending class with your video on if we are using zoom. In particular, participation in class requires that you regularly attend class. If anyone has reasons why they can not turn their video on during class they should talk to the instructor about it during the first week of the semester so that we can arrange for alternative accommodations.


Your final grade will be assigned based on the submitted homework (and/or project report), as well as on your participation (i.e., lecture attendance).

Some of the homework exercises will be challenging -- it is only expected that the submitted homework demonstrates effort.