 Homework 11General 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.
Details

Consider the following directed acyclic graph.
 (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!
 (8) Find a valid topological sorting of the DAG using the sourceremoval algorithm from the book. Clearly indicate the order in which the states are removed!
 (8) Design a decreasebyhalf algorithm that computes ⌊log_{2} 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.


