Algorithm Design: Divide and Conquer

Algorithm Design: Divide and Conquer

Lecture #7: 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 Conquer — Faster Integer Multiplication

• Lecture Notes
• Review Questions

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
• Review Questions
• Supplement:Additional Details about Shamos’s and Hoey’s Algorithm

Tutorial Exercise #9: Finding the Median Value in a Pair of Databases Using “Divide and Conquer”

• Pboblems To Be Solved

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

• Lecture Notes
• Review Questions

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

• Problems To Be Solved

Assignment #2: Design and Analysis of a “Divide and Conquer” Algorithm

• Problems To Be Solved
• LaTeX Source for This Assignment

cpsc 413 computer science faculty of science u of c

CPSC 413 Introduction Analysis of Algorithms Divide and Conquer Dynamic Programming Greedy Algorithms Computational Complexity Information about Assignments Information about Tests