Homework 11

General Comments

For full credit, provide context for each problem, show all calculations, and justify all answers by providing enough comments to explain your reasoning.
Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
You can get up to 50% credit on a problem if you get significant outside assistance. Thus, if you are totally stuck on a problem it might be worth getting help. However, you must indicate any assistance/collaboration (See the Homework Assistance section on the Policies page). Failure to do so could result in a failing grade for the course! Note that getting help from the Help Center or me does not count as significant outside assistance, but talking with your classmates or searching on the Internet does!
If a problem asks for an algorithm, you should give the most efficient algorithm you can find to ensure full credit. You should also specify the complexity of the algorithm with justification, whether or not the problem asks for it.

Consider the following directed acyclic graph.
1. (8) Find a valid topological sorting of the DAG using the DFS algorithm from the lecture notes (not from the book). Show all of your work, including the timestamps!
2. (8) Find a valid topological sorting of the DAG using the source-removal algorithm from the book. Clearly indicate the order in which the states are removed!
(8) Design a decrease-by-half algorithm that computes ⌊log₂ n⌋. Do not forget to give the work case complexity!
(8) You are given an n×n matrix whose rows and columns are sorted in increasing order. Design a O(n) algorithm to find a given number in the matrix. Make sure you justify the complexity of the algorithm. Also, make sure you understand the properties the matrix has—do not assume too much or too little! This one is a bit tricky, so it may take you some time and experimentation to find a good algorithm.