061 - Spring 2011 - UCLA

Back.

Time: 2pm MWF for lectures and 2pm T or R for discussion.
Place: MS 5200.

E-mail: antieau@math.ucla.edu.
Phone: 310-825-3068.
Course webpage: www.math.ucla.edu/~antieau/201102-061.html

Office hours: 3-4 Monday, 1-2 Wednesday, and 1-2 Friday in my office, MS 6617D.
TAs: Victoria Noquez (noquez@math.ucla.edu) and Daniel Ram (danielram@math.ucla.edu).
TA office hours: Victoria: 1-2 Tuesday. Daniel: 2:50-3:20 Tuesday and Thursday, 1-2 Wednesday at SMC.

Book: Johnsonbaugh Discrete Mathematics, UCLA 7th Edition, Pearson.

Course outline:

03/28 - Mathematical induction (2.4).
03/30 - Sets and functions (1.1, 3.1).
04/01 - Sequences and strings (3.2).
04/04 - Relations (3.3).
04/06 - Equivalence relations and matrices of relations (3.4, 3.5).
04/08 - Basic counting principles (6.1).
04/11 - Permutations and combinations (6.2).
04/13 - Generalized permutations and combinations (6.3).
04/15 - Binomial coefficients (6.7).
04/18 - Pigeonhole principle (6.8).
04/20 - Recurrence relations (7.1).
04/22 - Midterm 1. Midterm 1 will cover the material through the pigeonhole principle. [sample1], [sample2], [midterm1 sols].
04/25 - Solving recurrence relations (7.2).
04/27 - Solving recurrence relations (7.2).
04/29 - Examples of graphs (8.1).
05/02 - Paths and cycles (8.2, 8.3).
05/04 - Shortest-path algorithm (8.4).
05/06 - Representation of graphs (8.5).
05/09 - Isomorphisms of graphs (8.6).
05/11 - Planar graphs (8.7).
05/13 - Examples of trees (9.1).
05/16 - More trees (9.2).
05/18 - Minimal spanning trees (9.3, 9.4).
05/20 - Midterm 2. Midterm 2 will cover recurrence relations and graphs. [sample], [sample problem solutions], [midterm 2 sols].
05/23 - Binary trees (9.5).
05/25 - Decision trees and sorting (7.3, 9.7).
05/27 - Decision trees and sorting (7.3, 9.7).
05/30 - Memorial Day holiday; no class.
06/01 - Isomorphic trees (9.8).
06/03 - Review.
06/08 - Final. The final will be cumulative. The final will take place in Franz 1178 from 11:30am to 2:30pm on Wednesday 8 June. [sample], [sample sols], [final sols].

Homework: (note that you should show all work to receive full credit.)

04/01 - [1.7: 1-5, 21]. [2.1: 1-10, 32, 59, 60]. [2.2: 1-5, 12] [scanned pdf].
04/08 - [3.2: 4, 17, 39, 76]. [3.3: 10, 14, 24]. [3.4: 1-3, 9-11, 41]. [3.5: 1-6, 8-10] [scanned pdf].
04/15 - [6.1: 13, 20-24, 59, 61, 73]. [6.2: 42-47, 62, 79]. [6.3: 1-5, 10] [scanned pdf].
04/29 - [6.7: 6, 9, 15]. [6.8: 7-10, 13]. [7.1: 25, 26]. [7.2: 1, 4, 7, 10, 16, 17, 37] [scanned pdf].
05/06 - [8.1: 5-10, 46-49]. [8.2: 7-12, 33, 35, 36, 49, 53, 54]. [8.3: 1-10]. [8.4:1-5] [scanned pdf].
05/13 - [8.5: 1-3, 11, 12, 28, 29]. [8.6: 1-3, 10, 11, 31-34]. [8.7: 1-8, 16] [scanned pdf].
05/27 - [9.1: 32-37]. [9.2: 7-15]. [9.3: 1-2, 7-9, 10-13, 22]. [9.4: 1-5]. [9.5: 1, 2, 5, 18-25] [scanned pdf].
06/03 - [9.7: 1-3, 11-13]. [9.8: 1-22] [scanned pdf].

Policies:

There will be 8 homework assignments.
No late homework will be accepted.
The grade will be based on 20% homework, 20% midterm 1, 20% midterm 2, 40% final.
This class will use the myUCLA gradebook facility.
Requests for re-grading will only be considered within 14 calendar days of the due date of the original assignment or midterm and no later than the day before the final. All such requests are to be directed to the instructor; the TA may not make changes to the grades.
A grade of 'F' will be assigned to any student who misses the final. Incompletes are reserved for those who have completed all of the work for the class, including the midterm, but who, for a legitimate, documented reason, miss the final.
Use of electronics is strongly discouraged during class.
Come to office hours!

Catalogue description: 61. Introduction to Discrete Structures. (4) Lecture, three hours; discussion, one hour. Requisites: courses 31A and 31B. Not open for credit to students with credit for course 180. 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.