Math 55 Spring 2003

Math 55 -- Discrete Mathematics -- Spring 2003

Course Home Page

Professor: Mark Haiman
E-mail:
Office: 771 Evans, (510) 642-4318
Office Hours: Wednesday 12:15-1:45 PM, Thursday 1:30-2:30 PM

GSI's: Erik Closson, Alex Dugas, Seth Dutter, Ben Hough (head TA)
GSI Offices & Hours:

Ben - 739 Evans, office hours M 12-1 and TuTh 1-2. Also Friday, Feb. 7 from 12-2, but not on later Fridays.
Seth - 830 Evans, office hours M 9-10, WF 10-11, F 1-2
Alex - 1097 Evans, office hours M 2-3 and Th 1-2
Erik - 759 Evans, office hours Tu 1-2 and F 11-12

Lectures: TuTh 11am-12:30pm, Room 100 Lewis Hall
Sections: Mondays and Wednesdays, see schedule.

A new section is now open, MW1-2 in 3107 Etcheverry. Contact Ben for more information.

Text: Kenneth H. Rosen, Discrete Mathematics and its Applications, Fifth edition
Additional material will sometimes be presented in lectures. I will also provide some notes on this material on the web page.

Homework and Quizzes: Homework will be assigned weekly and due in section on Mondays. The homework is important and should be taken seriously, but we unfortunately don't have the resources to correct it! We will only record that you handed it in on time, but not count it toward your grade.
Instead, there will be a short quiz each Wednesday in section (except on the first day, Jan. 22, and on weeks with midterm exams). Each quiz will have just one or two problems, based closely on the homework due the preceding Monday. Quizzes will take 25 minutes, to allow time afterwards for discussion. If you do the homework on time, and bring up any questions you have in your sections or instructors' office hours, you will be well prepared for the quizzes.

Exams:

Midterm 1 - Thursday, Feb. 27
Midterm 2 - Thursday, April 10
Final exam - Wednesday, May 21, 8:00-11:00 AM (exam group 12), Room 10 Evans Hall

Grading: Quiz total (10 best of 12) = 30%, Midterms = 20% each, Final = 30%.
There will be no make-up quizzes. Make-up midterms or final allowed only for very serious reasons, and only with advance notice.

Preliminary Course Outline
(subject to change, especially towards the end)

Introduction to algorithms and complexity (Rosen 2.1-2.3). Logic, proofs, sets and functions (Rosen Ch. 1) to be discussed in sections.
Integers, division, congruence arithmetic; applications to cryptography (Rosen 2.4-2.6).
Matrices (Rosen 2.7) and finite fields (extra material presented in lecture); applications to error-correcting codes.
Strategies and techniques for proofs; mathematical induction (Rosen 3.1-3.3).
Recursive definitions and recursive algorithms (Rosen 3.4-3.5).
Combinatorics: counting; permutations and combinations; binomial coefficients; pigeonhole principle; Ramsey numbers (Rosen 4.1-4.5).
Probability; average-case complexity of algorithms; the probabilistic method (Rosen Ch. 5).
Recurrence relations; complexity of recursive algorithms (Rosen 6.1-6.3).
Principle of inclusion-exclusion (Rosen 6.5-6.6).
Directed graphs; transitive closure; equivalence relations; partial orderings (Rosen 7.1; 7.3-7.6)
Graphs and graph algorithms: shortest-path, travelling salesman (Rosen 8.1-8.6).
Graph coloring, planar graphs and the four-color theorem (Rosen 8.7-8.8 and extra material in lecture).
Trees and tree algorithms: Huffman coding, graph searches, minimum spanning trees (Rosen 9.1-9.2; 9.4-9.5).

Homework assignments

Note: Solutions are in PDF format. To read them you need to use a browser equipped with a PDF reader (such as Acrobat)

Assignment
Due
Quiz
Solutions

Chapter 1: 1.1 #11, 13, 42, 45; 1.2 #23; 1.3 #23, 30(a,d,e); 1.4 #9
Chapter 2: 2.1 #4, 5; 2.2 #2, 23, 18, 21, 35;
2.3 (A) Give a big-O estimate of the time-complexity of the algorithm in your textbook's solution to 2.1, exercise 31. (B) Suppose you knew an algorithm to sort a list x₁,...,x_n in time O(n log(n)). Devise a better solution to 2.1, exercise 31 than the one in the book. Mon. 1/27
Wed. 1/29
Homework
Quiz

