CMPUT 275 Wi18 - INTRO TO TANGIBLE COMPUT II
Combined LBL Wi18
Exercise 6: Divide and Conquer
Download the included file "exercise6.py" and complete both functions.
Part 1
The function findValley() should run in O(log(n)) time where n is the size of the list (hint: divide and
conquer, i.e., what underlies merge sort and many other recursive algorithms).
Trivial solutions that run linear time will not receive any marks.
Warning: if your code performs a list slice (something like l[:k] or l[k:]) then it is probably taking
linear time! In particular, list slice unfortunately makes a full copy of the sliced portion of the list.
Part 2
For full marks, the function climbing() should run in O(n * log(limit)) time where limit is the last
parameter of the function and n is the length of the list.
(hint: can you at least check if a proposed value for the value of 'burst' is sufficient to reach the top in
the given time limit?)
Feel free to change the docstring comments for both functions if you want. They are very long. You do
not need docstring tests.
Submit your completed implementation of both functions (along with any helper functions you want)
in a single file exercise6.py and upload it. Do not zip it. Remember to adhere to the code submission
guidelines, including helpful comments describing your solution with useful variable names.
Submission status
exercise6.py
Attempt number This is attempt 1.
Submission status Submitted for grading
Grading status Not graded
Due date Monday, 19 March 2018, 11:55 PM
Time remaining Assignment was submitted 12 hours 47 mins early
Last modified Monday, 19 March 2018, 11:07 AM
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
1 of 2 2018-04-14, 1:03 p.m.
File submissions
Export to portfolio
exercise6.py
Submission comments Comments (0)
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
2 of 2 2018-04-14, 1:03 p.m.
