Algorithmic Graph Theory

Instructor:	Dr. André Kündgen	akundgen@csusm.edu
Lecture :	TR 4:00-5:15 PM	Room 308, Science Hall 2
Office hours:	R 2:45-3:45 PM	Room 339 Science Hall 2
	(M 1:15-2:15 PM	& W 9:30-10:30 AM)

Course Announcements:

• 12/06: The final exam is now complete (see the link below). Do 5 out of the 6 problems, and ask by email if anything is unclear.
• 12/05: The last question for the Final exam will be announced tomorrow.
• 10/27: Tentative schedule of talks

  11/14	Serena	NP-complete "puzzles"
  11/21	Janina	Matchings in general graphs
  11/23	Thanksgiving	No class
  11/28	Michael	Algorithmic questions for tournaments
  11/30	Josh	Coloring graphs in the plane
  12/5	Jaime	Sorting and lower bounds
  12/7	James	Quantum computing

• 10/11: The deadline on Assignment 3 has been extended to next week Tuesday.
• 10/5: Exam 1 Study guide.
• 9/24: Student presentations
  • Every student (graduate or undergraduate) will have a full 75-minute class period to talk about a topic of his/her choice. It is never to early to start thinking about topics.
  • Every talk should have an algorithmic component, such as an actual algorithm or a complexity result. Talk to me about this before you get too deep into a topic!
  • Our book is one good source of topics, but there are other good books, and there are also many good papers.
  • Possible dates for talks are November 7,9,14,16,21,28,30 and December 5,7.
  • If you already know when you want to talk or what you would like to talk about, then tell me your plans. If you declare early, then you have priority.
• 9/24: The midterm will be on October 19.
• 8/31: HW 1 has now been posted, you have 2 weeks to do it. After todays lecture you should be able to do all questions, except 4, 5(e) and 6 -- these will require next Tuesdays lecture. You can also read page 44 on "BIG-OH" notation, and then you can attempt basically all questions.
• 8/31: Lectures 1 and 2 have been re-scanned in a format that should make them easier to read.
• 8/04: There are also office hours Mondays 1:15-2:15 and Wednesdays 9:30-10:30, but in these Pre-Calculus (MATH 125) students have priority.
• 8/04: The office hour will be Thursdays 2:45-3:45 or by appointment.
• 8/04: There are two very good books on graph theory that may prove helpful in this course:
  • Introduction to Graph Theory by D.B. West is a comprehensive, thorough book that is intended as an undergraduate introduction to graph theory. It is not cheap, but the library has a copy and older editions are fine too.
  • Graph Theory by R. Diestel is also a very well written book. It is more advanced and selective in its material. This book is at the beginning graduate level and can be downloaded for free, even though a hard copy is also well worth it.
• 8/04: MathSciNet: On campus or remotely.
• 8/04: Universal grade change form.
• 8/04: This is where all course announcements will be posted, except for homework assignments (available on homework page) and lectures, exam solutions, and homework hints and solutions (available on WebCT).
• 8/04: Welcome to Math 542!