Chapter 1: 1.5 #11, 21, 25, 42; 1.6 #5, 18, 27
Chapter 2: 2.4 #13, 14, 20, 23, 24(a,b,c), 32, 50, 53(c).
On 53(c), use the fact that 3 x 9 is congruent to 1 (mod 26) to find the the decryption function g such that p = g(f(p)), and use it to decrypt this message: BXP CHST VXU. Mon. 2/3
Wed. 2/5
Homework
Quiz

Chapter 1: 1.7 #17(a), 18; 1.8 #12, 13, 21
Chapter 2: 2.5 #7, 15, 21(f); 2.6 #27, 29, 59 <- was posted incorrectly earlier
Extra problem: (A) Show that if p is prime and ab=0 (mod p), then a=0 or b=0.
(B) Show that the only solutions of x²=1 (mod p) are x=±1 (mod p).
(C) Let p be a prime congruent to 3 (mod 4), so q = (p-1)/2 is odd. Show that if x is relatively prime to p, then x to the power (q+1)/2 is either a square root of x or a square root of -x (mod p).
(D) Find a square root of 2 (mod 103). Mon. 2/10
Wed. 2/12
Homework
Quiz

Chapter 2: 2.6 #31 (do also for n=25 with the base 7), 32, 45, 46, 47
A hint on #45: Given the sum p+q and product pq of two numbers p and q, show that the numbers themselves are solutions of the quadratic equation x²-(p+q)x+pq=0.
Wed. 2/19
Wed. 2/19
Homework
Quiz

Click here Mon. 2/24
No quiz this week.
Midterm Exam 2/27. Homework
Review problems, with answers.
Exam solutions

Chapter 2: 2.7 #18, 19, 20, 27
Extra problem: (a) Formulate the system of equations w+x-z=0, w+x-y+z=0, x+y-4z=0 as a matrix equation, as in the lecture or Exercise 26(a).
(b) Use row operations to get an equivalent system Ax=b in which the first three columns of A form an identity matrix.
(c) Find all solutions of the system. Your answer should have one variable free and the other three variables given in terms of the free variable. Also find the specific solution with z=1.
-------------
Start reading Notes on Reed-Solomon codes, to be discussed in the lectures beginning 3/4. Some exercises from these notes will be assigned later. Mon. 3/3
Wed. 3/5
Homework
Quiz

Reading: sections 1-3 of Notes on Reed-Solomon codes. Exercises #1, 8, 9, 10, 11, 12. Hint for #9: the number of code vectors is equal to the number of message vectors, 2^m. How many vectors are distance 1 from a code vector?
Mon. 3/10
Wed. 3/12
Homework
Quiz

Finish reading Notes on Reed-Solomon codes. Exercises: #6, 7, 13, 14. Do Exercise 13 first using the decoding algorithm in Section 4, by solving a system of linear equations for the coefficients of the polynomials Q(t) and E(t) in the key equation. Then do it using the improved algorithm in Section 5. Mon. 3/17
Wed. 3/19
Homework
Quiz

Rosen Chapter 3.1: #2, 10, 11, 17, 25, 29, 30, 49, 51.
On #10, also find the smallest possible integer side lengths of a right triangle not proportional to (3:4:5) or (5:12:13).
On #25, what if we change the question to ask for consecutive odd primes greater than 3?
Enjoy your spring break!
Mon. 3/31
Wed. 4/2
Homework
Quiz

Rosen Chapter 3.3: #6, 11, 13, 34^*, 43, 52
Chapter 3.4: #5(a,c,d)^*, 12^*, 18^*
Problems with ^* due next week (Mon. 4/14) instead.
Erik's office hours Tuesday 4/8 are extended to 1-4 PM, to make up for his missed sections. Mon. 4/7, except ^*. Midterm Exam Thurdsay 4/10.
No quiz this week. Homework;
Review problems, with answers.
Exam

Problems with ^* from last week's assignment, plus:
Chapter 3.3: 40, 53, 65; Chapter 3.4: #17, 47
Prof. Haiman's office hour this Wednesday changed to 2:00-3:00 Mon. 4/14 Wed. 4/16
Homework
Quiz

