Math 2602L Linear and Discrete Mathematics lecture schedule

Week 1, August 17-21, 2009

Monday: Induction
Tuesday: Induction. Followed class handout, solved several problems.
Wednesday: Induction.
Thursday: Induction. Homogeneus linear recurrence relations of first degree.

Homework 1: Section 5.1, problems 3, 4(c), 4(g), 6(b), 9(g). Due before 4:05PM on Wednesday. Solutions, courtesy of Spencer Backman.

Week 2, August 24-28, 2009

Monday: Induction.
Tuesday: Recurrence relations, section 5.3. Here is a handout about multiplicities of roots, and here is one about solving recurrence relations.
Wednesday: Homework 1 due. Practice recurrence relations.
Thursday: Examples involving recurrence relations.

Homework 2: Section 5.3, problems 12(b), 12(c), 15(a), 15(b), 17. Due before 4:05PM on Wednesday. Solutions.

Week 3, August 31-September 4, 2009

Monday: Practice recurrence relations, especially non-homegeneous one.
Tuesday: Applications of recurrence relations.
Wednesday: Homework 2 due.
Thursday: Applications of recurrence relations to analysis of algorithms. Chapter 8.

Homework 3: Section 8.3, problems 1(c), 8, 14 and problems 27 and 28 from here. Due before 4:05PM on Wednesday. Solutions: part 1, part 2.

Week 4, September 7-11, 2009

Monday: Official school holiday.
Tuesday: Big Oh notation. Section 8.2
Wednesday: Homework 3 due.
Thursday: Section 6.1 and 6.2

Homework 4: Section 8.2, problems 7(a)-(d), 14(a), 14(b), 19(a)-(d). Solutions.

Week 5, September 14-18, 2009

Monday: Review.
Tuesday: Review and the Pigeonhole Principle.
Wednesday: Homework 4 due. Test 1. Solutions
Thursday: Permutations and combinations.

Homework 5: Section 6.1 problem 4. Section 6.2 problems 1, 5(a), 10. Section 6.3 problems 8, 12. Section 7.1, problems 7(a)-(c). Section 7.2, problems 1, 2.

Week 6, September 21-25, 2009

Monday: Chapter 6
Tuesday: Arrangements and selections with repetition
Wednesday: Homework 5 due.
Thursday: The distribution model of counting, multinomial coefficients and their use in counting sequences with restricted entries, the Binomial Theorem

Homework 6: Section 7.2 problems 10, 11. Section 7.5 problems 10, 11, 13, 14(a). Section 7.7 problems 2, 4, 10.

Week 7, September 28-October 2, 2009

Monday: Counting problems
Tuesday: Elementary probability
Wednesday: Homework 6 due
Thursday: Probability

Homework 7: Section 7.3 problems 5(e), 16(a), 19. Section 7.5 problems 4, 7, 8, 12.

Week 8, October 5-9, 2009

Monday: Fall recess
Tuesday: Fall recess
Wednesday: Homework 7 due. Probability.
Thursday: Basic properties of graphs, isomorphism. Sections 9.2 and 9.3.

Homework 8: Section 7.4 problems 1, 7(a), 9(a), 9(b), 17, 18. Section 9.2 problems 12, 13, 15, 21(a), 21(b). Section 9.3 problems 4, 6.

Week 9, October 12-16, 2009

Monday: Graph theory
Tuesday: Eulerian graphs
Wednesday: Homework 8 due.
Thursday: Hamiltonian graphs, adjacency matrices

Homework 9: Section 10.1 problems 3, 4, 7, 16. Section 10.2 problems 3, 5, 10. Section 10.3 problems 3a, 5, 6a.

Week 10, October 19-23, 2009

Monday: Problems
Tuesday: Shortest path algorithms
Wednesday: Homework 9 due. Test 2. Solutions.
Thursday: Trees and spanning trees

Homework 10: Section 10.4 problems 5, 17. Section 12.1 problem 27. Section 12.2 problems 8, 12, 13. Solutions.

Week 11, October 26-29, 2009

Monday: Problems
Tuesday: Prim's algorithm to find a minimum weight spanning tree
Wednesday: Homework 10 due.
Thursday: Planar graphs

Homework 11: Section 12.3 problems 2, 5(a), 5(b)iii (i.e. find a maximum weight spanning tree in the graph of Figure 12.13) Section 13.1 problems 1, 5, 10, 13, 19(a) Solutions.

Week 12, November 2-6, 2009

Monday:
Tuesday: Coloring planar graphs. Begin linear programming
Wednesday: Homework 11 due.
Thursday: Definition of LP, standard form, geometric interpretation

Homework 12: Section 13.2 problems 4, 7(c), 24. Part II section 6 problems 1(a), 1(b), 2. Solutions.

Week 13, November 9-13, 2009

Monday:
Tuesday: The simplex algorithm
Wednesday: Homework 12 due.
Thursday: The simplex tableaux.

Homework 13: Part II section 6 problems 1(c), 4(a), 4(c), 5, 6.

Week 14, November 16-20, 2009

Monday:
Tuesday: Review. The big-M method to find a basic feasible solution.
Wednesday: Homework 13 due. Test 3. Emphasis on material covered during weeks 9-13. Solutions.
Thursday: The two-phase method. Empty solution space.

Homework 14: Part II section 6 problems 8, 10, 13, 14.

Week 15, November 23-27, 2009

Monday:
Tuesday: Unbounded solution spaces. Echelon form of a matrix. Solving linear systems
Wednesday: Homework 14 due. Recitation will meet as scheduled.
Thursday: Thanksgiving holiday.

Homework 15: Part III section 2.2 problems 6, 14.

Week 16, November 30-December 4, 2009

Monday: Finding basic feasible solutions (if needed). Unbounded solution space. Solving linear systems.
Tuesday:
Wednesday: Homework 15 due.
Thursday:

Final examination

Period 15, Thursday, December 10, 2:50-5:40PM. Please see Exam guidelines and conflicts policy. I will be out of town during the finals week. Please plan accordingly.