Lecture 5/15: Lecture 18 Q&A
Lecture 18 Questions and Answers (Exported from Zoom Q&A log)
Q: Quick question, when you use "new" without "delete", does the system clear up the memory used after your program exits?
A1: live answered
Q: Is the Spotify playlist public?
A1: Yes! Linked on the home page of the course website
Q: I had problems downloading the practice file for Bluebook, as it just went to a url of weird text. Will this be an issue for the actual exam file do you think, Nick?
A1: If that happens, just right-click the page with weird text and uses “Save as” to save it as “exam.json”. Then you can open it from BlueBook
Q: What day will the homework be released?
A1: Saturday or Sunday
Q: Is bubble sort related to the bubble-up bubble-down thing we talked about last class?
A1: Not quite, there is some simiilarity in exchanging elements to move into position and reuse of “bubble” as verb
Q: is page rank considered a sorting algorithm?
A1: No, it is an algorithm for evaluating the relevance of a page for a given search term (i.e. google’s search results are sorted by page rank)
Q: that looks like my last brain cell
A1:
Q: How is insertion sort different than bubble sort?
A1:
Q: ^^ nevermind on that insertio vs bubble question!
A1:
Q: Are these algorithms implicated in card games/card counting?
A1: Not sure what you mean? You could sort a deck of cards using any of these sorting algorithms, insertion sort is one of the more common sorts that a human would do (pick up each card and insert into your hand)
Q: did it skip the 9 when it moved?
A1: It slides the 8 past the 9 because it needs to be inserted before it
Q: is the “shuffling loop” chris talked about a while loop?
A1: You will continue shuffling the previous elements over until you reach the place where the element is to be placed. Thiis could be written as a while loop, but probably still likely to be a for because it has start, stop, increment and that fits nicely into for loop format
A2: Chris example code does use a while loop in fact
Q: Could we use binary search to make this sort faster?
A1: Great idea! The binary search would help find the position in O(logN) time, but sadly, you still need to move all those elements over to make space for the inserted element, so that work is still O(N) that cost will dominate
Q: Should that heading be selesction sort now?
A1: Yeah, thanks for the catch I can update that in the slides
Q: Is there a typo is slide 9? Shouldn't it say Selection Sort Example?
A1: Yep, I just changed it, thanks for heads up
Q: for selection sort, dont you have to only look through the rest of the list, each time, not the whole list
A1: You’re correct, but searching N things, then searching N-1, then searching N-2, still adds up to quadratic overall…
Q: Same typo for slide 10 Selection Sort Code.
A1: yep, I changed both just a sec ago. Thanks for the heads up!
Q: If Merge only takes in sorted list, isn’t it dependent on other kind of sorting?
A1: The general merge sort algorithm does not require the lists come in sorted — that was specific to the multi merge tasks in assignment 4
Q: It seems there are a lot of lists in the quick sort. Does it mean the space complexity is big?
A1: For this naive version, yes. Wait to see the in-place version, much more space efficient
Q: Should the pivot always be the left-most element? What if you picked the middle as a pivot?
A1: You can select any element from remaining to use as pivot. Ideally you want that element to be as close to the median as possible for best effect. If the elemetns are in random order, no way to know for sure which is best. But if elements are close/in sorted order, the leftmost is gauranteed to be a bad choice
Q: I've heard a lot that quick sort is just the bees knees, but from lecture today it doesn't seem to be that much faster than mergesort since they're both nlogn and Chris would take merge sort to the desert island. What's the quicksort hype?
A1: live answered
Q: if we went back to our merge sort homework and implemented quick sort, would it work a lot faster?
A1: live answered
Q: What would be the bottom line takeaway from this lecture? Should we be comfortable writinh all theses algoritms or just recogonize them or big O analyze them?
A1: live answered
Q: This is outside the scope of the class but are there any quantum based sorting methods that blow these classical sorts out of the water?
A1: live answered
Q: Nvm I just googled it
A1: live answered
Q: thanks!
A1: live answered
Q: What is the best way to pick the best pivot?
A1: live answered
Q: what is the space complexity of the naive quick sort?
A1: live answered
Q: Thanks Chris!
A1: live answered