# 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