Winter 2020, Prof. Tesler

Syllabus

INSTRUCTOR: Glenn Tesler

DESCRIPTION: This is a one-quarter introduction to basic concepts in graph theory. Topics include trees, walks, paths, and connectivity, cycles, matching theory, vertex and edge-coloring, planar graphs, flows and combinatorial algorithms, Hall's theorem, the max-flow min-cut theorem, Euler's formula, and the travelling salesman problem.

REQUIRED MATERIALS:

Textbook:Introduction to Graph Theoryby Prof. Jacques Verstaete (UCSD Department of Mathematics).

Download it from the front page of this class website. It may be revised during the course; please make sure you have the latest version.

COURSE REQUIREMENTS: Weekly homework, one midterm, one final. Your composite grade is comprised of homework (30% for all homeworks combined), the midterm (30%), and the final (40%).Slides:Lectures may be on the chalkboard or on slides. For lectures with slides, the slides will be posted on the Calendar page of the class website. You may want to print the slides in advance, 4 or 6 per sheet, to facilitate note-taking.

Homework:Homework assignments will be posted on the class website and are due Fridays at 1 p.m. (unless otherwise noted). You may turn them in at discussion section or at your T.A.'s homework box located in the basement of AP&M (from the AP&M lobby, go down the stairs one floor and take a left for the homework boxes). Graded homework will be handed back in discussion sections.

- Please write your name, student ID number, date, section number (A01-A03), and assignment number at the top of the first page.
- Show your work, and when relevant, circle your final answer.
- Please present your solutions in the order the problems are listed.
- On proof-oriented problems, you need to write a coherent proof.
- Certain problems will be selected for detailed grading. The remaining problems that are not graded in detail will count towards completeness points. You need to do all assigned problems, including any with full or partial solutions in the book.
Please staple the pages together.If you turn in loose pages, fold pages together, tear and twist the corners, use paper clips, etc., your pages will probably be separated or snagged into someone else's assignment, and you will not receive credit.- You may study with others currently enrolled in the class, but the work you turn in should be your own; do not just copy someone else's answer. That includes that you should not copy from an answer manual, answer key, or the internet.
You are strongly advised to attend section.Late homeworks will not be accepted.- Your lowest homework score (including 0 for not turning in an assignment) will be dropped.

Exams:There will be one midterm (Friday February 7, in class) and one final (Wednesday March 18, 3-6 p.m.). They will be comprehensive. Rules and material covered on each exam will be announced the prior week.No make up exams will be given.

ACCOMODATIONS: Students with special needs or disabilities must provide the instructor with an Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (OSD) in the first week of class, or as soon as possible if the situation arises later. Arrangements for UCSD Athletics teams, documented medical emergencies, etc., must be requested with appropriate documentation as soon as possible.Lectures and discussion sections:Attending lectures and discussion sections is a fundamental part of the course. You are responsible for all of the material presented whether or not it is discussed in the textbook or slides.

ACADEMIC INTEGRITY: Cheating will not be tolerated. See the UCSD Policy on Integrity of Scholarship.