# Winter 18 - Math 61 - Introduction to Discrete Structures

This is the course website for Math 61 in Winter 2018. Most relevant information and links can be found here.

Please note that we are using Campuswire for this class (see below).

## Instructor, TAs and office hours

### Instructor

Jens Eberhardt (firstname@math.ucla.edu)
MS 6118, Tuesday 10:00-11:30,
MS 3974, Friday 10:00-11:30.

### TAs

Chris Hunt (clastname98@ucla.edu)
MS 2943, Tuesday and Thursday 10:00-11:00

Kyutae Paul Han (firstname.han93@gmail.com)
MS2905, Thursday 11-12

TBA (TBA@math.ucla.edu)
TBA

Please check back here as office hours and locations may change.

## Schedule

The lectures take place Monday, Wednesday and Friday at 9:00 to 9:50AM in Humanities A51. Time and date of the discussions can be found here.

In the following table you can see the preliminary lecture schedule and find your weekly problems list and homework.

# Date Content Homework
1 M, 01/08 Introduction, Mathematical Induction (2.4) Week 1
Problems:
2.4: 1-5, 13,15,18,19,22,26-28, 50, 70,71,73
1.1: 1-16, 18-23, 28-31, 52-59, 68-71, 72, 87-92, 97,98, 101
3.1: 8-12, 17-22, 29, 80-87, 92
Homework:
2.4.1, 2.4.22, 1.1.52, 3.1.80
2 W, 01/10 Sets, Functions (1.1, 3.1)
3 F, 01/12 Sequences and Strings (3.2)
Monday, 01/15: Martin Luther King, Jr, holiday! Week 2
Problems:
Learn about monotonicity of sequences. (P. 132 in the textbook)
3.2: 1, 3, 5-9, 10, 13-15, 57-64, 73-79, 138, 139, 140, 142, 155-157
3.3: 1-4, 9, 10, 13-15, 18-23, 24, 26, 29-31, 35, 45-58, 62
Homework:
3.2.59 (Prove your formula by induction!), 3.2.142, 3.2.155, 3.3.31, 3.3.58
4 W, 01/17 Relations (3.3)
5 F, 01/19 Equivalence Relations, Matrices of relations (3.4, 3.5)
6 M, 01/22 Basic Counting Principles (6.1) Week 3
Problems:
3.4: 1-22, 27, 28, 30, 32, 35, 43, 44, 67
6.1: 1-4,7,10,16,17,18,26-33, 44,47,50,51,70,71,92,93, 97
6.2: 1-9,11,25-32, 60-64
Homework:
3.4.12, 3.4.43, 6.1.92, 6.2.30
7 W, 01/24 Permutations and Combinations (6.2)
8 F, 01/26 Generalized permutations and combinations (6.3)
9 M, 01/29 Binomial Coefficients (6.7) Week 4
Problems:
6.3: 1-7,9, 10-12, 13, 15, 18-22, 25-29, 32
6.7: 1-9,10,13,15,16,19,23,41
6.8: 1-10,31
Homework:
No Homework!
10 W, 01/31 Pigeonhole Principle (6.8)
11 F, 02/02 Midterm #1
12 M, 02/05 Recurrence Relations (7.1) Week 5
Problems:
7.1: 4-8, 19-21, 25-27, 30, 62, 65-67
7.2: 13-22, 37, 38, 41
Homework:
6.7.22, 6.8.1, 7.1.4, 7.1.19, 7.1.20
Hint for 7.1.19/20: A string ends in either 0 or 1...
13 W, 02/07 Recurrence Relations (7.1)
14 F, 02/09 Solving Recurrence Relations (7.2)
15 M, 02/12 Examples of graphs (8.1) Week 6
Problems:
8.1: 1-4, 8-10, 11-13, 25
8.2: 10-13,15,22,23,29,34,46,47,49,52,56,64,71
8.4: 1-5
Homework:
7.2.14, 7.2.15, Rock-Paper-Scissor (see below), 8.1.10, 8.1.11
Draw a graph visualizing the rules of the game Rock-Paper-Scissor.
It should have three vertices representing Rock, Paper and Scissor, and edges representing what beats what, no edge for a tie.
Is the graph directed or undirected? Is the graph simple?
16 W, 02/14 Paths and Cycles (8.2)
17 F, 02/16 Shortest-path Algorithm (8.4)
Monday, 02/19: Presidents’ Day holiday ! Week 7
Problems:
8.6: 1-3, 7,8 31-34, 28, 29
8.7: 1, 2, 4, 5, 6, 7, 9, 11
Homework:
8.2.19, 8.2.22, 8.2.47, 8.2.78, Dijkstra (see below),
Use Dijkstra's algorithm to compute the shortest path from a to g in the graph depicted in Exercise 8.1.49.
Illustrate the state after every iteration (As in the lecture or in Figure 8.4.11).
Hint for 8.2.78: Use an earlier exercise!
18 W, 02/21 Representations of Graphs (8.5), Isomorphisms of Graphs (8.6)
19 F, 02/23 Planar Graphs (8.7)
20 M, 02/26 Midterm #2 Week 8
Problems:
9.1: 1-4, 5, 6, 8, 14, 15, 18, 24
9.2: 1-6, 22-27, 33, 34
Homework:
8.6.1, 8.6.10, 8.7.11
21 W, 02/28 Examples of Trees (9.1)
22 F, 03/02 More Trees (9.2)
23 M, 03/05 Minimal Spanning Trees (9.3) Week 9
Problems:
9.3: 1, 2, 3, 7, 8
9.4: 1, 2, 3, 4
9.5: 9-11, 12, 22-24
Homework:
9.1.(14-17), 9.2.33 (you may assume that G is acyclic), 9.3.1 (provide V', E' and S after every iteration of the while-loop)
24 W, 03/07 Minimal Spanning Trees (9.4)
25 F, 03/09 Binary Trees (9.5)
26 M, 03/12 Decision Trees, Sorting (7.3, 9.7) Week 10
Problems:
9.7: 1, 2, 3, 9, 12
Homework:
9.4.1, 9.5.12
27 W, 03/14 Isomorphic Trees (9.8)
28 F, 03/16 Review

