10-607, Fall 2021

Computational Foundations for Machine Learning


Key Information

Mondays and Wednesdays: 3:05 - 4:25 pm, GHC 6115. Lecture sessions will be recorded and posted on Canvas.
Lecture attendance in person is expected and will be the primary means to earn participation points. Quizzes will also take place during lecture time.

Fridays: 3:05 - 4:25 pm, GHC 6115.
See Recitation section for more details.

Dorothy Holland-Minkley and Marcie Baker

Kellen Gibson and Ian Char, see the 607 Staff page

Grades will be collected in Canvas.
Assignments 50%, Participation 10%, Quizzes 15%, Final 25%

There is no required textbook for this course. Whenever possible, we'll post links to readings for an alternate presentation of some of the course material.

We will use Piazza for questions and any course announcements.

Students will turn in their homework electronically using Gradescope.

10-606/607 Course Descriptions


10-606 provides a place for students to practice the necessary mathematical background for further study in machine learning. Topics covered include probability (random variables, modeling with continuous and discrete distributions), linear algebra (inner product spaces, linear operators), and multivariate differential calculus (partial derivatives, matrix differentials). The course assumes some background in each of the above, but will review and give practice in each. (It does not provide from-scratch coverage of all of the above, which would be impossible in a course of this length.) Some coding will be required: the course will provide practice with translating the above mathematical concepts into concrete programs.


This course provides a place for students to practice the necessary computational background for further study in machine learning. Topics covered include computational complexity, analysis of algorithms, proof techniques, optimization, dynamic programming, recursion, and data structures. The course assumes some background in each of the above, but will review and give practice in each. (It does not provide from-scratch coverage of all of the above, which would be impossible in a course of this length.) Some coding will be required: the course will provide practice with translating the above computational concepts into concrete programs.

Relationship between 10-606 and 10-607

These two minis are intended to prepare students for further study in machine learning – particularly for taking 10-601 and 10-701. One of the courses (10-606) focuses on mathematical background, and the other course (10-607) focuses on computational background. Most students take both mini courses, but this is not required. 10-606 is not a prerequisite of 10-607.


Below is a summary of the background required for these two courses (consistent with the previous offering of the courses):


  • We’re assuming mathematical maturity: you should be familiar with the idea of derivations and proofs, and of building formal representations for objects given their English­ language description.
  • We’ll assume that you can take scalar derivatives.
  • We’ll assume that you’ve seen real vector spaces and matrices (linear operators) and know how to reason about things like matrix multiplication and solving systems of linear equations.
  • We’ll assume that you’ve seen sets and data types.
  • We’ll assume that you’ve worked with probabilities (e.g., conditioning, Bayes rule).
  • We will also assume familiarity with coding. The assignments and in-class activities will include some Python.
  • For the above topics, we intend to give complete definitions and/or resources to learn from, but often we will go over them quickly: we expect that most people will know a lot of the definitions, and will be willing to work outside of class to understand the ones they don’t know. So, for each topic that you’re unfamiliar with, you should expect to do some extra work; if you’re unfamiliar with several of them, that could make it hard to keep up.


  • We’ll assume you are comfortable with all the topics listed above for 10-606.
  • In addition, the first mini (10-606) is a recommended, but certainly not necessary, prerequisite. It is expected that some students will take 10-607 without 10-606. The material for 10-607 stands alone; however, the machine learning applications we consider may require the level of mathematical maturity of someone who has completed 10-606.

Please see the instructor if you are unsure whether your background is suitable for these courses.

Office Hours

See office hours on the calendar below.

Schedule (subject to change)

