ANNOUNCEMENTS

• Solution 6 is now available below.
• If you would like a few practice questions, see here.
• Even though there are no assignments left, you can still come to an office hour to discuss the material. There will be two office hours on Monday December 5th. Karlming will have an office hour at 3pm and Cosmin will have an office hour at 5pm. No other hours will take place.
• Want to see how to write a proper solution to an assignment? Click here. Thank you C!
• And this is how you take the exam. Thank you S and V!!!

COURSE DESCRIPTION

CS/Math 6a introduces several basic combinatorial and algorithmic topics.  These include generating functions, graph theory with a focus on graph algorithms, cryptography (including some elementary number theory), and an introduction to algebraic structures.

Extras

Still not convinced that Euler is amazing? Watch the first half of this Youtube video. The second half we will study in more detail later in the course.

Is the NSA reading your RSA-encrypted messages? Possibly.

A youtube video about partitions.

SCHEDULE

MWF, 13:00 - 13:55, 201 E. Bridge.

INSTRUCTORS

Adam Sheffer
HARRY BATEMAN INSTRUCTOR IN MATHEMATICS
276 Sloan
626-395-4347
Office hours: 4pm Mondays at Sloan 276.

TA's

Cosmin Pohoata (head TA), apohoata@caltech.edu, Kellog 307.
Office hours: 4pm and 5pm Mondays at Sloan 153.

Siqi He she@caltech.edu, Sloan 356.

Karlming Chen kchen7@caltech.edu, Sloan 158.
Office hours: 8pm Mondays at Sloan 153.

HOMEWORK POLICIES

• Please staple a blank page containing only your name at the front of the assignment.
• You are encouraged to work in groups on the assignments. However, you are required to write your solution on your own and not to look at written solutions of other students.
• You may not rely on any related tools that we did not study in class (such as the DFS algorithm). Using such tools to solve a problem may result in zero points. If you are not sure whether you are allowed to use something, please ask someone from the staff of the course.
• There is no need to formally prove anything, unless the question specifically asks for a proof. However, you do need to explain what you did. The grader needs to see that you did not just write an algorithm/answer without understanding how to get to it or why it works.
• Unless stated otherwise, every given graph is simple.
• There is no need to find the running time of the algorithms that you create in your homework. However, the running times must be polynomial in the size of the input.
• There is no need to write pseudocodes for algorithms - we even prefer a description in words.
• There is no need to reprove anything that was proven in class. On the other hand, you are not allowed to refer to any other sources, including the course's text book (answers of the form "The proof can be found in page X of the book" will receive no points).
• Make sure that you submit your assignments in the LOCKED 6a mailbox, and not in the open box for graded assignments.

TEXTBOOKS

Discrete Mathematics / Norman Biggs, 2nd edition, Oxford.  ISBN:  978-0-19-850717-8

Introduction to Algorithms / Cormen, Leiserson, Rivest, and Stein. Some of the algorithms are not written in detail in Biggs' book, and then more details can be found in this book. On the other hand, this book is too advanced for us since it includes running time analysis for the various algorithms. Feel free to completely ignore these.

LECTURE NOTES

The book covers most of the material but not all of it. Also, some of the relevant sections contain various topics that are not part of the course. Thus, please do not rely only on the book sections stated below. To see what is missing/redundant, compare with the lecture notes. Books sections starting with an "A" refer to the 2nd edition of the book "introduction to algorithms" (see above).

HOMEWORK

Unless stated otherwise, the assignments are due by noon on Tuesdays. We prefer that you send emails concerning an assignment to the TA that is in charge of that assignment (for example, when asking for a clarification, asking for a late submission, complaining about the grading, or reporting a mistake) . If you have any special issues, you are always welcome to email Adam. You may also ask any of these questions in any of the office hours (issues with the grading should go to the TA in charge or to Adam).

EXAMS