Hint: If you are using your phone, turning the screen horizontal makes the table easier to read.

# Textbook

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

Owning a copy of the textbook will be very helpful and is recommended however you might not find it necessary.

## Homework

Solving problems on your own is one of the most important parts of this course. It will teach you how to apply your new knowledge and also be the best preparation for the midterms and final exam.

I encourage you to discuss the problems in teams but write up the solutions on your own. Simply copying your homework will not prepare you for the exams at all and is also not allowed (i.e. considered academic misconduct/cheating).

Hint: You can use Campuswire to find teammates!

Every week you will be able to find a list of problems in the lecture schedule. They will be covering the material of the lectures and similar to exam questions.

Certain problems will be your homework which you will have to hand in during the lecture every Friday.

Your homework has to be submitted in a form obeying the following rules:

• In the upper right corner of the first page put:

 First and last name Student ID Date, Homework number TAs name Number of discussion session 

• In the upper right corner of every additional page, put your name.
• Write legible. No crumpled, torn paper.
• Label each solution with the section and problem number (e.g. 7.2 #2).
We will not accept your homework if it violates any of the above rules.

# Exams

There will be two midterms and a final exam. Apart from the exceptions mentioned below, only writing equipment will be allowed in exams. Exams must be written in pen.

• Midterm 1: 9-9:50am Friday, 02 February, 2018
• Midterm 2: 9-9:50am Monday, 26 February, 2018
• Final Exam: TBA

Cheatsheets: For each exam, students may bring a cheat sheet. Each student must prepare their own handwritten cheat sheet. For the midterms, the cheat sheet may consist of one side of half a standard (A4 or letter) sheet of paper (i.e. A5 or letter folded in half lengthways). For the final, the cheat sheet may consist of one side of a standard sheet of paper. Cheatsheets that do not meet these requirements will be confiscated at the beginning of the exam.

Calculators: You may use a non-programmable, non-graphing calculator in exams. Calculators not meeting this specification will be confiscated.

Study: Here I will post some practice exams which might aid your study.

The midterm scores will be adjusted to account for any difference in difficulty. Your final grade will be calculated using the maximum of the following two grading schemes. Your letter grade will then be determined by your rank in the class. Unless something very out of the ordinary occurs I expect to give approximately 20-30% A’s and 55-65% A’s and B’s combined.

Option 1:

10% (7 best homework scores) +
40% (combined midterm scores) +
50% (final exam score)


Option 2:

10% (7 best homework scores) +
30% (best midterm score) +
60% (final exam score)


Effectively, this will mean that unless you score worse in the final than both midterms, your lowest midterm score will be dropped. This also means missing one midterm probably will not impact your grade in any serious way.

## Questions and Help

Mathematical questions should be asked on Campuswire. Click here to sign up, then search for the Introduction to Discrete Structures course, the code for this class is 6144. You can either do so anonymously or with you full name. You are also encouraged to answer or take part in the discussion of the questions of others!

Obviously homework questions and solutions should not be posted on Campuswire. Offences will be treated as academic dishonesty/cheating.

You can also visit me and the TAs in our office hours.

Administrative questions should in the first instance be directed to your TA. If your TA cannot resolve your query then you should contact me.

If you need to email me, the subject line must include the string math31. If not, then there is a good chance your email will slip through the cracks and remain unanswered.