Journal 35

Jan 4 - Jan 10

This week, we focused on divide-and-conquer and decrease-and-conquer techniques. We took a look at quicksort, insertion sort, and topological sorting via Kahn's algorithm. In particular, we learned how different pivot selections (first element and median-of-three) affect quicksort's performance on ascending, descending, and random inputs. Our homework 4_1 centered around this, and provided great insight into the topic. I actually had a lot of fun completing this week's two homework assignments and found them to be very useful in learning the material. We also reviewed binary tree traversals (I have studied this quite a bit in past classes), and how tree height relates to worst-case search times. In addition, we also practiced analyzing DAGs and applying Kahn's algorithm to find topological orders.