Computer Science 413: Divide and Conquer

Divide and Conquer

Lecture #7: Algorithm Design — Divide and Conquer Algorithms

• Lecture Notes
• Further Details about the mergeSort Algorithm
• Review Questions

Tutorial Exercise #7: Binary Search as a Divide and Conquer Algorithm

• Problems To Be Solved

Lecture #8: Divide and Coonquer — Faster Integer Multiplication

• Lecture Notes
• Questions for Review

Reading Exercise #5: Proof of “The Master Theorem”

• Assigned Reading

Tutorial Exercise #8: Faster Computation of the Fibonacci Numbers using “Divide and Conquer”

• Problems To Be Solved

Lecture #9: Divide and Conquer — Finding a Pair of Closest Points in the Plane

• Lecture Notes
• Further Details about Shamos’ and Hoey’s Algorithm
• Questions for Review

Tutorial Exericise #9: Finding the Median Element in a Pair of Databases using “Divide and Conquer”

• Problems To Be Solved

Lecture #10: Divide and Conquer — Median Finding and Selection in Linear Time

• Lecture Notes
• Questions for Review

Tutorial Exercise #10: Counting the Inversions in a List using “Divide and Conquer”

• Problems To Be Solved

Assignment #2: Divide and Conquer

• Problems To Be Solved
• LaTeX Source for This Assignment

cpsc 413 computer science faculty of science u of c

CPSC 413 introduction and math review analysis of algorithms divide and conquer dynamic programming greedy algorithms complexity theory assignments tests