Syllabus, Math 154A, Spring 2021

Discrete Math and Graph Theory

Instructor: Ioana Dumitriu

E-mail: [email protected]

Course website: www.math.ucsd.edu/∼dumitriu/m154.html All information in this syllabus can be found in more detail on the course website.

Office Hours (via Zoom): MW, 2pm-3:30pm; F, 2-3pm; Thu, 4-6pm (shared with Math 170)

Textbook: Introduction to Graph Theory, Jacques Verstraete Available as a PDF on Canvas.

TAs: Qingyuan Chen, Nathan Liittschwager, Shubham Sinha (see course website).

About this class. Math 154 will be an introduction to graph theory. We will cover a number of topics including, basic definitions, trees, colorings, planarity, matchings, and some algorithms related to these topics. We will prove theorems (including some that validate algorithms), find equivalent characterizations of graph properties, and occasionally see some applications.

Lectures: There will be pre-recorded “lectures”, which will be made available each week; each “lecture” will be a collection of one or more videos where I will be explaining one topic, and each lecture will roughly cover one or more chapters from the textbook. The videos will include slides and audio. You should watch these videos and then attend the Zoom office hours to ask questions, clarify concepts, see more examples worked out, discuss homework, etc.

    In addition to lectures, I will be posting lecture notes, covering the same material.

    You are responsible for watching/reading the lectures and lecture notes. Please do this before attending office hours. Although I will offer a brief summary of the most important topics covered in lecture during office hours, I will not repeat proofs. Instead, I will be happy to answer questions, clarify notions, do examples, etc.

Homework: will be assigned weekly by posting them BOTH on the website and in Canvas. Solu-tions will be posted ONLY in Canvas.

    Homework will be due on Thursdays, by 11pm. Late homework will not be accepted, BUT the lowest homework grade will be dropped from the final grade calculation.

    All homework will be turned in using Gradescope AND will have to be in .pdf form (one single file for each homework). For more information on Gradescope, please go to the course website and click on the Gradescope tab.

    For write-up and collaboration guidelines, please go to the course website and read all instructions. It is your responsibility to know what is allowed and what is not.

    Note: Homework 0, due Thursday, 04/01 (no joke!), includes a simple Canvas quiz that is meant to make sure you read the syllabus, website, and are familiar with the rules and logistics. The rest of it will ONLY be graded for completion; it is meant to familiarize you with Gradescope. Nevertheless, I suggest you do your best to answer all questions!

Exams: There will be three quizzes, on 04/16, 05/14, and 05/28, respectively. Each will take 30 minutes; they will be Canvas-based, multiple-choice, randomized, and unproctored. Each will be subject to the Academic Integrity Rules (see the website for more info). You will have a time-window (TBA) to take the quiz, but once you start, you will have 30 minutes to complete it.

    The midterm and final exam are scheduled for 04/28, respectively, 06/07. The midterm will take one hour, and the final will take two hours. There will be two possible synchronous options for each: to either take it during the ”regular” time, which means during class time for the midterm and during the announced time for the final, or to take it in the evening of the same day (this will be mostly for the students who are geographically located in Asia/Oceania, or for those with conflicts, and you will need to sign up for it). If for some (very good!) reason you need some alternative to both options, we will figure it out.

    For the midterm and final: you will have to download the exams from Canvas, solve them and write up your answers, and upload the answers to Gradescope at the end of your allotted time (you will be given 15 minutes to do this). In addition, you will have to submit a signed Academic Integrity Pledge alongside your solutions (I will provide the text of that Pledge).

    For each exam you will be allowed to use your lecture and discussion session notes, homework solutions, and textbook. No other notes, software, calculators, online resources, textbooks and NO HUMAN HELP will be allowed.

Grading. Your total grade will be computed as follows.

• 20% Homework, 10% each of the 3 Quizzes, 20% Midterm, 30% Final Exam

• 20% Homework, 10% each of the top 2 Quizzes, 25% Midterm, 35% Final Exam.

    If you become sick or your internet connection fails and you cannot take the final exam, and had up to that point passing grades, you will get an Incomplete (see below).

Incomplete Grades. The only way to obtain an Incomplete is if a student had been doing satis-factory work up until the final exam, and then misses the final exam because of a good (preferrably documented) excuse. If the excuse is undocumented, it will be up to the instructor to decide whether to grant the Incomplete.

Discussions. We encourage you to follow and participate in discussions using Piazza. The TAs and I will be monitoring and answering the questions raised there.