Dates Topic Slides / Notes Reading (optional)
10/18 Mon 1: Overview, Logic, Proofs pptx (inked) pdf (inked) handout.pdf (sol) Mary Radcliffe notes on Propositional Logic
10/20 Wed 2: Proof Techniques pptx (inked) pdf (inked) whiteboard.pdf Geoff Gordon notes on Logic and Proofs
10/25 Mon 3: Proof Techniques, Perceptron Algorithm pptx (inked) pdf (inked) whiteboard.pdf Hal Daumé, Course in Machine Learning, 4.1-3
10/27 Wed 4: Application: Perceptron Mistake Bound pptx (inked) pdf (inked) handout.pdf (sol) Hal Daumé, Course in Machine Learning, 4.5
Geoff Gordon notes on Perceptron Mistake Bound
11/1 Mon 5: Computational Complexity pptx (inked) pdf (inked) Aho and Ullman, Foundations of Computer Science, 3.1-3.8
CMU 15-112: Efficiency
11/3 Wed 6: Computational Complexity Proofs pptx (inked) pdf (inked) handout.pdf (inked) notebook.ipynb
11/8 Mon 7: Recursion pptx (inked) pdf (inked) Aho and Ullman, Foundations of Computer Science, 2.1-2.4, 2.6-2.9
CMU 15-112: Recursion
11/10 Wed 8: Proof by Induction, Divide and Conquer, & Dynamic Programming pptx (inked) pdf (inked)
notebook.ipynb (sol)
CMU 15-210: Divide & Conquer
CMU 15-112: MergeSort
CMU 15-210: Dynamic Programming
CMU 15-112: Memoization
11/15 Mon 9: Data Structures for ML Algorithms pptx (inked) pdf (inked)
Aho and Ullman, Foundations of Computer Science, Ch. 5
11/17 Wed 10: Data Structures for ML Algorithms pptx (inked) pdf (inked)
Aho and Ullman, Foundations of Computer Science, Ch. 9
11/22 Mon 11: Application: Graphical Models pptx (inked) pdf (inked)
11/24 Wed No class: Thanksgiving
11/29 Mon Canceled
12/1 Wed 12: Wrap-up Workshop pptx (inked) pdf (inked)
12/10 Fri FINAL EXAM 5:30-8:30 pm, location TEP 2700 Review Slides (pptx, pdf)


Recitations are on Friday 3:05-4:25 pm, GHC 6115. Recitations might not be recorded. Recitation attendance is recommended to help solidfy weekly course topics. That being said, the recitation materials published below are required content and are in-scope for quizzes and exams.

Dates Recitation Slides/Handouts Code/Demo
10/22 Fri Recitation 1 CoLab (Solutions)
10/29 Fri Recitation 2 worksheet (Solutions)
11/5 Fri No class Community Engagement
11/12 Fri Recitation 3 CoLab (Solutions)
11/19 Fri Recitation 4 CoLab (Solutions)
11/26 Fri No class Thanksgiving
12/3 Fri Recitation 5 code CoLab (Solutions)

Quizzes and Exams

Quizzes will take in person during a portion of the lecture time. Quizzes will be announced at least two days before the quiz takes place.

The final exam will be on Friday, 12/10, 5:30-8:30 pm, location TEP 2700.


There will be approximately three homework assignments. Homework assignments will often have both written and online components. Follow the instructions in the Piazza post when homework is announced to make sure complete all necessary components. Due dates are tentative for any assignments that haven't been released yet.

Assignment due dates

Assignment Link (if released) Due Date
HW 1 Gradescope, hw1_blank.pdf, hw1.zip 11/3 Wed, 11:59 pm
HW 2 Gradescope, hw2_blank.pdf, hw2.zip 11/22 Mon, 11:59 pm
HW 3 Gradescope, hw3_blank.pdf, hw3.zip 12/3 Fri, 11:59 pm



Grades will be collected and reported in Canvas. Please let us know if you believe there to be an error the grade reported in Canvas.

Final scores will be composed of:

  • 50% Homework assignments
  • 10% Participation
  • 15% Quizzes
  • 25% Final exam

Participation Grades

Participation will be based on the percentage of in-class polling questions answered:

  • 10% for 80% or greater poll participation
  • 7.5% for 70%
  • 5% for 60%
  • 2.5% for 50%

Correctness of in-class polling responses will not be taken into account for participation grades.

It is against the course academic integrity policy to answer in-class polls when you are not present in lecture. Violations of this policy will be reported as an academic integrity violation. Information about academic integrity at CMU may be found at https://www.cmu.edu/academic-integrity.

There will be a few other means to collect participation points; stay tuned to Piazza for more details.

Final Grade