Chapter 3.5: 11, 28, 33, 38, 43.
Extra problem: you are given n coins and a balance. One coin is counterfeit and lighter than the others. With each weighing on the balance you can compare two piles of coins to see if they have equal weight, or if not, which one is heavier. Devise a recursive algorithm to locate the counterfeit coin in N weighings, where N is the smallest integer greater than or equal to log₃n. Prove that no algorithm using fewer weighings is possible. Mon. 4/21 Wed. 4/23
Homework
Quiz
Textbook's answer to #11 is wrong. See updated solutions.

4.1 #3, #18, #46, #50; 4.3 #30; 4.5 #14, #30
Extra problem: An e-error correcting code is perfect if every possible received word has Hamming distance at most e from a codeword. If C is a perfect e-error correcting code with n code symbols over an alphabet of size p, show that C(n,0)+C(n,1)(p-1)+...+C(n,e)(p-1)^e must divide pⁿ. Find all possible n<25 for which there might exist a perfect 3-error correcting code over Z₂.
Ben's office hours this week changed to Friday 9:00-11:00. Mon. 4/28 Wed. 4/30
Homework
Quiz

4.4 #22, #33; 4.5 #27, #39, #42-43; 4.2 #3, #9, #10
Mon. 5/5 Wed. 5/7
Homework
Quiz

Click here. There is no quiz on this homework, but as an incentive for you to do it, I can promise that at least one problem on the final exam will be closely related to a problem from this homework set.
Mon. 5/12 No Quiz
Homework

Final Exam Information

Finals week office hours
Prof. Haiman: Wednesday-Thusday, May 14-15, 12:00-1:30 PM.
Seth: Wednesday, May 14, 1:00-2:00 PM
Ben: Mon. May 19, 1-3 PM and Tues. May 20, 10-12 AM
Alex: Thurs. May 15 2-4, Mon. May 19 2-3, and Tues. May 20 1-3
Eric: Thurs. May 15 2-3, Tues. May 20 1-2

Review sessions
Seth: Tuesday, May 20, 5:00-7:00 PM, Room 150 GSPP
Alex: Monday, May 19, 6:00-8:00 PM, Room 70 Evans Hall
Erik: Saturday, May 17, 1:00-3:00 PM, Room 9 Evans Hall

The final exam is Wednesay, May 21, 8:00-11:00 AM, in Room 10 Evans Hall.
Here are some review problems, with answers. Final exam solutions.

Graded final exams are kept on file by the math office. You can inspect your exam two weeks after the beginning of the next semester. If you want to know your final exam score, you can ask me or your GSI, after grades are reported.

