Math 182:Homework and Tentative Schedule

Syllabus :[PDF] with a full description about this course.

Note: Weekly homework is due on Thursday, at the beginning of Disccusion section (except the first one).

Week 1: Lecture 1-3: Stable matching algorithm, Chapter 1

Week 2:

Lec 4: Big O notation, O(log n)-algorithm on determining if a given value belongs to a sorted sequence or not (section 2.1-2.2, 2.4)

Lec 5: linear time algorithm on merging two sorted lists into one, definitions of Array and linked list (section 2.4)

Lec 6: Implementation of Stable matching algorithm, some definition of graphs (section 2.3, 3.1)

Week 3:

Lec 7: BFS, DFS (3.2)

Lec 8: Implementing of BFS and its application: testing bipartite graph (section 3.3, 3.4)

Lec 9: digraph, DAG and topological ordering (section 3.5, 3.6)

Week 4:

Lec 10: DAG and topological ordering, Interval Scheduling (section 3.6, 4.1)

Lec 11: Interval Scheduling (section 4.1)

Lec 12: Minimize Lateness (section 4.2)

Week 5:

Lec 13: Dijkstra's algorithm, Heap (section 4.4, 2.5)

Lec 14: Implementation of Dijkstra's, Kruskal's Algorithm (section 4.4, 4.5)

Lec 15: Prim's and Reverse-delet algprithms (section 4.5). (Section 4.7 is the same spirit of Kruskal's algorithm. I also recommend you to read it)

Week 6:

Lec 16: review

Lec 17: Midterm

Lec 18: Mergesort and Recurrences. (Section 5.1, 5.2)

Week 7:

Lec 19: Counting inversions (section 5.3)

Lec 20: Finding the closest pair of points (section 5.4)

Lec 21: Dynamic Programming: Weighted interval scheduling (section 6.1, 6.2)

Week 8:

Lec 22: Segmented least squares (section 6.3)

Lec 23: Subsets sum and Knapsacks (section 6.4)

Lec 24: Sequence Aligment (section 6.6, 6.7)

Week 9:

Monday is a holiday.

Lec 25: Shortest path in graph (section 6.8, 6.10)

Lec 26: Ford-Fulkerson Algorithm (section 7.1)

Week 10:

Lec 27: Ford-Fulkerson Algorithm (7.1-7.2)

Lec 28: Application of F-F Algorithm (7.4, 7.5)

Lec 29: Review.

HW1, due on Thursday, 4/12 (or Friday, as it was stated here). Chapter 1: 1, 2, 3, 4, 6.

You are also encouraged to try 5, 7, 8: 7 is "kind of" similar to 6, while 8 and a part of 5 need to consider couterexamples.

HW2, due on Thursday, 4/19. Chapter 2: 2, 3, 4, 6. Chapter 3: 2.

HW3, due on Thursday, 4/26. Chapter 3: 3, 5, 6, 7, 9, 10.

HW4, due on Thursday, 5/3. Chapter 4: 2, 3, 4, 5, 6.

The later homeworks are harder. It is better to think problems in ahead of time.

HW5, do not need to be graded due to the midterm of this week. Chapter 4: 8, 9, 18, 24, 27 (it can be solved by induction)

HW6, due on Thursday, 5/17. Chapter 5: 1, 3, 6.

HW7, due on Thursday, 5/24. Chapter 5: 7. Chapter 6: 1, 3, 6, 7.

For NO. 7 in Chapter 5, divide and conquer, and keep in mind that finding "minimal" vertex in a smaller region makes progress.

HW8, due on Thursday, 5/31. Chapter 6: 10, 16, 22, 26.

HW9, due on Thursday, 6/7. Chapter 7: 2, 5, 7, 10, 12.