# Math 61: Introduction to Discrete Structures

Winter 2012

Time and Place: MWF 9-9:50 am in Boelter 3400
• Instructor: Ciprian Manolescu
• E-mail: cm@math.ucla.edu
• Office Hours: W 10-11am, Th 11am-12pm and 2-3pm in MS 6921
Discussion Sections: Tu or Th 9-9:50 am in Boelter 5420 or Boelter 5422
• Teaching Assistant: Davide Alessandro Reduzzi
• E-mail: devredu83@math.ucla.edu
• Office Hours: TuTh 10-11 am in MS 6617A; SMC: Tu 11am-12pm in MS 3974

Web site: http://www.math.ucla.edu/~cm/61.1.12w. Homework is posted at http://www.math.ucla.edu/~cm/61.1.12w/homework.html. Exam review materials are posted at http://www.math.ucla.edu/~cm/61.1.12w/exam.html.

Prerequisites: Courses 31A and 31B. Not open for credit to students with credit for course 113 or 180.

Topics to be covered: Calculus is "continuous" mathematics, based on the real number system, convergence, and limits. "Discrete" mathematics is everything else; the objects in discrete structures are not the limits of nearby objects. Some of the topics we will study are sets and relations, induction, permutations, combinations, graphs and trees. These topics are intended to give the mathematical background relevant to theoretical computer science. Note: This is a mathematics course; you will be asked to understand abstract concepts, and to do some proofs.

Textbook: R. Johnsonbaugh, Discrete Mathematics, 7th Edition, Prentice Hall, 2008.

Grading: Your numerical score will be computed based on the higher score resulting from the following two schemes:

• Scheme 1: 15% Homework, 25% Midterm 1, 25% Midterm 2, 35% Final Exam.
• Scheme 2: 15% Homework, 30% Higher midterm score, 55% Final Exam.
The resulting numerical score will be converted to a letter grade based on class ranking. Grades will be recorded using the myUCLA gradebook facility.

Exams: There will be two midterms in class, on Monday, January 30 and Friday, February 24. The final exam will take place from 11:30am to 2:30pm on Wednesday, March 21. Exams must be taken during the scheduled times. There will be NO makeup exams with the exception of medical emergencies or university approved absences. 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 midterms, but who, for a legitimate, documented reason, miss the final.

Homework: There will be nine homework assignments. The assignments will be posted on the web page, and will be collected in lecture, on the days when the are due (usually Fridays). The two lowest homework grades will be dropped. No late homework will be accepted. You should first attempt to complete the homework assignments by yourself and then seek outside help (i.e., other students, the TA, the instructor or the Student Math Center) for any problems you are not able to complete. You are expected to write up the solutions by yourself.

Free Tutoring: available at Student Math Center in MS 3974. For details visit http://www.math.ucla.edu/ugrad/smc.shtml.

Special Needs: Students wanting extra accommodation should contact the Office for Students with Disabilities in Murphy A255, or online at http://www.osd.ucla.edu.

Schedule of lectures:

• M 01/09 - Mathematical induction (2.4).
• W 01/11 - Sets and functions (1.1, 3.1).
• F 01/13 - Sequences and strings (3.2). Homework 1 due.

• M 01/16 - No class: Martin Luther King, Jr. Day
• W 01/18 - Relations (3.3).
• F 01/20 - Equivalence relations and matrices of relations (3.4, 3.5). Homework 2 due.

• M 01/23 - Basic counting principles (6.1).
• W 01/25 - Permutations and combinations (6.2).
• F 01/27 - Generalized permutations and combinations (6.3). Homework 3 due.

• M 01/30 - Midterm 1. It will cover the material up to (and including) Section 6.2.
• W 02/01 - Binomial coefficients (6.7).
• F 02/03 - Pigeonhole principle (6.8). Homework 4 due.

• M 02/06 - Recurrence relations (7.1).
• W 02/08 - Solving recurrence relations (7.2).
• F 02/10 - Examples of graphs (8.1). Homework 5 due.

• M 02/13 - Paths and cycles (8.2, 8.3).
• W 02/15 - Shortest-path algorithm (8.4).
• F 02/17 - Representations of graphs (8.5).

• M 02/20 - No class: Presidents' Day
• W 02/22 - Isomorphisms of graphs (8.6). Homework 6 due.
• F 02/24 - Midterm 2. It will cover sections 6.3 though 8.5.

• M 02/27 - Planar graphs (8.7).
• W 02/29 - Examples of trees (9.1).
• F 03/02 - More trees (9.2). Homework 7 due.

• M 03/05 - Minimal spanning trees (9.3, 9.4).
• W 03/07 - Binary trees (9.5).
• F 03/09 - Theta notation (from 4.3) and merge sort (7.3). Homework 8 due.

• M 03/12 - Decision trees and sorting (9.7).
• W 03/14 - Isomorphic trees (9.8).
• F 03/16 - Review. Homework 9 due.

• W 03/21 - Final, 11:30am-2:30pm. The final will be cumulative, but with more emphasis on the material after Midterm 2.