[ Top of page | Prof. Haiman's home page ]

Assignment	Due	Quiz	Solutions
Chapter 1: 1.1 #11, 13, 42, 45; 1.2 #23; 1.3 #23, 30(a,d,e); 1.4 #9 Chapter 2: 2.1 #4, 5; 2.2 #2, 23, 18, 21, 35; 2.3 (A) Give a big-O estimate of the time-complexity of the algorithm in your textbook's solution to 2.1, exercise 31. (B) Suppose you knew an algorithm to sort a list x₁,...,x_n in time O(n log(n)). Devise a better solution to 2.1, exercise 31 than the one in the book.	Mon. 1/27	Wed. 1/29	Homework Quiz
Chapter 1: 1.5 #11, 21, 25, 42; 1.6 #5, 18, 27 Chapter 2: 2.4 #13, 14, 20, 23, 24(a,b,c), 32, 50, 53(c). On 53(c), use the fact that 3 x 9 is congruent to 1 (mod 26) to find the the decryption function g such that p = g(f(p)), and use it to decrypt this message: BXP CHST VXU.	Mon. 2/3	Wed. 2/5	Homework Quiz
Chapter 1: 1.7 #17(a), 18; 1.8 #12, 13, 21 Chapter 2: 2.5 #7, 15, 21(f); 2.6 #27, 29, 59 <- was posted incorrectly earlier Extra problem: (A) Show that if p is prime and ab=0 (mod p), then a=0 or b=0. (B) Show that the only solutions of x²=1 (mod p) are x=±1 (mod p). (C) Let p be a prime congruent to 3 (mod 4), so q = (p-1)/2 is odd. Show that if x is relatively prime to p, then x to the power (q+1)/2 is either a square root of x or a square root of -x (mod p). (D) Find a square root of 2 (mod 103).	Mon. 2/10	Wed. 2/12	Homework Quiz
Chapter 2: 2.6 #31 (do also for n=25 with the base 7), 32, 45, 46, 47 A hint on #45: Given the sum p+q and product pq of two numbers p and q, show that the numbers themselves are solutions of the quadratic equation x²-(p+q)x+pq=0.	Wed. 2/19	Wed. 2/19	Homework Quiz
Click here	Mon. 2/24	No quiz this week. Midterm Exam 2/27.	Homework Review problems, with answers. Exam solutions
Chapter 2: 2.7 #18, 19, 20, 27 Extra problem: (a) Formulate the system of equations w+x-z=0, w+x-y+z=0, x+y-4z=0 as a matrix equation, as in the lecture or Exercise 26(a). (b) Use row operations to get an equivalent system Ax=b in which the first three columns of A form an identity matrix. (c) Find all solutions of the system. Your answer should have one variable free and the other three variables given in terms of the free variable. Also find the specific solution with z=1. ------------- Start reading Notes on Reed-Solomon codes, to be discussed in the lectures beginning 3/4. Some exercises from these notes will be assigned later.	Mon. 3/3	Wed. 3/5	Homework Quiz
Reading: sections 1-3 of Notes on Reed-Solomon codes. Exercises #1, 8, 9, 10, 11, 12. Hint for #9: the number of code vectors is equal to the number of message vectors, 2^m. How many vectors are distance 1 from a code vector?	Mon. 3/10	Wed. 3/12	Homework Quiz
Finish reading Notes on Reed-Solomon codes. Exercises: #6, 7, 13, 14. Do Exercise 13 first using the decoding algorithm in Section 4, by solving a system of linear equations for the coefficients of the polynomials Q(t) and E(t) in the key equation. Then do it using the improved algorithm in Section 5.	Mon. 3/17	Wed. 3/19	Homework Quiz
Rosen Chapter 3.1: #2, 10, 11, 17, 25, 29, 30, 49, 51. On #10, also find the smallest possible integer side lengths of a right triangle not proportional to (3:4:5) or (5:12:13). On #25, what if we change the question to ask for consecutive odd primes greater than 3? Enjoy your spring break!	Mon. 3/31	Wed. 4/2	Homework Quiz
Rosen Chapter 3.3: #6, 11, 13, 34^, 43, 52 Chapter 3.4: #5(a,c,d)^, 12^, 18^ **Problems with ^ due next week (Mon. 4/14) instead.* Erik's office hours Tuesday 4/8 are extended to 1-4 PM, to make up for his missed sections.**	Mon. 4/7, except ^*.	Midterm Exam Thurdsay 4/10. No quiz this week.	Homework; Review problems, with answers. Exam
Problems with ^* from last week's assignment, plus: Chapter 3.3: 40, 53, 65; Chapter 3.4: #17, 47 *Prof. Haiman's office hour this Wednesday changed to 2:00-3:00*	Mon. 4/14	Wed. 4/16	Homework Quiz
Chapter 3.5: 11, 28, 33, 38, 43. Extra problem: you are given n coins and a balance. One coin is counterfeit and lighter than the others. With each weighing on the balance you can compare two piles of coins to see if they have equal weight, or if not, which one is heavier. Devise a recursive algorithm to locate the counterfeit coin in N weighings, where N is the smallest integer greater than or equal to log₃n. Prove that no algorithm using fewer weighings is possible.	Mon. 4/21	Wed. 4/23	Homework Quiz Textbook's answer to #11 is wrong. See updated solutions.
4.1 #3, #18, #46, #50; 4.3 #30; 4.5 #14, #30 Extra problem: An e-error correcting code is perfect if every possible received word has Hamming distance at most e from a codeword. If C is a perfect e-error correcting code with n code symbols over an alphabet of size p, show that C(n,0)+C(n,1)(p-1)+...+C(n,e)(p-1)^e must divide pⁿ. Find all possible n<25 for which there might exist a perfect 3-error correcting code over Z₂. *Ben's office hours this week changed to Friday 9:00-11:00.*	Mon. 4/28	Wed. 4/30	Homework Quiz
4.4 #22, #33; 4.5 #27, #39, #42-43; 4.2 #3, #9, #10	Mon. 5/5	Wed. 5/7	Homework Quiz
Click here. There is no quiz on this homework, but as an incentive for you to do it, I can promise that at least one problem on the final exam will be closely related to a problem from this homework set.	Mon. 5/12	No Quiz	Homework