# Math 61: General Course Outline

## Course Description

**61. Introduction to Discrete Structures. (4)** Lecture, three hours; discussion, one hour. Requisites: courses 31A, 31B. Not open for credit to students with credit for course 180 or 184. Discrete structures commonly used in computer science and mathematics, including sets and relations, permutations and combinations, graphs and trees, induction. P/NP or letter grading.

## Course Information:

The following schedule, with textbook sections and topics, is based on 26 lectures. The remaining classroom meetings are for two midterm exams and review. These are scheduled by the individual instructor. Often there are midterm exams about the beginning of the fourth and eighth weeks of instruction.

Math 61 has two goals. One goal is the introduction of certain basic mathematical concepts, such as equivalence relations, graphs, and trees. The other goal is to introduce non-mathematicians to abstraction and rigor in mathematics. Finite graphs are well-suited to this purpose. Exercises asking for simple proofs are assigned where appropriate.

Roughly half of the students in Math 61 are engineering students in Computer Science. Of the remaining students, many are in business and economics. Relatively few (about one out of ten) have declared as Mathematics majors.

Math 61 is offered each quarter. Recent enrollment statistics are given in the following table.

## Textbook(s)

R. Johnsonbaugh, *Discrete Mathematics (8th Edition) *, Prentice-Hall.

Outline update: I. Neeman 7/12

## Schedule of Lectures

Lecture | Section | Topics |
---|---|---|

1 |
2.4 |
Mathematical induction |

2 |
1.1, 3.1 |
Sets, functions |

3 |
3.2 |
Sequences and strings |

4 |
3.3 |
Relations |

5 |
3.4, 5 |
Equivalence relations, matrices of relations |

6 |
6.1 |
Basic counting principles |

7 |
6.2 |
Permutations and combinations |

8 |
6.3 |
Generalized permutations and combinations |

9 |
6.7 |
Binomial coefficients |

10 |
6.8 |
Pigeonhole principle |

11 |
7.1 |
Recurrence relations |

12-13 |
7.2 |
Solving recurrence relations (including material in exercises 40-46) |

14 |
8.1 |
Examples of graphs |

15 |
8.2-3 |
Paths and cycles |

16 |
8.4 |
Shortest-path algorithm |

17 |
8.5 |
Representation of graphs |

18 |
8.6 |
Isomorphisms of graphs |

19 |
8.7 |
Planar graphs |

20 |
9.1 |
Examples of trees |

21 |
9.2 |
More trees |

22 |
9.3-4 |
Minimal spanning trees |

23 |
9.5 |
Binary trees |

24-25 |
7.3, 9.7 |
Decision trees, sorting (including merge sort from 7.3) |

26 |
9.8 |
Isomorphic trees |