Class Notes (811,179)
CSC108H1 (113)
Lecture

# november 28 notes

2 Pages
112 Views

School
University of Toronto St. George
Department
Computer Science
Course
CSC108H1
Professor
Michelle Craig
Semester
Fall

Description
 Pass function as permeter to another function 1. import time 2. import random 3. from bubble_sort import bubble_sort 4. from insertion_sort import insertion_sort 5. from merge_sort import merge_sort 6. 7. def runtime(f, arg): 8. '''f is a function of one argument. arg is a suitable argument for f. 9. Return the amount of time it takes to execute f on argument arg.''' 10. 11. before = time.time() 12. f(arg) #output ignored 13. after = time.time() 14. return after – before 15. 16. def mystery(L): 17. '''L is a list. Return ???''' 18. 19. answer = [] 20. for item1 in L: 21. for item2 in L: 22. answer.append([item1, item2]) 23. return answer 24. 25. if _ _name_ _ == ‘_ _main_ _’ 26. # mystery program runtime 27. # double list length, runtime increases more than doubled 28. # ex. bubble sort worst case 2^2 number of comparisons 29. # insertion_sort  sorting-algorithms.com  compare sorts runtime; merge sort fastest  Complexity  how complicated the code is compared to the # of operations (not how complicated to understand)  Recap o The run-time of code is usually greater when operating on a larger input o There can be massive differences in run-time between different algorithms, even for the same problem o Knowing the shape of the run-time growth curve is very valuable  “can I wait long enough to get the answer for this input?”  “is it even worth writing this code?” o efficiency not really # of lines  not gaining speed, compiler already done the job  runtime growth cruve  ways to determine run-time o run the code and measure run-time  run it for different input sizes to determine the growth curve o estimate run-time “on paper”
More Less

Related notes for CSC108H1

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.