title

3. Sets and Sorting

description

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Justin Solomon
View the complete course: https://ocw.mit.edu/6-006S20
YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY
Stored sets sorted by key allows for faster searching. This lecture covers how to construct a sorted array efficiently and the types of sorts.
License: Creative Commons BY-NC-SA
More information at https://ocw.mit.edu/terms
More courses at https://ocw.mit.edu
Support OCW at http://ow.ly/a1If50zVRlQ
We encourage constructive comments and discussion on OCW’s YouTube and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at https://ocw.mit.edu/comments.

detail

{'title': '3. Sets and Sorting', 'heatmap': [{'end': 1242.184, 'start': 1176.507, 'weight': 0.714}, {'end': 2101.656, 'start': 2061.955, 'weight': 0.716}, {'end': 2320.8, 'start': 2190.777, 'weight': 0.748}], 'summary': 'Justin nervously introduces sorting to 400 students in chapter 1, while subsequent chapters cover data structures, set interface operations, sorting algorithms like permutation sort, selection sort, recursive functions, merge sort, and their respective time complexities and implementations.', 'chapters': [{'end': 96.551, 'segs': [{'end': 49.04, 'src': 'embed', 'start': 12.578, 'weight': 0, 'content': [{'end': 15.26, 'text': "OK, so it's a pleasure to see all of you guys.", 'start': 12.578, 'duration': 2.682}, {'end': 16.059, 'text': "I'm Justin.", 'start': 15.36, 'duration': 0.699}, {'end': 20.683, 'text': 'I am your third instructor for 6.006.', 'start': 16.56, 'duration': 4.123}, {'end': 27.287, 'text': 'This is my first time with this course, although, of course, this is material that we all know and love in the computer science department.', 'start': 20.683, 'duration': 6.604}, {'end': 33.911, 'text': "I'll admit I find the prospect of teaching sorting to 400 people all at once kind of low-key terrifying.", 'start': 27.727, 'duration': 6.184}, {'end': 38.513, 'text': "But we're going to give it a shot and hopefully that will subside as the lecture goes on today.", 'start': 33.971, 'duration': 4.542}, {'end': 38.754, 'text': 'all right?', 'start': 38.513, 'duration': 0.241}, {'end': 49.04, 'text': "So we're going to pick up where we left off in our last lecture and continue on with a similar theme that we're going to see throughout our algorithms class here in 6.006..", 'start': 40.175, 'duration': 8.865}], 'summary': 'Justin is the new instructor for 6.006, feeling nervous about teaching sorting to 400 people.', 'duration': 36.462, 'max_score': 12.578, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s12578.jpg'}, {'end': 81.639, 'src': 'embed', 'start': 55.745, 'weight': 1, 'content': [{'end': 60.468, 'text': "And so I thought I'd start with just a tiny bit of review of some key vocabulary words.", 'start': 55.745, 'duration': 4.723}, {'end': 68.732, 'text': 'Incidentally, typically I teach the intro graphics class, a geometry course, and last year I got feedback that said I have serial killer handwriting.', 'start': 60.888, 'duration': 7.844}, {'end': 70.753, 'text': "I'm not 100% sure what that means.", 'start': 68.872, 'duration': 1.881}, {'end': 75.696, 'text': "But we're going to use the slides a tiny bit more than normal just to make sure you guys can read.", 'start': 71.614, 'duration': 4.082}, {'end': 81.639, 'text': "And when I'm writing on the board, at any point, if you can't tell what I wrote, it's definitely me and not you.", 'start': 76.096, 'duration': 5.543}], 'summary': 'Reviewing key vocabulary words; teaching intro graphics and geometry; emphasizing use of slides for better readability.', 'duration': 25.894, 'max_score': 55.745, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s55745.jpg'}], 'start': 12.578, 'title': 'Teaching sorting to 400 students', 'summary': 'Introduces justin as the new instructor for 6.006, expressing his nervousness in teaching sorting to 400 students and reviewing key vocabulary words, aligning with the theme of the algorithms class.', 'chapters': [{'end': 96.551, 'start': 12.578, 'title': 'Teaching sorting to 400 students', 'summary': 'Introduces justin as the new instructor for 6.006, expressing his nervousness in teaching sorting to 400 students and reviewing key vocabulary words, aligning with the theme of the algorithms class.', 'duration': 83.973, 'highlights': ['Justin expresses nervousness in teaching sorting to 400 students Justin admits finding the prospect of teaching sorting to 400 people all at once kind of low-key terrifying.', 'Review of key vocabulary words Justin starts with just a tiny bit of review of some key vocabulary words, which were introduced in the first lecture of 6.006.', "Justin's experience in teaching related subjects Justin mentions that he typically teaches the intro graphics class and a geometry course, and last year got feedback about his handwriting."]}], 'duration': 83.973, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s12578.jpg', 'highlights': ['Justin admits finding the prospect of teaching sorting to 400 people all at once kind of low-key terrifying.', 'Justin starts with just a tiny bit of review of some key vocabulary words, which were introduced in the first lecture of 6.006.', 'Justin mentions that he typically teaches the intro graphics class and a geometry course, and last year got feedback about his handwriting.']}, {'end': 437.578, 'segs': [{'end': 126.473, 'src': 'embed', 'start': 97.511, 'weight': 3, 'content': [{'end': 101.614, 'text': "But roughly, there's a theme here, which is that there's an object called an interface.", 'start': 97.511, 'duration': 4.103}, {'end': 104.647, 'text': 'which is just sort of like a program specification.', 'start': 102.666, 'duration': 1.981}, {'end': 108.828, 'text': "It's just telling us that there's a collection of operations that we want to implement.", 'start': 104.707, 'duration': 4.121}, {'end': 113.089, 'text': "So for example, a set, as we're going to see today, is like a big pile of things.", 'start': 108.848, 'duration': 4.241}, {'end': 120.771, 'text': 'And behind the scenes, how I choose to implement it can affect the runtime and sort of how efficient my set is.', 'start': 113.649, 'duration': 7.122}, {'end': 126.473, 'text': 'But the actual way that I interact with it is the same, whether I use an unsorted array, a sorted array, or what have you.', 'start': 121.171, 'duration': 5.302}], 'summary': 'An interface defines a program specification with a collection of operations to implement, affecting runtime and efficiency, while maintaining consistent interaction.', 'duration': 28.962, 'max_score': 97.511, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s97511.jpg'}, {'end': 210.654, 'src': 'embed', 'start': 153.903, 'weight': 0, 'content': [{'end': 155.923, 'text': "And we're going to see that there's a bunch of trade-offs.", 'start': 153.903, 'duration': 2.02}, {'end': 158.944, 'text': 'Some of them are really fast for certain operations and slow for others.', 'start': 155.963, 'duration': 2.981}, {'end': 164.066, 'text': 'And so essentially, we have two different decisions to make when we choose an algorithm.', 'start': 159.624, 'duration': 4.442}, {'end': 168.207, 'text': "One is making sure that the interface is correct for the problem that we're concerned with.", 'start': 164.486, 'duration': 3.721}, {'end': 178.269, 'text': 'And the other is choosing an appropriate data structure whose efficiency and memory usage and so on kind of aligns with the priorities that we have for the application we have in mind.', 'start': 168.627, 'duration': 9.642}, {'end': 181.09, 'text': 'So hopefully this kind of high-level theme makes sense.', 'start': 178.289, 'duration': 2.801}, {'end': 182.33, 'text': 'And really kind of spiritually.', 'start': 181.15, 'duration': 1.18}, {'end': 186.571, 'text': "I think that's sort of the main message to get out of this course in the first couple of weeks,", 'start': 182.33, 'duration': 4.241}, {'end': 191.652, 'text': 'even though all these Os and Thetas and so on are kind of easy to lose the forest to the trees.', 'start': 186.571, 'duration': 5.081}, {'end': 198.61, 'text': "In any event, today in our lecture, we're concerned with one particular interface, which is called a set.", 'start': 192.768, 'duration': 5.842}, {'end': 200.591, 'text': 'Set is exactly what it sounds like.', 'start': 199.45, 'duration': 1.141}, {'end': 201.611, 'text': "It's a big pile of things.", 'start': 200.611, 'duration': 1}, {'end': 210.654, 'text': 'And so a set interface is sort of like an object that just you can keep adding things to it and then querying inside of my set.', 'start': 203.292, 'duration': 7.362}], 'summary': 'Understanding trade-offs between algorithms and data structures is crucial for efficient implementation.', 'duration': 56.751, 'max_score': 153.903, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s153903.jpg'}, {'end': 260.709, 'src': 'embed', 'start': 232.402, 'weight': 2, 'content': [{'end': 235.227, 'text': "And that might be the key that's associated to every object in the room.", 'start': 232.402, 'duration': 2.825}, {'end': 239.857, 'text': "And so when I'm searching for students, maybe I enter in the student number.", 'start': 236.215, 'duration': 3.642}, {'end': 247.662, 'text': 'And then I want to ask myself, does this number exist in the set of students that are in 6006? And if it does, then I can pull that student back.', 'start': 240.017, 'duration': 7.645}, {'end': 251.664, 'text': "And then associated with that object is a bunch of other information that I'm not using to search.", 'start': 247.982, 'duration': 3.682}, {'end': 260.709, 'text': 'So for instance, your name, your social security number, credit card number, all the stuff that I need to have a more interesting profession.', 'start': 251.985, 'duration': 8.724}], 'summary': 'Using student numbers as keys to fetch associated information for course 6006.', 'duration': 28.307, 'max_score': 232.402, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s232402.jpg'}], 'start': 97.511, 'title': 'Data structures and set interface operations', 'summary': 'Covers the significance of choosing appropriate data structures for efficient implementation in computer programming and introduces the set interface, emphasizing its support for dynamic operations like insertion, deletion, and querying.', 'chapters': [{'end': 186.571, 'start': 97.511, 'title': 'Interface and data structure', 'summary': 'Explains the critical theme of interfaces and data structures in computer programming, emphasizing the importance of choosing an appropriate data structure for efficient implementation and the trade-offs involved in different implementation methods.', 'duration': 89.06, 'highlights': ['The distinction between an interface, which specifies a collection of operations, and a data structure, which is a way to implement an interface, is a critical theme in the course.', 'Choosing an appropriate data structure is essential for aligning efficiency, memory usage, and priorities for the application, with trade-offs between different implementation methods.', 'Implementing an interface correctly for the problem at hand and choosing an efficient data structure are the two key decisions to make when selecting an algorithm.']}, {'end': 437.578, 'start': 186.571, 'title': 'Set interface operations', 'summary': 'Introduces the set interface, which represents a collection of objects and supports dynamic operations such as insertion, deletion, and querying, providing an abstract view of the operations without specifying the implementation details.', 'duration': 251.007, 'highlights': ['The set interface allows dynamic operations like insertion, deletion, and querying. It supports dynamic operations such as insertion, deletion, and querying, providing an abstract view of the operations without specifying the implementation details.', 'Objects in the set can be associated with additional information, such as student IDs and other details. Objects in the set can be associated with additional information, such as student IDs, allowing for efficient querying and retrieval of associated data.', 'The set interface abstracts the implementation details, allowing high-level interfacing with the objects. The set interface abstracts implementation details, allowing high-level interfacing with the objects, similar to the abstraction provided by high-level programming languages like Python and MATLAB.']}], 'duration': 340.067, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s97511.jpg', 'highlights': ['Choosing an appropriate data structure is essential for aligning efficiency, memory usage, and priorities for the application, with trade-offs between different implementation methods.', 'The set interface allows dynamic operations like insertion, deletion, and querying. It supports dynamic operations such as insertion, deletion, and querying, providing an abstract view of the operations without specifying the implementation details.', 'Objects in the set can be associated with additional information, such as student IDs, allowing for efficient querying and retrieval of associated data.', 'The distinction between an interface, which specifies a collection of operations, and a data structure, which is a way to implement an interface, is a critical theme in the course.', 'Implementing an interface correctly for the problem at hand and choosing an efficient data structure are the two key decisions to make when selecting an algorithm.', 'The set interface abstracts the implementation details, allowing high-level interfacing with the objects. The set interface abstracts implementation details, allowing high-level interfacing with the objects, similar to the abstraction provided by high-level programming languages like Python and MATLAB.']}, {'end': 1285.508, 'segs': [{'end': 479.219, 'src': 'embed', 'start': 438.834, 'weight': 1, 'content': [{'end': 446.78, 'text': "So, of course, in today's lecture, now that we've set out our goal, which is to fill in, if I wanted to write code for a set, how could I do it?", 'start': 438.834, 'duration': 7.946}, {'end': 453.425, 'text': 'Now, of course, our goal is to give different data structures that implement these and then understand them in terms of their efficiency,', 'start': 447.44, 'duration': 5.985}, {'end': 455.406, 'text': 'data storage correctness, all that good stuff.', 'start': 453.425, 'duration': 1.981}, {'end': 460.59, 'text': 'So before we get into all these ugly details, let me pause for a second.', 'start': 456.827, 'duration': 3.763}, {'end': 463.292, 'text': 'Are there any questions about this basic interface?', 'start': 460.61, 'duration': 2.682}, {'end': 469.089, 'text': "Y'all should feel free to stop me any time, because this is going to be hella boring if you're not getting the first slide or two.", 'start': 464.465, 'duration': 4.624}, {'end': 479.219, 'text': "Yes?. Can you explain how insert works as in like you're replacing with And then like you're adding this all the way back to the set.", 'start': 471.111, 'duration': 8.108}], 'summary': 'Lecture focuses on implementing code for data structures with a goal of understanding efficiency and correctness.', 'duration': 40.385, 'max_score': 438.834, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s438834.jpg'}, {'end': 747.803, 'src': 'embed', 'start': 718.49, 'weight': 0, 'content': [{'end': 723.673, 'text': 'But this is all just to say that an unordered array is a perfectly reasonable way to implement the set interface.', 'start': 718.49, 'duration': 5.183}, {'end': 728.015, 'text': 'And then searching that array will take linear time every single time I search.', 'start': 724.313, 'duration': 3.702}, {'end': 736.436, 'text': "Yeah?. And of course, if you go down your list of all of the different operations you might want to do on a set, you'll see that they all take linear time.", 'start': 728.831, 'duration': 7.605}, {'end': 741.599, 'text': 'So for instance, how do I build my set? Well, I have to reserve n slots in memory.', 'start': 736.876, 'duration': 4.723}, {'end': 747.803, 'text': 'And at least according to our model of computation in this class, that takes order n time.', 'start': 742.52, 'duration': 5.283}], 'summary': 'Unordered array for set interface, linear time for search and operations.', 'duration': 29.313, 'max_score': 718.49, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s718490.jpg'}, {'end': 1242.184, 'src': 'heatmap', 'start': 1176.507, 'weight': 0.714, 'content': [{'end': 1181.17, 'text': "It's going to be a sorted array.", 'start': 1176.507, 'duration': 4.663}, {'end': 1183.632, 'text': "And we'll call this guy b.", 'start': 1181.911, 'duration': 1.721}, {'end': 1184.593, 'text': "And we'll call this one.", 'start': 1183.632, 'duration': 0.961}, {'end': 1189.255, 'text': 'A This classroom is not optimized for short people.', 'start': 1186.593, 'duration': 2.662}, {'end': 1196.219, 'text': "OK So there's a lot of variations on the basic sorting problem and the different algorithms that are out there.", 'start': 1190.595, 'duration': 5.624}, {'end': 1198.62, 'text': "Two vocabulary words I'm going to highlight really quick.", 'start': 1196.839, 'duration': 1.781}, {'end': 1201.102, 'text': 'One is if your sort is destructive.', 'start': 1199.221, 'duration': 1.881}, {'end': 1209.587, 'text': 'what that means is that, rather than reserving some new memory for my sorted array B and then putting a sorted version of A into B,', 'start': 1201.102, 'duration': 8.485}, {'end': 1214.09, 'text': 'a destructive algorithm is one that just overwrites A with a sorted version of A.', 'start': 1209.587, 'duration': 4.503}, {'end': 1218.676, 'text': 'Right, so certainly the C++ interface does this.', 'start': 1215.174, 'duration': 3.502}, {'end': 1220.897, 'text': 'I assume the Python one does too.', 'start': 1219.196, 'duration': 1.701}, {'end': 1223.079, 'text': 'I always forget this detail.', 'start': 1221.378, 'duration': 1.701}, {'end': 1229.623, 'text': 'In addition to destructive sorts, some sorts are in place.', 'start': 1225.44, 'duration': 4.183}, {'end': 1235.539, 'text': "meaning that not only are they destructive, but they also don't use extra memory in the process of sorting.", 'start': 1230.916, 'duration': 4.623}, {'end': 1242.184, 'text': 'You could imagine a sorting algorithm that has to reserve a bunch of scratch space to do its work and then put it back into A.', 'start': 1236.139, 'duration': 6.045}], 'summary': 'Discussion on sorting algorithms and their memory usage in programming languages.', 'duration': 65.677, 'max_score': 1176.507, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s1176507.jpg'}, {'end': 1229.623, 'src': 'embed', 'start': 1201.102, 'weight': 2, 'content': [{'end': 1209.587, 'text': 'what that means is that, rather than reserving some new memory for my sorted array B and then putting a sorted version of A into B,', 'start': 1201.102, 'duration': 8.485}, {'end': 1214.09, 'text': 'a destructive algorithm is one that just overwrites A with a sorted version of A.', 'start': 1209.587, 'duration': 4.503}, {'end': 1218.676, 'text': 'Right, so certainly the C++ interface does this.', 'start': 1215.174, 'duration': 3.502}, {'end': 1220.897, 'text': 'I assume the Python one does too.', 'start': 1219.196, 'duration': 1.701}, {'end': 1223.079, 'text': 'I always forget this detail.', 'start': 1221.378, 'duration': 1.701}, {'end': 1229.623, 'text': 'In addition to destructive sorts, some sorts are in place.', 'start': 1225.44, 'duration': 4.183}], 'summary': 'Destructive sorting overwrites array a with a sorted version. c++ and python interfaces do this, along with in-place sorts.', 'duration': 28.521, 'max_score': 1201.102, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s1201102.jpg'}], 'start': 438.834, 'title': 'Implementing data structures for efficient set operations and sets sorting', 'summary': 'Discusses implementing code for a set, different data structures efficiency, and the basic interface of the insert operation. it also covers sets implementation using arrays, importance of sorting for efficient set operations, and trade-offs between unordered and sorted arrays, as well as key vocabulary words related to sorting algorithms.', 'chapters': [{'end': 531.307, 'start': 438.834, 'title': 'Implementing data structures for efficient set operations', 'summary': 'Discusses the goal of implementing code for a set, understanding different data structures in terms of efficiency and data storage, and answering questions about the basic interface of the insert operation.', 'duration': 92.473, 'highlights': ['Understanding different data structures in terms of efficiency and data storage The goal is to give different data structures that implement these and then understand them in terms of their efficiency, data storage correctness.', 'Discussing the basic interface of the insert operation and answering questions about its functionality The chapter addresses questions about the insert operation, explaining how it works and its functionality in relation to student objects and key searching.', 'Setting out the goal of implementing code for a set The lecture aims to fill in, if wanting to write code for a set, and how it could be done.']}, {'end': 1285.508, 'start': 533.39, 'title': 'Implementing sets and sorting', 'summary': 'Discusses the implementation of sets using arrays and the importance of sorting for efficient set operations, highlighting the trade-offs between unordered and sorted arrays, and the efficiency of operations like searching and sorting. it also introduces key vocabulary words related to sorting algorithms.', 'duration': 752.118, 'highlights': ['Sorting an array is crucial for efficient set operations, with unordered arrays leading to linear time complexity for operations like searching and sorting, while sorted arrays enable faster operations with logarithmic time complexity. The efficiency of set operations is influenced by the choice of data structure, with sorted arrays offering faster search and sorting operations compared to unordered arrays.', 'Using an unordered array to implement a set results in linear time complexity for operations like building the set, insertion, deletion, and finding the minimum element, making it inefficient for large sets or frequent operations. Unordered arrays are inefficient for set operations as they result in linear time complexity, making them unsuitable for large sets or frequent operations.', 'The introduction of the concept of destructive and in-place sorting algorithms, highlighting the differences in memory usage and overwriting of the original array during sorting. The distinction between destructive and in-place sorting algorithms is important due to their impact on memory usage and overwriting of the original array during sorting.', 'The importance of sorting algorithms, including the use of additional O(1) space and the distinction between destructive and in-place sorting algorithms. Understanding the importance of sorting algorithms involves considering factors such as additional O(1) space and the differences between destructive and in-place sorting algorithms.']}], 'duration': 846.674, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s438834.jpg', 'highlights': ['Sorting an array is crucial for efficient set operations, with unordered arrays leading to linear time complexity for operations like searching and sorting, while sorted arrays enable faster operations with logarithmic time complexity.', 'Understanding different data structures in terms of efficiency and data storage.', 'The introduction of the concept of destructive and in-place sorting algorithms, highlighting the differences in memory usage and overwriting of the original array during sorting.', 'Discussing the basic interface of the insert operation and answering questions about its functionality.']}, {'end': 2107.078, 'segs': [{'end': 1481.157, 'src': 'embed', 'start': 1449.146, 'weight': 0, 'content': [{'end': 1451.287, 'text': 'So this step incurs order n time.', 'start': 1449.146, 'duration': 2.141}, {'end': 1455.104, 'text': "because theta of n time, because we've got to go all the way to the end of the list.", 'start': 1452.483, 'duration': 2.621}, {'end': 1465.209, 'text': 'So when I put these things together, permutation sort, well, remember that this check if sorted happens for every single permutation.', 'start': 1456.765, 'duration': 8.444}, {'end': 1472.813, 'text': 'So at the end of the day, our algorithm takes at least n factorial times n time.', 'start': 1465.229, 'duration': 7.584}, {'end': 1481.157, 'text': "It's a great example of something that's even worse than n factorial, which somehow in my head is like the worst possible algorithm.", 'start': 1474.894, 'duration': 6.263}], 'summary': 'Permutation sort takes at least n factorial times n time', 'duration': 32.011, 'max_score': 1449.146, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s1449146.jpg'}, {'end': 1735.388, 'src': 'embed', 'start': 1704.38, 'weight': 1, 'content': [{'end': 1707.442, 'text': "we're going to write it in kind of a funny way, which is recursive.", 'start': 1704.38, 'duration': 3.062}, {'end': 1714.955, 'text': "Now, I can't emphasize strongly enough how little you guys should implement this at home.", 'start': 1709.229, 'duration': 5.726}, {'end': 1720.02, 'text': 'This is mostly a theoretical version of selection sort, rather than one that you would actually want to write in code,', 'start': 1714.995, 'duration': 5.025}, {'end': 1721.661, 'text': "because there's obviously a much better way to do it.", 'start': 1720.02, 'duration': 1.641}, {'end': 1723.903, 'text': "And you'll see that in your recitation this week, I believe.", 'start': 1721.701, 'duration': 2.202}, {'end': 1728.227, 'text': "But in terms of analysis, there's a nice easy way to write it down.", 'start': 1725.285, 'duration': 2.942}, {'end': 1735.388, 'text': "So we're going to take the selection sort algorithm And we're going to divide it into two kind of chunks.", 'start': 1729.489, 'duration': 5.899}], 'summary': 'Theoretical version of selection sort, not for practical implementation.', 'duration': 31.008, 'max_score': 1704.38, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s1704380.jpg'}, {'end': 1938.155, 'src': 'embed', 'start': 1914.619, 'weight': 2, 'content': [{'end': 1922.244, 'text': 'So this gives us a really simple algorithm for finding the biggest element in the array between index 0 and index i,', 'start': 1914.619, 'duration': 7.625}, {'end': 1923.765, 'text': "which is what I've shown you on the screen here.", 'start': 1922.244, 'duration': 1.521}, {'end': 1926.867, 'text': "I'd write it on the board, but I am a slow writer and already low on time.", 'start': 1923.805, 'duration': 3.062}, {'end': 1938.155, 'text': 'And so essentially, what did I implement? Well, I found the biggest element between index 0 and index i minus 1.', 'start': 1928.088, 'duration': 10.067}], 'summary': 'Algorithm finds biggest element in array between index 0 and i-1.', 'duration': 23.536, 'max_score': 1914.619, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s1914619.jpg'}, {'end': 2101.656, 'src': 'heatmap', 'start': 2061.955, 'weight': 0.716, 'content': [{'end': 2071.462, 'text': 'We already, by our inductive hypothesis, have argued that our code can find the biggest element between index 0 and index i minus 1.', 'start': 2061.955, 'duration': 9.507}, {'end': 2074.545, 'text': "So as long as we take the max of that and the very last guy, we're in good shape.", 'start': 2071.462, 'duration': 3.083}, {'end': 2078.628, 'text': 'So this is our very informal proof of correctness.', 'start': 2075.525, 'duration': 3.103}, {'end': 2083.989, 'text': 'OK, so now we have to justify runtime for this algorithm.', 'start': 2080.668, 'duration': 3.321}, {'end': 2086.751, 'text': "And that's actually not 100% obvious from the way I've written it here.", 'start': 2084.07, 'duration': 2.681}, {'end': 2087.531, 'text': "There's no for loop.", 'start': 2086.771, 'duration': 0.76}, {'end': 2089.972, 'text': 'But what do I do??', 'start': 2089.252, 'duration': 0.72}, {'end': 2101.656, 'text': 'Well, in some sense, if my runtime is a function s well for one thing, if my array has one element in it, well, my runtime might be 7..', 'start': 2090.052, 'duration': 11.604}], 'summary': 'The code can find the largest element between index 0 and i-1, and the runtime depends on the size of the array.', 'duration': 39.701, 'max_score': 2061.955, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2061955.jpg'}], 'start': 1286.349, 'title': 'Sorting algorithms', 'summary': 'Covers the permutation sort algorithm with at least n factorial times n time complexity and discusses the implementation of the selection sort algorithm in a recursive manner, emphasizing correctness, efficiency, and justifying the runtime.', 'chapters': [{'end': 1666.48, 'start': 1286.349, 'title': 'Permutation sort algorithm', 'summary': 'Discusses the permutation sort algorithm, which involves listing every possible permutation and checking which one is in the right order, incurring at least n factorial times n time complexity.', 'duration': 380.131, 'highlights': ['Permutation sort involves listing every possible permutation and checking which one is in the right order, incurring at least n factorial times n time complexity. The algorithm involves listing every possible permutation and double checking which one is in the right order, incurring at least n factorial times n time complexity.', 'The time complexity of the algorithm is at least n factorial times n, making it even worse than n factorial. The algorithm takes at least n factorial times n time complexity, which is considered worse than n factorial.', "The algorithm's inefficiency is highlighted by the fact that it is even worse than n factorial. The inefficiency of the algorithm is emphasized by its time complexity being worse than n factorial."]}, {'end': 2107.078, 'start': 1667.489, 'title': 'Selection sort algorithm', 'summary': 'Discusses the implementation of the selection sort algorithm in a recursive manner, emphasizing on proving correctness and efficiency, and includes a discussion on finding the biggest element in the array and justifying the runtime of the algorithm.', 'duration': 439.589, 'highlights': ['The chapter discusses the implementation of the selection sort algorithm in a recursive manner, emphasizing on proving correctness and efficiency. It explains the theoretical version of selection sort and the importance of proving correctness and efficiency.', 'The algorithm for finding the biggest element in the array between index 0 and index i is explained. The algorithm for finding the biggest element between index 0 and index i is demonstrated, along with a discussion on its correct implementation and a proof of correctness through an inductive approach.', "The justification of the runtime for the algorithm is discussed. The chapter emphasizes the need to justify the runtime for the algorithm and discusses the absence of a for loop in the implementation, highlighting the simplicity of the algorithm's runtime behavior."]}], 'duration': 820.729, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s1286349.jpg', 'highlights': ['Permutation sort incurs at least n factorial times n time complexity.', 'Selection sort algorithm is implemented in a recursive manner, emphasizing correctness and efficiency.', 'The algorithm for finding the biggest element in the array between index 0 and index i is explained.', 'The time complexity of permutation sort is worse than n factorial.']}, {'end': 2436.031, 'segs': [{'end': 2169.485, 'src': 'embed', 'start': 2138.632, 'weight': 0, 'content': [{'end': 2140.073, 'text': 'Yeah, order n.', 'start': 2138.632, 'duration': 1.441}, {'end': 2142.374, 'text': "So let's say that we hypothesize that this takes n time.", 'start': 2140.073, 'duration': 2.301}, {'end': 2149.678, 'text': 'You kind of see that, because at step n, we call n minus 1, we call n minus 2, and so on, all the way down to 1.', 'start': 2142.394, 'duration': 7.284}, {'end': 2158.583, 'text': "If we want to prove this, one of the ways that we, I think in theory, you guys have learned in the past and you're going to cover in recitation,", 'start': 2149.678, 'duration': 8.905}, {'end': 2159.824, 'text': 'is a technique called substitution.', 'start': 2158.583, 'duration': 1.241}, {'end': 2169.485, 'text': "What we do is we're going to look at this relationship, and we're going to hypothesize that we think s of n maybe looks something like cn.", 'start': 2160.624, 'duration': 8.861}], 'summary': "The algorithm's time complexity is hypothesized to be o(n) using a technique called substitution.", 'duration': 30.853, 'max_score': 2138.632, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2138632.jpg'}, {'end': 2320.8, 'src': 'heatmap', 'start': 2190.777, 'weight': 0.748, 'content': [{'end': 2197.641, 'text': "So in particular, if I plug into this recursive relationship here, on the left-hand side, I'm going to get cn.", 'start': 2190.777, 'duration': 6.864}, {'end': 2206.341, 'text': "On the right-hand side, I'm going to get cn minus 1 plus theta of 1.", 'start': 2199.778, 'duration': 6.563}, {'end': 2209.983, 'text': 'We just have to make sure that this is like an OK equal sign.', 'start': 2206.341, 'duration': 3.642}, {'end': 2213.605, 'text': 'So what can I do? I can subtract cn from both sides.', 'start': 2211.144, 'duration': 2.461}, {'end': 2215.746, 'text': 'Maybe put that 1 on the other side here.', 'start': 2214.305, 'duration': 1.441}, {'end': 2220.308, 'text': 'And we get that c equals big O of 1.', 'start': 2216.626, 'duration': 3.682}, {'end': 2221.429, 'text': 'c is, of course, a constant.', 'start': 2220.308, 'duration': 1.121}, {'end': 2222.289, 'text': "So we're in good shape.", 'start': 2221.529, 'duration': 0.76}, {'end': 2229.566, 'text': 'My undergrad algorithms professor told me never to write a victory mark at the end of a proof.', 'start': 2225.305, 'duration': 4.261}, {'end': 2231.046, 'text': 'You have to do a little square.', 'start': 2229.926, 'duration': 1.12}, {'end': 2233.667, 'text': "But he's not here.", 'start': 2231.867, 'duration': 1.8}, {'end': 2236.608, 'text': 'OK Right.', 'start': 2234.647, 'duration': 1.961}, {'end': 2239.148, 'text': "So now I see you, but we're a little low on time.", 'start': 2236.628, 'duration': 2.52}, {'end': 2240.489, 'text': "So we'll save it for the end of lecture.", 'start': 2239.188, 'duration': 1.301}, {'end': 2246.09, 'text': 'OK. So, if we want to implement the selection sort algorithm, well, what do we do??', 'start': 2241.769, 'duration': 4.321}, {'end': 2251.271, 'text': "Well, we're going to think of i as the index of that red line that I was showing you before.", 'start': 2246.55, 'duration': 4.721}, {'end': 2253.972, 'text': 'So everything beyond i is already sorted.', 'start': 2251.291, 'duration': 2.681}, {'end': 2261.181, 'text': "So in selection sort, the first thing I'm going to do is find the max element between 0 and i.", 'start': 2255.737, 'duration': 5.444}, {'end': 2262.562, 'text': "And then I'm going to swap it into place.", 'start': 2261.181, 'duration': 1.381}, {'end': 2267.606, 'text': "So this is just a code version of the technique we've already talked about.", 'start': 2264.204, 'duration': 3.402}, {'end': 2269.128, 'text': 'Hopefully this makes sense.', 'start': 2268.267, 'duration': 0.861}, {'end': 2272.89, 'text': 'So you find the biggest element between 0 and index i.', 'start': 2269.548, 'duration': 3.342}, {'end': 2274.932, 'text': "That's what we're going to call j here.", 'start': 2272.89, 'duration': 2.042}, {'end': 2278.375, 'text': 'I swap that with the one in index i.', 'start': 2274.952, 'duration': 3.423}, {'end': 2280.516, 'text': "That's step 2.", 'start': 2278.375, 'duration': 2.141}, {'end': 2283.859, 'text': 'And then step 3 is I still have to sort everything to the left of index i.', 'start': 2280.516, 'duration': 3.343}, {'end': 2284.9, 'text': "And that's that recursive call.", 'start': 2283.859, 'duration': 1.041}, {'end': 2294.994, 'text': "OK, so if I want to justify the runtime of this particular technique, well, now let's call that t for time.", 'start': 2286.169, 'duration': 8.825}, {'end': 2303.339, 'text': 'Well, what do I do? Well, for one, I call selection sort with index i minus 1.', 'start': 2298.336, 'duration': 5.003}, {'end': 2305.44, 'text': 'So that incurs time that looks like this.', 'start': 2303.339, 'duration': 2.101}, {'end': 2309.922, 'text': 'But I also call that prefix max function.', 'start': 2307.461, 'duration': 2.461}, {'end': 2313.344, 'text': 'And how much time does that take? That takes order n time.', 'start': 2309.942, 'duration': 3.402}, {'end': 2320.8, 'text': 'So at the end of the day, I have some relationship that looks like this.', 'start': 2315.396, 'duration': 5.404}], 'summary': 'In the lecture, the speaker demonstrates a proof and explains the selection sort algorithm, stating its runtime complexity.', 'duration': 130.023, 'max_score': 2190.777, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2190777.jpg'}, {'end': 2267.606, 'src': 'embed', 'start': 2241.769, 'weight': 5, 'content': [{'end': 2246.09, 'text': 'OK. So, if we want to implement the selection sort algorithm, well, what do we do??', 'start': 2241.769, 'duration': 4.321}, {'end': 2251.271, 'text': "Well, we're going to think of i as the index of that red line that I was showing you before.", 'start': 2246.55, 'duration': 4.721}, {'end': 2253.972, 'text': 'So everything beyond i is already sorted.', 'start': 2251.291, 'duration': 2.681}, {'end': 2261.181, 'text': "So in selection sort, the first thing I'm going to do is find the max element between 0 and i.", 'start': 2255.737, 'duration': 5.444}, {'end': 2262.562, 'text': "And then I'm going to swap it into place.", 'start': 2261.181, 'duration': 1.381}, {'end': 2267.606, 'text': "So this is just a code version of the technique we've already talked about.", 'start': 2264.204, 'duration': 3.402}], 'summary': 'Implementing selection sort algorithm to find max element between 0 and i, and swap it into place.', 'duration': 25.837, 'max_score': 2241.769, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2241769.jpg'}, {'end': 2313.344, 'src': 'embed', 'start': 2286.169, 'weight': 4, 'content': [{'end': 2294.994, 'text': "OK, so if I want to justify the runtime of this particular technique, well, now let's call that t for time.", 'start': 2286.169, 'duration': 8.825}, {'end': 2303.339, 'text': 'Well, what do I do? Well, for one, I call selection sort with index i minus 1.', 'start': 2298.336, 'duration': 5.003}, {'end': 2305.44, 'text': 'So that incurs time that looks like this.', 'start': 2303.339, 'duration': 2.101}, {'end': 2309.922, 'text': 'But I also call that prefix max function.', 'start': 2307.461, 'duration': 2.461}, {'end': 2313.344, 'text': 'And how much time does that take? That takes order n time.', 'start': 2309.942, 'duration': 3.402}], 'summary': 'Justifying the runtime of a technique involves calling selection sort and prefix max function, incurring a time complexity of order n.', 'duration': 27.175, 'max_score': 2286.169, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2286169.jpg'}, {'end': 2398.131, 'src': 'embed', 'start': 2341.918, 'weight': 1, 'content': [{'end': 2345.659, 'text': "OK, I can never remember exactly the formula, but I'm pretty sure that it looks like n squared.", 'start': 2341.918, 'duration': 3.741}, {'end': 2356.223, 'text': 'So, based on that and taking a look at this recursive thing, which is essentially doing exactly that n plus n minus 1 plus n minus 2, and so on,', 'start': 2348.04, 'duration': 8.183}, {'end': 2360.744, 'text': 'I might hypothesize that this thing is really order n squared.', 'start': 2356.223, 'duration': 4.521}, {'end': 2366.601, 'text': "So, if I'm going to do that, then again, if I want to use the same technique for proof,", 'start': 2362.659, 'duration': 3.942}, {'end': 2370.504, 'text': "I have to plug this relationship in and then double check that it's consistent.", 'start': 2366.601, 'duration': 3.903}, {'end': 2378.929, 'text': 'So maybe I hypothesize that T of n equals Cn squared, in which case I plug it in here.', 'start': 2370.564, 'duration': 8.365}, {'end': 2391.476, 'text': 'I have Cn squared equals, with a question mark over it, Cn minus 1 squared plus big O or even theta n here.', 'start': 2378.949, 'duration': 12.527}, {'end': 2398.131, 'text': "So if I expand the square, notice I'm going to get c times n squared plus a bunch of linear stuff.", 'start': 2393.049, 'duration': 5.082}], 'summary': 'Hypothesizing t(n) = cn^2, consistent with recursive n+n-1+n-2', 'duration': 56.213, 'max_score': 2341.918, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2341918.jpg'}], 'start': 2107.078, 'title': 'Recursive functions and selection sort', 'summary': 'Delves into analyzing recursive functions, hypothesizing and verifying their runtime using substitution, concluding a linear runtime of theta of n. it also covers the selection sort algorithm, its implementation, runtime analysis, and the hypothesis of its time complexity being o(n^2), supported by recursive formula and consistent equation.', 'chapters': [{'end': 2240.489, 'start': 2107.078, 'title': 'Analyzing recursive functions', 'summary': 'Discusses the analysis of a recursive function, hypothesizing its runtime, and verifying the hypothesis using a technique called substitution, ultimately concluding a linear runtime of theta of n.', 'duration': 133.411, 'highlights': ["The recursive function's total runtime is hypothesized to be order n, and to prove this, the technique of substitution is used to verify the relationship and conclude a linear runtime of theta of n.", 'By hypothesizing that s of n is theta of n, the relationship cn = cn - 1 + theta of 1 is verified, ultimately leading to the conclusion that the constant c is big O of 1, indicating a linear runtime.', "The process of proving the recursive function's runtime involves hypothesizing its time complexity, using the technique of substitution, and verifying the relationship to conclude a linear runtime of theta of n."]}, {'end': 2436.031, 'start': 2241.769, 'title': 'Selection sort algorithm analysis', 'summary': 'Discusses the implementation of the selection sort algorithm, its runtime analysis, and the hypothesis of its time complexity being o(n^2), supported by recursive formula and consistent equation.', 'duration': 194.262, 'highlights': ['The chapter discusses the implementation of the selection sort algorithm. It explains the process of finding the max element between 0 and i, swapping it into place, and sorting the elements to the left of index i.', 'The runtime analysis involves the recursive call and prefix max function. The time complexity involves calling selection sort with index i minus 1 and the prefix max function, incurring O(n) time.', 'The hypothesis of the time complexity being O(n^2) is supported by the recursive formula and consistent equation. The hypothesis is based on the recursive relationship resembling n + (n-1) + (n-2) ... and is further supported by plugging the relationship into an equation to confirm consistency.']}], 'duration': 328.953, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2107078.jpg', 'highlights': ["The process of proving the recursive function's runtime involves hypothesizing its time complexity, using the technique of substitution, and verifying the relationship to conclude a linear runtime of theta of n.", 'By hypothesizing that s of n is theta of n, the relationship cn = cn - 1 + theta of 1 is verified, ultimately leading to the conclusion that the constant c is big O of 1, indicating a linear runtime.', "The recursive function's total runtime is hypothesized to be order n, and to prove this, the technique of substitution is used to verify the relationship and conclude a linear runtime of theta of n.", 'The hypothesis of the time complexity being O(n^2) is supported by the recursive formula and consistent equation. The hypothesis is based on the recursive relationship resembling n + (n-1) + (n-2) ... and is further supported by plugging the relationship into an equation to confirm consistency.', 'The runtime analysis involves the recursive call and prefix max function. The time complexity involves calling selection sort with index i minus 1 and the prefix max function, incurring O(n) time.', 'The chapter discusses the implementation of the selection sort algorithm. It explains the process of finding the max element between 0 and i, swapping it into place, and sorting the elements to the left of index i.']}, {'end': 3169.41, 'segs': [{'end': 2497.571, 'src': 'embed', 'start': 2436.451, 'weight': 2, 'content': [{'end': 2437.831, 'text': 'Yeah, this is the substitution method.', 'start': 2436.451, 'duration': 1.38}, {'end': 2440.132, 'text': "And again, I think you'll cover it more in your recitation.", 'start': 2437.871, 'duration': 2.261}, {'end': 2443.421, 'text': 'So what have we done? We have derived the selection sort.', 'start': 2441.141, 'duration': 2.28}, {'end': 2445.762, 'text': "We've checked that it runs an n squared time.", 'start': 2443.882, 'duration': 1.88}, {'end': 2450.603, 'text': "And by this nice inductive strategy, we know that it's correct.", 'start': 2447.002, 'duration': 3.601}, {'end': 2452.863, 'text': 'So life is pretty good.', 'start': 2452.123, 'duration': 0.74}, {'end': 2456.904, 'text': 'Unfortunately, I promised for you guys on the slides that sorting really takes n log n time.', 'start': 2453.303, 'duration': 3.601}, {'end': 2458.944, 'text': 'And this is an order n squared algorithm.', 'start': 2457.284, 'duration': 1.66}, {'end': 2460.064, 'text': "So we're not quite done yet.", 'start': 2458.984, 'duration': 1.08}, {'end': 2462.385, 'text': "I'm way over time.", 'start': 2461.385, 'duration': 1}, {'end': 2466.466, 'text': "So we're going to skip a different algorithm, which is called insertion sort.", 'start': 2462.465, 'duration': 4.001}, {'end': 2467.586, 'text': 'Also runs an n time.', 'start': 2466.666, 'duration': 0.92}, {'end': 2473.059, 'text': 'OK Essentially, insertion sort kind of runs in the reverse order.', 'start': 2469.738, 'duration': 3.321}, {'end': 2476.16, 'text': "I'm going to sort everything to the left and then insert a new object.", 'start': 2473.119, 'duration': 3.041}, {'end': 2479.981, 'text': "Whereas in selection sort, I'm going to choose the biggest object and then sort everything to the left.", 'start': 2476.68, 'duration': 3.301}, {'end': 2482.282, 'text': "But I'll let you guys piece through that at home.", 'start': 2480.941, 'duration': 1.341}, {'end': 2483.962, 'text': "It's essentially the same argument.", 'start': 2482.882, 'duration': 1.08}, {'end': 2491.084, 'text': 'And instead, we should jump to an algorithm that actually matters, which is something called merge sort.', 'start': 2484.763, 'duration': 6.321}, {'end': 2494.829, 'text': 'How many of you have encountered merge sort before? Fabulous.', 'start': 2491.464, 'duration': 3.365}, {'end': 2495.87, 'text': "Good So then I'm done.", 'start': 2495.07, 'duration': 0.8}, {'end': 2497.571, 'text': 'No, OK.', 'start': 2496.791, 'duration': 0.78}], 'summary': 'Selection sort runs in n squared time, and we need a sorting algorithm that takes n log n time, like merge sort.', 'duration': 61.12, 'max_score': 2436.451, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2436451.jpg'}, {'end': 2740.252, 'src': 'embed', 'start': 2709.995, 'weight': 0, 'content': [{'end': 2714.077, 'text': 'So what does the merge sort do? Well, it computes an index C, which is the middle of my array.', 'start': 2709.995, 'duration': 4.082}, {'end': 2722.902, 'text': "And it's going to make a recursive call, which is sort the left, which is everything between index A and index C.", 'start': 2715.475, 'duration': 7.427}, {'end': 2727.627, 'text': 'And then sort everything on the right, which is everything from index C to index B.', 'start': 2722.902, 'duration': 4.725}, {'end': 2730.09, 'text': 'I know this is confusing because usually letters appear in order.', 'start': 2727.627, 'duration': 2.463}, {'end': 2734.454, 'text': 'But C, if you think of as standing for center, then it kind of makes sense.', 'start': 2730.91, 'duration': 3.544}, {'end': 2735.215, 'text': "Like here's my array.", 'start': 2734.474, 'duration': 0.741}, {'end': 2740.252, 'text': "I'm going to choose an index right in the middle.", 'start': 2738.41, 'duration': 1.842}], 'summary': 'Merge sort computes index c, sorts left and right recursively.', 'duration': 30.257, 'max_score': 2709.995, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2709995.jpg'}, {'end': 3063.904, 'src': 'embed', 'start': 3027.592, 'weight': 1, 'content': [{'end': 3034.615, 'text': 'OK And now what does our algorithm do? Well, it makes two recursive calls on lists that are half the length.', 'start': 3027.592, 'duration': 7.023}, {'end': 3041.746, 'text': 'Yeah And then it calls that merge function.', 'start': 3039.284, 'duration': 2.462}, {'end': 3045.049, 'text': 'And we know that the merge function takes theta of n time.', 'start': 3042.026, 'duration': 3.023}, {'end': 3063.904, 'text': 'That make sense? So one thing we might do, because we have some intuition from your 6042 course, is that we think that this thing is order n log n.', 'start': 3047.351, 'duration': 16.553}], 'summary': 'Algorithm makes two recursive calls on lists half the length, and the merge function takes theta of n time, suggesting an order n log n complexity.', 'duration': 36.312, 'max_score': 3027.592, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s3027592.jpg'}], 'start': 2436.451, 'title': 'Merge sort algorithm', 'summary': 'Covers the derivation and time complexity of selection sort, promise of n log n time for sorting, insertion sort, and the importance of merge sort in algorithms, also the implementation of the merge sort algorithm involving sorting an array by recursively dividing it into smaller sub-arrays, sorting them, and then merging them together using the two-finger algorithm with a time complexity of o(n log n) and the use of recursive calls for sorting and merging.', 'chapters': [{'end': 2497.571, 'start': 2436.451, 'title': 'Sorting algorithms and merge sort', 'summary': 'Covers the derivation of selection sort, its time complexity of n squared, the promise of n log n time for sorting, the mention of insertion sort, and the importance of merge sort in algorithms.', 'duration': 61.12, 'highlights': ['The chapter covers the derivation of selection sort and checks its time complexity, running in n squared time.', 'Mention of the promise that sorting takes n log n time, which is not fulfilled by the order n squared algorithm.', 'Introduction of insertion sort, which runs in an n time and functions differently from selection sort.', 'Importance of focusing on merge sort, an algorithm that matters and is introduced as the next topic.']}, {'end': 3169.41, 'start': 2497.591, 'title': 'Merge sort algorithm', 'summary': 'Covers the implementation of the merge sort algorithm, which involves sorting an array by recursively dividing it into smaller sub-arrays, sorting them, and then merging them together using the two-finger algorithm, with key points such as the time complexity being o(n log n) and the use of recursive calls for sorting and merging.', 'duration': 671.819, 'highlights': ['The merge sort algorithm involves recursively dividing the array into smaller sub-arrays, sorting them, and then merging them together using the two-finger algorithm. The chapter explains the process of using recursive calls to sort the left and right sub-arrays, followed by merging them together using the two-finger algorithm.', 'The time complexity of the merge sort algorithm is O(n log n). The chapter discusses the time complexity of the merge sort algorithm, emphasizing that it takes O(n log n) time to sort an array by making recursive calls and merging the sub-arrays.', 'The merge sort algorithm uses recursive calls to sort sub-arrays of half the length and then merges them using the merge function with a time complexity of O(n). The chapter explains how the merge sort algorithm makes recursive calls to sort sub-arrays of half the length and then uses the merge function, which takes O(n) time, to merge the sorted sub-arrays together.']}], 'duration': 732.959, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/oS9aPzUNG-s/pics/oS9aPzUNG-s2436451.jpg', 'highlights': ['The merge sort algorithm involves recursively dividing the array into smaller sub-arrays, sorting them, and then merging them together using the two-finger algorithm with a time complexity of O(n log n).', 'The time complexity of the merge sort algorithm is O(n log n).', 'The chapter covers the derivation of selection sort and checks its time complexity, running in n squared time.', 'Importance of focusing on merge sort, an algorithm that matters and is introduced as the next topic.', 'The merge sort algorithm uses recursive calls to sort sub-arrays of half the length and then merges them using the merge function with a time complexity of O(n).', 'Introduction of insertion sort, which runs in an n time and functions differently from selection sort.']}], 'highlights': ['Justin nervously introduces sorting to 400 students in chapter 1, while subsequent chapters cover data structures, set interface operations, sorting algorithms like permutation sort, selection sort, recursive functions, merge sort, and their respective time complexities and implementations.', 'Choosing an appropriate data structure is essential for aligning efficiency, memory usage, and priorities for the application, with trade-offs between different implementation methods.', 'The set interface allows dynamic operations like insertion, deletion, and querying. It supports dynamic operations such as insertion, deletion, and querying, providing an abstract view of the operations without specifying the implementation details.', 'Sorting an array is crucial for efficient set operations, with unordered arrays leading to linear time complexity for operations like searching and sorting, while sorted arrays enable faster operations with logarithmic time complexity.', 'Permutation sort incurs at least n factorial times n time complexity.', "The process of proving the recursive function's runtime involves hypothesizing its time complexity, using the technique of substitution, and verifying the relationship to conclude a linear runtime of theta of n.", 'The merge sort algorithm involves recursively dividing the array into smaller sub-arrays, sorting them, and then merging them together using the two-finger algorithm with a time complexity of O(n log n).']}