# Math 213: Basic Discrete Mathematics, Fall 2008

## Section G1 meeting MWF 3:00-3:50 in 243 ALTGELD

### Introduction

• Instructor: John Mackay
Office: 337 Illini Hall,
Phone: (217)244-4697,
Email: jmmackay at illinois dot edu
• Course website: http://www.math.uiuc.edu/~jmmackay/08f-213.html
• Office hours: M 2:00-2:50, W 4:10-5:00 and by arrangement.
• Textbook: Kenneth H. Rosen: Discrete Mathematics and Its Applications, Sixth Edition
(If you have the fifth edition you will probably be OK, but you will have to do the legwork to make sure you are doing the correct homework problems from the correct sections.)
• Homework assignments and week-to-week schedule: See website.

Question: Can you find a way, starting from a place of your choosing, to cross all the bridges in the city of Königsberg? You are only allowed to cross each bridge once.

This question, and its solution, is best understood by introducing a discrete structure (called a graph). As we will see, problems with a discrete structure are particularly common in computer science and related fields. In this course we will cover the basics of discrete mathematics.

We will study objects such as sets, functions, relations, graphs and trees, and you will learn techniques of counting (harder than you might think) and probability. Along the way, we'll see the basic methods of proof used in mathematics and logic. Finally, in all these areas, we will emphasise ways -- algorithms -- to actually work out problems, and study how efficient these algorithms are.

### Homework and quizzes

There will be weekly homework assignments, collected at the start of class on Fridays. The first homework assignment will be due the end of the second week of class.

You are free (and encouraged) to work with fellow students on the homework problems. However, you should write up your final solutions by yourself. If your solutions to an assignment resulted from discussions with your fellow students, you should list their names at the end of your assignment. (It is good to get in the habit of giving credit where credit is due.)

Your lowest homework score will be dropped.

Most weeks there will be a short (~10 minute) quiz at the start of class on Friday.

### Exams

There will be three hour long exams in class, and a final. The class exams are set to be on October 1, November 5 and December 3.

The first class exam will cover material through section 5.2. The second class exam will cover material from 5.3 through to the end of Chapter 7. The third class exam will cover material from Chapters 8, 9 and 10.

(Note that this is provisional and may be adjusted as the semester progresses.)

The final will be on Friday, December 12 from 7:00-10:00 PM, and will cover all the material we have seen on the course.