We convert final course scores to letter grades based on grade boundaries that are determined at the end of the semester. What follows is a rough guide to how course grades will be established, not a precise formula — we will fine-tune cutoffs and other details as we see fit after the end of the course. This is meant to help you set expectations and take action if your trajectory in the class does not take you to the grade you are hoping for. So, here's a rough, very rough heuristics about the correlation between final grades and total scores:

  • A: above 90%
  • B: 80-90%
  • C: 70-80%
  • D: 60-70%

Grades for graduate students will be broken down further with +/- distinctions. See CMU grading polices for more information.

The above heuristic assumes that the makeup of a student's grade is not wildly anomalous: exceptionally low overall scores on exams, quizzes, and assignments will be treated on a case-by-case basis.

Precise grade cutoffs will not be discussed at any point during or after the semester. For students very close to grade boundaries, instructors may, at their discretion, consider participation in lecture and recitation, exam performance, and overall grade trends when assigning the final grade.

Late Policy

Homework assignments:

  • 4 slip days across all assignments
  • Use up to two per assignment
  • Slip days are counted by the granularity of days. For example, if you turn in your assignment 30 minutes after the deadline, that will count as one full slip day.
  • You may use these at your discretion, but they are intended for minor illness and other disruptive events outside of your control, and not for poor time management
  • You are responsible to keep track of your own slip days. Gradescope will not enforce the total number of slip days
  • Homework submitted after these two slip days or submitted by a student without any slip days remaining will be given a score of 0.

Aside from this, there will be no extensions on assignments in general. If you think you really really need an extension on a particular assignment, contact the instructor as soon as possible and before the deadline. Please be aware that extensions are entirely discretionary and will be granted only in exceptional circumstances outside of your control (e.g., due to severe illness or major personal/family emergencies, but not for competitions, club-related events or interviews). The instructors will require confirmation from University Health Services or your academic advisor, as appropriate.
Nearly all situations that make you run late on an assignment homework can be avoided with proper planning — often just starting early. Here are some examples:

  • I have so many deadlines this week: you know your deadlines ahead of time — plan accordingly.
  • It's a minute before the deadline and the network is down: you always have multiple submissions - it's not a good idea to wait for the deadline for your first submission.
  • My computer crashed and I lost everything: Use Dropbox or similar to do real-time backup - recover your files onto AFS and finish your homework from a cluster machine.
  • My fraternity/sorority/club has that big event that is taking all my time: Schedule your extra-curricular activities around your classes, not vice versa.

Collaboration Policy

We encourage you to discuss course content and assignments with your classmates. However, these discussions must be kept at a conceptual level only.

  • You may NOT view, share, or communicate about any artifact that will be submitted as part of an assignment. Example artifacts include, but are not limited to: code, pseudocode, diagrams, and text.
  • You may look at another student's code output and discuss it at a conceptual level, as long as it is not output that appears directly in the homework submission.
  • You may look at another student's code error messages and discuss what the error means at a conceptual level. However, you may NOT give specific instructions to fix the error.
  • All work that you present must be your own.
  • Using any external sources of code or algorithms in any way must have approval from the instructor before submitting the work. For example, you must get instructor approval before using an algorithm you found online for implementing a heuristic function in a programming assignment.

Violations of these policies will be reported as an academic integrity violation. Information about academic integrity at CMU may be found at https://www.cmu.edu/academic-integrity. Please contact the instructor if you ever have any questions regarding academic integrity or these collaboration policies.

Accommodations for Students with Disabilities

If you have a disability and have an accommodations letter from the Disability Resources office, we encourage you to discuss your accommodations and needs with us as early in the semester as possible. We will work with you to ensure that accommodations are provided as appropriate. If you suspect that you may have a disability and would benefit from accommodations but are not yet registered with the Office of Disability Resources, we encourage you to visit their website.

Statement of Support for Students’ Health & Well-being

Take care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, getting enough sleep, and taking some time to relax. This will help you achieve your goals and cope with stress.
All of us benefit from support during times of struggle. There are many helpful resources available on campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is almost always helpful.
If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit their website at http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.
If you have questions about this or your coursework, please let us know. Thank you, and have a great semester.