CS18 Bridge Assignment: Running Times
In class, we’ve been taking an intuitive approach to worst-case running times, summarizing our thoughts in terms of “linear”, “quadratic”, or “constant”. But there is a more formal approach to determining the worst-case running time of a function, based on writing out a function that summarizes how many computational steps get taken on each element.
Understanding the basics of this is the main non-programming topic from CS17 that we continue to build on in CS18.
Luckily for us, CS19 covers this material with a good textbook chapter (written relative to Pyret). The material on recurrences is the part you’ll particularly need for CS18 (the whole chapter builds up to that, so don’t skip sections). Kathi gave a lecture on this in Fall 2018 based on the textbook chapter.
Exercises
For your CS18 prep, we want you to:
- write formal recurrences, and
- summarize them with big-O notation (explained in chapter and in the lecture capture) For example, O(k) (or whatever is appropriate).
for four programs:
- insertion sort
- mergesort
- quicksort
- binary search tree lookup (
has-elt on the binary search tree assignment)
Handin
You can write these on paper (then scan them in) or use a word processor, as you prefer. Many word processors are rather poor at mathematical formulas, so you may find paper easier (fyi, most computer scientists use a tool called LaTeX for such formatting, but you are by no means expected to learn or know that for CS18).
You can submit these answers either as part of the sorting and binary search tree assignments (analyzing each function in its corresponding assignment), or all together as part of this assignment. If you do the analyses as part of the lists and binary tree assignments, you won’t submit anything additional for this assignment.
Use the name runningtimes.pdf (or .arr or .txt) for your file.
CS18 Bridge Assignment: Running Times
In class, we’ve been taking an intuitive approach to worst-case running times, summarizing our thoughts in terms of “linear”, “quadratic”, or “constant”. But there is a more formal approach to determining the worst-case running time of a function, based on writing out a function that summarizes how many computational steps get taken on each element.
Understanding the basics of this is the main non-programming topic from CS17 that we continue to build on in CS18.
Luckily for us, CS19 covers this material with a good textbook chapter (written relative to Pyret). The material on recurrences is the part you’ll particularly need for CS18 (the whole chapter builds up to that, so don’t skip sections). Kathi gave a lecture on this in Fall 2018 based on the textbook chapter.
The textbook chapter
Lecture Capture from CS-111, Dec 2018
Code handout that went with lecture capture
Exercises
For your CS18 prep, we want you to:
for four programs:
has-elton the binary search tree assignment)Handin
You can write these on paper (then scan them in) or use a word processor, as you prefer. Many word processors are rather poor at mathematical formulas, so you may find paper easier (fyi, most computer scientists use a tool called LaTeX for such formatting, but you are by no means expected to learn or know that for CS18).
You can submit these answers either as part of the sorting and binary search tree assignments (analyzing each function in its corresponding assignment), or all together as part of this assignment. If you do the analyses as part of the lists and binary tree assignments, you won’t submit anything additional for this assignment.
Use the name
runningtimes.pdf(or.arror.txt) for your file.