Math 61: General Course Outline
Catalog Description
    61. Introduction to Discrete Structures. (4) Lecture, three hours; discussion, one hour. Requisites: courses 31A, 31B, Program in Computing 10A. Not open for credit to students with credit for course 113. Discrete structures commonly used in computer science and mathematics, including sets and relations, permutations and combinations, graphs and trees, induction, Boolean algebras. P/NP or letter grading.
Textbook
    R. Johnsonbaugh, Discrete Source: The Prentice Hall Custom Program for Discrete Mathematics, (Custom UCLA edition), Prentice-Hall.
Reviews & Exams
    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.
Schedule of Lectures

Lecture
Sections
Topics
1
1.7-8
Mathematical induction
2
2.1-2
Sets, functions
3
2.3
Sequences and strings
4
3.1
Relations
5
3.2-3
Equivalence relations, matrices of relations
6
6.1
Basic counting principles
7
6.2
Permutations and combinations
8
6.6
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

Comments

Outline update: I. Neeman 7/05

For more information, please contact Student Services, ugrad@math.ucla.edu.

UCLA Department of Mathematics                          Search     Home