As a result of the US Election, a wall is built along the entire Canadian border



1. As a result of the US Election, a wall is built along the entire Canadian border. You have been told there is a mouse hole in the wall, but it can only be seen when you are standing in front of it. Your task is to find the mouse hole by walking along the wall; however, you are standing in Minnesota and do not know whether the hole is East or West of your current location. Give an algorithm that will allow you to find the mouse hole in O(n) steps, where n is the (unknown to you) distance in steps from your initial location to the mouse hole. 2. Solve the following recurrence (c is a positive constant): T(n) = T(n − 1) + clog(n) if n > 1 T(1) = 1 It is ok for your solution to include big-Oh terms, but it should be as simple as possible. 3. Consider the following assertion: given a graph G with n nodes (for some even number n), if every node of G has degree at least n/2 then the graph is connected. Prove or disprove this assertion. 4. Prove the following theorem about graphs: Theorem. Let G be an undirected graph on n nodes. Any two of the following statements imply the third. • G is connected. • G does not contain a cycle. • G has n − 1 edges.

Instruction Files

Related Questions in engineering category

The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.