# CS 4850

## Mathematical Foundations for the Information Age

Location: Online

Lecture: MWF 1:25pm - 2:15pm

Instructor: John Hopcroft

Office Hours: By Appointment

Textbook (2019): Mathematical Foundations for the Information Age

## Announcements

**4/06**: Online instruction officially starts.**2/12**: Review session for MT1 on 2/19 in Phillips 101 at 7:30 pm.**1/22**: Note: OH start next week.**1/22**: Update two: Class will be scheduled normally on Friday 1/24, with Eric covering for Prof. Hopcroft.**1/22**: Update: Class canceled both Wednesday 1/22 and Friday 1/24 due to instructor sickness.

## Concepts

This course will focus not only on Discrete Math, but also Probability Theory and Numerical Methods. In this light, materials covered in **CS 2800: Discrete Structures**, **MATH 1910: Calculus for Engineers** or **MATH 1920: Multivariable Calculus for Engineers**, and **MATH 2210: Linear Algebra** or **MATH 2940: Linear Algebra for Engineers** are recommended prerequisites for the course. Students with a particular weakness in one of these areas are highly encouraged to come to office hours or request tutoring early on.

We will cover the mathematical foundations of data science, machine learning, and other mathematically-intensive areas of Computer Science. A sparse sampling of fundamental concepts includes High-Dimensional Spaces, the Singular Value Decomposition, Random Walks, Machine Learning, Massive Data, Clustering, and Topic Models. For a complete list of concepts covered in this course, please see the textbook's table of contents. We hope to cover most, if not all, of the material in the textbook by the end of this semester.

The textbook used in this class is the 2019 edition of **Mathematics for the Information Age by Avrim Blum, John Hopcroft and Ravindran Kannan **. The the book is found here. There are many different editions of the book online which may have different numbers for the chapter questions. Please refer to this most recent edition for correct HW questions.

Grades will be determined holistically. If a student does poorly but brings his/her later grades up, we will give the later test scores more weight as this shows hard work on the student's part.

## Online Instruction

Due to campus shutdown, online instruction will start April 6. The following changes have been made to the course.

**Lectures** will be recorded and uploaded to Cornell's video on-demand system.
Links to these lectures will be posted during regular instruction time.
We have found the recorder in G01 to be somewhat blurry, and have done our best to make them clear.
We have set up a class Piazza, and a discussion slot for each lecture will be set-up.
Students are highly encouraged to participate.
**Homeworks** will be shorter. Two problems a week, due Mondays on Gradescope.
We now require HW to be typeset, though figures and diagrams may be drawn in.
**Exams** will not occur for the rest of the semester.
**Office hours** will be held virtually on Zoom. Students will call into the links provided.

## Lectures

Lecture 1, April 6 | Topic: Deep learning | Link |
---|---|---|

Lecture 2, April 8 | Topic: Algorithms for massive data | Link |

Lecture 3, April 10 | Topic: Algorithms for massive data | Link |

Lecture 4, April 13 | Topic: Algorithms for massive data | Link |

Lecture 5, April 15 | Topic: Random graphs | Link |

Lecture 6, April 17 | Topic: Random graphs | Link |

Lecture 7, April 20 | Topic: Topic modeling and non-negative matrix factorization | Link |

Lecture 8, April 22 | Topic: Ranking | Link |

Lecture 9, April 24 | Topic: Compressed Sensing | Link |

Lecture 10, April 27 | Topic: Wavelets | Link |

Lecture 11, April 29 | Topic: Electrical Networks | Link |

## Homework

HW1 | Due Date: January 31 | Problems: 2.11, 2.12, 2.13, 2.14, 2.15 |
---|---|---|

HW2 | Due Date: February 7 | Problems: 2.22, 2.23, 2.25, 2.31, 2.33. Note: we will be especially strict about clarity for 2.25. |

HW3 | Due Date: February 14 | Problems: 2.16, 2.37, 2.40, 2.48, 3.3 |

HW4 | Due Date: February 21 | Problems: 3.7, 3.9, 3.12, 3.14, 3.18 |

HW5 | Due Date: February 28 | Problems: 3.5, 3.6, 3.28, 3.32, 3.33 |

HW6 | Due Date: March 6 | Problems: 4.3, 4.6, 4.7, 4.9, 4.22 |

HW7 | Due Date: March 13 | Problems: 5.4, 5.5, 5.8, 5.10, 5.12 |

HW8 | Due Date: April 13 | Problems: PDF |

HW9 | Due Date: April 20 | Problems: PDF |

HW10 | Due Date: April 27 | Problems: PDF |

HW11 | Due Date: May 4 | Problems: PDF |

** HW Notes: **

Questions for the HWs are from the Blum, Hopcroft and Kannan textbook (see above). Students are encouraged to work together but each must submit their own HW (written in their own words). Students must understand everything they turn in, and must show all their work to receive substantial credit. This includes all the relevant parts of their code for the coding questions and the assumptions made / parameters used that were not specified in the question text. Homeworks are due via Gradescope on the due date listed inside the chart above.

HW solutions must typeset in LaTeX or a word processor such as Microsoft Word. For graphs or diagrams, space can be left in the document, and then the figure neatly hand-drawn in, although we recommend Tikz for students using LaTeX. HW will be graded on BOTH correctness and neatness. In particular, 20 percent of the HW grade depends on clarity of writing, and 10 percent of the HW grade depends on the style of solution and proof; if we cannot understand your solutions, we cannot give you points!

** HW Regrade Policy: **

Regrade requests will be considered if:

## Course Staff

Professor | John Hopcroft | Office hours by appointment only | |
---|---|---|---|

TA | Max Jiang | OH Tuesday 5:30-6:30pm | Zoom |

TA | Karen Zhou | OH Wednesday 11:15am-12:15pm | Zoom |

TA | Youngjin Kim | OH Wednesday 1:00-2:00pm | Zoom |

TA | Samuel Sorenson | OH Thursday 12:00-1:00pm | Zoom |

TA | Anmol Kabra | OH Thursday 5:30-6:30pm | Zoom |

TA | Eric Hans Lee | OH Friday 3:00-4:00pm | Zoom |

**Please email ehl59@cornell.edu for any administrative questions/inquiries.** Students struggling in the class or lacking certain background knowledge may opt for private tutoring sessions, which have been highly recommended by past students and have often greatly improved a student's academic performance. Enrolling for a private tutoring session can be done by emailing the private tutors. Students who are not as mathematically mature and want tutoring in a particular mathematical subject e.g. linear algebra, please contact

`qj46@cornell.edu`

. Students who want private tutoring in a class-related topic should contact `ywk2@cornell.edu`

.
**This course follows the Cornell University Code of Academic Integrity. Each student in this course is expected to abide by the Cornell University Code of Academic Integrity. Any work submitted by a student in this course for academic credit will be the student's own work. Violations of the rules (e.g. cheating, copying) will not be tolerated.