title
Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer

description
Learn and master the most common data structures in this full course from Google engineer William Fiset. This course teaches data structures to beginners using high quality animations to represent the data structures visually. You will learn how to code various data structures together with simple to follow step-by-step instructions. Every data structure presented will be accompanied by some working source code (in Java) to solidify your understanding. 💻 Code: https://github.com/williamfiset/data-structures 🎥 Course created by William Fiset. Check out his YouTube channel: https://www.youtube.com/channel/UCD8yeTczadqdARzQUp29PJw ⭐️ Course Contents ⭐️ ⌨️ (0:00:00) Abstract data types ⌨️ (0:04:28) Introduction to Big-O ⌨️ (0:17:00) Dynamic and Static Arrays ⌨️ (0:27:40) Dynamic Array Code ⌨️ (0:35:03) Linked Lists Introduction ⌨️ (0:49:16) Doubly Linked List Code ⌨️ (0:58:26) Stack Introduction ⌨️ (1:09:40) Stack Implementation ⌨️ (1:12:49) Stack Code ⌨️ (1:15:58) Queue Introduction ⌨️ (1:22:03) Queue Implementation ⌨️ (1:27:26) Queue Code ⌨️ (1:31:32) Priority Queue Introduction ⌨️ (1:44:16) Priority Queue Min Heaps and Max Heaps ⌨️ (1:49:55) Priority Queue Inserting Elements ⌨️ (1:59:27) Priority Queue Removing Elements ⌨️ (2:13:00) Priority Queue Code ⌨️ (2:28:26) Union Find Introduction ⌨️ (2:33:57) Union Find Kruskal's Algorithm ⌨️ (2:40:04) Union Find - Union and Find Operations ⌨️ (2:50:30) Union Find Path Compression ⌨️ (2:56:37) Union Find Code ⌨️ (3:03:54) Binary Search Tree Introduction ⌨️ (3:15:57) Binary Search Tree Insertion ⌨️ (3:21:20) Binary Search Tree Removal ⌨️ (3:34:47) Binary Search Tree Traversals ⌨️ (3:46:17) Binary Search Tree Code ⌨️ (3:59:26) Hash table hash function ⌨️ (4:16:25) Hash table separate chaining ⌨️ (4:24:10) Hash table separate chaining source code ⌨️ (4:35:44) Hash table open addressing ⌨️ (4:46:36) Hash table linear probing ⌨️ (5:00:21) Hash table quadratic probing ⌨️ (5:09:32) Hash table double hashing ⌨️ (5:23:56) Hash table open addressing removing ⌨️ (5:31:02) Hash table open addressing code ⌨️ (5:45:36) Fenwick Tree range queries ⌨️ (5:58:46) Fenwick Tree point updates ⌨️ (6:03:09) Fenwick Tree construction ⌨️ (6:09:21) Fenwick tree source code ⌨️ (6:14:47) Suffix Array introduction ⌨️ (6:17:54) Longest Common Prefix (LCP) array ⌨️ (6:21:07) Suffix array finding unique substrings ⌨️ (6:25:36) Longest common substring problem suffix array ⌨️ (6:37:04) Longest common substring problem suffix array part 2 ⌨️ (6:43:41) Longest Repeated Substring suffix array ⌨️ (6:48:13) Balanced binary search tree rotations ⌨️ (6:56:43) AVL tree insertion ⌨️ (7:05:42) AVL tree removals ⌨️ (7:14:12) AVL tree source code ⌨️ (7:30:49) Indexed Priority Queue | Data Structure ⌨️ (7:55:10) Indexed Priority Queue | Data Structure | Source Code -- Learn to code for free and get a developer job: https://www.freecodecamp.org Read hundreds of articles on programming: https://www.freecodecamp.org/news

detail
{'title': 'Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer', 'heatmap': [{'end': 24940.546, 'start': 24644.452, 'weight': 1}], 'summary': 'A comprehensive tutorial on data structures, covering abstract data types, array complexity analysis, stack and queue structures, binary heaps, priority queues, union find data structure, binary and search trees, hash tables, fenwick tree, suffix arrays, sliding window method, balanced binary search trees, avl tree operations, and indexed priority queue data structures, presented with detailed explanations and practical examples.', 'chapters': [{'end': 251.905, 'segs': [{'end': 59.948, 'src': 'embed', 'start': 27.294, 'weight': 0, 'content': [{'end': 37.997, 'text': 'It is a way of organizing data in some fashion so that later on, it can be accessed, queried, or perhaps even updated quickly and easily.', 'start': 27.294, 'duration': 10.703}, {'end': 51.542, 'text': 'So why data structures? Why are they important? Well, they are essential ingredients in creating fast and powerful algorithms.', 'start': 40.521, 'duration': 11.021}, {'end': 59.948, 'text': 'Another good reason might be that they help us manage and organize our data in a very natural way.', 'start': 52.483, 'duration': 7.465}], 'summary': 'Data structures are essential for creating fast algorithms and help in managing data efficiently.', 'duration': 32.654, 'max_score': 27.294, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM27294.jpg'}, {'end': 136.27, 'src': 'embed', 'start': 89.426, 'weight': 3, 'content': [{'end': 95.087, 'text': 'data structures can make the difference between having an okay product and an outstanding one.', 'start': 89.426, 'duration': 5.661}, {'end': 103.129, 'text': "It's no wonder that every computer science undergraduate student is required to take a course in data structures.", 'start': 95.487, 'duration': 7.642}, {'end': 113.231, 'text': 'It is strange that before we even begin talking about data structures that we need to talk about the abstraction of data structures.', 'start': 104.429, 'duration': 8.802}, {'end': 117.852, 'text': "What I'm talking about is the concept of an abstract data type.", 'start': 113.871, 'duration': 3.981}, {'end': 124.856, 'text': 'What is an abstract data type? And how does it differ from a data structure??', 'start': 120.791, 'duration': 4.065}, {'end': 136.27, 'text': 'Well, the answer is that an abstract data type is an abstraction of a data structure which provides only the interface to which that data structure must adhere to.', 'start': 125.517, 'duration': 10.753}], 'summary': 'Understanding data structures and abstract data types is crucial in computer science education.', 'duration': 46.844, 'max_score': 89.426, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM89426.jpg'}, {'end': 191.184, 'src': 'embed', 'start': 167.526, 'weight': 6, 'content': [{'end': 177.19, 'text': 'So which one do you choose? Some specific modes of transportation might be walking or biking, perhaps even taking a train and so on.', 'start': 167.526, 'duration': 9.664}, {'end': 183.893, 'text': 'These specific modes of transportation would be analogous to the data structures themselves.', 'start': 177.57, 'duration': 6.323}, {'end': 189.742, 'text': 'we want to get from one place to another through some mode of transportation.', 'start': 183.893, 'duration': 5.849}, {'end': 191.184, 'text': 'That was our abstract data type.', 'start': 189.782, 'duration': 1.402}], 'summary': 'Choosing from specific modes of transportation like walking, biking, or taking a train, analogous to data structures, to achieve the goal of moving from one place to another.', 'duration': 23.658, 'max_score': 167.526, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM167526.jpg'}], 'start': 0.47, 'title': 'Data structures and abstract data types', 'summary': 'Introduces the concept of data structures for organizing data efficiently, emphasizing their importance in creating fast algorithms. it discusses the significance of understanding abstract data types, highlighting their role in code cleanliness and product quality.', 'chapters': [{'end': 59.948, 'start': 0.47, 'title': 'Data structures: organizing data efficiently', 'summary': 'Introduces the concept of data structures as a way of organizing data efficiently, emphasizing their importance in creating fast and powerful algorithms and their role in managing and organizing data.', 'duration': 59.478, 'highlights': ['Data structures are a way of organizing data so that it can be used efficiently, playing a crucial role in creating fast and powerful algorithms.', 'Understanding data structures helps in managing and organizing data in a very natural way, emphasizing their importance in efficient data management.', 'Data structures enable efficient access, querying, and updating of data, highlighting the practical significance of organizing data effectively.']}, {'end': 251.905, 'start': 60.949, 'title': 'Understanding data structures and abstract data types', 'summary': 'Discusses the importance of understanding data structures and abstract data types, highlighting how they can make code cleaner and easier to understand and how they can be the difference between an okay product and an outstanding one. it emphasizes the significance of choosing the appropriate data structure for the task and the distinction between abstract data types and data structures.', 'duration': 190.956, 'highlights': ['Data structures can make the difference between having an okay product and an outstanding one.', "The ones who really excel are the ones who fundamentally understand how and when to use the appropriate data structure for the task they're trying to finish.", 'The chapter discusses the concept of an abstract data type and how it differs from a data structure.', 'An abstract data type is an abstraction of a data structure which provides only the interface to which that data structure must adhere to.', 'Abstract data types are compared to modes of transportation, while specific modes of transportation are analogous to the data structures themselves.']}], 'duration': 251.435, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM470.jpg', 'highlights': ['Data structures are a way of organizing data for efficient use, crucial for fast algorithms.', 'Understanding data structures is crucial for efficient data management and organization.', 'Data structures enable efficient access, querying, and updating of data.', 'Data structures can make the difference between an okay product and an outstanding one.', 'Fundamental understanding of appropriate data structure usage is key to excellence.', 'Abstract data type is an abstraction of a data structure, providing only the interface.', 'Comparison of abstract data types to modes of transportation for better understanding.']}, {'end': 987.506, 'segs': [{'end': 282.702, 'src': 'embed', 'start': 252.805, 'weight': 2, 'content': [{'end': 261.767, 'text': 'The point here is that the abstract data type only defines how a data structure should behave and what methods it should have,', 'start': 252.805, 'duration': 8.962}, {'end': 267.269, 'text': 'but not the details surrounding how those methods are implemented.', 'start': 261.767, 'duration': 5.502}, {'end': 272.437, 'text': 'All. right now that we were done with abstract data types,', 'start': 268.775, 'duration': 3.662}, {'end': 282.702, 'text': 'we need to have a quick look at the wild world of computational complexity to understand the performance that our data structures are providing.', 'start': 272.437, 'duration': 10.265}], 'summary': 'Abstract data types define structure behavior, computational complexity impacts performance.', 'duration': 29.897, 'max_score': 252.805, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM252805.jpg'}, {'end': 338.176, 'src': 'embed', 'start': 311.238, 'weight': 1, 'content': [{'end': 321.545, 'text': 'Similarly, if your program runs in constant time but requires a space equal to the sum of all the bytes of all the files on the internet,', 'start': 311.238, 'duration': 10.307}, {'end': 323.866, 'text': 'your algorithm is also useless.', 'start': 321.545, 'duration': 2.321}, {'end': 333.693, 'text': 'So to standardize a way of talking about how much time and how much space is required for an algorithm to run.', 'start': 325.888, 'duration': 7.805}, {'end': 338.176, 'text': 'theoretical computer scientists have invented big O notation.', 'start': 333.693, 'duration': 4.483}], 'summary': 'Big o notation standardizes time and space requirements for algorithms.', 'duration': 26.938, 'max_score': 311.238, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM311238.jpg'}, {'end': 886.628, 'src': 'embed', 'start': 841.411, 'weight': 0, 'content': [{'end': 852.013, 'text': 'So if you do the math, the worst case is you will do exactly log base 2 of n iterations, meaning that the binary search runs in logarithmic time.', 'start': 841.411, 'duration': 10.602}, {'end': 856.074, 'text': 'A very cool algorithm, a very powerful algorithm.', 'start': 853.113, 'duration': 2.961}, {'end': 859.849, 'text': "Here's a slightly different example worth going over.", 'start': 856.943, 'duration': 2.906}, {'end': 863.336, 'text': 'So first notice that there is an outer loop.', 'start': 860.871, 'duration': 2.465}, {'end': 867.322, 'text': 'with a counter i that does n work.', 'start': 864.161, 'duration': 3.161}, {'end': 875.604, 'text': 'Then notice that there are two inner loops, one that does 3n work and another one that does 2n work.', 'start': 867.902, 'duration': 7.702}, {'end': 886.628, 'text': 'So the rule we use to determine the complexity of this algorithm is to multiply loops on different levels and add those that are on the same generally speaking.', 'start': 876.305, 'duration': 10.323}], 'summary': 'Binary search runs in logarithmic time. algorithm involves loops with varying workloads.', 'duration': 45.217, 'max_score': 841.411, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM841411.jpg'}], 'start': 252.805, 'title': 'Abstract data types and algorithm complexity', 'summary': 'Explains abstract data types, computational complexity, and big o notation, highlighting worst-case time and space complexities. it introduces binary search algorithm with logarithmic time complexity and examples of algorithm complexities, including a big o notation of n to the fourth.', 'chapters': [{'end': 789.367, 'start': 252.805, 'title': 'Abstract data types and computational complexity', 'summary': 'Explains abstract data types and their behavior, introduces computational complexity and big o notation, highlighting worst-case time and space complexities, and demonstrating big o properties and examples of algorithm complexities.', 'duration': 536.562, 'highlights': ['The chapter explains abstract data types and their behavior, introducing computational complexity and big O notation, demonstrating worst-case time and space complexities, and providing examples of algorithm complexities.', "Big O notation standardizes a way of talking about time and space requirements for an algorithm, focusing on worst-case scenarios and ignoring input size when it's small.", 'The chapter provides examples of algorithms running in constant, linear, and quadratic time, explaining their time complexities and demonstrating how big O notation is used to analyze and compare different algorithms.']}, {'end': 987.506, 'start': 789.921, 'title': 'Binary search and algorithm complexity', 'summary': 'Explains the binary search algorithm, highlighting its logarithmic time complexity and provides examples of calculating algorithm complexities, with the most complex algorithm having a big o notation of n to the fourth.', 'duration': 197.585, 'highlights': ['The binary search algorithm has a logarithmic time complexity, running in exactly log base 2 of n iterations in the worst case scenario.', 'The algorithm complexity is determined by multiplying loops on different levels and adding those that are on the same level, resulting in a Big O notation of n squared for a specific example.', 'Another example involves a more complex algorithm with a Big O notation of n to the fourth, due to the dominant term in the function f of n.']}], 'duration': 734.701, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM252805.jpg', 'highlights': ['The binary search algorithm has a logarithmic time complexity, running in exactly log base 2 of n iterations in the worst case scenario.', "Big O notation standardizes a way of talking about time and space requirements for an algorithm, focusing on worst-case scenarios and ignoring input size when it's small.", 'The chapter explains abstract data types and their behavior, introducing computational complexity and big O notation, demonstrating worst-case time and space complexities, and providing examples of algorithm complexities.', 'The algorithm complexity is determined by multiplying loops on different levels and adding those that are on the same level, resulting in a Big O notation of n squared for a specific example.', 'The chapter provides examples of algorithms running in constant, linear, and quadratic time, explaining their time complexities and demonstrating how big O notation is used to analyze and compare different algorithms.']}, {'end': 1926.698, 'segs': [{'end': 1018.801, 'src': 'embed', 'start': 989.375, 'weight': 0, 'content': [{'end': 997.537, 'text': 'So if we have to find all the subsets of a set, that takes an exponential amount of time, because there are 2 to the n subsets.', 'start': 989.375, 'duration': 8.162}, {'end': 1001.998, 'text': 'Finding all permutations of a string takes big O of n factorial.', 'start': 998.077, 'duration': 3.921}, {'end': 1004.658, 'text': 'Another classic one is merge sort.', 'start': 1003.078, 'duration': 1.58}, {'end': 1009.359, 'text': 'So if we have n times log n for your merge sort.', 'start': 1004.898, 'duration': 4.461}, {'end': 1018.801, 'text': 'And if we have to iterate over all the cells of an array of size n by m, we have big O of nm time.', 'start': 1010.539, 'duration': 8.262}], 'summary': 'Finding subsets takes 2^n time, permutations take n!, merge sort takes n log n, and iterating over an n x m array takes nm time.', 'duration': 29.426, 'max_score': 989.375, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM989375.jpg'}, {'end': 1085.459, 'src': 'embed', 'start': 1049.423, 'weight': 1, 'content': [{'end': 1052.385, 'text': "So an outline for today's video.", 'start': 1049.423, 'duration': 2.962}, {'end': 1063.953, 'text': "First, we're going to begin by having a discussion about arrays and answer some fundamental questions such as what, where and how are arrays used.", 'start': 1052.906, 'duration': 11.047}, {'end': 1071.879, 'text': 'Next, I will explain the basic structure of an array and the common operations we are able to perform on them.', 'start': 1064.814, 'duration': 7.065}, {'end': 1085.459, 'text': 'Lastly, we will go over some complexity analysis and look at some source code on how to construct a dynamic array using only static arrays.', 'start': 1073.211, 'duration': 12.248}], 'summary': 'Video covers arrays: definition, operations, complexity analysis, and dynamic array construction.', 'duration': 36.036, 'max_score': 1049.423, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM1049423.jpg'}, {'end': 1467.396, 'src': 'embed', 'start': 1434.611, 'weight': 4, 'content': [{'end': 1447.824, 'text': 'Also remark that the very first element 44 is indexed or positioned at index of zero in the array, not one, zero.', 'start': 1434.611, 'duration': 13.213}, {'end': 1451.345, 'text': 'This confuses a lot of intro computer science students.', 'start': 1448.304, 'duration': 3.041}, {'end': 1460.987, 'text': 'The confusing part is that most if not all mathematics is one based while computer science is zero based.', 'start': 1452.265, 'duration': 8.722}, {'end': 1463.508, 'text': 'This is what causes the confusion.', 'start': 1461.767, 'duration': 1.741}, {'end': 1467.396, 'text': 'But worst of all is quantum computing.', 'start': 1464.414, 'duration': 2.982}], 'summary': 'Computer science uses zero-based indexing, confusing intro students.', 'duration': 32.785, 'max_score': 1434.611, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM1434611.jpg'}, {'end': 1605.734, 'src': 'embed', 'start': 1573.873, 'weight': 2, 'content': [{'end': 1578.714, 'text': 'So the dynamic array can do all the similar get set operation static arrays can do.', 'start': 1573.873, 'duration': 4.841}, {'end': 1583.876, 'text': 'But unlike the static array, it grows as dynamically as needed.', 'start': 1578.734, 'duration': 5.142}, {'end': 1592.998, 'text': 'So if we have a containing 34 and 4, then if we add minus 7, it gets appended to the end.', 'start': 1584.496, 'duration': 8.502}, {'end': 1598.24, 'text': "If we add 34 again, then it'll add it to the end.", 'start': 1593.799, 'duration': 4.441}, {'end': 1600.67, 'text': 'And we can also remove elements.', 'start': 1599.329, 'duration': 1.341}, {'end': 1604.253, 'text': 'So you see here our dynamic array shrank in size.', 'start': 1600.99, 'duration': 3.263}, {'end': 1605.734, 'text': 'Pretty cool, right?', 'start': 1605.154, 'duration': 0.58}], 'summary': 'Dynamic array grows as needed, can add/remove elements, shrinks as well.', 'duration': 31.861, 'max_score': 1573.873, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM1573873.jpg'}, {'end': 1771.614, 'src': 'embed', 'start': 1737.991, 'weight': 3, 'content': [{'end': 1743.955, 'text': "So I've designed an array class to support generics of type T.", 'start': 1737.991, 'duration': 5.964}, {'end': 1748.117, 'text': "So whatever type of data we want in this array, that's fine.", 'start': 1743.955, 'duration': 4.162}, {'end': 1757.043, 'text': 'So here are our three instance variables that we care about our which is our internal static array.', 'start': 1749.398, 'duration': 7.645}, {'end': 1762.092, 'text': 'Len, which is the length the user thinks the array is.', 'start': 1758.371, 'duration': 3.721}, {'end': 1766.213, 'text': 'And capacity is the length of the actual array.', 'start': 1762.992, 'duration': 3.221}, {'end': 1771.614, 'text': 'Because sometimes our array might have more free slots.', 'start': 1766.673, 'duration': 4.941}], 'summary': 'Designed array class for generics, with 3 instance variables: internal static array, len, and capacity.', 'duration': 33.623, 'max_score': 1737.991, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM1737991.jpg'}], 'start': 989.375, 'title': 'Array data structures and complexity analysis', 'summary': 'Delves into array complexity analysis, covering subsets, permutations, merge sort, and iterations. it also explores array fundamentals, structure, and diverse applications like lookup tables, buffers, and dynamic programming. additionally, it discusses array basics, indexing, dynamic arrays, and their implementation, including zero-based indexing confusion and dynamic array source code in java.', 'chapters': [{'end': 1357.899, 'start': 989.375, 'title': 'Array data structure and complexity analysis', 'summary': 'Discusses the complexity of finding subsets, permutations, merge sort, and array iterations. it also explores the fundamental usage of arrays, their structure, complexity analysis, and diverse applications, including lookup tables, buffers, and dynamic programming.', 'duration': 368.524, 'highlights': ['The chapter discusses the complexity of finding subsets, permutations, merge sort, and array iterations.', 'The chapter explores the fundamental usage of arrays, their structure, complexity analysis, and diverse applications, including lookup tables, buffers, and dynamic programming.']}, {'end': 1926.698, 'start': 1358.499, 'title': 'Understanding arrays: indexing, dynamic arrays, and source code', 'summary': 'Discusses the basics of arrays, emphasizing indexing, dynamic arrays, and their implementation, with insights into the confusion caused by zero-based indexing and a deep dive into dynamic array source code in java.', 'duration': 568.199, 'highlights': ['The array contains the values 44, 12, -5, 17, 6, 0, 3, 9, 100.', 'The very first element, 44, has index or position 0 in the array, not one.', 'Quantum computing tries to please mathematicians, computer scientists, and physicists all at the same time.', 'Dynamic arrays can grow and shrink in size as needed.', 'Dynamic arrays are typically implemented with a static array and the size is doubled when capacity is exceeded.', 'The source code is designed to support generics of type T and includes methods for adding, removing, and resizing the array.']}], 'duration': 937.323, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM989375.jpg', 'highlights': ['The chapter explores the complexity of finding subsets, permutations, merge sort, and array iterations.', 'The chapter delves into the fundamental usage of arrays, their structure, complexity analysis, and diverse applications.', 'Dynamic arrays can grow and shrink in size as needed.', 'The source code is designed to support generics of type T and includes methods for adding, removing, and resizing the array.', 'The very first element, 44, has index or position 0 in the array, not one.']}, {'end': 3441.25, 'segs': [{'end': 2101.356, 'src': 'embed', 'start': 2072.337, 'weight': 0, 'content': [{'end': 2084.168, 'text': 'Also, There is the next method, which just returns the next element in the array relative to the iterator.', 'start': 2072.337, 'duration': 11.831}, {'end': 2090.231, 'text': 'OK, and lastly is the toString to get a string representation of this array.', 'start': 2085.748, 'duration': 4.483}, {'end': 2092.331, 'text': 'Nothing too complicated.', 'start': 2090.991, 'duration': 1.34}, {'end': 2095.993, 'text': 'All right, so this is a very simple data structure.', 'start': 2092.351, 'duration': 3.642}, {'end': 2097.234, 'text': "It's just a dynamic array.", 'start': 2096.053, 'duration': 1.181}, {'end': 2101.356, 'text': "If you look at Java's array list, it looks very, very similar to this.", 'start': 2097.414, 'duration': 3.942}], 'summary': "Introduction to a simple dynamic array data structure with similarity to java's array list.", 'duration': 29.019, 'max_score': 2072.337, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM2072337.jpg'}, {'end': 2173.15, 'src': 'embed', 'start': 2147.264, 'weight': 1, 'content': [{'end': 2153.969, 'text': 'then how to insert and remove elements from both singly and doubly linked lists, as well as some source code.', 'start': 2147.264, 'duration': 6.705}, {'end': 2155.35, 'text': 'So stay tuned.', 'start': 2154.15, 'duration': 1.2}, {'end': 2157.152, 'text': 'All right, discussion.', 'start': 2156.291, 'duration': 0.861}, {'end': 2167.347, 'text': 'So what is a linked list? A linked list is a sequential list of nodes that hold data which point to other nodes also containing data.', 'start': 2159.363, 'duration': 7.984}, {'end': 2173.15, 'text': 'So below is an example of a singly linked list containing some arbitrary data.', 'start': 2168.088, 'duration': 5.062}], 'summary': 'Linked list: sequential nodes holding data, with examples of singly linked list.', 'duration': 25.886, 'max_score': 2147.264, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM2147264.jpg'}, {'end': 2765.695, 'src': 'embed', 'start': 2739.032, 'weight': 2, 'content': [{'end': 2745.875, 'text': 'This is especially important in C and C++ and other programming languages where you manage your memory.', 'start': 2739.032, 'duration': 6.843}, {'end': 2748.305, 'text': 'Now you can see that nine is gone.', 'start': 2746.784, 'duration': 1.521}, {'end': 2751.707, 'text': 'And our singly linked list is shorter.', 'start': 2748.985, 'duration': 2.722}, {'end': 2756.55, 'text': 'Okay, now for the last bit of implementation.', 'start': 2753.688, 'duration': 2.862}, {'end': 2765.695, 'text': "let's look at how to remove nodes from a doubly linked list, which is actually easier, in my opinion, to removing from singly linked lists.", 'start': 2756.55, 'duration': 9.145}], 'summary': 'Demonstration of removing nodes from a linked list in c/c++, reducing list length to nine nodes, and discussing easier removal from doubly linked lists.', 'duration': 26.663, 'max_score': 2739.032, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM2739032.jpg'}, {'end': 2865.32, 'src': 'embed', 'start': 2834.116, 'weight': 3, 'content': [{'end': 2842.161, 'text': 'And now if we flatten out the doubly linked list, we see that it no longer contains 9.', 'start': 2834.116, 'duration': 8.045}, {'end': 2846.103, 'text': "Let's do a bit of complexity analysis on linked lists.", 'start': 2842.161, 'duration': 3.942}, {'end': 2855.393, 'text': 'How good actually are linked lists? On the left column, we have singly linked lists, and on the right, doubly linked lists.', 'start': 2846.563, 'duration': 8.83}, {'end': 2865.32, 'text': "The complexity for searching in a linked list is linear in the worst case, because if the element we're looking for is not there,", 'start': 2856.193, 'duration': 9.127}], 'summary': 'Linked lists have linear search complexity in the worst case.', 'duration': 31.204, 'max_score': 2834.116, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM2834116.jpg'}], 'start': 1928.059, 'title': 'Data structures implementation', 'summary': 'Delves into the implementation of dynamic array, linked lists (singly and doubly), and their complexities. it covers methods such as remove, indexof, contains, iterator, hasnext, next, and tostring, along with the trade-offs, memory management, and complexity analysis.', 'chapters': [{'end': 2101.356, 'start': 1928.059, 'title': 'Dynamic array implementation', 'summary': 'Discusses the implementation of a dynamic array, demonstrating methods such as remove, indexof, contains, iterator, hasnext, next, and tostring, and their functionalities to manipulate the array.', 'duration': 173.297, 'highlights': ['The chapter discusses the implementation of a dynamic array, demonstrating methods such as remove, indexOf, contains, iterator, hasNext, next, and toString.', 'The remove method scans through the array, removes the specified object at the index, and returns true if found; otherwise, it returns false.', 'The indexOf method returns the index of the specified object if found, otherwise returns -1.', 'The contains method checks if the object exists in the array by utilizing the indexOf method.', 'The iterator method returns an iterator for the array, providing an abstraction for iteration and overriding hasNext and next methods.', 'The hasNext method checks if there exists a next element in the array based on the current index and performs potential concurrent modification checks.', 'The next method returns the next element in the array relative to the iterator.', 'The toString method provides a string representation of the array.']}, {'end': 2426.89, 'start': 2102.318, 'title': 'Linked lists: singly vs. doubly', 'summary': 'Discusses the basics of singly and doubly linked lists, including their usage, terminology, and the pros and cons of each. it also highlights the trade-offs between singly and doubly linked lists, with a focus on memory usage and access to previous elements.', 'duration': 324.572, 'highlights': ['A linked list is a sequential list of nodes that hold data which point to other nodes also containing data, commonly used in abstract data types, circular lists, real world object modeling, hash table separate chaining, and adjacency lists and graphs.', 'Singly linked lists use less memory but do not allow access to previous elements, whereas doubly linked lists allow for easy traversal of the list backwards and constant time removal of nodes, but use up twice as much memory.', 'Doubly linked lists allow for easy traversal of the list backwards and constant time removal of nodes, but use up twice as much memory.', 'Singly linked lists use less memory but do not allow access to previous elements, whereas doubly linked lists allow for easy traversal of the list backwards and constant time removal of nodes.']}, {'end': 2832.995, 'start': 2426.91, 'title': 'Linked lists implementation details', 'summary': 'Covers the implementation details of creating and removing elements from singly and doubly linked lists, emphasizing the process of inserting and removing nodes while highlighting the use of pointers and traversal. it also emphasizes the significance of memory management, particularly in c and c++.', 'duration': 406.085, 'highlights': ['The chapter emphasizes the process of inserting and removing nodes in singly and doubly linked lists, with a focus on the use of pointers, traversal, and memory management.', 'In the demonstration of inserting 11 into a singly linked list, it is highlighted that four pointers are changed to correctly insert the node at the desired position.', 'The explanation of removing elements from a singly linked list emphasizes the use of two pointers, Traverser1 and Traverser2, to efficiently identify and remove the targeted node, while also emphasizing the importance of memory deallocation.', 'The process of removing nodes from a doubly linked list is highlighted as easier compared to singly linked lists, with the emphasis on using only one traverser pointer and the automatic reference to the last node in the list.']}, {'end': 3441.25, 'start': 2834.116, 'title': 'Linked list complexity analysis & doubly linked list implementation', 'summary': 'Discusses the complexity analysis of singly and doubly linked lists, highlighting the constant time complexity for inserting at the head and tail, and the linear time complexity for removing from the tail in singly linked lists. it also provides a detailed implementation of a doubly linked list in java, including methods for adding, removing, and peeking elements.', 'duration': 607.134, 'highlights': ["The complexity for searching in a linked list is linear in the worst case, because if the element we're looking for is not there, we have to traverse all of the n elements.", 'Inserting at the head, though, is constant time, because we always maintain a pointer to the head for a linked list.', 'To remove the head of a singly linked list and a doubly linked list is also constant time, again, because we have a reference to it.', 'However, removing from the tail is another story. It takes linear time to remove elements from a singly linked list.', 'Doubly linked lists, however, do not have this problem, since they have a pointer to the previous node. So we can continually remove nodes from the tail.', 'This is part two of two in the linked list series. So the link for the source code can be found on GitHub at github.com slash Williams is a slash data dash structures.', 'We are keeping track of the size of the linked list, as well as what the head and the tail currently are.', "So if the list is not empty, then we say the head's previous pointer is equal to this new node. And then we set the head pointer to be whatever head's previous is.", 'Peaking is just looking at either the element at the beginning of the linked list or at the end of the linked list.', 'We can pretend that they are. So first check that the index is valid.', "So we're going to also support searching for null values in case someone decided that the value of the node should be null."]}], 'duration': 1513.191, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM1928059.jpg', 'highlights': ['The chapter discusses the implementation of a dynamic array, demonstrating methods such as remove, indexOf, contains, iterator, hasNext, next, and toString.', 'A linked list is a sequential list of nodes that hold data which point to other nodes, commonly used in abstract data types, circular lists, real world object modeling, hash table separate chaining, and adjacency lists and graphs.', 'The chapter emphasizes the process of inserting and removing nodes in singly and doubly linked lists, with a focus on the use of pointers, traversal, and memory management.', "The complexity for searching in a linked list is linear in the worst case, because if the element we're looking for is not there, we have to traverse all of the n elements."]}, {'end': 4829.615, 'segs': [{'end': 3600.663, 'src': 'embed', 'start': 3571.024, 'weight': 1, 'content': [{'end': 3582.531, 'text': 'A stack is a one ended linear data structure which models a real world stack by having two primary operations, namely push and pop.', 'start': 3571.024, 'duration': 11.507}, {'end': 3586.994, 'text': 'Below you can see an image of a stack I have constructed.', 'start': 3583.352, 'duration': 3.642}, {'end': 3594.458, 'text': 'There is one data member getting popped off the top of the stack and another data member getting added to the stack.', 'start': 3587.694, 'duration': 6.764}, {'end': 3600.663, 'text': 'Notice that there is a top pointer pointing to the to the block at the top of the stack.', 'start': 3595.559, 'duration': 5.104}], 'summary': 'A stack is a one-ended linear data structure with push and pop operations.', 'duration': 29.639, 'max_score': 3571.024, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM3571024.jpg'}, {'end': 3721.412, 'src': 'embed', 'start': 3693.446, 'weight': 0, 'content': [{'end': 3698.33, 'text': 'This is critical in our understanding of how a stack works.', 'start': 3693.446, 'duration': 4.884}, {'end': 3707.118, 'text': 'So when and where is a stack used? Stacks are surprisingly used absolutely everywhere.', 'start': 3699.431, 'duration': 7.687}, {'end': 3714.09, 'text': "They're used in text editors to enter text you've written in browsers to navigate backwards and forwards.", 'start': 3708.049, 'duration': 6.041}, {'end': 3721.412, 'text': "They're used in compilers to make sure you have the correct number of matching braces and in the right order.", 'start': 3714.71, 'duration': 6.702}], 'summary': 'Stacks are used extensively, from text editors to compilers.', 'duration': 27.966, 'max_score': 3693.446, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM3693446.jpg'}, {'end': 4119.176, 'src': 'embed', 'start': 4085.27, 'weight': 2, 'content': [{'end': 4092.855, 'text': 'I want to take a moment and look at the Tower of Hanoi, a very popular game amongst mathematicians and computer scientists,', 'start': 4085.27, 'duration': 7.585}, {'end': 4094.977, 'text': 'to see how it relates with stacks.', 'start': 4092.855, 'duration': 2.122}, {'end': 4096.957, 'text': 'The game is played as follows.', 'start': 4095.617, 'duration': 1.34}, {'end': 4106.604, 'text': 'You start with a pile of disks on the first peg on the left, and the objective of the game is to move all the disks to the right most disk pile.', 'start': 4097.618, 'duration': 8.986}, {'end': 4119.176, 'text': 'At each move, you can move the top disk of any pile to any other pile with a restriction that no disk be placed on top of a smaller disk.', 'start': 4107.225, 'duration': 11.951}], 'summary': "Analyzing tower of hanoi game's relation with stacks.", 'duration': 33.906, 'max_score': 4085.27, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM4085270.jpg'}, {'end': 4622.321, 'src': 'embed', 'start': 4589.339, 'weight': 3, 'content': [{'end': 4591.02, 'text': 'at the very end in the last video.', 'start': 4589.339, 'duration': 1.681}, {'end': 4594.178, 'text': 'So a discussion about queues.', 'start': 4592.657, 'duration': 1.521}, {'end': 4605.424, 'text': 'So what exactly is a queue? So below you can see an image of a queue, but a queue is just a linear data structure that models a real world queue.', 'start': 4594.538, 'duration': 10.886}, {'end': 4611.487, 'text': 'Having two primary operations we can do, which are enqueuing and dequeuing.', 'start': 4606.484, 'duration': 5.003}, {'end': 4616.79, 'text': 'So every queue has a front and a back end.', 'start': 4613.748, 'duration': 3.042}, {'end': 4622.321, 'text': 'We insert elements through the back and remove through the front.', 'start': 4617.796, 'duration': 4.525}], 'summary': 'A queue is a linear data structure with enqueuing and dequeuing operations.', 'duration': 32.982, 'max_score': 4589.339, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM4589339.jpg'}], 'start': 3442.601, 'title': 'Stack and queue data structures', 'summary': 'Provides an overview of the stack data structure, including its definition, operations, and a detailed example of adding and removing elements, along with the versatile applications of stacks in programming. it also explores the tower of hanoi game and its resemblance to stacks, covers the implementation of a stack using a doubly linked list in java, and provides a brief overview of the queue data structure and its real-world applications.', 'chapters': [{'end': 3692.765, 'start': 3442.601, 'title': 'Stack data structure overview', 'summary': 'Provides an overview of the stack data structure, including its definition, operations, and a detailed example of adding and removing elements from a stack, demonstrating the last in first out (lifo) behavior.', 'duration': 250.164, 'highlights': ['A stack is a one ended linear data structure with primary operations push and pop, exhibiting last in first out (LIFO) behavior.', 'Detailed example demonstrating the addition and removal of elements from a stack, following the LIFO behavior.', 'Overview of the upcoming topics in the video series, including stack implementation, examples, internal implementation, and time complexity.']}, {'end': 4083.602, 'start': 3693.446, 'title': 'Understanding stacks and their applications', 'summary': 'Explores the versatile applications of stacks in programming, such as text editors, compilers, recursion, depth first search, and complexity analysis, and provides a detailed example of using stacks to validate bracket sequences.', 'duration': 390.156, 'highlights': ['The chapter demonstrates the widespread use of stacks in programming, including text editors, browsers, compilers, real-world modeling, recursion, and graph traversal, exemplifying their ubiquitous nature.', 'It explains the efficiency of stack operations, with constant time for pushing, popping, and peeking, and linear time for searching, providing a comprehensive complexity analysis for stack implementation.', 'The detailed example illustrates the algorithmic use of stacks to validate bracket sequences, including the step-by-step process and pseudocode for determining the validity of bracket sequences using stacks.']}, {'end': 4326.857, 'start': 4085.27, 'title': 'Tower of hanoi and implementing a stack', 'summary': 'Explores the tower of hanoi game and its resemblance to stacks, then discusses the implementation of a stack using a singly linked list, highlighting the process of pushing and popping elements.', 'duration': 241.587, 'highlights': ['The Tower of Hanoi game is played by moving disks from the leftmost pile to the rightmost pile, simulating the behavior of a stack.', 'Implementing a stack can be achieved using a singly linked list, where new elements are inserted before the head, and popping elements involves moving the head pointer to the next node and deallocating the last node.']}, {'end': 4534.529, 'start': 4327.557, 'title': 'Implementing a simple stack in java', 'summary': 'Covers the implementation of a stack using a doubly linked list in java, including methods for size, push, pop, and peek, as well as a call to action for engagement with the github repository.', 'duration': 206.972, 'highlights': ['The chapter covers the implementation of a stack using a doubly linked list in Java, including methods for size, push, pop, and peek.', 'The source code for the stack implementation can be found at github.com/WilliamFizet/data-structures.', 'The implementation includes two constructors, methods for size, push, pop, and peek, and a check for stack emptiness before performing pop and peek operations.']}, {'end': 4829.615, 'start': 4536.549, 'title': 'Queue data structure overview', 'summary': 'Provides a brief overview of the queue data structure, explaining its fundamental operations, terminology, and real-world applications, accompanied by a detailed example. it also mentions the role of queues in server management and highlights their use in modeling real-world queues.', 'duration': 293.066, 'highlights': ['Queues are a fundamental data structure with two primary operations: enqueuing and dequeuing, and they are often used to model real-world queues. Enqueuing adds elements to the back of the queue, while dequeuing removes elements from the front.', 'The chapter provides a detailed example of enqueuing and dequeuing operations, demonstrating the functionality of a queue with specific elements being added and removed.', 'The real-world applications of queues include modeling physical queues such as those in movie theaters and restaurants, as well as managing server requests by maintaining a limited queue of incoming requests.', 'The chapter emphasizes the use of queues in server management, illustrating a scenario where a web server can only process a limited number of requests simultaneously, which can be managed using a queue to handle incoming requests.', 'The discussion also highlights the potential use of queues for managing sequences of elements, where only the most recent elements need to be tracked, with older elements being dequeued as the queue size exceeds a certain threshold.']}], 'duration': 1387.014, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM3442601.jpg', 'highlights': ['The widespread use of stacks in programming, including text editors, browsers, compilers, real-world modeling, recursion, and graph traversal.', 'A stack is a one ended linear data structure with primary operations push and pop, exhibiting last in first out (LIFO) behavior.', 'The Tower of Hanoi game is played by moving disks from the leftmost pile to the rightmost pile, simulating the behavior of a stack.', 'Queues are a fundamental data structure with two primary operations: enqueuing and dequeuing, often used to model real-world queues.']}, {'end': 6514.744, 'segs': [{'end': 4855.101, 'src': 'embed', 'start': 4830.115, 'weight': 9, 'content': [{'end': 4838.017, 'text': "So what you do is you process the five that you're able to, and the remaining seven get to chill in a queue waiting to be served.", 'start': 4830.115, 'duration': 7.902}, {'end': 4848.179, 'text': 'And whenever you finish processing a request, you dequeue the next request and then you start processing it, and you do this until the queue is empty.', 'start': 4838.817, 'duration': 9.362}, {'end': 4855.101, 'text': "While you're doing this, more requests come in to access your web page, while you just add them to the end of the queue.", 'start': 4849.04, 'duration': 6.061}], 'summary': 'Process 5 requests, queue 7, handle new requests', 'duration': 24.986, 'max_score': 4830.115, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM4830115.jpg'}, {'end': 4948.243, 'src': 'embed', 'start': 4874.556, 'weight': 4, 'content': [{'end': 4879.922, 'text': "So as we've seen, it's pretty obvious that enqueuing and dequeuing operations are constant time.", 'start': 4874.556, 'duration': 5.366}, {'end': 4885.686, 'text': "There's also another operation on a queue I have not mentioned yet, and this is peaking.", 'start': 4880.742, 'duration': 4.944}, {'end': 4891.45, 'text': "Peaking means that we're looking at the value at the front of the queue without removing it.", 'start': 4886.366, 'duration': 5.084}, {'end': 4893.812, 'text': 'This is also constant time.', 'start': 4892.371, 'duration': 1.441}, {'end': 4904.541, 'text': 'However, checking if an element is contained within the queue is linear time, since we would potentially need to scan through all of the elements.', 'start': 4894.733, 'duration': 9.808}, {'end': 4915.043, 'text': "There's also element removal, not in the sense of dequeuing or polling, but in actually removing an element from the queue internally.", 'start': 4906.155, 'duration': 8.888}, {'end': 4921.469, 'text': 'This also requires linear time, since we would have to scan through all the elements in the worst case.', 'start': 4915.523, 'duration': 5.946}, {'end': 4929.018, 'text': "In this video we're going to have a look at how queues are used to do a breadth-first search,", 'start': 4923.257, 'duration': 5.761}, {'end': 4936.8, 'text': "and then we're going to look at the actual implementation details of how enqueuing and dequeuing elements works.", 'start': 4929.018, 'duration': 7.782}, {'end': 4940.921, 'text': 'OK, on to the breadth-first search example.', 'start': 4938.641, 'duration': 2.28}, {'end': 4948.243, 'text': 'So a breadth-first search is an operation we can do on the graph to do a graph traversal.', 'start': 4942.201, 'duration': 6.042}], 'summary': 'Enqueuing and dequeuing in a queue are constant time operations. peaking is also constant time, but element containment check and internal element removal are linear time. queues are used for breadth-first search operation on a graph.', 'duration': 73.687, 'max_score': 4874.556, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM4874556.jpg'}, {'end': 4995.603, 'src': 'embed', 'start': 4966.289, 'weight': 1, 'content': [{'end': 4978.917, 'text': 'first by visiting all the neighbors of the starting node and then visiting all the neighbors of the first node you visited and then all the neighbors of the second node you visited,', 'start': 4966.289, 'duration': 12.628}, {'end': 4983.981, 'text': 'and so on and so forth, expanding through all the neighbors as you go.', 'start': 4978.917, 'duration': 5.064}, {'end': 4995.603, 'text': 'So you can think of each iteration of the breadth first search as expanding the frontier from one node outwards at each iteration as you go on.', 'start': 4985.336, 'duration': 10.267}], 'summary': 'Breadth first search expands frontier from one node outwards at each iteration.', 'duration': 29.314, 'max_score': 4966.289, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM4966289.jpg'}, {'end': 5094.442, 'src': 'embed', 'start': 5061.942, 'weight': 7, 'content': [{'end': 5065.605, 'text': 'So suppose we wanted to actually code a breadth-first search.', 'start': 5061.942, 'duration': 3.663}, {'end': 5070.294, 'text': 'How would that be done? Well, the idea is to use a queue.', 'start': 5065.665, 'duration': 4.629}, {'end': 5075.855, 'text': 'So first, we add the starting node to our queue.', 'start': 5071.454, 'duration': 4.401}, {'end': 5079.496, 'text': 'And then we mark the starting node as visited.', 'start': 5076.915, 'duration': 2.581}, {'end': 5087.538, 'text': 'And while our queue is not empty, we pull an element from our queue, or dequeuing.', 'start': 5080.196, 'duration': 7.342}, {'end': 5094.442, 'text': 'And then for every neighbor of this node we just dequeued.', 'start': 5088.68, 'duration': 5.762}], 'summary': 'Breadth-first search uses a queue to visit nodes in order, marking them as visited.', 'duration': 32.5, 'max_score': 5061.942, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM5061942.jpg'}, {'end': 5502.952, 'src': 'embed', 'start': 5474.678, 'weight': 6, 'content': [{'end': 5482.765, 'text': 'This is a lot faster than having to maintain references to the next nodes, such as in a linked list.', 'start': 5474.678, 'duration': 8.087}, {'end': 5485.727, 'text': "So I guess I'll say that's your homework.", 'start': 5483.445, 'duration': 2.282}, {'end': 5490.764, 'text': 'is to create a static array based queue.', 'start': 5486.661, 'duration': 4.103}, {'end': 5499.049, 'text': "Today, we're going to talk about everything to do with priority queues, from where they're used to how they're implemented.", 'start': 5491.344, 'duration': 7.705}, {'end': 5502.952, 'text': "And towards the end, we'll also have a look at some source code.", 'start': 5499.77, 'duration': 3.182}], 'summary': 'Create a static array-based queue for homework, prioritize queues discussed, and source code reviewed.', 'duration': 28.274, 'max_score': 5474.678, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM5474678.jpg'}, {'end': 5613.353, 'src': 'embed', 'start': 5582.435, 'weight': 2, 'content': [{'end': 5585.318, 'text': "So there's a lot to cover, so let's get started.", 'start': 5582.435, 'duration': 2.883}, {'end': 5589.14, 'text': 'discussion and examples.', 'start': 5587.399, 'duration': 1.741}, {'end': 5593.682, 'text': 'This is going to be part one of five in the priority queue series.', 'start': 5589.68, 'duration': 4.002}, {'end': 5596.864, 'text': 'So what is a priority queue?', 'start': 5594.283, 'duration': 2.581}, {'end': 5607.009, 'text': 'A priority queue is an abstract data type that operates similar to a normal queue, except for the fact that every element has a certain priority.', 'start': 5597.464, 'duration': 9.545}, {'end': 5613.353, 'text': 'So elements with a higher priority come out of the priority queue first.', 'start': 5607.49, 'duration': 5.863}], 'summary': 'Part one of a series on priority queue, an abstract data type with elements having different priorities.', 'duration': 30.918, 'max_score': 5582.435, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM5582435.jpg'}, {'end': 5876.339, 'src': 'embed', 'start': 5851.187, 'weight': 3, 'content': [{'end': 5860.934, 'text': 'So why are we interested in heaps? Well, heaps form the canonical underlying data structure for priority queues.', 'start': 5851.187, 'duration': 9.747}, {'end': 5868.276, 'text': "So much so that priority queues are sometimes called heaps, although this isn't technically correct,", 'start': 5862.074, 'duration': 6.202}, {'end': 5876.339, 'text': 'since the priority queue again is an abstract data type, meaning it can be implemented with other data structures also.', 'start': 5868.276, 'duration': 8.063}], 'summary': 'Heaps are important for priority queues and serve as their canonical underlying data structure.', 'duration': 25.152, 'max_score': 5851.187, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM5851187.jpg'}, {'end': 6077.497, 'src': 'embed', 'start': 6050.458, 'weight': 0, 'content': [{'end': 6057.787, 'text': "They're also used in Huffman encoding, which is often used for lossless data compression.", 'start': 6050.458, 'duration': 7.329}, {'end': 6069.22, 'text': "Many best first search algorithms use priority queues in their implementation to continuously again grab the next most promising node in the graph as it's being traversed.", 'start': 6059.328, 'duration': 9.892}, {'end': 6077.497, 'text': "And finally, we also see priority queues in PRIM's minimum spanning tree algorithm on directed graphs.", 'start': 6070.615, 'duration': 6.882}], 'summary': "Priority queues used in huffman encoding, best-first search, and prim's algorithm.", 'duration': 27.039, 'max_score': 6050.458, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM6050458.jpg'}], 'start': 4830.115, 'title': 'Queue operations and priority queues', 'summary': 'Explains queue operations including enqueuing, dequeuing, and complexity analysis, and covers priority queues, their implementation, usage in algorithms, and the role of heaps as the underlying data structure.', 'chapters': [{'end': 4921.469, 'start': 4830.115, 'title': 'Queue operations and complexity analysis', 'summary': 'Explains the operations of a queue, including enqueuing, dequeuing, and peaking, and highlights the complexity analysis of each operation, with enqueuing and dequeuing being constant time and checking for element containment and removal being linear time.', 'duration': 91.354, 'highlights': ['Enqueuing and dequeuing operations are constant time, while checking for element containment and removal are linear time.', 'Peaking, which involves looking at the value at the front of the queue without removing it, is also a constant time operation.', 'Queues are used to process requests, with the ability to process five requests at a time and adding additional requests to the end of the queue.', 'In graph theory, queues are utilized for performing a breadth-first search traversal, offering practical applications.']}, {'end': 5425.153, 'start': 4923.257, 'title': 'Breadth-first search & queue implementation', 'summary': 'Explains breadth-first search on a graph, demonstrating the traversal process and the implementation details using a queue, while also discussing the implementation of queues using linked lists and arrays.', 'duration': 501.896, 'highlights': ['Breadth-first search is an operation on a graph to traverse the entire graph by visiting all the neighbors of each node in an expanding manner, and it is demonstrated with an example of traversing a graph starting from node 0.', 'The process of implementing a breadth-first search involves using a queue to add and remove elements, marking visited nodes, and adding unvisited neighbors to the queue, making it a popular graph traversal algorithm.', 'The implementation of queues is discussed, with a focus on enqueuing and dequeuing elements using singly linked lists and the importance of ensuring the array size is sufficient when using arrays to implement a queue.']}, {'end': 6016.925, 'start': 5426.434, 'title': 'Priority queues & heaps', 'summary': 'Covers the basics of priority queues, including their implementation using static arrays and the role of heaps as the underlying data structure for priority queues. it also discusses the concepts of min and max heaps, their properties, and their relevance to priority queues.', 'duration': 590.491, 'highlights': ['Priority queues can be implemented using static arrays for faster processing, especially when the maximum number of elements is known, resulting in efficient addition and removal operations.', 'The chapter introduces the concept of priority queues as an abstract data type that operates similar to a normal queue but with elements having a certain priority, and the importance of comparable elements for priority queue support.', 'The discussion explores the use of heaps as the canonical underlying data structure for priority queues, distinguishing between max heaps and min heaps and their role in implementing priority queues.']}, {'end': 6514.744, 'start': 6019.987, 'title': 'Priority queues and heaps', 'summary': "Covers the usage of priority queues in algorithms such as dijkstra's shortest path, huffman encoding, best first search, and prim's minimum spanning tree. it also explains the complexity of priority queues implemented as a binary heap and the method to convert a min priority queue into a max priority queue.", 'duration': 494.757, 'highlights': ["Priority queues are used in Dijkstra's shortest path, Huffman encoding, best first search, and PRIM's minimum spanning tree algorithms.", 'Constructing a binary heap from an unordered array takes linear time and forms the basis for the sorting algorithm heap sort.', 'Removing an element from the root of the heap takes logarithmic time, while peeking takes constant time.', 'A method utilizing a hash table can reduce the removing time complexity of a heap to be logarithmic.', 'Converting a min priority queue into a max priority queue involves abusing the fact that all elements in a priority queue must implement some sort of comparable interface.']}], 'duration': 1684.629, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM4830115.jpg', 'highlights': ["Priority queues are used in Dijkstra's shortest path, Huffman encoding, best first search, and PRIM's minimum spanning tree algorithms.", 'Breadth-first search is an operation on a graph to traverse the entire graph by visiting all the neighbors of each node in an expanding manner, and it is demonstrated with an example of traversing a graph starting from node 0.', 'The chapter introduces the concept of priority queues as an abstract data type that operates similar to a normal queue but with elements having a certain priority, and the importance of comparable elements for priority queue support.', 'The discussion explores the use of heaps as the canonical underlying data structure for priority queues, distinguishing between max heaps and min heaps and their role in implementing priority queues.', 'Enqueuing and dequeuing operations are constant time, while checking for element containment and removal are linear time.', 'Peaking, which involves looking at the value at the front of the queue without removing it, is also a constant time operation.', 'Priority queues can be implemented using static arrays for faster processing, especially when the maximum number of elements is known, resulting in efficient addition and removal operations.', 'The process of implementing a breadth-first search involves using a queue to add and remove elements, marking visited nodes, and adding unvisited neighbors to the queue, making it a popular graph traversal algorithm.', 'In graph theory, queues are utilized for performing a breadth-first search traversal, offering practical applications.', 'Queues are used to process requests, with the ability to process five requests at a time and adding additional requests to the end of the queue.']}, {'end': 7979.464, 'segs': [{'end': 6573.942, 'src': 'embed', 'start': 6514.744, 'weight': 0, 'content': [{'end': 6530.516, 'text': "but we're interested in negating lex so that longer strings appear before shorter strings and also that strings with letters at the end of the alphabet appear before those containing letters at the beginning of the alphabet.", 'start': 6514.744, 'duration': 15.772}, {'end': 6531.556, 'text': 'I think I said that right.', 'start': 6530.716, 'duration': 0.84}, {'end': 6537.441, 'text': 'This would, in effect, turn a min heap into a max heap.', 'start': 6533.398, 'duration': 4.043}, {'end': 6539.454, 'text': "Let's look at a concrete example.", 'start': 6538.039, 'duration': 1.415}, {'end': 6550.353, 'text': "So by adding all the numbers on the right to our prior queue with a lexicographic comparator, here's the ordering we should expect.", 'start': 6541.206, 'duration': 9.147}, {'end': 6560.722, 'text': "First, we get a, because it's the shortest string that has characters appearing closest to the start of the alphabet.", 'start': 6551.094, 'duration': 9.628}, {'end': 6567.948, 'text': 'Then it comes out b, then fz, then x, then xr, and xx.', 'start': 6561.182, 'duration': 6.766}, {'end': 6573.942, 'text': "So now let's do the same thing with nlex.", 'start': 6571.581, 'duration': 2.361}], 'summary': 'Negating lex to prioritize longer strings and end-of-alphabet characters, turning min heap into max heap.', 'duration': 59.198, 'max_score': 6514.744, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM6514744.jpg'}, {'end': 6638.478, 'src': 'embed', 'start': 6607.165, 'weight': 10, 'content': [{'end': 6619.829, 'text': "But first there's some important terminology and concepts leading to that which we need to go over prior to add elements effectively to our Priority Queue.", 'start': 6607.165, 'duration': 12.664}, {'end': 6627.89, 'text': 'OK A very popular way to implement a priority queue is to use some kind of heap.', 'start': 6621.169, 'duration': 6.721}, {'end': 6638.478, 'text': 'This is because heaps are the data structure which give us the best possible time complexity for the operations we need to perform with a priority queue.', 'start': 6628.61, 'duration': 9.868}], 'summary': 'Heaps are the best for priority queue due to their time complexity.', 'duration': 31.313, 'max_score': 6607.165, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM6607165.jpg'}, {'end': 6708.985, 'src': 'embed', 'start': 6667.163, 'weight': 8, 'content': [{'end': 6668.264, 'text': 'So concerning heaps.', 'start': 6667.163, 'duration': 1.101}, {'end': 6677.942, 'text': 'There are many different types of heaps, including binary heaps, Fibonacci heaps, binomial heaps, pairing heaps, and so on and so on.', 'start': 6669.4, 'duration': 8.542}, {'end': 6681.343, 'text': "But for simplicity, we're just going to use the binary heap.", 'start': 6678.842, 'duration': 2.501}, {'end': 6690.305, 'text': 'A binary heap is a binary tree that supports the heap invariant.', 'start': 6685.704, 'duration': 4.601}, {'end': 6695.212, 'text': 'In a binary tree, every node has exactly two children.', 'start': 6691.468, 'duration': 3.744}, {'end': 6708.985, 'text': "So the following structure is a binary heap which satisfies the heap property that every parent's value is greater than or equal to that of the child that every node has exactly two children.", 'start': 6695.792, 'duration': 13.193}], 'summary': 'Binary heaps are a type of heap data structure that supports the heap invariant, with every node having exactly two children.', 'duration': 41.822, 'max_score': 6667.163, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM6667163.jpg'}, {'end': 6782.69, 'src': 'embed', 'start': 6758.252, 'weight': 5, 'content': [{'end': 6769.921, 'text': 'As you will see when we insert nodes we always insert them at the bottom row as far left to meet this complete binary tree property.', 'start': 6758.252, 'duration': 11.669}, {'end': 6779.087, 'text': 'Maintaining the complete binary tree property is very, very important because it gives us an insertion point,', 'start': 6770.761, 'duration': 8.326}, {'end': 6782.69, 'text': 'no matter what the heap looks like or what values are in it.', 'start': 6779.087, 'duration': 3.603}], 'summary': 'Maintaining complete binary tree property ensures insertion at the bottom left, providing a consistent insertion point.', 'duration': 24.438, 'max_score': 6758.252, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM6758252.jpg'}, {'end': 6932.835, 'src': 'embed', 'start': 6901.005, 'weight': 6, 'content': [{'end': 6911.031, 'text': 'And also another interesting property of storing a binary heap in an array is that you can easily access all the children and parent nodes.', 'start': 6901.005, 'duration': 10.026}, {'end': 6922.548, 'text': 'So suppose i is the index of a parent node, then the left child is going to be at index two times i plus one.', 'start': 6912.642, 'duration': 9.906}, {'end': 6928.632, 'text': 'And the right child of that node is going to be at two i plus two.', 'start': 6923.349, 'duration': 5.283}, {'end': 6932.835, 'text': "This is zero base, if it's one base, then you would just subtract one.", 'start': 6929.333, 'duration': 3.502}], 'summary': 'Storing a binary heap in an array allows easy access to parent and children nodes using specific index calculations.', 'duration': 31.83, 'max_score': 6901.005, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM6901005.jpg'}, {'end': 7013.389, 'src': 'embed', 'start': 6967.92, 'weight': 3, 'content': [{'end': 6972.785, 'text': 'So using this technique, we have all we need to manipulate the nodes in our array.', 'start': 6967.92, 'duration': 4.865}, {'end': 6981.773, 'text': "And the source code I will be presenting in part five for the series, we'll see that I use this representation for simplicity.", 'start': 6973.746, 'duration': 8.027}, {'end': 6990.551, 'text': 'Alright. so now we want to know How do I add nodes to a binary heap and maintain the heap invariant?', 'start': 6982.474, 'duration': 8.077}, {'end': 6998.077, 'text': "Because if we add nodes to our binary tree and we don't maintain the heap property, well, the binary heap is useless.", 'start': 6991.072, 'duration': 7.005}, {'end': 7000.359, 'text': "We'll do some examples.", 'start': 6999.278, 'duration': 1.081}, {'end': 7004.882, 'text': 'On the left, I have some instructions which tell us what values we need to insert into the heap.', 'start': 7000.559, 'duration': 4.323}, {'end': 7013.389, 'text': "The first value is a 1, which we can see, which should actually appear at the root, since we're dealing with a min heap.", 'start': 7006.423, 'duration': 6.966}], 'summary': 'Technique presented for manipulating nodes in array. exploring addition of nodes to binary heap while maintaining heap invariant.', 'duration': 45.469, 'max_score': 6967.92, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM6967920.jpg'}, {'end': 7532.126, 'src': 'embed', 'start': 7506.196, 'weight': 2, 'content': [{'end': 7513.781, 'text': "However, if you're as dissatisfied with this linear removal as I am, you'd figure out that there has to be a better way.", 'start': 7506.196, 'duration': 7.585}, {'end': 7523.482, 'text': "And indeed there is and I'm about to show you a hack to improve this complexity to be logarithmic in the general case.", 'start': 7515.217, 'duration': 8.265}, {'end': 7524.742, 'text': 'So stay tuned.', 'start': 7523.942, 'duration': 0.8}, {'end': 7532.126, 'text': "Okay, so now we're going to look at how to remove nodes from a heap with the improved time complexity.", 'start': 7524.762, 'duration': 7.364}], 'summary': 'Improve time complexity of node removal in heap to logarithmic', 'duration': 25.93, 'max_score': 7506.196, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM7506196.jpg'}, {'end': 7581.319, 'src': 'embed', 'start': 7557.596, 'weight': 1, 'content': [{'end': 7565.098, 'text': 'And instead of doing a linear scan to find out where the node we want to remove is, we just want to be able to do a lookup and figure that out.', 'start': 7557.596, 'duration': 7.502}, {'end': 7573.713, 'text': "The way we're going to do this is that every node is going to be mapped to the indexes found at.", 'start': 7566.428, 'duration': 7.285}, {'end': 7581.319, 'text': 'So when we want to remove a particular node, we just look up its index instead of doing a linear scan.', 'start': 7575.234, 'duration': 6.085}], 'summary': 'Improving node removal process by mapping nodes to indexes for quicker lookup.', 'duration': 23.723, 'max_score': 7557.596, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM7557596.jpg'}, {'end': 7647.989, 'src': 'embed', 'start': 7615.792, 'weight': 11, 'content': [{'end': 7626.896, 'text': 'And we can do this by maintaining a set or tree set of indices for which a particular node value or key, if you want, maps to.', 'start': 7615.792, 'duration': 11.104}, {'end': 7629.037, 'text': "Let's look at an example.", 'start': 7626.916, 'duration': 2.121}, {'end': 7633.398, 'text': 'So observe the blue heap.', 'start': 7629.057, 'duration': 4.341}, {'end': 7636.719, 'text': 'Remark that it has repeated values.', 'start': 7634.078, 'duration': 2.641}, {'end': 7647.989, 'text': 'Namely, we can see that the 2 is there 3 times, 7 is there twice, 11 and 13 once.', 'start': 7637.924, 'duration': 10.065}], 'summary': 'Maintain set of indices for node values; 2 repeated 3 times, 7 repeated twice, 11 and 13 once.', 'duration': 32.197, 'max_score': 7615.792, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM7615792.jpg'}], 'start': 6514.744, 'title': 'Binary heaps and operations', 'summary': 'Covers adding elements to a binary heap, binary heap properties, adding and removing nodes, and optimization techniques. it emphasizes the importance of lexicographic ordering, complete binary tree property, bubbling up and down operations, and hash table optimization for efficient node removal, improving time complexity to be logarithmic in the general case.', 'chapters': [{'end': 6665.362, 'start': 6514.744, 'title': 'Binary heap: adding elements', 'summary': 'Explains how to add elements to a binary heap, emphasizing the importance of lexicographic ordering and the role of heaps in implementing priority queues, with an example demonstrating the negation of lex to achieve max heap transformation.', 'duration': 150.618, 'highlights': ['Lexicographic comparator used to negate lex, turning min heap to max heap', 'Example demonstrating ordering using lexicographic comparator', 'Importance of heaps in implementing priority queues']}, {'end': 6966.459, 'start': 6667.163, 'title': 'Binary heaps and complete binary trees', 'summary': "Introduces binary heaps as a type of heap data structure, focusing on binary heaps due to their simplicity and array representation, emphasizing the complete binary tree property and the array-based representation's convenience and efficiency.", 'duration': 299.296, 'highlights': ['Binary heaps are introduced as a type of heap data structure, with a focus on binary heaps due to their simplicity and efficiency, using array representation.', 'The importance of the complete binary tree property is emphasized for insertion point determination and its significance in maintaining the structure of the binary heap.', 'The array-based representation of binary heaps is discussed, highlighting its convenience and efficiency, allowing easy access to parent and child nodes.']}, {'end': 7483.221, 'start': 6967.92, 'title': 'Binary heap: adding and removing nodes', 'summary': 'Discusses the process of adding and removing nodes in a binary heap, explaining the operation of bubbling up and bubbling down to maintain the heap invariant, and provides examples of adding and removing nodes while satisfying the heap property.', 'duration': 515.301, 'highlights': ['The chapter explains the process of adding nodes to a binary heap, including the operation of bubbling up to maintain the heap invariant and provides examples of adding nodes to satisfy the heap property.', 'It details the procedure of removing nodes from a binary heap, emphasizing the operation of bubbling down to maintain the heap invariant and provides examples of removing nodes while satisfying the heap property.', 'The chapter provides examples of adding and removing nodes in a binary heap, illustrating the process of maintaining the heap invariant while satisfying the heap property.']}, {'end': 7979.464, 'start': 7484.782, 'title': 'Heap node removal optimization', 'summary': 'Discusses the optimization of node removal from a heap, introducing a hash table to map node values to multiple positions and using the table to efficiently locate and remove nodes, ultimately improving the time complexity to be logarithmic in the general case.', 'duration': 494.682, 'highlights': ['The optimization of node removal from a heap involves using a hash table to map node values to multiple positions, enabling efficient lookup and removal of nodes.', 'The improvement in time complexity is achieved by leveraging the hash table to locate and remove nodes, ultimately reducing the complexity to be logarithmic in the general case.', 'The process involves maintaining a set or tree set of indices for which a particular node value or key maps to, addressing the challenge of multiple nodes with the same value in the heap.']}], 'duration': 1464.72, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM6514744.jpg', 'highlights': ['Lexicographic comparator used to negate lex, turning min heap to max heap', 'The optimization of node removal from a heap involves using a hash table to map node values to multiple positions, enabling efficient lookup and removal of nodes', 'The improvement in time complexity is achieved by leveraging the hash table to locate and remove nodes, ultimately reducing the complexity to be logarithmic in the general case', 'The chapter explains the process of adding nodes to a binary heap, including the operation of bubbling up to maintain the heap invariant and provides examples of adding nodes to satisfy the heap property', 'The chapter provides examples of adding and removing nodes in a binary heap, illustrating the process of maintaining the heap invariant while satisfying the heap property', 'The importance of the complete binary tree property is emphasized for insertion point determination and its significance in maintaining the structure of the binary heap', 'The array-based representation of binary heaps is discussed, highlighting its convenience and efficiency, allowing easy access to parent and child nodes', 'The chapter details the procedure of removing nodes from a binary heap, emphasizing the operation of bubbling down to maintain the heap invariant and provides examples of removing nodes while satisfying the heap property', 'Binary heaps are introduced as a type of heap data structure, with a focus on binary heaps due to their simplicity and efficiency, using array representation', 'Example demonstrating ordering using lexicographic comparator', 'Importance of heaps in implementing priority queues', 'The process involves maintaining a set or tree set of indices for which a particular node value or key maps to, addressing the challenge of multiple nodes with the same value in the heap']}, {'end': 8821.656, 'segs': [{'end': 8098.554, 'src': 'embed', 'start': 8062.903, 'weight': 0, 'content': [{'end': 8069.245, 'text': "And we're going to be maintaining it as a dynamic list of elements using Java's list.", 'start': 8062.903, 'duration': 6.342}, {'end': 8077.828, 'text': "Next, for our log of n removals, I'm also going to keep track of this map.", 'start': 8072.166, 'duration': 5.662}, {'end': 8083.25, 'text': "And it's going to map an element to a tree set of integers.", 'start': 8078.608, 'duration': 4.642}, {'end': 8089.872, 'text': 'So these are going to be all the positions inside our heap, which we can find this element t.', 'start': 8083.45, 'duration': 6.422}, {'end': 8098.554, 'text': "Alright, next I've got a few different constructors for our priority queue.", 'start': 8092.99, 'duration': 5.564}], 'summary': "Using java's list to maintain a dynamic list of elements, tracking removals with a map and tree set, and implementing multiple constructors for the priority queue.", 'duration': 35.651, 'max_score': 8062.903, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM8062903.jpg'}, {'end': 8157.317, 'src': 'embed', 'start': 8125.616, 'weight': 1, 'content': [{'end': 8133.301, 'text': 'But also even better is if you know all the elements that are going to be inside your heap.', 'start': 8125.616, 'duration': 7.685}, {'end': 8143.468, 'text': "you can actually construct the priority queue in linear time using an operation called heapify, which I didn't talk about in the slides.", 'start': 8133.301, 'duration': 10.167}, {'end': 8148.151, 'text': 'But it can be very, very useful.', 'start': 8144.168, 'duration': 3.983}, {'end': 8152.736, 'text': 'So this just has all the usual setup stuff.', 'start': 8149.255, 'duration': 3.481}, {'end': 8157.317, 'text': "Here I'm adding all the elements to the map, but also to the heap.", 'start': 8153.976, 'duration': 3.341}], 'summary': 'Construct priority queue in linear time using heapify for better efficiency.', 'duration': 31.701, 'max_score': 8125.616, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM8125616.jpg'}, {'end': 8406.12, 'src': 'embed', 'start': 8373.259, 'weight': 3, 'content': [{'end': 8380.304, 'text': 'So what we do is first we check if our heap size is less than capacity.', 'start': 8373.259, 'duration': 7.045}, {'end': 8385.207, 'text': 'Otherwise, we have to expand our capacity of the heap.', 'start': 8381.103, 'duration': 4.104}, {'end': 8392.89, 'text': 'Next we make sure we add it to the map so we can keep track of it and then we swim it up.', 'start': 8386.966, 'duration': 5.924}, {'end': 8401.156, 'text': 'Remember that we have to swim a node up because we add it to the very end of our list,', 'start': 8394.191, 'duration': 6.965}, {'end': 8406.12, 'text': 'and so we have to adjust where it goes inside our heap by swimming upwards.', 'start': 8401.156, 'duration': 4.964}], 'summary': 'Check heap size, expand capacity, add to map, swim up.', 'duration': 32.861, 'max_score': 8373.259, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM8373259.jpg'}, {'end': 8821.656, 'src': 'embed', 'start': 8788.284, 'weight': 2, 'content': [{'end': 8795.828, 'text': "And it's going to recursively go down the tree and check, are we maintaining the heap invariant property, which we need.", 'start': 8788.284, 'duration': 7.544}, {'end': 8801.292, 'text': 'So our basis is going to be that k is outside the heap size.', 'start': 8797.709, 'duration': 3.583}, {'end': 8805.034, 'text': "And if so, we're just going to return true.", 'start': 8803.373, 'duration': 1.661}, {'end': 8808.556, 'text': 'Otherwise, get our children left and right.', 'start': 8806.274, 'duration': 2.282}, {'end': 8818.294, 'text': "And now we're going to make sure that k is less than both our children.", 'start': 8809.469, 'duration': 8.825}, {'end': 8821.656, 'text': "And if that's not the case, return false.", 'start': 8818.794, 'duration': 2.862}], 'summary': 'Recursively check heap invariant, k outside heap, then compare with children.', 'duration': 33.372, 'max_score': 8788.284, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM8788284.jpg'}], 'start': 7980.296, 'title': 'Priority queue source code', 'summary': 'Presents an overview of the priority queue source code, including types of elements, constructors, heapify operation, and methods like add and remove, highlighting the importance of using heapify for linear time complexity.', 'chapters': [{'end': 8821.656, 'start': 7980.296, 'title': 'Priority queue source code overview', 'summary': 'Presents an overview of the priority queue source code, discussing the types of elements allowed, instance variables, constructors, heapify operation, methods like add, remove, and integrity checking, emphasizing the importance of using heapify for linear time complexity.', 'duration': 841.36, 'highlights': ['The Priority Queue source code allows comparable elements and includes instance variables for heap size, heap capacity, and a map for log of n removals.', 'The chapter emphasizes the efficiency of the heapify operation, enabling linear time construction of the priority queue using an operation called heapify.', 'The add method checks the heap size to ensure capacity and then adds the element to the map before swimming it up, while the removeAt method swaps the index to be removed with the last element and adjusts the position through sinking or swimming.', 'The chapter discusses the significance of maintaining the heap invariant property for integrity check, ensuring that the heap maintains the required property throughout the operations.']}], 'duration': 841.36, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM7980296.jpg', 'highlights': ['The Priority Queue source code allows comparable elements and includes instance variables for heap size, heap capacity, and a map for log of n removals.', 'The chapter emphasizes the efficiency of the heapify operation, enabling linear time construction of the priority queue using an operation called heapify.', 'The chapter discusses the significance of maintaining the heap invariant property for integrity check, ensuring that the heap maintains the required property throughout the operations.', 'The add method checks the heap size to ensure capacity and then adds the element to the map before swimming it up, while the removeAt method swaps the index to be removed with the last element and adjusts the position through sinking or swimming.']}, {'end': 11006.068, 'segs': [{'end': 8966.78, 'src': 'embed', 'start': 8912.491, 'weight': 3, 'content': [{'end': 8914.873, 'text': 'This is my favorite data structure.', 'start': 8912.491, 'duration': 2.382}, {'end': 8917.174, 'text': "So let's get started.", 'start': 8915.553, 'duration': 1.621}, {'end': 8921.597, 'text': "So an outline of things we'll be covering about the union find.", 'start': 8918.635, 'duration': 2.962}, {'end': 8930.142, 'text': "First, I'll be going over a motivating example, magnets, just to illustrate how useful the union find can be.", 'start': 8922.117, 'duration': 8.025}, {'end': 8935.486, 'text': "Then we'll go over a classic example of an algorithm which uses the union find.", 'start': 8930.703, 'duration': 4.783}, {'end': 8942.637, 'text': "specifically Kruskal's minimum spanning tree algorithm, which is very elegant,", 'start': 8936.033, 'duration': 6.604}, {'end': 8948.041, 'text': "and you'll see why it needs the union find to get the complexity it has.", 'start': 8942.637, 'duration': 5.404}, {'end': 8957.087, 'text': "Then we're going to go into some detail concerning the find and the union operations, the two core operations the union find uses.", 'start': 8949.382, 'duration': 7.705}, {'end': 8966.78, 'text': "And finally, we'll have a look at path compression, what gives us the really nice amortized constant time the union find provides.", 'start': 8957.711, 'duration': 9.069}], 'summary': 'Introduction to union find data structure, using examples and operations, for efficient algorithms.', 'duration': 54.289, 'max_score': 8912.491, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM8912491.jpg'}, {'end': 9171.879, 'src': 'embed', 'start': 9144.461, 'weight': 0, 'content': [{'end': 9156.747, 'text': "Well Well, we see the union find again in Cussell's minimum spanning tree algorithm in another problem called grid percolation,", 'start': 9144.461, 'duration': 12.286}, {'end': 9166.054, 'text': "where there's a bunch of dots on a grid and then we're trying to see if there's a path from the bottom of the grid to the top of the grid or vice versa.", 'start': 9156.747, 'duration': 9.307}, {'end': 9171.879, 'text': 'Then the union find lets us do that efficiently by merging together paths.', 'start': 9166.415, 'duration': 5.464}], 'summary': 'Union find used in grid percolation for efficient path merging.', 'duration': 27.418, 'max_score': 9144.461, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM9144461.jpg'}, {'end': 9224.475, 'src': 'embed', 'start': 9198.257, 'weight': 1, 'content': [{'end': 9203.861, 'text': "So its construction is linear time, which isn't actually bad at all.", 'start': 9198.257, 'duration': 5.604}, {'end': 9214.43, 'text': "Then the union find, get component, and check if connected operations all happened in what's called amortized constant time.", 'start': 9204.462, 'duration': 9.968}, {'end': 9219.814, 'text': 'So almost constant time, although not quite constant time.', 'start': 9214.93, 'duration': 4.884}, {'end': 9224.475, 'text': 'And finally, count components.', 'start': 9221.613, 'duration': 2.862}], 'summary': 'Construction is linear time; operations happen in amortized constant time.', 'duration': 26.218, 'max_score': 9198.257, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM9198257.jpg'}, {'end': 9584.479, 'src': 'embed', 'start': 9554.767, 'weight': 2, 'content': [{'end': 9557.309, 'text': 'So merge the two groups into one larger group.', 'start': 9554.767, 'duration': 2.542}, {'end': 9563.653, 'text': "So we have found the minimum spanning tree using Kruskal's minimum spanning tree algorithm.", 'start': 9557.649, 'duration': 6.004}, {'end': 9570.058, 'text': 'Pretty neat, right? So the underlying data structure which allows us to do this is the union find.', 'start': 9564.234, 'duration': 5.824}, {'end': 9581.152, 'text': "It allows us to merge groups of colors together efficiently, but also to find out which groups nodes belong to so that we don't create a cycle.", 'start': 9570.936, 'duration': 10.216}, {'end': 9584.479, 'text': "So that's Kruskal's algorithm.", 'start': 9582.219, 'duration': 2.26}], 'summary': "Using kruskal's algorithm, we merged two groups into one larger group efficiently.", 'duration': 29.712, 'max_score': 9554.767, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM9554767.jpg'}], 'start': 8823.057, 'title': "Union find data structure and kruskal's algorithm", 'summary': "Explains the union find data structure and its operations, including its application in kruskal's minimum spanning tree algorithm. it also discusses the implementation of the union find data structure, merging components, complexity, and the efficiency achieved through path compression, with practical examples and source code link.", 'chapters': [{'end': 9553.626, 'start': 8823.057, 'title': 'Union find data structure', 'summary': "Explains the union find data structure, emphasizing its primary operations, motivating example with magnets, and its applications in algorithms like kruskal's minimum spanning tree. it also highlights the efficiency and complexity of the union find data structure.", 'duration': 730.569, 'highlights': ['The union find data structure tracks elements split into disjoint sets and has two primary operations: find and union, which efficiently merge and find groups of elements.', 'The motivating example illustrates the use of union find with magnets, where the data structure efficiently unifies magnets into groups based on their attraction, demonstrating the practical application of the union find.', "The union find is used in algorithms like Kruskal's minimum spanning tree, grid percolation, network connectivity, and other advanced examples, showcasing its wide applicability.", 'The complexity of the union find data structure is excellent with linear construction time and amortized constant time for operations like get component, check if connected, and count components, which is very efficient.', "Kruskal's minimum spanning tree algorithm utilizes the union find to efficiently unify vertices into groups and select edges with minimal cost, demonstrating its practical application and significance in algorithms."]}, {'end': 9860.306, 'start': 9554.767, 'title': "Kruskal's algorithm and union find", 'summary': "Discusses kruskal's minimum spanning tree algorithm and the implementation of the union find data structure, with a focus on creating an efficient array-based implementation for grouping and merging elements.", 'duration': 305.539, 'highlights': ["The chapter explains the application of Kruskal's minimum spanning tree algorithm to merge groups efficiently using the union find data structure.", 'It highlights the creation of a bijection mapping between objects and integers for efficient storage and retrieval in the array-based union find implementation.', 'The chapter delves into the process of unifying groups by updating the array to map parent nodes, demonstrating the internal workings of the union find operations.']}, {'end': 10146.528, 'start': 9860.306, 'title': 'Union find algorithm', 'summary': 'Demonstrates the process of merging components using the union find algorithm, illustrating the steps to find the root node of a component, merge smaller components into larger ones, and determine which component an element belongs to. notably, it highlights the example where the orange component has four elements, while the green component has three, resulting in the merge of the green component into the orange component.', 'duration': 286.222, 'highlights': ['The example showcases the merge of the green component into the orange component, as the orange component has four elements, while the green component has three, resulting in J pointing to C. (4 elements in orange component, 3 elements in green component)', 'The process involves finding the root nodes of each component and then merging them if they are different, with one root node becoming the parent of the other root node. (Merging process)', 'The demonstration emphasizes that to find which component an element maps to, the root of that component is found by following all the parent nodes until reaching a self-loop or a node whose parent is itself. (Method to determine component belonging)']}, {'end': 10571.141, 'start': 10148.529, 'title': 'Union find complexity and path compression', 'summary': 'Discusses the complexity of the union find data structure, highlighting the importance of path compression in achieving amortized constant time and efficiency, with examples demonstrating the impact of path compression on the structure and traversal of components.', 'duration': 422.612, 'highlights': ['Path compression in union find allows for amortized constant time lookup and efficient traversal by compressing the path to the root node, leading to improved efficiency and reduced traversal time.', 'The number of components in union find is equal to the number of remaining root nodes, with the number of root nodes consistently decreasing as components are unified, leading to a reduced number of root nodes.', 'Without path compression, determining whether two elements belong to the same group may take multiple hops, demonstrating the inefficiency of union find without path compression.']}, {'end': 11006.068, 'start': 10571.141, 'title': 'Union find: path compression', 'summary': 'Introduces the concept of union find with path compression, explaining its efficiency and implementation in detail, while also providing a link to the source code. it discusses the instance variables, methods like find, size, and unify, and their practical applications, emphasizing the efficiency achieved through path compression and its impact on the number of components and time complexity.', 'duration': 434.927, 'highlights': ['Union Find with path compression is efficient due to path compression, resulting in constant time complexity for most operations.', "The class 'union find' has instance variables like size, id, and number of components, facilitating practical storage and access of tree-like structures.", "The method 'find' efficiently determines the component to which a node belongs and performs path compression along the way, contributing to the amortized time complexity.", "The 'unify' method merges two components by finding their root nodes and appropriately adjusting the number of components, ensuring efficient grouping and reducing the total number of components by one."]}], 'duration': 2183.011, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM8823057.jpg', 'highlights': ["The union find data structure is used in algorithms like Kruskal's minimum spanning tree, grid percolation, and network connectivity, showcasing its wide applicability.", 'The complexity of the union find data structure is excellent with linear construction time and amortized constant time for operations like get component, check if connected, and count components, which is very efficient.', "Kruskal's minimum spanning tree algorithm utilizes the union find to efficiently unify vertices into groups and select edges with minimal cost, demonstrating its practical application and significance in algorithms.", 'Path compression in union find allows for amortized constant time lookup and efficient traversal by compressing the path to the root node, leading to improved efficiency and reduced traversal time.', 'The motivating example illustrates the use of union find with magnets, where the data structure efficiently unifies magnets into groups based on their attraction, demonstrating the practical application of the union find.']}, {'end': 12044.832, 'segs': [{'end': 11087.583, 'src': 'embed', 'start': 11061.588, 'weight': 3, 'content': [{'end': 11069.351, 'text': "So today's tutorial is going to focus on binary trees and binary search trees, where they're used, and what they are.", 'start': 11061.588, 'duration': 7.763}, {'end': 11075.132, 'text': "And in later tutorials we're going to cover how to insert nodes into binary search trees,", 'start': 11070.768, 'duration': 4.364}, {'end': 11087.583, 'text': 'remove nodes and also do some of the more popular tree traversals which can apply to other general trees also, not just binary trees.', 'start': 11075.132, 'duration': 12.451}], 'summary': 'Tutorial on binary trees and binary search trees, covering insertion, removal, and tree traversals.', 'duration': 25.995, 'max_score': 11061.588, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM11061588.jpg'}, {'end': 11313.601, 'src': 'embed', 'start': 11289.355, 'weight': 4, 'content': [{'end': 11295.957, 'text': 'So just as an example, if we pick the node zero, it has two children, three and two, and a parent, four.', 'start': 11289.355, 'duration': 6.602}, {'end': 11300.098, 'text': 'We also have the concept of something called a leaf node.', 'start': 11297.297, 'duration': 2.801}, {'end': 11305.359, 'text': 'This is a node which has no children, and these have been highlighted in orange.', 'start': 11300.598, 'duration': 4.761}, {'end': 11308.4, 'text': "So they're just at the very bottom of your tree.", 'start': 11305.899, 'duration': 2.501}, {'end': 11309.36, 'text': 'Think of it that way.', 'start': 11308.64, 'duration': 0.72}, {'end': 11313.601, 'text': "And there's also another term, which is subtree.", 'start': 11310.1, 'duration': 3.501}], 'summary': "Tree nodes can have children and parents, with leaf nodes having no children, and there's also a concept of a subtree.", 'duration': 24.246, 'max_score': 11289.355, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM11289355.jpg'}, {'end': 11372.362, 'src': 'embed', 'start': 11344.901, 'weight': 2, 'content': [{'end': 11350.287, 'text': "then we pick another subtree and look what's inside of it, and then we get a another tree.", 'start': 11344.901, 'duration': 5.386}, {'end': 11352.489, 'text': "And eventually we're going to hit the bottom.", 'start': 11350.908, 'duration': 1.581}, {'end': 11360.054, 'text': 'So now we can pose the question, what is a binary tree? And this is simple.', 'start': 11353.65, 'duration': 6.404}, {'end': 11364.497, 'text': 'This is a tree in which every node has at most two children.', 'start': 11360.434, 'duration': 4.063}, {'end': 11372.362, 'text': 'So both those trees below are binary trees, because they have at most two children.', 'start': 11365.677, 'duration': 6.685}], 'summary': 'A binary tree has at most two children per node.', 'duration': 27.461, 'max_score': 11344.901, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM11344901.jpg'}, {'end': 11630.857, 'src': 'embed', 'start': 11605.571, 'weight': 0, 'content': [{'end': 11612.735, 'text': "It doesn't look like a tree, but it satisfies our definitions of a tree and a binary search tree.", 'start': 11605.571, 'duration': 7.164}, {'end': 11616.563, 'text': "Okay, so we've been talking about binary trees, binary search trees.", 'start': 11613.376, 'duration': 3.187}, {'end': 11618.046, 'text': 'Where are they used??', 'start': 11617.165, 'duration': 0.881}, {'end': 11618.888, 'text': 'Why are they useful?', 'start': 11618.187, 'duration': 0.701}, {'end': 11630.857, 'text': 'So, in particular, binary search trees are used in many implementations of abstract data types, for sets and maps and so on.', 'start': 11620.31, 'duration': 10.547}], 'summary': 'Binary search trees are used in many implementations of abstract data types, such as sets and maps.', 'duration': 25.286, 'max_score': 11605.571, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM11605571.jpg'}, {'end': 11708.699, 'src': 'embed', 'start': 11683.513, 'weight': 1, 'content': [{'end': 11689.578, 'text': "So now let's look at the complexity of these binary search trees, because they looked very interesting and also very useful.", 'start': 11683.513, 'duration': 6.065}, {'end': 11691.119, 'text': 'And indeed they are.', 'start': 11690.298, 'duration': 0.821}, {'end': 11701.287, 'text': "So in the average case, when you're just given some random data, the time complexity is going to be logarithmic.", 'start': 11692.26, 'duration': 9.027}, {'end': 11703.557, 'text': 'which is really good.', 'start': 11702.216, 'duration': 1.341}, {'end': 11708.699, 'text': "So if you're inserting nodes, deleting nodes, removing nodes, searching for value in a tree,", 'start': 11704.017, 'duration': 4.682}], 'summary': 'Binary search trees have logarithmic time complexity, making them efficient for operations.', 'duration': 25.186, 'max_score': 11683.513, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM11683513.jpg'}], 'start': 11006.068, 'title': 'Binary trees and search trees', 'summary': 'Discusses binary trees and search trees, including their concepts, properties, time complexity, and trade-offs. it emphasizes the importance of understanding these data structures and their applications in programming.', 'chapters': [{'end': 11288.307, 'start': 11006.068, 'title': 'Binary trees and search trees', 'summary': 'Discusses the concepts of binary trees, binary search trees, and the properties of trees, emphasizing the importance of understanding these data structures and their applications in programming.', 'duration': 282.239, 'highlights': ['A tree is an undirected graph with multiple definitions, such as being connected, acyclic, and having n nodes with n-1 edges.', 'The chapter explains the concept of a rooted tree, child and parent nodes, and the absence of a parent for the root node.', 'The tutorial provides a foundation for understanding binary trees and binary search trees, highlighting their significance in programming.']}, {'end': 11682.032, 'start': 11289.355, 'title': 'Binary trees and search trees', 'summary': 'Explains the concept of binary trees and search trees, including the definition, characteristics, and applications of binary search trees with examples and use cases.', 'duration': 392.677, 'highlights': ['Binary search trees are used in many implementations of abstract data types, for sets and maps and also to implement balanced binary search trees.', 'Binary trees are used in binary heaps and syntax trees, for parsing and evaluating expressions in compilers and calculators.', 'A binary tree is a tree in which every node has at most two children, and a binary search tree satisfies the binary search tree invariant.']}, {'end': 12044.832, 'start': 11683.513, 'title': 'Binary search tree complexity', 'summary': 'Discusses the time complexity of binary search trees, noting that in the average case, the time complexity is logarithmic, making it efficient for inserting, deleting, and searching for values, but in the worst case, the behavior could degrade to linear time, highlighting the trade-offs of using pure binary search trees.', 'duration': 361.319, 'highlights': ['In the average case, the time complexity for inserting, deleting, and searching for values in a binary search tree is logarithmic, making it efficient.', 'However, in the worst case, if the binary search tree degenerates to a line, the time complexity can become linear, indicating a less efficient behavior.', 'The process of inserting elements into a binary search tree involves ensuring comparability of elements and encountering four cases based on the comparison of values.']}], 'duration': 1038.764, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM11006068.jpg', 'highlights': ['Binary search trees are used in many implementations of abstract data types, for sets and maps and also to implement balanced binary search trees.', 'In the average case, the time complexity for inserting, deleting, and searching for values in a binary search tree is logarithmic, making it efficient.', 'A binary tree is a tree in which every node has at most two children, and a binary search tree satisfies the binary search tree invariant.', 'The tutorial provides a foundation for understanding binary trees and binary search trees, highlighting their significance in programming.', 'The chapter explains the concept of a rooted tree, child and parent nodes, and the absence of a parent for the root node.']}, {'end': 14317.592, 'segs': [{'end': 12122.203, 'src': 'embed', 'start': 12069.114, 'weight': 0, 'content': [{'end': 12071.457, 'text': 'which balance themselves as you insert nodes.', 'start': 12069.114, 'duration': 2.343}, {'end': 12075.101, 'text': "We'll be getting to that later, but that's it for insertion.", 'start': 12072.017, 'duration': 3.084}, {'end': 12076.602, 'text': "It's really simple.", 'start': 12075.701, 'duration': 0.901}, {'end': 12078.785, 'text': "Don't overcomplicate it.", 'start': 12077.704, 'duration': 1.081}, {'end': 12088.699, 'text': 'Alright, now that we know how to insert elements into a binary search tree, we might also want to remove elements from a binary search tree.', 'start': 12080.615, 'duration': 8.084}, {'end': 12094.262, 'text': "And this is slightly more complicated, but I'm going to make it very simple for you guys.", 'start': 12089.339, 'duration': 4.923}, {'end': 12101.205, 'text': "So when we're moving elements from a binary search tree, you can think of it as a two step process.", 'start': 12096.363, 'duration': 4.842}, {'end': 12108.577, 'text': 'First, we have to find the element we wish to remove within the binary search tree, if it exists at all.', 'start': 12102.495, 'duration': 6.082}, {'end': 12118.521, 'text': "And in the second stage we want to replace the node we're removing with its successor, if one exists,", 'start': 12109.378, 'duration': 9.143}, {'end': 12122.203, 'text': 'in order to maintain the binary search tree invariant.', 'start': 12118.521, 'duration': 3.682}], 'summary': 'Insertion and removal in binary search tree explained simply.', 'duration': 53.089, 'max_score': 12069.114, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM12069114.jpg'}, {'end': 13298.314, 'src': 'embed', 'start': 13265.466, 'weight': 4, 'content': [{'end': 13268.587, 'text': 'It prints the values in increasing order, which is really neat.', 'start': 13265.466, 'duration': 3.121}, {'end': 13272.649, 'text': "That's quite a nice property of the in-order traversal.", 'start': 13268.667, 'duration': 3.982}, {'end': 13276.471, 'text': "Now let's look at the post-order traversal.", 'start': 13274.29, 'duration': 2.181}, {'end': 13283.874, 'text': 'And the post-order traversal says, OK, traverse the left subtree, then traverse the right subtree.', 'start': 13277.251, 'duration': 6.623}, {'end': 13289.297, 'text': "And after you're done doing both of those, only then print the value of the node.", 'start': 13283.894, 'duration': 5.403}, {'end': 13298.314, 'text': "So this means, if you look at our tree right now, the last value we're going to print should be 11,", 'start': 13290.529, 'duration': 7.785}], 'summary': 'Explanation of post-order traversal: traverse left subtree, then right subtree, then print node value.', 'duration': 32.848, 'max_score': 13265.466, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM13265466.jpg'}, {'end': 13757.128, 'src': 'embed', 'start': 13729.062, 'weight': 3, 'content': [{'end': 13737.365, 'text': 'This insertion method will return true if we successfully insert a new element into the binary search tree,', 'start': 13729.062, 'duration': 8.303}, {'end': 13741.706, 'text': "and it will return false if there's already something inside the binary search tree.", 'start': 13737.365, 'duration': 4.341}, {'end': 13746.488, 'text': 'So elements have to be unique inside this binary search tree.', 'start': 13741.746, 'duration': 4.742}, {'end': 13757.128, 'text': "OK, so supposing this branch doesn't get executed, meaning the element does not already exist in the tree, then we're looking at this branch.", 'start': 13747.849, 'duration': 9.279}], 'summary': 'Binary search tree insertion returns true for success, false for existing element, and requires unique elements.', 'duration': 28.066, 'max_score': 13729.062, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM13729062.jpg'}], 'start': 12044.852, 'title': 'Binary search tree operations and tree traversals', 'summary': 'Covers the process of inserting and removing elements in a binary search tree, emphasizing the importance of balance and demonstrates various tree traversals - pre, in, post, and level order - with a detailed explanation of their working and characteristics.', 'chapters': [{'end': 12270.996, 'start': 12044.852, 'title': 'Binary search tree operations', 'summary': 'Explains the process of inserting and removing elements in a binary search tree, emphasizing the importance of maintaining balance and the two-step process of finding and replacing elements, illustrated with examples and animation.', 'duration': 226.144, 'highlights': ['The process of inserting and removing elements in a binary search tree is explained, highlighting the importance of maintaining balance and the two-step process of finding and replacing elements, with examples and animation.', 'The chapter introduces the concept of balanced binary search trees or self-balancing trees, which aim to optimize operations by balancing themselves as nodes are inserted, thus avoiding linear time complexities.', 'The two-step process of removing elements from a binary search tree is outlined, emphasizing the need to find the element to be removed and then replace it with its successor to maintain the binary search tree invariant, ensuring the left subtree has smaller elements and the right subtree has larger elements than the current node.', 'The find phase in searching for an element within the binary search tree is described, presenting the four possible outcomes when searching for a value and explaining the role of the comparator function in determining the subtree to traverse.']}, {'end': 12566.987, 'start': 12271.016, 'title': 'Binary search tree removal', 'summary': 'Discusses the process of removing nodes from a binary search tree, including identifying cases and successors, such as leaf nodes, nodes with only one subtree, and nodes with both left and right subtrees.', 'duration': 295.971, 'highlights': ['The process of removing nodes from a binary search tree involves identifying cases such as leaf nodes, nodes with only one subtree, and nodes with both left and right subtrees, and determining successors for each case.', 'If a node to be removed is a leaf node, it can be removed without any side effects, simplifying the removal process.', 'In the case of a node with only one subtree, the successor of the node is the root node of the left or right subtree, depending on the specific case.', 'When removing a node with both a left and right subtree, the successor can be either the largest value in the left subtree or the smallest value in the right subtree, satisfying the binary search tree invariant.']}, {'end': 12885.936, 'start': 12567.467, 'title': 'Binary search tree removal', 'summary': 'Explains the process of removing nodes from a binary search tree, including finding successors in left and right subtrees, replacing values, and rebalancing the tree, with detailed examples and cases of removal.', 'duration': 318.469, 'highlights': ['The process of removing nodes from a binary search tree involves finding successors in left and right subtrees, replacing values, and rebalancing the tree, with detailed examples and cases of removal.', 'In the process of removing a node from a binary search tree, if the node has both a left and right subtree, the successor can be chosen from either subtree.', 'When removing a node with both left and right subtrees, the smallest value in the right subtree becomes the successor, and its value is copied into the node to be removed, followed by removing the successor.']}, {'end': 13461.046, 'start': 12887.378, 'title': 'Tree traversals: pre, in, post, level order', 'summary': 'Covers tree traversals including pre-order, in-order, post-order, and level order. it explains the working of each traversal, highlighting the specific order of printing and recursion, and demonstrates the unique characteristics of each traversal method, culminating in a focus on level order traversal using breadth-first search.', 'duration': 573.668, 'highlights': ['Level order traversal explained using breadth-first search', 'Pre-order traversal details and demonstration', 'In-order traversal and its unique property of printing values in increasing order', 'Post-order traversal and its specific order of printing values']}, {'end': 14317.592, 'start': 13461.326, 'title': 'Binary search tree source code in java', 'summary': 'Explains the iterative level order traversal of a binary search tree using a queue and provides a detailed walkthrough of the source code for a binary search tree in java, covering its insertion, removal, contains, height calculation, and iterative tree traversals.', 'duration': 856.266, 'highlights': ['The chapter explains the iterative level order traversal of a binary search tree using a queue', 'Detailed walkthrough of the source code for a binary search tree in Java', 'The insertion method returns true if a new element is successfully inserted into the binary search tree']}], 'duration': 2272.74, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM12044852.jpg', 'highlights': ['The chapter introduces the concept of balanced binary search trees or self-balancing trees, optimizing operations by balancing themselves as nodes are inserted, avoiding linear time complexities.', 'The process of inserting and removing elements in a binary search tree is explained, emphasizing the importance of maintaining balance and the two-step process of finding and replacing elements.', 'The process of removing nodes from a binary search tree involves finding successors in left and right subtrees, replacing values, and rebalancing the tree, with detailed examples and cases of removal.', 'The insertion method returns true if a new element is successfully inserted into the binary search tree.', 'In-order traversal and its unique property of printing values in increasing order.']}, {'end': 16099.732, 'segs': [{'end': 14469.081, 'src': 'embed', 'start': 14439.07, 'weight': 0, 'content': [{'end': 14450.372, 'text': 'So the hash table is a data structure that lets us construct a mapping from some keys to some values via a technique called hashing,', 'start': 14439.07, 'duration': 11.302}, {'end': 14451.552, 'text': "which we'll talk about shortly.", 'start': 14450.372, 'duration': 1.18}, {'end': 14461.777, 'text': "So the key could be any value, as long as it's unique, which maps to a value.", 'start': 14452.731, 'duration': 9.046}, {'end': 14469.081, 'text': "So for instance, keys could be names, which are people names, and the value could be someone's favorite color.", 'start': 14462.477, 'duration': 6.604}], 'summary': 'Hash table maps unique keys to values using hashing technique.', 'duration': 30.011, 'max_score': 14439.07, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM14439070.jpg'}, {'end': 14837.833, 'src': 'embed', 'start': 14805.834, 'weight': 4, 'content': [{'end': 14812.42, 'text': 'But if the hash functions are not equal, then x and y are certainly not equal.', 'start': 14805.834, 'duration': 6.586}, {'end': 14815.122, 'text': "Here's a good question.", 'start': 14813.701, 'duration': 1.421}, {'end': 14818.946, 'text': 'How can we use this to our advantage to speed up object comparisons?', 'start': 14815.202, 'duration': 3.744}, {'end': 14829.071, 'text': "The answer is that instead of comparing x and y directly, if we've already computed their hash values,", 'start': 14820.589, 'duration': 8.482}, {'end': 14837.833, 'text': "then first let's compare the hash values of x and y instead of comparing x and y explicitly.", 'start': 14829.071, 'duration': 8.762}], 'summary': 'Using hash values can speed up object comparisons.', 'duration': 31.999, 'max_score': 14805.834, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM14805834.jpg'}, {'end': 15354.9, 'src': 'embed', 'start': 15323.089, 'weight': 1, 'content': [{'end': 15327.615, 'text': 'There are many, but the two most popular ones are separate chaining and open addressing.', 'start': 15323.089, 'duration': 4.526}, {'end': 15337.087, 'text': 'The idea behind separate chaining is that we deal with hash collisions by maintaining a data structure, usually a linked list,', 'start': 15328.095, 'duration': 8.992}, {'end': 15341.953, 'text': 'to hold all the different key-value pairs which hash to some particular value.', 'start': 15337.087, 'duration': 4.866}, {'end': 15345.078, 'text': 'Open addressing is slightly different.', 'start': 15343.177, 'duration': 1.901}, {'end': 15354.9, 'text': 'It deals with hash collisions by probing and finding another place within the hash table offset from the place where we originally hashed to.', 'start': 15345.778, 'duration': 9.122}], 'summary': 'Two popular collision resolution methods: separate chaining and open addressing.', 'duration': 31.811, 'max_score': 15323.089, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM15323089.jpg'}, {'end': 15405.171, 'src': 'embed', 'start': 15370.794, 'weight': 2, 'content': [{'end': 15375.097, 'text': 'So on average, we can achieve constant time for insertion, removal, and search.', 'start': 15370.794, 'duration': 4.303}, {'end': 15384.383, 'text': "But if you have a terrible hash function that's not uniform, then you can get linear time, which is really, really bad.", 'start': 15375.697, 'duration': 8.686}, {'end': 15393.329, 'text': "OK, let's talk about something super, super cool, and that is hash tables and separate chaining.", 'start': 15385.744, 'duration': 7.585}, {'end': 15395.771, 'text': "All right, let's dive right in.", 'start': 15393.349, 'duration': 2.422}, {'end': 15405.171, 'text': 'What is separate chaining? So separate chaining is just one of many, many hash collision resolution techniques.', 'start': 15395.991, 'duration': 9.18}], 'summary': 'Achieve constant time for insertion, removal, and search with a good hash function.', 'duration': 34.377, 'max_score': 15370.794, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM15370794.jpg'}, {'end': 15794.951, 'src': 'embed', 'start': 15764.326, 'weight': 3, 'content': [{'end': 15764.906, 'text': 'Good question.', 'start': 15764.326, 'duration': 0.58}, {'end': 15770.07, 'text': "And the answer is that once there's a lot of elements within your hash table,", 'start': 15765.046, 'duration': 5.024}, {'end': 15775.315, 'text': "you'll actually want to create a new hash table with a larger capacity and rehash all your items and reinsert them.", 'start': 15770.07, 'duration': 5.245}, {'end': 15782.729, 'text': 'into this new larger table, because tables are fixed size.', 'start': 15776.628, 'duration': 6.101}, {'end': 15791.791, 'text': 'Okay, and another good question how do I remove key value pairs from my hash table with separate chaining??', 'start': 15782.749, 'duration': 9.042}, {'end': 15794.951, 'text': 'Well, the answer is basically the same procedure.', 'start': 15792.211, 'duration': 2.74}], 'summary': 'To handle large elements, create a new hash table with larger capacity and rehash items. for removing key-value pairs, apply the same procedure.', 'duration': 30.625, 'max_score': 15764.326, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM15764326.jpg'}], 'start': 14318.933, 'title': 'Hash tables and functions', 'summary': 'Covers hash tables as a data structure for mapping, hash functions for constructing mappings, properties of hash functions, and separate chaining in hash tables, achieving constant time complexity for insertion, removal, and search.', 'chapters': [{'end': 14526.889, 'start': 14318.933, 'title': 'Hash tables: data structure to rule them all', 'summary': 'Introduces hash tables as a data structure allowing mapping from keys to values via hashing, with coverage on collision resolution methods, including separate chaining and open addressing, and examples on implementing linear probing and quadratic probing.', 'duration': 207.956, 'highlights': ['Hash tables allow mapping from keys to values via hashing, with keys being unique and values not necessarily unique.', 'Coverage on collision resolution methods, including separate chaining and open addressing.', 'Examples provided for implementing linear probing and quadratic probing, with emphasis on understanding their functionality.']}, {'end': 14770.134, 'start': 14529.07, 'title': 'Hash functions in mapping', 'summary': 'Discusses hash functions and their role in constructing mappings, showcasing examples of hash functions for various data types and a simple hash function for a person mapping, emphasizing the arbitrary nature of hash function definitions.', 'duration': 241.064, 'highlights': ['The chapter discusses hash functions and their role in constructing mappings, showcasing examples of hash functions for various data types and a simple hash function for a person mapping.', 'Emphasizing the arbitrary nature of hash function definitions.', 'Illustrating examples of hash functions for integers and strings, along with a mini challenge for defining a hash function for a person.']}, {'end': 15321.83, 'start': 14770.154, 'title': 'Properties of hash functions', 'summary': 'Discusses the properties of hash functions, including their role in determining object equality, use in speeding up object comparisons, application in determining file content equality, importance of determinism, uniformity, and immutability in hash functions, and their role in implementing hash tables for quick insertion, lookup, and removal.', 'duration': 551.676, 'highlights': ['Hash functions play a role in determining object equality, speeding up object comparisons, and determining file content equality.', 'The importance of determinism, uniformity, and immutability in hash functions.', 'The role of hash functions in implementing hash tables for quick insertion, lookup, and removal.']}, {'end': 15729.6, 'start': 15323.089, 'title': 'Hash table: separate chaining', 'summary': 'Explains the concepts of separate chaining and open addressing in hash tables, highlighting their differences, time complexity, and application in handling collisions, with separate chaining achieving constant time complexity for insertion, removal, and search, and includes a demonstration of using separate chaining to handle collisions while inserting and looking up key-value pairs in a hash table.', 'duration': 406.511, 'highlights': ['Separate chaining and open addressing are the two most popular techniques for handling hash collisions in hash tables, with separate chaining using auxiliary data structures like linked lists and open addressing using probing within the hash table.', 'The time complexity of a hash table using separate chaining is remarkably efficient, achieving constant time for insertion, removal, and search on average, but can degrade to linear time with a non-uniform hash function.', 'Separate chaining maintains an auxiliary data structure, such as a linked list, to hold all the collisions, allowing easy lookup and insertion of key-value pairs, thereby achieving constant time complexity for these operations on average.', 'A demonstration of using separate chaining to handle collisions while inserting key-value pairs in a hash table is provided, showcasing how collisions are managed by appending new entries to the linked list at the corresponding index.', 'The process of looking up key-value pairs in a hash table using separate chaining involves scanning the linked list at the hashed index to find the desired key, demonstrating the ease of retrieving values using this technique.']}, {'end': 16099.732, 'start': 15731.6, 'title': 'Hash table with separate chaining', 'summary': 'Discusses the implementation of a hash table with separate chaining, addressing questions about maintaining constant time complexity, removing key-value pairs, alternative data structures for separate chaining, and source code explanation.', 'duration': 368.132, 'highlights': ['To maintain a constant time insertion and lookup time complexity when the hash table gets full, a new hash table with a larger capacity should be created, and all items should be rehashed and reinserted.', 'Removing key-value pairs from a hash table with separate chaining involves hashing the key and then removing the corresponding entry from the linked list.', 'Alternative data structures like arrays, binary trees, and self-balancing trees can be used within the linked list for separate chaining, with Java employing a hybrid approach involving binary trees for certain chain lengths.', "The source code for the hash table with separate chaining is available in the 'hash table' folder of the will.mcsdata.data-structures repository on GitHub, with the possibility of exploring multiple implementations."]}], 'duration': 1780.799, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM14318933.jpg', 'highlights': ['Hash tables allow mapping from keys to values via hashing, with keys being unique and values not necessarily unique.', 'Separate chaining and open addressing are the two most popular techniques for handling hash collisions in hash tables.', 'The time complexity of a hash table using separate chaining is remarkably efficient, achieving constant time for insertion, removal, and search on average.', 'To maintain a constant time insertion and lookup time complexity when the hash table gets full, a new hash table with a larger capacity should be created, and all items should be rehashed and reinserted.', 'Hash functions play a role in determining object equality, speeding up object comparisons, and determining file content equality.']}, {'end': 17320.403, 'segs': [{'end': 16154.643, 'src': 'embed', 'start': 16120.979, 'weight': 2, 'content': [{'end': 16127.422, 'text': 'And it says in the comments here, essentially, this strips the negative sign and places the hash value in the domain zero to capacity.', 'start': 16120.979, 'duration': 6.443}, {'end': 16139.744, 'text': 'Because hash values are integers, they could be anywhere in the domain of an integer, which is about minus 32 to the 31,.', 'start': 16129.441, 'duration': 10.303}, {'end': 16142.245, 'text': 'sorry to positive to the 31, around that.', 'start': 16139.744, 'duration': 2.501}, {'end': 16154.643, 'text': 'So what this does is a mask, it strips off the negative sign from the hash value and then mod it by the capacity.', 'start': 16146.434, 'duration': 8.209}], 'summary': 'The process strips the negative sign from hash values and assigns them to the domain zero to capacity, with the domain of integers ranging from about -2^31 to 2^31.', 'duration': 33.664, 'max_score': 16120.979, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM16120979.jpg'}, {'end': 16470.999, 'src': 'embed', 'start': 16440.108, 'weight': 1, 'content': [{'end': 16442.469, 'text': "And if there's a match, return that entry.", 'start': 16440.108, 'duration': 2.361}, {'end': 16443.449, 'text': 'Otherwise, return null.', 'start': 16442.508, 'duration': 0.941}, {'end': 16449.715, 'text': "Okay, here's the last really complicated method called the resize table.", 'start': 16444.973, 'duration': 4.742}, {'end': 16456.396, 'text': 'So this resizes the initial table, doubling this capacity of the table.', 'start': 16450.395, 'duration': 6.001}, {'end': 16458.475, 'text': 'So first we double the capacity.', 'start': 16457.135, 'duration': 1.34}, {'end': 16465.498, 'text': "We recompute the new threshold because now we have a higher threshold because we've increased the capacity.", 'start': 16459.956, 'duration': 5.542}, {'end': 16470.999, 'text': 'Now create a new table with this new capacity.', 'start': 16468.078, 'duration': 2.921}], 'summary': "Method 'resize table' doubles initial table capacity to create new table.", 'duration': 30.891, 'max_score': 16440.108, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM16440108.jpg'}, {'end': 16558.724, 'src': 'embed', 'start': 16529.027, 'weight': 3, 'content': [{'end': 16532.528, 'text': "So that's essentially separate chaining in a nutshell.", 'start': 16529.027, 'duration': 3.501}, {'end': 16535.208, 'text': 'Fairly simple to implement with a linked list.', 'start': 16533.289, 'duration': 1.919}, {'end': 16542.951, 'text': 'Much more difficult to implement with, say, a balanced binary tree or something like that.', 'start': 16535.669, 'duration': 7.282}, {'end': 16544.773, 'text': "I'm pretty excited.", 'start': 16543.772, 'duration': 1.001}, {'end': 16550.858, 'text': "We're going to be talking about the open addressing collision resolution technique for hash tables.", 'start': 16544.793, 'duration': 6.065}, {'end': 16552.438, 'text': "So let's get going.", 'start': 16551.457, 'duration': 0.981}, {'end': 16558.724, 'text': "First, let's just do a quick recap on hash tables so that everyone's on the same page.", 'start': 16553.38, 'duration': 5.344}], 'summary': 'Summary: separate chaining is simple with linked list, difficult with balanced binary tree. excited to discuss open addressing for hash tables.', 'duration': 29.697, 'max_score': 16529.027, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM16529026.jpg'}, {'end': 16635.541, 'src': 'embed', 'start': 16604.379, 'weight': 6, 'content': [{'end': 16609.622, 'text': "so when we're going to be using the open addressing collision resolution technique,", 'start': 16604.379, 'duration': 5.243}, {'end': 16617.426, 'text': 'the one thing you need to keep in mind is the actual key value pairs themselves are going to be stored in the table itself.', 'start': 16609.622, 'duration': 7.804}, {'end': 16626.491, 'text': 'So as opposed to, say, an auxiliary data structure like in the separate chaining method we saw in the last video.', 'start': 16618.226, 'duration': 8.265}, {'end': 16635.541, 'text': 'So this means that we care a great deal about the size of the hash tables and how many elements are currently in the hash table.', 'start': 16628.092, 'duration': 7.449}], 'summary': 'Open addressing stores key-value pairs in table, emphasizing size of hash tables and number of elements.', 'duration': 31.162, 'max_score': 16604.379, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM16604379.jpg'}, {'end': 16705.689, 'src': 'embed', 'start': 16677.399, 'weight': 0, 'content': [{'end': 16686.963, 'text': 'And what you can see from the linear probing one is that once it gets to a certain threshold, it gets exponentially bad.', 'start': 16677.399, 'duration': 9.564}, {'end': 16690.305, 'text': "So you don't want it to go anywhere near that, say, 0.8 mark.", 'start': 16687.163, 'duration': 3.142}, {'end': 16695.006, 'text': "In fact, we're going to be keeping it a lot lower than that usually.", 'start': 16692.185, 'duration': 2.821}, {'end': 16705.689, 'text': 'And what this says is we always need to keep the load factor which we denote by the Greek letter alpha below a certain threshold.', 'start': 16695.905, 'duration': 9.784}], 'summary': 'Linear probing becomes exponentially bad at 0.8 load factor.', 'duration': 28.29, 'max_score': 16677.399, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM16677399.jpg'}, {'end': 17000.127, 'src': 'embed', 'start': 16973.896, 'weight': 7, 'content': [{'end': 16985.272, 'text': 'So imagine your probing sequence just hops between three different values and cycles, and your table is of size 10,', 'start': 16973.896, 'duration': 11.376}, {'end': 16989.096, 'text': "but you're only ever able to hit three slots because it's stuck in a cycle.", 'start': 16985.272, 'duration': 3.824}, {'end': 16992.159, 'text': 'And then all of those three slots are full.', 'start': 16989.596, 'duration': 2.563}, {'end': 16995.002, 'text': "Well, you're stuck in an infinite loop.", 'start': 16992.78, 'duration': 2.222}, {'end': 17000.127, 'text': 'So this is very problematic and something we absolutely, absolutely need to handle.', 'start': 16995.823, 'duration': 4.304}], 'summary': 'Probing sequence hops between 3 values, cycles, and hits only 3 out of 10 slots, causing an infinite loop.', 'duration': 26.231, 'max_score': 16973.896, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM16973896.jpg'}, {'end': 17128.061, 'src': 'embed', 'start': 17098.984, 'weight': 5, 'content': [{'end': 17104.848, 'text': "So that's quite concerning because not all probing functions are viable.", 'start': 17098.984, 'duration': 5.864}, {'end': 17108.31, 'text': 'They produce cycles which are shorter than the table size.', 'start': 17105.328, 'duration': 2.982}, {'end': 17114.694, 'text': "How do we handle this? And in general, the consensus is that we don't handle this issue.", 'start': 17108.37, 'duration': 6.324}, {'end': 17128.061, 'text': 'Instead, we try to avoid it altogether by restricting the domain of probing functions that we choose to be those which produce a cycle of exactly length n.', 'start': 17115.395, 'duration': 12.666}], 'summary': 'Probing functions may produce cycles shorter than table size. solution: restrict domain to produce cycle of length n.', 'duration': 29.077, 'max_score': 17098.984, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM17098984.jpg'}, {'end': 17176.328, 'src': 'embed', 'start': 17150.188, 'weight': 4, 'content': [{'end': 17160.098, 'text': "Alright. so just to recap techniques such as linear probing and quadratic probing and double hashing, they're all subject to this issue of the cycles.", 'start': 17150.188, 'duration': 9.91}, {'end': 17170.468, 'text': 'And what we need to do is we need to find probing functions, which are very specific, that produce a cycle of length n,', 'start': 17161.339, 'duration': 9.129}, {'end': 17176.328, 'text': 'to avoid not being able to insert an element and being stuck in an infinite loop.', 'start': 17170.468, 'duration': 5.86}], 'summary': 'Techniques like linear probing, quadratic probing, and double hashing are subject to cycles, requiring specific probing functions to avoid infinite loops.', 'duration': 26.14, 'max_score': 17150.188, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM17150188.jpg'}], 'start': 16101.173, 'title': 'Hash table methods and techniques', 'summary': 'Covers methods of a hash table, such as normalizeindex, linked lists for collisions, open addressing technique, load factor importance, insertion process, probing sequences like linear, quadratic, double hashing, and addressing cycles in probing functions.', 'chapters': [{'end': 16439.428, 'start': 16101.173, 'title': 'Hash table methods overview', 'summary': 'Covers the methods of a hash table, including the normalizeindex method, which converts a hash value into an index and strips the negative sign, and the use of linked lists for handling collisions.', 'duration': 338.255, 'highlights': ['The NormalizeIndex method strips the negative sign from the hash value and places it in the domain zero to capacity, allowing it to be used as a lookup index.', 'The use of linked lists for handling collisions, including methods such as seekEntry and bucketInsertEntry, to add, update, or remove entries from the linked list structure.', 'Methods like clear, containsKey, and getKey are used for common operations like clearing the table, checking if a key exists, and retrieving the value associated with a key.']}, {'end': 16705.689, 'start': 16440.108, 'title': 'Open addressing hash tables', 'summary': 'Discusses the open addressing collision resolution technique for hash tables, emphasizing the importance of load factor and the adverse effects of high load factors, demonstrated through a chart comparison between separate chaining and linear probing.', 'duration': 265.581, 'highlights': ["The load factor, denoted by the Greek letter alpha, is the ratio between the number of items in the table and the size of the table, and it's crucial to keep it below a certain threshold, as high load factors can lead to exponentially bad performance.", 'Open addressing is a solution for hash collisions, where the key value pairs themselves are stored in the table, leading to a great deal of concern regarding the size of the hash tables and the number of elements inside them.', 'The resize table method involves doubling the capacity of the initial table, recomputing the new threshold, creating a new table with the new capacity, transferring data, and removing the old data, illustrating the process of resizing hash tables.']}, {'end': 17000.127, 'start': 16706.09, 'title': 'Hash table insertion and probing sequences', 'summary': 'Discusses the process of inserting key-value pairs into a hash table, exploring various probing sequences such as linear probing, quadratic probing, double hashing, and pseudo random number generator probing, and addressing the issue of cycles in probing sequences.', 'duration': 294.037, 'highlights': ['The chapter discusses the process of inserting key-value pairs into a hash table and explores various probing sequences such as linear probing, quadratic probing, double hashing, and pseudo random number generator probing.', 'The issue of cycles in probing sequences, which can result in infinite loops, is addressed.', 'An important aspect emphasized is setting up the probing function in a way that ensures a free slot is always found, considering the load factor is kept below a certain amount.']}, {'end': 17320.403, 'start': 17000.147, 'title': 'Open addressing and linear probing', 'summary': 'Discusses the issue of cycles in probing functions within the context of open addressing and linear probing, highlighting the problems with certain probing sequences and the need for specific probing functions to avoid infinite loops.', 'duration': 320.256, 'highlights': ['The probing function does not work in this particular situation as it produces cycles, posing a challenge for open addressing.', 'Efforts to handle the issue of cycles in probing functions are generally avoided, and specific probing functions that produce a cycle of exactly length n are sought to overcome this challenge.', 'Linear probing, a probing method using a linear formula p(x) = ax + b, faces challenges in producing a full cycle of order n.']}], 'duration': 1219.23, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM16101173.jpg', 'highlights': ['The load factor, denoted by the Greek letter alpha, is crucial to keep below a certain threshold for performance (3)', 'The resize table method involves doubling the capacity, recomputing the threshold, and transferring data (2)', 'The NormalizeIndex method places the hash value in the domain zero to capacity for use as a lookup index (1)', 'Linked lists handle collisions with methods like seekEntry and bucketInsertEntry (1)', 'Various probing sequences like linear, quadratic, double hashing are explored for insertion (1)', 'Efforts to handle cycles in probing functions are generally avoided (4)', 'Open addressing stores key-value pairs in the table, raising concerns about table size and elements (2)', 'Cycles in probing sequences can result in infinite loops, posing a challenge (3)']}, {'end': 18913.758, 'segs': [{'end': 17417.772, 'src': 'embed', 'start': 17380.262, 'weight': 1, 'content': [{'end': 17389.998, 'text': 'It turns out that this happens when the constant a and n the table size are relatively prime to each other.', 'start': 17380.262, 'duration': 9.736}, {'end': 17399.607, 'text': 'So two numbers are relatively prime, if their greatest common denominator is equal to one.', 'start': 17391.62, 'duration': 7.987}, {'end': 17406.393, 'text': 'So that is a and n have a GCD of one.', 'start': 17400.588, 'duration': 5.805}, {'end': 17413.369, 'text': 'And when that happens, the probing function will always be able to generate a complete cycle.', 'start': 17407.745, 'duration': 5.624}, {'end': 17417.772, 'text': 'And we will always be able to find an empty bucket.', 'start': 17414.229, 'duration': 3.543}], 'summary': 'When a and n are relatively prime, probing function generates a complete cycle and finds an empty bucket.', 'duration': 37.51, 'max_score': 17380.262, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM17380262.jpg'}, {'end': 17485.399, 'src': 'embed', 'start': 17448.785, 'weight': 2, 'content': [{'end': 17452.047, 'text': 'So we resize once we hit six elements.', 'start': 17448.785, 'duration': 3.262}, {'end': 17463.441, 'text': 'Okay, so, based on the probing function we chose and a table size, are we likely to run into an infinite loop while inserting?', 'start': 17453.536, 'duration': 9.905}, {'end': 17466.142, 'text': 'based on what I told you in the last few slides?', 'start': 17463.441, 'duration': 2.701}, {'end': 17469.043, 'text': 'And the answer is yes.', 'start': 17467.622, 'duration': 1.421}, {'end': 17475.206, 'text': 'the greatest common denominator of nine and six is equal to three, which is not one.', 'start': 17469.043, 'duration': 6.163}, {'end': 17485.399, 'text': "So let's go ahead and attempt to insert some elements regardless, we may or may not hit any problems.", 'start': 17477.714, 'duration': 7.685}], 'summary': 'Resizing occurs at six elements, leading to potential infinite loops during insertion due to the chosen probing function and table size.', 'duration': 36.614, 'max_score': 17448.785, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM17448785.jpg'}, {'end': 17881.156, 'src': 'embed', 'start': 17841.636, 'weight': 5, 'content': [{'end': 17849.719, 'text': "And we just finished inserting the fourth element, so it's time that we resize the table.", 'start': 17841.636, 'duration': 8.083}, {'end': 17858.803, 'text': 'So how we usually resize the table is via some exponential fashion, such as doubling or tripling or so on.', 'start': 17851, 'duration': 7.803}, {'end': 17867.068, 'text': 'But we need to double in such a way that the GCD of n and a still holds.', 'start': 17859.824, 'duration': 7.244}, {'end': 17876.313, 'text': 'So after doubling, n is equal to 24, and the GCD property is still good.', 'start': 17868.489, 'duration': 7.824}, {'end': 17881.156, 'text': "Alpha is a constant, so it's still 3.5.", 'start': 17877.694, 'duration': 3.462}], 'summary': 'Resized table after inserting 4th element, doubled n to 24, maintaining gcd property.', 'duration': 39.52, 'max_score': 17841.636, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM17841636.jpg'}, {'end': 18145.458, 'src': 'embed', 'start': 18111.74, 'weight': 4, 'content': [{'end': 18114.641, 'text': 'Otherwise, we degrade to linear probing.', 'start': 18111.74, 'duration': 2.901}, {'end': 18120.183, 'text': 'But, as we saw in the previous videos,', 'start': 18116.581, 'duration': 3.602}, {'end': 18127.366, 'text': "not all quadratic functions are viable because they don't produce a cycle of order n and we might get stuck in an infinite loop.", 'start': 18120.183, 'duration': 7.183}, {'end': 18135.369, 'text': 'So as it turns out, most randomly selected quadratic probing functions will end up producing a cycle.', 'start': 18128.306, 'duration': 7.063}, {'end': 18137.61, 'text': "Here's an example.", 'start': 18136.71, 'duration': 0.9}, {'end': 18145.458, 'text': 'Suppose we chose our probing function to be p of x equals 2x squared plus 2.', 'start': 18137.67, 'duration': 7.788}], 'summary': 'Quadratic probing functions may produce cycles, as shown with p(x) = 2x^2 + 2.', 'duration': 33.718, 'max_score': 18111.74, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM18111740.jpg'}, {'end': 18197.433, 'src': 'embed', 'start': 18172.385, 'weight': 0, 'content': [{'end': 18184.389, 'text': 'So our probing function is only ever able to hit the buckets 4 and 7, so it makes it impossible to reach all the other buckets 0, 1, 2, 3, 5, 6,', 'start': 18172.385, 'duration': 12.004}, {'end': 18185.17, 'text': 'and 8..', 'start': 18184.389, 'duration': 0.781}, {'end': 18188.731, 'text': "So we're stuck in an infinite loop when 4 and 7 are already occupied.", 'start': 18185.17, 'duration': 3.561}, {'end': 18190.111, 'text': 'This is really, really bad.', 'start': 18188.771, 'duration': 1.34}, {'end': 18197.433, 'text': 'So the question, then, is how do we pick a probing function which always works?', 'start': 18192.611, 'duration': 4.822}], 'summary': 'Probing function hits only buckets 4 and 7, leading to an infinite loop when occupied. need a new probing function.', 'duration': 25.048, 'max_score': 18172.385, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM18172385.jpg'}, {'end': 18309.125, 'src': 'embed', 'start': 18277.266, 'weight': 6, 'content': [{'end': 18288.729, 'text': "So we're going to focus on the second one where p of x equals x squared plus x divided by 2 and the table size is a power of 2.", 'start': 18277.266, 'duration': 11.463}, {'end': 18295.794, 'text': 'All right, suppose we have an initially empty hash table and we want to insert some key value pair.', 'start': 18288.729, 'duration': 7.065}, {'end': 18301.078, 'text': "And we're using the following quadratic probing function.", 'start': 18296.555, 'duration': 4.523}, {'end': 18305.522, 'text': 'P of x equals x squared plus x divided by two.', 'start': 18301.639, 'duration': 3.883}, {'end': 18309.125, 'text': "And the table size is a power of two, so it's eight.", 'start': 18306.262, 'duration': 2.863}], 'summary': 'Using a quadratic probing function with p(x) = x^2 + x/2 and a table size of 8.', 'duration': 31.859, 'max_score': 18277.266, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM18277266.jpg'}, {'end': 18599.001, 'src': 'embed', 'start': 18571.893, 'weight': 3, 'content': [{'end': 18580.437, 'text': "All right, let's talk about hash tables and the double hashing open addressing collision resolution technique.", 'start': 18571.893, 'duration': 8.544}, {'end': 18582.918, 'text': 'So just a quick recap.', 'start': 18581.397, 'duration': 1.521}, {'end': 18594.92, 'text': "For those of you who don't know how we do insertions into hash tables for open addressing, we start with a variable x initialized to 1.", 'start': 18583.717, 'duration': 11.203}, {'end': 18599.001, 'text': 'We compute the hash value of the key.', 'start': 18594.92, 'duration': 4.081}], 'summary': 'Discussion on hash tables and double hashing open addressing technique.', 'duration': 27.108, 'max_score': 18571.893, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM18571893.jpg'}], 'start': 17320.403, 'title': 'Hash table probing and resizing', 'summary': 'Discusses the importance of avoiding infinite loops in hash table probing, along with the need for table resizing when reaching the threshold. it highlights the significance of selecting probing functions with constant values relatively prime to the table size and provides examples demonstrating potential infinite loop scenarios, as well as doubling the table size while maintaining the gcd property. the chapter also explains the process of resizing a hash table using quadratic probing and the idea behind quadratic probing, providing examples and ways to pick a probing function, as well as the explanation and application of double hashing open addressing collision resolution technique.', 'chapters': [{'end': 17475.206, 'start': 17320.403, 'title': 'Avoiding infinite loops in hash table probing', 'summary': 'Discusses the importance of avoiding infinite loops in hash table probing, highlighting the significance of selecting probing functions with constant values relatively prime to the table size and provides an example demonstrating potential infinite loop scenarios.', 'duration': 154.803, 'highlights': ["The probing function will always generate a complete cycle when the constant 'a' and the table size 'n' are relatively prime, ensuring the ability to find an empty bucket.", 'The example demonstrates the potential for an infinite loop while inserting key-value pairs based on the selected probing function and table size, as the greatest common denominator of nine and six is not one.', 'Selecting probing functions with constant values relatively prime to the table size is crucial to avoid getting stuck in infinite loops and ensures the ability to reach all buckets.']}, {'end': 17881.156, 'start': 17477.714, 'title': 'Hash table probing and resizing', 'summary': 'Discusses hash table insertion using probing functions and demonstrates the need for table resizing when reaching the threshold, with an example of doubling the table size while maintaining the gcd property.', 'duration': 403.442, 'highlights': ['The chapter introduces the concept of hash table insertion using probing functions to handle hash collisions, demonstrating the process of inserting key-value pairs and handling collisions by incrementing the probing offset.', 'It explains the need for table resizing when the threshold of the table is reached, exemplifying the process of doubling the table size while ensuring the GCD property is maintained.', 'It emphasizes the significance of selecting a probing function that avoids cycles, showcasing an example of choosing a probing function to prevent cycle occurrence and ensure smooth key insertion.']}, {'end': 18913.758, 'start': 17881.156, 'title': 'Quadratic probing for hash table', 'summary': 'Explains the process of resizing a hash table using quadratic probing and the idea behind quadratic probing, providing examples and ways to pick a probing function, as well as the explanation and application of double hashing open addressing collision resolution technique.', 'duration': 1032.602, 'highlights': ['The chapter explains the process of resizing a hash table using quadratic probing', 'The idea behind quadratic probing is thoroughly explained with examples and ways to pick a probing function', 'Explanation and application of double hashing open addressing collision resolution technique']}], 'duration': 1593.355, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM17320403.jpg', 'highlights': ['Selecting probing functions with constant values relatively prime to the table size is crucial to avoid getting stuck in infinite loops and ensures the ability to reach all buckets.', "The probing function will always generate a complete cycle when the constant 'a' and the table size 'n' are relatively prime, ensuring the ability to find an empty bucket.", 'The example demonstrates the potential for an infinite loop while inserting key-value pairs based on the selected probing function and table size, as the greatest common denominator of nine and six is not one.', 'The chapter introduces the concept of hash table insertion using probing functions to handle hash collisions, demonstrating the process of inserting key-value pairs and handling collisions by incrementing the probing offset.', 'It emphasizes the significance of selecting a probing function that avoids cycles, showcasing an example of choosing a probing function to prevent cycle occurrence and ensure smooth key insertion.', 'It explains the need for table resizing when the threshold of the table is reached, exemplifying the process of doubling the table size while ensuring the GCD property is maintained.', 'The chapter explains the process of resizing a hash table using quadratic probing.', 'Explanation and application of double hashing open addressing collision resolution technique.', 'The idea behind quadratic probing is thoroughly explained with examples and ways to pick a probing function.']}, {'end': 20716.525, 'segs': [{'end': 18997.635, 'src': 'embed', 'start': 18968.001, 'weight': 1, 'content': [{'end': 18973.966, 'text': '75, so our threshold to resize is five, so once we hit five elements, we need to grow the table size.', 'start': 18968.001, 'duration': 5.965}, {'end': 18981.325, 'text': "All right, so let's insert all these key value pairs on the left into this hash table.", 'start': 18975.501, 'duration': 5.824}, {'end': 18984.427, 'text': 'So first key value pair is k1 and v1.', 'start': 18981.925, 'duration': 2.502}, {'end': 18995.734, 'text': 'Now suppose that the hash value for the first hash function of k1 is 67 and h2 of k1 is 34.', 'start': 18985.788, 'duration': 9.946}, {'end': 18997.635, 'text': 'And first thing we do is we compute delta.', 'start': 18995.734, 'duration': 1.901}], 'summary': 'Hash table resizes at 75% capacity, with first key-value pair k1:v1', 'duration': 29.634, 'max_score': 18968.001, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM18968001.jpg'}, {'end': 19633.22, 'src': 'embed', 'start': 19608.609, 'weight': 4, 'content': [{'end': 19614.332, 'text': "The naive removing method doesn't work because k3 clearly exists within the hash table.", 'start': 19608.609, 'duration': 5.723}, {'end': 19617.973, 'text': 'We can see it there in index 3.', 'start': 19614.372, 'duration': 3.601}, {'end': 19620.214, 'text': "So here's a solution to the removing.", 'start': 19617.973, 'duration': 2.241}, {'end': 19623.075, 'text': 'When we remove an element,', 'start': 19621.535, 'duration': 1.54}, {'end': 19633.22, 'text': "we're going to place a unique marker called a tombstone instead of a null element to indicate that a specific key value pair has been deleted or removed.", 'start': 19623.075, 'duration': 10.145}], 'summary': 'Naive removing method fails, solution: use tombstone marker instead of null for deleted elements.', 'duration': 24.611, 'max_score': 19608.609, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM19608609.jpg'}, {'end': 19905.485, 'src': 'embed', 'start': 19879.4, 'weight': 5, 'content': [{'end': 19884.945, 'text': 'And then just go to the hash table folder to find a whole bunch of hash table implementations.', 'start': 19879.4, 'duration': 5.545}, {'end': 19889.293, 'text': 'I have three different open addressing implementations here.', 'start': 19886.07, 'duration': 3.223}, {'end': 19893.436, 'text': 'In particular, we have quadratic probing, linear probing, and double hashing.', 'start': 19889.353, 'duration': 4.083}, {'end': 19895.718, 'text': "They're all very similar to each other.", 'start': 19894.156, 'duration': 1.562}, {'end': 19899.58, 'text': 'So I will only be looking at one right now.', 'start': 19896.418, 'duration': 3.162}, {'end': 19905.485, 'text': "But if you're curious, you can go on GitHub and check them out for yourself.", 'start': 19899.661, 'duration': 5.824}], 'summary': 'The transcript discusses three open addressing hash table implementations: quadratic probing, linear probing, and double hashing.', 'duration': 26.085, 'max_score': 19879.4, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM19879400.jpg'}, {'end': 20122.84, 'src': 'embed', 'start': 20093.628, 'weight': 3, 'content': [{'end': 20105.475, 'text': "Essentially it, it finds the power of 2, that is, just above this current number, or it'll also take the default capacity,", 'start': 20093.628, 'duration': 11.847}, {'end': 20108.536, 'text': "which itself is a power of 2, so we don't have to worry about that.", 'start': 20105.475, 'duration': 3.061}, {'end': 20112.737, 'text': "So either way, it's going to be a power of 2.", 'start': 20109.597, 'duration': 3.14}, {'end': 20119.539, 'text': 'Then we compute the threshold, which is just load factor times the capacity, and initialize our tables.', 'start': 20112.737, 'duration': 6.802}, {'end': 20122.84, 'text': "All right, so let's get rolling.", 'start': 20120.819, 'duration': 2.021}], 'summary': 'The algorithm uses power of 2 for capacity to compute a threshold for initializing tables.', 'duration': 29.212, 'max_score': 20093.628, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM20093628.jpg'}, {'end': 20215.23, 'src': 'embed', 'start': 20182.39, 'weight': 2, 'content': [{'end': 20189.196, 'text': 'This inserts a key value pair inside the hash table or updates a value if the key already exists.', 'start': 20182.39, 'duration': 6.806}, {'end': 20192.699, 'text': "All right, we don't want to allow null keys.", 'start': 20190.917, 'duration': 1.782}, {'end': 20194.621, 'text': 'If that happens, we throw an exception.', 'start': 20192.719, 'duration': 1.902}, {'end': 20204.94, 'text': "If the number of buckets used is greater than or equal to the threshold we're tolerating, we're going to resize the table before doing anything else.", 'start': 20195.991, 'duration': 8.949}, {'end': 20215.23, 'text': 'Otherwise, we want to calculate the hash value from the key using the built-in hash code method, and you can override this for your particular object.', 'start': 20205.921, 'duration': 9.309}], 'summary': 'Updates hash table with key-value pair, throws exception for null keys, resizes when buckets exceed threshold.', 'duration': 32.84, 'max_score': 20182.39, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM20182390.jpg'}, {'end': 20442.342, 'src': 'embed', 'start': 20412.325, 'weight': 7, 'content': [{'end': 20419.548, 'text': 'So contains key and has key just check if a key exists within the hash table.', 'start': 20412.325, 'duration': 7.223}, {'end': 20431.716, 'text': "And to do this I'm being pretty lazy and I'm just calling the get method and I'm setting an instance variable in there called contains flag,", 'start': 20420.349, 'duration': 11.367}, {'end': 20436.218, 'text': 'which gets set to true or false whether a key is inside our hash table or not,', 'start': 20431.716, 'duration': 4.502}, {'end': 20442.342, 'text': 'because the hash key in the get method would look would have essentially the same code.', 'start': 20436.218, 'duration': 6.124}], 'summary': 'Using the get method to check if a key exists in the hash table.', 'duration': 30.017, 'max_score': 20412.325, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM20412325.jpg'}, {'end': 20498.337, 'src': 'embed', 'start': 20469.57, 'weight': 6, 'content': [{'end': 20477.035, 'text': 'We set the flag to be true when we identify that the key is indeed inside the hash table.', 'start': 20469.57, 'duration': 7.465}, {'end': 20482.538, 'text': 'And here, our else condition is just shorter.', 'start': 20478.355, 'duration': 4.183}, {'end': 20490.223, 'text': 'We return if we hit a null cell instead of inserting a new element, and set the contains flag to be false.', 'start': 20483.038, 'duration': 7.185}, {'end': 20493.494, 'text': 'Okay, so pretty easy.', 'start': 20492.153, 'duration': 1.341}, {'end': 20498.337, 'text': 'And the remove method is actually quite a bit shorter, interestingly.', 'start': 20494.194, 'duration': 4.143}], 'summary': 'Flag set to true when key is inside hash table, remove method shorter', 'duration': 28.767, 'max_score': 20469.57, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM20469570.jpg'}, {'end': 20637.461, 'src': 'embed', 'start': 20609.355, 'weight': 0, 'content': [{'end': 20615.138, 'text': 'But since we know that the capacity is already a power of 2, multiplying by 2 will keep it a power of 2.', 'start': 20609.355, 'duration': 5.783}, {'end': 20616.059, 'text': "So that's fine.", 'start': 20615.138, 'duration': 0.921}, {'end': 20618.24, 'text': 'So recompute the new threshold.', 'start': 20616.419, 'duration': 1.821}, {'end': 20625.925, 'text': 'Allocate some new memory for a new table.', 'start': 20619.861, 'duration': 6.064}, {'end': 20629.627, 'text': "I called it old table, but it's actually going to be the new table.", 'start': 20626.265, 'duration': 3.362}, {'end': 20637.461, 'text': 'shortly So here I perform a kind of interesting maneuver here.', 'start': 20630.613, 'duration': 6.848}], 'summary': 'Memory capacity is a power of 2, multiplying by 2 maintains this. new memory allocated for a new table.', 'duration': 28.106, 'max_score': 20609.355, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM20609355.jpg'}], 'start': 18914.919, 'title': 'Hash table methods and resizing', 'summary': 'Discusses various hash table methods and resizing, covering concepts such as double hashing, open addressing, quadratic probing, design and implementation, collision resolution, table resizing strategy, load factor, capacity, and efficient insertion and resizing processes, highlighting issues, tombstones, lazy relocation, source code details, and method functionalities.', 'chapters': [{'end': 19274.21, 'start': 18914.919, 'title': 'Double hashing example', 'summary': 'Explains the concept of double hashing through an example, demonstrating the insertion and resizing process of a hash table using delta values and probing functions, with a focus on collision resolution and table resizing strategy.', 'duration': 359.291, 'highlights': ['The strategy to resize the table with double hashing is to double the table size and then find the next prime number above this value. In this case, when the table size is doubled from 7 to 14, the next prime number above 14, which becomes the new table size, is 17.', 'When attempting to insert a new key-value pair, the computation of delta values and probing functions is used to handle hash collisions, ensuring the insertion of elements into the hash table without conflicts.', 'The process of inserting elements into the hash table and resolving collisions involves the calculation of delta values, determining the positions of key-value pairs, and updating the table size based on the load factor threshold.']}, {'end': 19854.923, 'start': 19274.21, 'title': 'Open addressing in hash tables', 'summary': 'Discusses the open addressing scheme in hash tables, highlighting the issues with naive removal, the use of tombstones for deletion, and lazy relocation for efficient lookup.', 'duration': 580.713, 'highlights': ['Naive removal of elements from a hash table results in flawed search functionality, as demonstrated by the removal of K2 and subsequent inability to find K3.', 'The solution to removing elements involves using tombstones to indicate deleted key-value pairs, enabling efficient search functionality by skipping over tombstones during lookup.', 'Lazy relocation involves moving key-value pairs to the first encountered tombstone position, optimizing future lookups and reducing the need for excessive probing.']}, {'end': 20034.67, 'start': 19854.943, 'title': 'Hash table with quadratic probing', 'summary': 'Discusses a hash table implementation using quadratic probing, along with details on the source code and its components, such as load factor, capacity, and unique keys.', 'duration': 179.727, 'highlights': ['The chapter provides details on a hash table implementation using open addressing with specific focus on quadratic probing, along with references to other implementations like linear probing and double hashing.', 'The hash table class for quadratic probing takes generic types K and V and includes instance variables for load factor, current capacity, maximum threshold, modification count, total number of buckets, and key count, thus providing insight into the internal workings of the implementation.', 'The implementation stores key-value pairs directly inside separate arrays for keys and values, and includes a tombstone marker for deletions, simplifying the code and enhancing its efficiency.']}, {'end': 20411.164, 'start': 20036.05, 'title': 'Hash table design and implementation', 'summary': 'Explains the design and implementation of a hash table, covering default constants, capacity initialization, quadratic probing function, and insert method optimization, with a focus on load factor and capacity calculations, hash value stripping, and key insertion or update. the chapter also emphasizes the importance of handling null keys and resizing the table based on the number of used buckets and the specified threshold.', 'duration': 375.114, 'highlights': ['The method for calculating the capacity ensures that it is a power of two, which is essential for hash table optimization.', 'The normalized index method plays a crucial role in dumping the hash value inside the domain, zero to the capacity, non-inclusive, ensuring efficient hash table operations.', 'The insert method optimizes the process by handling null keys, resizing the table based on the specified threshold, and utilizing an efficient probing mechanism to avoid hash collisions and ensure successful key insertion or update.', 'The chapter emphasizes the importance of handling null keys and resizing the table based on the number of used buckets and the specified threshold, showcasing a robust approach to hash table implementation.']}, {'end': 20716.525, 'start': 20412.325, 'title': 'Hash table methods and resizing', 'summary': 'Discusses the contains, get, remove, resize table, and return all methods which support hash table functionality, including the identification of key existence, insertion, and resizing of the table.', 'duration': 304.2, 'highlights': ['The resize table method is called when inserting new elements to grow the table size, ensuring the capacity remains a power of 2, and it involves re-computing the new threshold, allocating new memory for a new table, and performing a swap operation to reset the key count and bucket count.', 'The get method involves finding the original hash, setting flags based on whether the key is inside the hash table or not, and returning null if a null cell is encountered instead of inserting a new element, while the remove method decrements the key count, updates the modification count, and sets tombstones to remove a key from the hash table.', 'The contains method checks if a key exists within the hash table and sets an instance variable to true or false based on the existence of the key.', 'The return all methods simply return all the keys and values contained within the hash table, making them self-explanatory.']}], 'duration': 1801.606, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM18914919.jpg', 'highlights': ['The resize table method ensures the capacity remains a power of 2, involving re-computing the new threshold and performing a swap operation.', 'The process of inserting elements into the hash table involves calculating delta values, determining positions of key-value pairs, and updating the table size based on the load factor threshold.', 'The insert method optimizes the process by handling null keys, resizing the table based on the specified threshold, and utilizing an efficient probing mechanism to avoid hash collisions.', 'The method for calculating the capacity ensures it is a power of two, essential for hash table optimization.', 'The solution to removing elements involves using tombstones to indicate deleted key-value pairs, enabling efficient search functionality by skipping over tombstones during lookup.', 'The chapter provides details on a hash table implementation using open addressing with specific focus on quadratic probing.', 'The get method involves finding the original hash, setting flags based on whether the key is inside the hash table or not, and returning null if a null cell is encountered.', 'The contains method checks if a key exists within the hash table and sets an instance variable to true or false based on the existence of the key.']}, {'end': 22438.968, 'segs': [{'end': 20796.111, 'src': 'embed', 'start': 20743.8, 'weight': 3, 'content': [{'end': 20752.682, 'text': "This is one of my personal favorites because it's such a powerful data structure, and it boasts efficiency, and it's really, really simple to code.", 'start': 20743.8, 'duration': 8.882}, {'end': 20754.583, 'text': "So let's dive right in.", 'start': 20753.703, 'duration': 0.88}, {'end': 20761.4, 'text': "So things we're covering in the Fenwick Tree video series, just some standard stuff.", 'start': 20755.831, 'duration': 5.569}, {'end': 20770.073, 'text': 'So go over some motivation, why this data structure exists, analyze its time complexity, and then go into some implementation details.', 'start': 20761.68, 'duration': 8.393}, {'end': 20780.523, 'text': "So in this video, we'll get to the range query and later videos, how to do point updates and how to construct the Fenwick tree in linear time.", 'start': 20771.178, 'duration': 9.345}, {'end': 20789.327, 'text': "You can also do things like range updates, but I'm not going to be covering that in this series, at least not yet.", 'start': 20780.863, 'duration': 8.464}, {'end': 20796.111, 'text': 'Okay, so what is the motivation behind the Fenwick tree?', 'start': 20791.068, 'duration': 5.043}], 'summary': 'Fenwick tree: powerful, efficient, simple data structure for range queries and linear time construction.', 'duration': 52.311, 'max_score': 20743.8, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM20743800.jpg'}, {'end': 21525.239, 'src': 'embed', 'start': 21492.185, 'weight': 1, 'content': [{'end': 21496.095, 'text': 'So we start at i, and while i is not equal to 0,', 'start': 21492.185, 'duration': 3.91}, {'end': 21508.265, 'text': "We're going to sum up the values in our Fenwick tree and we're going to remove the value of the least significant bit.", 'start': 21496.095, 'duration': 12.17}, {'end': 21515.831, 'text': "And we're going to keep doing this until our value is 0, and then we can return the sum.", 'start': 21509.506, 'duration': 6.325}, {'end': 21521.095, 'text': 'So the range query now is just a difference between those prefix sums.', 'start': 21516.572, 'duration': 4.523}, {'end': 21525.239, 'text': 'So a really neat little algorithm.', 'start': 21522.336, 'duration': 2.903}], 'summary': 'Algorithm sums values in fenwick tree using least significant bit.', 'duration': 33.054, 'max_score': 21492.185, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM21492185.jpg'}, {'end': 21657.603, 'src': 'embed', 'start': 21622.728, 'weight': 2, 'content': [{'end': 21633.412, 'text': 'So for instance, if we want to add a value at index 9, then we have to find out all the cells which are responsible for 9.', 'start': 21622.728, 'duration': 10.684}, {'end': 21640.795, 'text': 'Because remember, cells are responsible for a range of responsibility.', 'start': 21633.412, 'duration': 7.383}, {'end': 21649.638, 'text': 'So if we start with 9 and we find the least significant bit and add it to 9, then we get 10.', 'start': 21642.594, 'duration': 7.044}, {'end': 21654.261, 'text': 'So 10, find the least significant bit, has a value of 2.', 'start': 21649.638, 'duration': 4.623}, {'end': 21657.603, 'text': 'Then we add it to 10.', 'start': 21654.261, 'duration': 3.342}], 'summary': 'Algorithm adds value to index 9, finds responsible cells, and calculates new values.', 'duration': 34.875, 'max_score': 21622.728, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM21622728.jpg'}, {'end': 21862.528, 'src': 'embed', 'start': 21829.348, 'weight': 0, 'content': [{'end': 21840.256, 'text': 'What we could do is initialize our Fenwick tree to be an array containing all zeros and add the values into the Fenwick tree one at a time,', 'start': 21829.348, 'duration': 10.908}, {'end': 21842.837, 'text': 'using point updates to get a total time.', 'start': 21840.256, 'duration': 2.581}, {'end': 21846.88, 'text': 'complexity of order n log n.', 'start': 21842.837, 'duration': 4.043}, {'end': 21849.162, 'text': 'However, we can do better.', 'start': 21846.88, 'duration': 2.282}, {'end': 21851.824, 'text': 'We can actually do this in linear time.', 'start': 21849.302, 'duration': 2.522}, {'end': 21854.706, 'text': 'So why bother with n log n?', 'start': 21852.284, 'duration': 2.422}, {'end': 21862.528, 'text': "All right, so in the linear construction we're going to be given an array of values.", 'start': 21856.305, 'duration': 6.223}], 'summary': 'Initialize fenwick tree with zeros, update values one at a time for linear construction, achieving linear time complexity.', 'duration': 33.18, 'max_score': 21829.348, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM21829348.jpg'}], 'start': 20717.146, 'title': 'Fenwick tree data structure', 'summary': 'Discusses the efficiency, time complexity, and implementation details of the fenwick tree data structure, emphasizing range query and linear time construction, with a focus on motivation and practical applications. it also explains the concept of efficiently computing range sum queries, outlining benefits, trade-offs, and implementation details, and covers the construction process, including point updates and linear time construction method, achieving a fully functional fenwick tree at the end.', 'chapters': [{'end': 20796.111, 'start': 20717.146, 'title': 'Fenwick tree data structure', 'summary': 'Discusses the fenwick tree data structure, its efficiency, time complexity, and implementation details, including range query and linear time construction, with a focus on motivation and practical applications.', 'duration': 78.965, 'highlights': ['The Fenwick tree is a powerful and efficient data structure that is simple to code.', 'The video series will cover motivation, time complexity analysis, implementation details, range query, point updates, and linear time construction of the Fenwick tree.', 'The iterator loops through all the keys and returns them one at a time, demonstrating the standard two-string method for quadratic probing with open addressing.']}, {'end': 21550.216, 'start': 20797.202, 'title': 'Fenwick tree for range sum queries', 'summary': 'Explains the concept of fenwick tree to efficiently compute range sum queries and highlights its benefits over linear queries, while also addressing the trade-offs and its implementation details. it outlines how to compute prefix sums, perform range queries, and the time complexity of the operations, emphasizing the logarithmic time complexity for point updates. it also mentions the limitations of fenwick tree for adding or removing elements from the array.', 'duration': 753.014, 'highlights': ['The chapter outlines the concept of computing prefix sums for an array, enabling constant time range queries compared to linear queries, which are inefficient. This emphasizes the benefit of using a Fenwick tree for efficient range sum queries.', 'The explanation of how a Fenwick tree functions, assigning responsibilities to specific cells based on their binary representation and utilizing bit manipulation for efficient range sum queries, provides insight into its underlying structure and operation.', 'The chapter details the process of performing interval sum queries using the Fenwick tree, demonstrating the step-by-step cascade down operation to compute the prefix sum for a given range, highlighting its efficiency in handling range queries.', 'Additionally, it mentions the limitations of the Fenwick tree, such as the inability to add or remove elements from the array, providing a comprehensive overview of the trade-offs associated with using this data structure for range sum queries.']}, {'end': 21916.882, 'start': 21551.637, 'title': 'Fenwick tree construction', 'summary': 'Covers the concept of fenwick tree construction, explaining the process of point updates and detailing the linear time construction method, which propagates values throughout the tree, achieving a fully functional fenwick tree at the end.', 'duration': 365.245, 'highlights': ['The chapter explains the process of point updates, where adding a value at an index involves finding the cells responsible for the index by adding the least significant bit successively, exemplified by adding a constant at position 6 in the Fenwick tree.', 'The chapter details the linear time construction method for a Fenwick tree, which involves propagating the values throughout the tree by updating the immediate cell responsible for each value, achieving a fully functional Fenwick tree with a time complexity of linear time.', 'The chapter discusses the naive construction of a Fenwick tree, where an array of values is transformed into a Fenwick tree using point updates with a total time complexity of order n log n.']}, {'end': 22438.968, 'start': 21918.103, 'title': 'Fenwick tree construction', 'summary': 'Explains the construction algorithm for the fenwick tree, demonstrating how to propagate values to their parent cells and providing source code in java for implementing the tree, along with crucial methods like finding prefix sums and performing point updates.', 'duration': 520.865, 'highlights': ['The chapter explains the construction algorithm for the Fenwick tree', 'Source code in Java is provided for implementing the tree', 'Methods like finding prefix sums and performing point updates are crucial']}], 'duration': 1721.822, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM20717146.jpg', 'highlights': ['The chapter details the linear time construction method for a Fenwick tree, achieving a fully functional Fenwick tree with a time complexity of linear time.', 'The chapter outlines the concept of computing prefix sums for an array, enabling constant time range queries compared to linear queries, emphasizing the benefit of using a Fenwick tree for efficient range sum queries.', 'The chapter explains the process of point updates, where adding a value at an index involves finding the cells responsible for the index by adding the least significant bit successively.', 'The chapter discusses the efficiency, time complexity, and implementation details of the Fenwick tree data structure, emphasizing range query and linear time construction, with a focus on motivation and practical applications.', 'The video series will cover motivation, time complexity analysis, implementation details, range query, point updates, and linear time construction of the Fenwick tree.']}, {'end': 23600.571, 'segs': [{'end': 22534.301, 'src': 'embed', 'start': 22499.695, 'weight': 2, 'content': [{'end': 22508.179, 'text': 'Suffix arrays are a relatively new data structure appearing around the early 90s due to the heavy memory consumption needs of suffix trees.', 'start': 22499.695, 'duration': 8.484}, {'end': 22514.467, 'text': "Let's start with the basics and talk about just what a suffix is.", 'start': 22509.884, 'duration': 4.583}, {'end': 22520.791, 'text': 'For our purposes, a suffix is a non empty substring at the end of a string.', 'start': 22515.328, 'duration': 5.463}, {'end': 22534.301, 'text': 'For example, if we ask ourselves what all the possible suffixes of the string horse are, we are able to come up with five unique suffixes.', 'start': 22522.553, 'duration': 11.748}], 'summary': 'Suffix arrays are a new data structure from the early 90s, addressing memory needs of suffix trees.', 'duration': 34.606, 'max_score': 22499.695, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM22499695.jpg'}, {'end': 22649.438, 'src': 'embed', 'start': 22622.955, 'weight': 4, 'content': [{'end': 22629.981, 'text': 'In summary, a suffix array is an array of indices which store the sorted suffixes of a string.', 'start': 22622.955, 'duration': 7.026}, {'end': 22634.845, 'text': 'Furthermore, for a bit of history on the suffix array,', 'start': 22630.762, 'duration': 4.083}, {'end': 22642.832, 'text': 'it is a data structure originally designed to be a space efficient alternative to a suffix tree, which, in turn,', 'start': 22634.845, 'duration': 7.987}, {'end': 22649.438, 'text': 'is itself meant to be a compressed version of another data structure called a try.', 'start': 22642.832, 'duration': 6.606}], 'summary': 'A suffix array stores sorted suffixes of a string, designed as a space-efficient alternative to a suffix tree.', 'duration': 26.483, 'max_score': 22622.955, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM22622955.jpg'}, {'end': 22705.92, 'src': 'embed', 'start': 22673.378, 'weight': 7, 'content': [{'end': 22684.305, 'text': "In this video we're going to talk about perhaps the most important piece of information associated, And that is the longest common prefix array,", 'start': 22673.378, 'duration': 10.927}, {'end': 22687.027, 'text': 'also known as the LCP array.', 'start': 22684.305, 'duration': 2.722}, {'end': 22697.414, 'text': 'The LCP array is an array where each index stores how many characters to sorted suffixes have in common with each other.', 'start': 22687.748, 'duration': 9.666}, {'end': 22699.175, 'text': "Let's have a closer look.", 'start': 22697.774, 'duration': 1.401}, {'end': 22705.92, 'text': 'Perhaps the best way to show what the LCP array is, is to do an example.', 'start': 22700.416, 'duration': 5.504}], 'summary': 'Explaining the significance of the lcp array in sorting suffixes.', 'duration': 32.542, 'max_score': 22673.378, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM22673378.jpg'}, {'end': 22804.216, 'src': 'embed', 'start': 22773.761, 'weight': 0, 'content': [{'end': 22780.323, 'text': 'And the next two only have one character in common, then three characters in common.', 'start': 22773.761, 'duration': 6.562}, {'end': 22784.145, 'text': 'And lastly, only one character in common.', 'start': 22780.684, 'duration': 3.461}, {'end': 22793.048, 'text': 'So the result is the following LCP array highlighted in purple.', 'start': 22786.706, 'duration': 6.342}, {'end': 22804.216, 'text': 'In summary, the LCP array is an array which tracks how many characters to sorted suffixes have in common with each other.', 'start': 22795.254, 'duration': 8.962}], 'summary': 'The lcp array tracks common characters in sorted suffixes.', 'duration': 30.455, 'max_score': 22773.761, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM22773761.jpg'}, {'end': 22873.781, 'src': 'embed', 'start': 22838.341, 'weight': 8, 'content': [{'end': 22840.002, 'text': 'And this is fine for most purposes.', 'start': 22838.341, 'duration': 1.661}, {'end': 22850.589, 'text': 'Lastly, we saw what the LCP array was, but not how to construct it very efficiently.', 'start': 22843.826, 'duration': 6.763}, {'end': 22861.834, 'text': 'There are other algorithms than the one I showed you to construct the LCP array, which run in a much better time complexity, that is,', 'start': 22851.269, 'duration': 10.565}, {'end': 22866.036, 'text': 'in n log n time and even in linear time.', 'start': 22861.834, 'duration': 4.202}, {'end': 22873.781, 'text': 'In this video, I want to discuss a neat application of suffix arrays and LCP arrays.', 'start': 22867.076, 'duration': 6.705}], 'summary': 'Discussion on efficient lcp array construction and its applications in suffix arrays.', 'duration': 35.44, 'max_score': 22838.341, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM22838341.jpg'}, {'end': 22988.439, 'src': 'embed', 'start': 22903.553, 'weight': 1, 'content': [{'end': 22908.817, 'text': 'A superior approach is to use the information stored inside the LCPA.', 'start': 22903.553, 'duration': 5.264}, {'end': 22914.201, 'text': 'This provides not only a quick but also a space efficient solution.', 'start': 22909.457, 'duration': 4.744}, {'end': 22919.725, 'text': "I'm not saying that this is the canonical way of finding all unique substrings.", 'start': 22914.861, 'duration': 4.864}, {'end': 22927.19, 'text': 'Because there exists other notable algorithms such as Rabin Karp in combination with bloom filters.', 'start': 22920.325, 'duration': 6.865}, {'end': 22932.554, 'text': "Let's now look at an example of how to find unique substrings.", 'start': 22928.391, 'duration': 4.163}, {'end': 22941.786, 'text': "Let's now look at an example of how to find all the unique substrings of the string a z a z a.", 'start': 22933.564, 'duration': 8.222}, {'end': 22947.148, 'text': 'For every string, there are exactly n times n plus one over two substrings.', 'start': 22941.786, 'duration': 5.362}, {'end': 22953.609, 'text': "The proof of this I will leave as an exercise so listener, but it's really not that hard to derive.", 'start': 22947.508, 'duration': 6.101}, {'end': 22959.851, 'text': 'Now notice that all the substrings here, there are a few duplicate ones.', 'start': 22954.45, 'duration': 5.401}, {'end': 22968.493, 'text': 'I have highlighted the repeated substrings, there are exactly six of them, and nine unique ones.', 'start': 22961.491, 'duration': 7.002}, {'end': 22976.836, 'text': "Now let's use the information inside the LCP array to figure out which of those substrings really were the duplicate ones.", 'start': 22969.334, 'duration': 7.502}, {'end': 22985.458, 'text': 'In the table on the right, I generate the LCP array for the string a z a z a.', 'start': 22978.234, 'duration': 7.224}, {'end': 22988.439, 'text': 'Remember what the LCP array represents.', 'start': 22985.458, 'duration': 2.981}], 'summary': "Using lcpa to find unique substrings in 'a z a z a', resulting in 9 unique substrings and 6 duplicates.", 'duration': 84.886, 'max_score': 22903.553, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM22903553.jpg'}, {'end': 23082.683, 'src': 'embed', 'start': 23055.834, 'weight': 3, 'content': [{'end': 23059.277, 'text': 'So there are two repeated substrings here we can eliminate.', 'start': 23055.834, 'duration': 3.443}, {'end': 23069.391, 'text': 'z, and z, a, we can then come up with an interesting way of counting all unique substrings.', 'start': 23061.383, 'duration': 8.008}, {'end': 23076.077, 'text': 'We know how many substrings there are, and that is n times n plus one over two.', 'start': 23069.991, 'duration': 6.086}, {'end': 23082.683, 'text': 'And we also know the number of duplicate strings, that is the sum of all the LCP values.', 'start': 23076.918, 'duration': 5.765}], 'summary': 'Eliminate two repeated substrings to count unique substrings, n(n+1)/2 total, with lcp values for duplicates.', 'duration': 26.849, 'max_score': 23055.834, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM23055834.jpg'}, {'end': 23413.934, 'src': 'embed', 'start': 23384.485, 'weight': 9, 'content': [{'end': 23393.375, 'text': "The answer is, we're going to look for k strings, each of different colors whom share the largest LCP value.", 'start': 23384.485, 'duration': 8.89}, {'end': 23396.818, 'text': "Let's do an example with k equals three.", 'start': 23394.216, 'duration': 2.602}, {'end': 23405.648, 'text': 'Since k equals three, and we have three strings, this means that we need one string of each color.', 'start': 23397.519, 'duration': 8.129}, {'end': 23413.934, 'text': 'we can achieve a maximum of two if we select the following three adjacent suffixes.', 'start': 23407.648, 'duration': 6.286}], 'summary': 'Looking for k strings of different colors with largest lcp value, example with k=3, can achieve max of 2 with three adjacent suffixes.', 'duration': 29.449, 'max_score': 23384.485, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM23384485.jpg'}], 'start': 22438.968, 'title': 'Suffix arrays and lcp arrays', 'summary': 'Introduces the concept of suffix arrays, which store sorted suffixes of a string, and the lcp array, which tracks common characters between sorted suffixes. it discusses space efficiency, unique substring counting algorithms, and practical application on caddis online judge and github.', 'chapters': [{'end': 22873.781, 'start': 22438.968, 'title': 'Suffix array and lcp array', 'summary': 'Introduces the concept of a suffix array, a data structure containing all the sorted suffixes of a string, and the lcp array, which tracks how many characters two sorted suffixes have in common with each other, providing a compressed representation of the sorted suffixes. the chapter also discusses the space efficiency of suffix arrays as an alternative to suffix trees and their application in string processing.', 'duration': 434.813, 'highlights': ['A suffix array is an array containing all the sorted suffixes of a string, providing a compressed representation of the sorted suffixes without needing to physically store the suffixes themselves.', 'The LCP array is an array which tracks how many characters two sorted suffixes have in common with each other, offering valuable information derived from a simple construction.', 'Suffix arrays are a relatively new data structure appearing around the early 90s due to the heavy memory consumption needs of suffix trees, providing a space-efficient alternative.', 'The suffix array is an array of indices which store the sorted suffixes of a string, requiring only the original string and the array of associated indices for representation, contributing to its space efficiency.', 'The LCP array is an array where each index stores how many characters two sorted suffixes have in common with each other, providing valuable information associated with the suffix array.']}, {'end': 23246.525, 'start': 22874.442, 'title': 'Counting unique substrings', 'summary': "Discusses finding and counting unique substrings, comparing different algorithms' time complexity, and using lcp arrays to identify duplicate substrings, ending with a recommendation to practice on caddis online judge and access source code on github.", 'duration': 372.083, 'highlights': ["The chapter discusses finding and counting unique substrings, comparing different algorithms' time complexity, and using LCP arrays to identify duplicate substrings.", 'The superior approach is to use the information stored inside the LCPA, providing a quick and space-efficient solution.', "For the string 'azaz', there are exactly 6 repeated substrings and 9 unique substrings.", 'The LCP array is used to figure out which substrings were duplicate, and the example shows the process of identifying duplicate substrings using the LCP array.', 'A recommendation to practice on caddis online judge and access source code on GitHub is provided at the end.']}, {'end': 23600.571, 'start': 23247.866, 'title': 'Suffix array and lcp array analysis', 'summary': 'Explains the process of creating a suffix array and lcp array from concatenated strings, and then finding the longest common substring by identifying k different-colored suffixes with the largest lcp value and using a sliding window technique to capture the correct amount of suffix colors.', 'duration': 352.705, 'highlights': ['The chapter explains the process of creating a suffix array and LCP array from concatenated strings', 'Finding the longest common substring by identifying k different-colored suffixes with the largest LCP value', 'Using a sliding window technique to capture the correct amount of suffix colors', 'Performing a query to obtain the minimum LCP value on the current window']}], 'duration': 1161.603, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM22438968.jpg', 'highlights': ['The LCP array is an array which tracks how many characters two sorted suffixes have in common with each other, offering valuable information derived from a simple construction.', 'The superior approach is to use the information stored inside the LCPA, providing a quick and space-efficient solution.', 'Suffix arrays are a relatively new data structure appearing around the early 90s due to the heavy memory consumption needs of suffix trees, providing a space-efficient alternative.', "The chapter discusses finding and counting unique substrings, comparing different algorithms' time complexity, and using LCP arrays to identify duplicate substrings.", 'The suffix array is an array of indices which store the sorted suffixes of a string, requiring only the original string and the array of associated indices for representation, contributing to its space efficiency.', 'The LCP array is used to figure out which substrings were duplicate, and the example shows the process of identifying duplicate substrings using the LCP array.', "For the string 'azaz', there are exactly 6 repeated substrings and 9 unique substrings.", 'Introduces the concept of suffix arrays, which store sorted suffixes of a string, and the lcp array, which tracks common characters between sorted suffixes.', 'The chapter explains the process of creating a suffix array and LCP array from concatenated strings', 'Finding the longest common substring by identifying k different-colored suffixes with the largest LCP value']}, {'end': 24481.022, 'segs': [{'end': 23628.655, 'src': 'embed', 'start': 23602.321, 'weight': 0, 'content': [{'end': 23609.245, 'text': 'So to implement the sliding window, we will also need an additional data structure to keep track of the colors in our window.', 'start': 23602.321, 'duration': 6.924}, {'end': 23613.027, 'text': 'I recommend using a hash table for this task.', 'start': 23610.125, 'duration': 2.902}, {'end': 23618.79, 'text': 'On the bottom left, I drew a table to indicate how much of each color we are capturing.', 'start': 23613.787, 'duration': 5.003}, {'end': 23628.655, 'text': 'And the current window, a valid window will require at least k or more columns to have a value greater than zero.', 'start': 23619.591, 'duration': 9.064}], 'summary': 'Implement sliding window with hash table to track colors and capture at least k columns with value >0.', 'duration': 26.334, 'max_score': 23602.321, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM23602321.jpg'}, {'end': 23717.634, 'src': 'embed', 'start': 23662.944, 'weight': 2, 'content': [{'end': 23667.747, 'text': "So our rule when we're missing a certain color is to expand the window down.", 'start': 23662.944, 'duration': 4.803}, {'end': 23672.69, 'text': 'And when we already meet the criteria, we shrink the window down.', 'start': 23668.368, 'duration': 4.322}, {'end': 23678.994, 'text': "So let's expand our window downwards to capture some blue.", 'start': 23673.29, 'duration': 5.704}, {'end': 23684.297, 'text': 'Now we have enough blue and enough of each color to do a valid query.', 'start': 23679.614, 'duration': 4.683}, {'end': 23697.748, 'text': 'When we perform the query, we would see that the longest common substring for the window we are in will have length three representing the string a g.', 'start': 23685.197, 'duration': 12.551}, {'end': 23703.633, 'text': 'Now, since we have enough of each color, we can then reduce the window size.', 'start': 23697.748, 'duration': 5.885}, {'end': 23710.728, 'text': 'I removed one green suffix and we still have at least one of each color,', 'start': 23705.063, 'duration': 5.665}, {'end': 23717.634, 'text': 'so we can again perform a query to find out that we get the same result as last time.', 'start': 23710.728, 'duration': 6.906}], 'summary': 'Using window expansion and shrinking, we find the longest common substring of length three and successfully perform queries.', 'duration': 54.69, 'max_score': 23662.944, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM23662944.jpg'}, {'end': 23850.01, 'src': 'embed', 'start': 23823.389, 'weight': 4, 'content': [{'end': 23827.41, 'text': "we're going to finish where we left off in the last video.", 'start': 23823.389, 'duration': 4.021}, {'end': 23835.301, 'text': 'In this video, I want to do a full example solving the longest common substring problem with a suffix array.', 'start': 23828.05, 'duration': 7.251}, {'end': 23844.786, 'text': "For this example, we're going to have four strings s1 s2 s3 and s4.", 'start': 23836.84, 'duration': 7.946}, {'end': 23850.01, 'text': 'I have also selected the value of k to be equal to two,', 'start': 23845.587, 'duration': 4.423}], 'summary': 'Video solving longest common substring problem with a suffix array for 4 strings and k=2.', 'duration': 26.621, 'max_score': 23823.389, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM23823389.jpg'}, {'end': 24271.163, 'src': 'embed', 'start': 24237.306, 'weight': 5, 'content': [{'end': 24240.189, 'text': 'Lots of problems can actually be reduced to this problem.', 'start': 24237.306, 'duration': 2.883}, {'end': 24243.252, 'text': "So it's important that we have an efficient way of solving it.", 'start': 24240.229, 'duration': 3.023}, {'end': 24248.437, 'text': 'The naive approach requires n squared time and lots of space.', 'start': 24244.513, 'duration': 3.924}, {'end': 24260.031, 'text': 'What we want to do instead is use the information stored inside the longest common prefix array to yield a faster and also space efficient solution.', 'start': 24249.639, 'duration': 10.392}, {'end': 24262.433, 'text': "Let's do an example.", 'start': 24261.352, 'duration': 1.081}, {'end': 24271.163, 'text': 'What is the longest repeated substring of the string abracadabra? Feel free to pause the video and figure it out yourself.', 'start': 24262.653, 'duration': 8.51}], 'summary': 'Efficiently solve problems using longest common prefix array for faster and space efficient solutions.', 'duration': 33.857, 'max_score': 24237.306, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM24237306.jpg'}, {'end': 24491.806, 'src': 'embed', 'start': 24459.574, 'weight': 6, 'content': [{'end': 24465.396, 'text': 'The other repeated substring is found using the second largest common prefix value.', 'start': 24459.574, 'duration': 5.822}, {'end': 24471.838, 'text': 'And its first occurrence is found here and the second one just next to it.', 'start': 24466.396, 'duration': 5.442}, {'end': 24475.28, 'text': 'That is all for repeated substrings.', 'start': 24472.999, 'duration': 2.281}, {'end': 24481.022, 'text': 'Pretty easy once the suffix array and the LCP array have already been constructed.', 'start': 24476.08, 'duration': 4.942}, {'end': 24491.806, 'text': 'Here is a practice problem on caddis if you want to tackle a longest repeated substring problem which requires you to have an efficient solution.', 'start': 24482.422, 'duration': 9.384}], 'summary': 'Repeated substrings found using lcp array. practice problem available on caddis.', 'duration': 32.232, 'max_score': 24459.574, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM24459574.jpg'}], 'start': 23602.321, 'title': 'Sliding window method and longest common substring', 'summary': 'Covers the sliding window method for color querying and the implementation of the longest common substring problem with a suffix array for four strings with a k value of 2, demonstrating the use of suffix array and lcp array.', 'chapters': [{'end': 23798.058, 'start': 23602.321, 'title': 'Sliding window method for color querying', 'summary': 'Explains the implementation of the sliding window method using a hash table to track colors, requiring at least k columns to have a value greater than zero, and demonstrates color querying and window size adjustment with an example.', 'duration': 195.737, 'highlights': ['The chapter emphasizes the usage of a hash table as an additional data structure to track colors in the window, facilitating efficient color querying.', 'The explanation includes the requirement of at least k columns to have a value greater than zero for a valid window, providing a clear criterion for window validity.', 'The example demonstrates the process of expanding and shrinking the window to capture and verify the presence of each color, illustrating the practical application of the sliding window method.', 'The chapter showcases the querying process to find the longest common substring for the current window and the subsequent window size adjustment based on the color availability, offering a comprehensive understanding of the methodology.']}, {'end': 24481.022, 'start': 23799.625, 'title': 'Longest common substring with suffix array', 'summary': 'Covers a full example solving the longest common substring problem with a suffix array for four strings with a k value of 2, demonstrating the use of suffix array and lcp array, and then discusses an efficient way to solve the longest repeated substring problem using the information stored inside the longest common prefix array.', 'duration': 681.397, 'highlights': ['Solving the longest common substring problem with a suffix array for four strings with a k value of 2', 'Efficient way to solve the longest repeated substring problem using the information stored inside the longest common prefix array', 'Demonstrates the use of suffix array and LCP array']}], 'duration': 878.701, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM23602321.jpg', 'highlights': ['The chapter emphasizes the usage of a hash table for efficient color querying.', 'The explanation includes the requirement of at least k columns with a value greater than zero for a valid window.', 'The example demonstrates the process of expanding and shrinking the window to capture and verify the presence of each color.', 'The chapter showcases the querying process to find the longest common substring for the current window and subsequent window size adjustment based on color availability.', 'Solving the longest common substring problem with a suffix array for four strings with a k value of 2', 'Efficient way to solve the longest repeated substring problem using the information stored inside the longest common prefix array', 'Demonstrates the use of suffix array and LCP array']}, {'end': 25302.514, 'segs': [{'end': 24582.132, 'src': 'embed', 'start': 24503.87, 'weight': 0, 'content': [{'end': 24514.915, 'text': 'balanced binary search trees are very different from the traditional binary search tree because they not only conform to the binary search tree invariant,', 'start': 24503.87, 'duration': 11.045}, {'end': 24516.636, 'text': 'but they are also balanced.', 'start': 24514.915, 'duration': 1.721}, {'end': 24526.041, 'text': 'What I mean by balanced is that they are self adjusting to maintain a logarithmic height in proportion to the number of nodes they hold.', 'start': 24517.197, 'duration': 8.844}, {'end': 24537.004, 'text': 'This is very important because it keeps operations such as insertion and deletion extremely fast, because the tree is much more squashed.', 'start': 24526.801, 'duration': 10.203}, {'end': 24545.546, 'text': 'In terms of complexity, a binary search tree has average logarithmic operations, which is quite good.', 'start': 24537.704, 'duration': 7.842}, {'end': 24553.709, 'text': 'However, the worst case still remains linear, because the tree could degrade into a chain for some inputs.', 'start': 24546.107, 'duration': 7.602}, {'end': 24558.491, 'text': 'one such input is a sequence of increasing numbers.', 'start': 24554.649, 'duration': 3.842}, {'end': 24569.436, 'text': "To avoid this linear complexity, we've invented balanced binary search trees, in which the worst case is logarithmic for all operations,", 'start': 24559.612, 'duration': 9.824}, {'end': 24571.097, 'text': 'which makes them very appealing.', 'start': 24569.436, 'duration': 1.661}, {'end': 24582.132, 'text': 'Central to how nearly all balanced binary surgery implementations keep themselves balanced is the concept of tree rotations,', 'start': 24572.64, 'duration': 9.492}], 'summary': 'Balanced binary search trees maintain logarithmic height, ensuring fast operations. worst case complexity is logarithmic for all operations, making them appealing.', 'duration': 78.262, 'max_score': 24503.87, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM24503870.jpg'}, {'end': 24940.546, 'src': 'heatmap', 'start': 24644.452, 'weight': 1, 'content': [{'end': 24656.84, 'text': "Assuming node A has a left child B, we can perform a right rotation to put B where node A was and push node A down to become B's right child.", 'start': 24644.452, 'duration': 12.388}, {'end': 24662.911, 'text': 'When I first learned about this in my undergrad, I was mind blown.', 'start': 24658.447, 'duration': 4.464}, {'end': 24672.9, 'text': 'literally. I thought it was absurd, or even to the point of being illegal, that we should be allowed to do this and just move around nodes in a tree.', 'start': 24662.911, 'duration': 9.989}, {'end': 24680.275, 'text': "But what I've realized since is that a transformation like this is totally legitimate,", 'start': 24674.13, 'duration': 6.145}, {'end': 24684.198, 'text': "since we're not breaking the binary search tree and variant in any way.", 'start': 24680.275, 'duration': 3.923}, {'end': 24694.926, 'text': "If you inspect the left tree, you'll discover that, in terms of ordering and placement, node D is less than node B is less than E, is less than A,", 'start': 24684.598, 'duration': 10.328}, {'end': 24696.327, 'text': 'is less than C.', 'start': 24694.926, 'duration': 1.401}, {'end': 24700.731, 'text': 'then you inspect the right tree and remark that well, this is also true.', 'start': 24696.327, 'duration': 4.404}, {'end': 24706.919, 'text': 'a bit more detail on why performing tree rotations is a valid operation.', 'start': 24702.057, 'duration': 4.862}, {'end': 24717.484, 'text': 'First, you have to remember that all balanced binary search trees are binary search trees, meaning that the binary search tree invariant holds.', 'start': 24707.58, 'duration': 9.904}, {'end': 24719.985, 'text': 'So for every node n,', 'start': 24718.064, 'duration': 1.921}, {'end': 24727.829, 'text': 'the values in the left subtree are less than the value of n and the values in the right subtree are all greater than the value of n.', 'start': 24719.985, 'duration': 7.844}, {'end': 24733.994, 'text': "So in this sense, it doesn't matter what the tree structure itself looks like.", 'start': 24728.749, 'duration': 5.245}, {'end': 24738.818, 'text': 'All that fundamentally matters is that the binary search tree invariant holds.', 'start': 24734.655, 'duration': 4.163}, {'end': 24747.546, 'text': 'This means we are free to shuffle, transform or even rotate the values and nodes in our tree as we please,', 'start': 24739.699, 'duration': 7.847}, {'end': 24751.45, 'text': 'as long as the binary search tree invariant remains satisfied.', 'start': 24747.546, 'duration': 3.904}, {'end': 24758.282, 'text': "Now let's look at how these rotations are done in great detail.", 'start': 24753.419, 'duration': 4.863}, {'end': 24762.084, 'text': 'For simplicity, since the rotations are symmetric,', 'start': 24758.782, 'duration': 3.302}, {'end': 24767.847, 'text': 'I will only do the right rotation and you should be able to figure out the left rotation on your own.', 'start': 24762.084, 'duration': 5.763}, {'end': 24770.568, 'text': 'First, have a look at the tree on the right.', 'start': 24768.547, 'duration': 2.021}, {'end': 24780.854, 'text': 'Notice that there are directed edges pointing downwards, and another node P above a, which may or may not exist.', 'start': 24771.208, 'duration': 9.646}, {'end': 24784.636, 'text': 'This is why there is a dotted line on that edge.', 'start': 24781.074, 'duration': 3.562}, {'end': 24793, 'text': 'If note A does have a parent node P, then it is important that we take it into account when doing the rotation.', 'start': 24785.496, 'duration': 7.504}, {'end': 24803.448, 'text': "In either case, we start with a pointer reference to node A, this is the orange arrow, then we'll want a pointer to node B.", 'start': 24794.477, 'duration': 8.971}, {'end': 24812.58, 'text': "After that, set A's left pointer to point to B's right child.", 'start': 24806.292, 'duration': 6.288}, {'end': 24820.549, 'text': "then change B's right pointer to point to node a, and we've successfully done a right rotation.", 'start': 24812.58, 'duration': 7.969}, {'end': 24825.715, 'text': 'If we rearrange the nodes, this is what we would end up with.', 'start': 24821.35, 'duration': 4.365}, {'end': 24829.337, 'text': "However, notice that there's a slight problem.", 'start': 24827.096, 'duration': 2.241}, {'end': 24839.441, 'text': 'If node A had a parent node, then either the parents left or right pointer would still be referencing a.', 'start': 24829.957, 'duration': 9.484}, {'end': 24844.783, 'text': 'this is problematic, since B is a successor after the rotation.', 'start': 24839.441, 'duration': 5.342}, {'end': 24856.288, 'text': 'So we change the link to now point to be this step is usually done on the recursive callback using the return value of the right to rotate function.', 'start': 24845.524, 'duration': 10.764}, {'end': 24863.679, 'text': 'We just finished looking at the case where each node has a reference the left and the right child nodes.', 'start': 24858.356, 'duration': 5.323}, {'end': 24873.726, 'text': "But in some balance binary search tree implementations, it's more convenient for nodes to also have a reference to the parent node.", 'start': 24864.42, 'duration': 9.306}, {'end': 24882.331, 'text': 'This complicates tree rotations because now, instead of updating three pointers, we need to update six pointers.', 'start': 24874.626, 'duration': 7.705}, {'end': 24883.472, 'text': "Let's have a look.", 'start': 24882.791, 'duration': 0.681}, {'end': 24895.748, 'text': 'In this case, where we also have a parent link, every node is in a sense, doubly linked, we start off with a pointer referencing a.', 'start': 24885.345, 'duration': 10.403}, {'end': 24902.23, 'text': "And the first thing we'll want to do is also reference node B and node P.", 'start': 24895.748, 'duration': 6.482}, {'end': 24904.891, 'text': "So we don't lose them as we shuffle around pointers.", 'start': 24902.23, 'duration': 2.661}, {'end': 24913.695, 'text': "Next, we'll adjust the left subtree of a to make a is left pointer reference B's right subtree.", 'start': 24906.211, 'duration': 7.484}, {'end': 24918.938, 'text': 'Of course, throughout this example, assume B is not null.', 'start': 24914.436, 'duration': 4.502}, {'end': 24924.221, 'text': "If you're paranoid, you can add an extra if statement to check for this condition.", 'start': 24919.459, 'duration': 4.762}, {'end': 24930.305, 'text': "However, it would be a mistake to assume B's right subtree is not null.", 'start': 24925.162, 'duration': 5.143}, {'end': 24940.546, 'text': "we actually have to check against this before setting B's right child's parent to reference a.", 'start': 24931.26, 'duration': 9.286}], 'summary': 'Tree rotations maintain binary search tree invariant, allowing for node rearrangement while preserving order.', 'duration': 296.094, 'max_score': 24644.452, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM24644452.jpg'}, {'end': 25054.119, 'src': 'embed', 'start': 25025.131, 'weight': 3, 'content': [{'end': 25033.993, 'text': 'An AVL tree is one of many types of balanced binary search trees, which allow for logarithmic insertion, deletion and search operations.', 'start': 25025.131, 'duration': 8.862}, {'end': 25042.935, 'text': 'Something really special about AVL tree is that it was the first type of balanced binary search tree to be discovered.', 'start': 25035.253, 'duration': 7.682}, {'end': 25054.119, 'text': 'Then, soon after, a whole bunch of other types of balanced binary search trees started to emerge, including the two, three tree, the A tree,', 'start': 25045.151, 'duration': 8.968}], 'summary': 'Avl tree is the first balanced binary search tree, enabling logarithmic operations.', 'duration': 28.988, 'max_score': 25025.131, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM25025131.jpg'}, {'end': 25159.501, 'src': 'embed', 'start': 25128.678, 'weight': 4, 'content': [{'end': 25140.63, 'text': 'The invariant on the AVL tree that keeps it balanced is forcing the balance factor of every node to be either minus one, zero or plus one.', 'start': 25128.678, 'duration': 11.952}, {'end': 25148.037, 'text': 'If the balance factor of a node is anything else, we need to resolve that with tree rotations.', 'start': 25141.13, 'duration': 6.907}, {'end': 25155.215, 'text': 'In terms of information we need to store in each node to actually make the AVL tree work.', 'start': 25149.108, 'duration': 6.107}, {'end': 25159.501, 'text': "what we'll need is the actual value the node stores.", 'start': 25155.215, 'duration': 4.286}], 'summary': 'Avl tree maintains balance with balance factors of -1, 0, or 1.', 'duration': 30.823, 'max_score': 25128.678, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM25128678.jpg'}, {'end': 25312.766, 'src': 'embed', 'start': 25279.331, 'weight': 5, 'content': [{'end': 25285.896, 'text': 'Last but not least is the right left case, which is metric to the left right case.', 'start': 25279.331, 'duration': 6.565}, {'end': 25288.278, 'text': 'For this case,', 'start': 25286.616, 'duration': 1.662}, {'end': 25302.514, 'text': 'you would perform a right rotation about the yellow note on the left most image to transform this case into the right right case and then do a left rotation about the green note in the middle image.', 'start': 25288.278, 'duration': 14.236}, {'end': 25312.766, 'text': "Next, I want to show you some pseudocode for inserting nodes into an AVL tree because it's not all that obvious or easy.", 'start': 25304.58, 'duration': 8.186}], 'summary': 'Demonstrates transforming a case and introducing avl tree insertion pseudocode.', 'duration': 33.435, 'max_score': 25279.331, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM25279331.jpg'}], 'start': 24482.422, 'title': 'Balanced binary search trees and avl tree insertion', 'summary': 'Introduces the concept of balanced binary search trees emphasizing their self-adjusting nature to maintain a logarithmic height, tree rotations, and valid operation of tree transformations. it also explains avl tree insertion and the process of maintaining balance using tree rotations and balance factors.', 'chapters': [{'end': 24996.241, 'start': 24482.422, 'title': 'Balanced binary search trees', 'summary': 'Introduces the concept of balanced binary search trees, emphasizing on their self-adjusting nature to maintain a logarithmic height, the significance of tree rotations, and the valid operation of tree transformations within the binary search tree invariant, with detailed explanations of right and left rotations.', 'duration': 513.819, 'highlights': ['Balanced binary search trees are self-adjusting to maintain a logarithmic height, ensuring fast operations like insertion and deletion.', 'Worst case complexity of balanced binary search trees is logarithmic for all operations, making them very appealing compared to traditional binary search trees.', 'The significance of tree rotations is central to keeping balanced binary search trees balanced, with tree rotations being the main topic of discussion.', 'The operation of tree rotations is a valid transformation within the binary search tree invariant, as long as the binary search tree invariant remains satisfied.', 'Detailed explanations of right and left rotations are provided, emphasizing the importance of tree transformations and the adjustments required when a parent link is present.']}, {'end': 25302.514, 'start': 24997.182, 'title': 'Avl tree insertion', 'summary': 'Explains how to insert nodes into an avl tree, a type of balanced binary search tree, and the process of maintaining balance using tree rotations and balance factors.', 'duration': 305.332, 'highlights': ['An AVL tree allows for logarithmic insertion, deletion, and search operations.', 'The balance factor of a node is the difference between the height of the right subtree and the left subtree, and it must be maintained at minus one, zero, or plus one to keep the AVL tree balanced.', 'The process of maintaining balance in AVL trees involves four distinct cases of tree rotations: left heavy, left right, right right, and right left.']}], 'duration': 820.092, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM24482422.jpg', 'highlights': ['Balanced binary search trees maintain logarithmic height for fast operations', 'Worst case complexity of balanced binary search trees is logarithmic for all operations', 'Tree rotations are central to keeping balanced binary search trees balanced', 'AVL tree allows for logarithmic insertion, deletion, and search operations', 'The balance factor of a node must be maintained at minus one, zero, or plus one in AVL tree', 'Detailed explanations of right and left rotations are provided']}, {'end': 27032.178, 'segs': [{'end': 25330.362, 'src': 'embed', 'start': 25304.58, 'weight': 2, 'content': [{'end': 25312.766, 'text': "Next, I want to show you some pseudocode for inserting nodes into an AVL tree because it's not all that obvious or easy.", 'start': 25304.58, 'duration': 8.186}, {'end': 25319.771, 'text': 'This first method is the public facing method for the insert method, which returns true or false,', 'start': 25313.406, 'duration': 6.365}, {'end': 25324.214, 'text': 'depending on whether the value was successfully inserted or not.', 'start': 25319.771, 'duration': 4.443}, {'end': 25330.362, 'text': "For simplicity, we're going to ban duplicate values in our AFL tree.", 'start': 25325.1, 'duration': 5.262}], 'summary': 'Pseudocode for inserting nodes into an avl tree with ban on duplicate values.', 'duration': 25.782, 'max_score': 25304.58, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM25304580.jpg'}, {'end': 25394.882, 'src': 'embed', 'start': 25353.914, 'weight': 1, 'content': [{'end': 25360.078, 'text': 'If we hit the base case a null node, we simply return a new instance of the node with a value we want to insert.', 'start': 25353.914, 'duration': 6.164}, {'end': 25370.086, 'text': "Otherwise we get the comparator value with the value we're trying to insert against the current node to determine if we should go on the left or the right subtree.", 'start': 25361.119, 'duration': 8.967}, {'end': 25379.034, 'text': 'After that, on the recursive callback, we call the update method which updates the balance factor and height values for this node.', 'start': 25370.927, 'duration': 8.107}, {'end': 25383.316, 'text': 'And lastly, we rebalance the tree with a balance method.', 'start': 25379.634, 'duration': 3.682}, {'end': 25389.219, 'text': "Now let's take a look at the update and balance method and what they're actually doing.", 'start': 25384.016, 'duration': 5.203}, {'end': 25394.882, 'text': 'The update method updates the balance factor and height values of our node.', 'start': 25390.26, 'duration': 4.622}], 'summary': 'Updating balance factor and height values for binary tree nodes', 'duration': 40.968, 'max_score': 25353.914, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM25353914.jpg'}, {'end': 25584.78, 'src': 'embed', 'start': 25560.353, 'weight': 4, 'content': [{'end': 25570.415, 'text': "we're going to actually be looking at how to remove elements from a binary search tree and at the very end argument that algorithm for AVL trees specifically.", 'start': 25560.353, 'duration': 10.062}, {'end': 25571.515, 'text': "So let's get started.", 'start': 25570.795, 'duration': 0.72}, {'end': 25579.138, 'text': 'So just for review, I want to look at how to remove nodes in a binary search tree in detail.', 'start': 25572.595, 'duration': 6.543}, {'end': 25584.78, 'text': 'So we can generally break it up into two steps finding and replacing.', 'start': 25579.798, 'duration': 4.982}], 'summary': 'The transcript covers removing elements from a binary search tree and discussing the algorithm for avl trees.', 'duration': 24.427, 'max_score': 25560.353, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM25560353.jpg'}, {'end': 25749.623, 'src': 'embed', 'start': 25720.467, 'weight': 0, 'content': [{'end': 25724.749, 'text': "And when we're looking for successor node, one of four cases will happen.", 'start': 25720.467, 'duration': 4.282}, {'end': 25729.732, 'text': 'Either were a leaf node, in which case there are no sub trees.', 'start': 25725.39, 'duration': 4.342}, {'end': 25732.533, 'text': 'the node to remove has no left sub tree.', 'start': 25729.732, 'duration': 2.801}, {'end': 25739.437, 'text': 'the node to remove has no right sub tree, or the node to remove has both a left sub tree and a right sub tree.', 'start': 25732.533, 'duration': 6.904}, {'end': 25741.918, 'text': "we'll see how to handle all these cases.", 'start': 25740.037, 'duration': 1.881}, {'end': 25749.623, 'text': 'In the first case, where the node to remove is a leaf node, we can simply remove it without any side effects.', 'start': 25742.559, 'duration': 7.064}], 'summary': 'Handling different cases for removing a node in a tree structure.', 'duration': 29.156, 'max_score': 25720.467, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM25720467.jpg'}, {'end': 26050.887, 'src': 'embed', 'start': 25999.682, 'weight': 5, 'content': [{'end': 26011.127, 'text': 'So we we stage the removal and get ready to remove 11 that we remove 11 and then hook 14 back up to 18.', 'start': 25999.682, 'duration': 11.445}, {'end': 26015.869, 'text': 'And if we rebalance the tree, then we can see that the duplicate 11 value is gone.', 'start': 26011.127, 'duration': 4.742}, {'end': 26019.421, 'text': "All right the moment we've been waiting for.", 'start': 26017.398, 'duration': 2.023}, {'end': 26024.648, 'text': 'how do we augment the binary citri removal algorithm for AVL trees?', 'start': 26019.421, 'duration': 5.227}, {'end': 26034, 'text': 'the solution is simple you only need to add two lines of code to ensure that the tree remains balanced and that the balance factor and height values remain up to date.', 'start': 26024.648, 'duration': 9.352}, {'end': 26041.063, 'text': 'On the recursive callback, you invoke the update and balance methods you saw in the insert video,', 'start': 26034.941, 'duration': 6.122}, {'end': 26049.346, 'text': 'which ensure that when the node is removed from the AVL tree, that the tree remains balanced.', 'start': 26041.063, 'duration': 8.283}, {'end': 26050.887, 'text': "it's as easy as that.", 'start': 26049.346, 'duration': 1.541}], 'summary': 'Avl tree removal algorithm maintains balance with two lines of code.', 'duration': 51.205, 'max_score': 25999.682, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM25999682.jpg'}, {'end': 26167.109, 'src': 'embed', 'start': 26139.867, 'weight': 11, 'content': [{'end': 26148.334, 'text': 'Here we are in the source code of a recursive AVL tree implementation and the Java programming language.', 'start': 26139.867, 'duration': 8.467}, {'end': 26150.055, 'text': "So let's get started.", 'start': 26149.115, 'duration': 0.94}, {'end': 26165.648, 'text': 'If you look at the class definition for the AVL tree, you will notice that this class takes a generic type argument, which is of type T,', 'start': 26150.416, 'duration': 15.232}, {'end': 26167.109, 'text': 'which extends a comparable.', 'start': 26165.648, 'duration': 1.461}], 'summary': 'Recursive avl tree implementation in java with generic type argument t extending comparable.', 'duration': 27.242, 'max_score': 26139.867, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM26139867.jpg'}, {'end': 26281.421, 'src': 'embed', 'start': 26231.713, 'weight': 6, 'content': [{'end': 26239.396, 'text': 'And notice that this, this node class implements the tree printer printable node interface.', 'start': 26231.713, 'duration': 7.683}, {'end': 26248.62, 'text': "And that's just an interface I have somewhere in this folder that allows me to display the tree I did on the terminal.", 'start': 26240.076, 'duration': 8.544}, {'end': 26253.102, 'text': "So this isn't quite a requirement if you're actually building an AVL tree.", 'start': 26249, 'duration': 4.102}, {'end': 26261.868, 'text': 'And nor are these overrides, those are also for being able to display the tree in the terminal, which is really handy for debugging, actually.', 'start': 26253.702, 'duration': 8.166}, {'end': 26278.859, 'text': "Alright, so instance variables at the AVL tree class level, we have the root node, this should really be private, although I'm using it for testing.", 'start': 26264.409, 'duration': 14.45}, {'end': 26281.421, 'text': "So I'm leaving it package private.", 'start': 26279.059, 'duration': 2.362}], 'summary': 'The avl tree class implements interfaces for tree printing and debugging.', 'duration': 49.708, 'max_score': 26231.713, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM26231713.jpg'}, {'end': 26343.809, 'src': 'embed', 'start': 26312.049, 'weight': 8, 'content': [{'end': 26316.07, 'text': 'This the display method I call to actually print the tree in a terminal.', 'start': 26312.049, 'duration': 4.021}, {'end': 26324.413, 'text': 'This contains method to check if a certain value already exists inside the tree.', 'start': 26318.091, 'duration': 6.322}, {'end': 26334.357, 'text': 'So this the public facing method, which calls the private method, and I give it the root as the initial node to start off with.', 'start': 26325.034, 'duration': 9.323}, {'end': 26343.809, 'text': 'So to check if a node exists inside a tree, if we hit the base case, then we know that that value does not exist.', 'start': 26335.805, 'duration': 8.004}], 'summary': 'The method displays and checks for existing values in a tree.', 'duration': 31.76, 'max_score': 26312.049, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM26312049.jpg'}, {'end': 26461.399, 'src': 'embed', 'start': 26430.413, 'weight': 9, 'content': [{'end': 26439.457, 'text': 'So if we reach the base case, meaning we traverse all the way down our tree and the value of node is null,', 'start': 26430.413, 'duration': 9.044}, {'end': 26444.019, 'text': 'then we know this is the position where we need to insert that new node.', 'start': 26439.457, 'duration': 4.562}, {'end': 26447.2, 'text': 'So create a new node and give it the value.', 'start': 26444.239, 'duration': 2.961}, {'end': 26451.951, 'text': "Otherwise, we're searching for the insertion position.", 'start': 26449.001, 'duration': 2.95}, {'end': 26455.734, 'text': 'So again, invoke the comparator function.', 'start': 26452.892, 'duration': 2.842}, {'end': 26461.399, 'text': 'Then do value dot compare to no dot value.', 'start': 26458.216, 'duration': 3.183}], 'summary': 'Traverse tree to find insertion position for new node.', 'duration': 30.986, 'max_score': 26430.413, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM26430413.jpg'}], 'start': 25304.58, 'title': 'Avl tree operations', 'summary': 'Covers avl tree insertion pseudocode, removal and source code, implementation, update, and remove methods, aiming to ensure successful operations and efficient manipulation, including insights into source code and handling of duplicate values.', 'chapters': [{'end': 25370.086, 'start': 25304.58, 'title': 'Avl tree insertion pseudocode', 'summary': 'Explains the pseudocode for inserting nodes into an avl tree, including the public and private methods, and the handling of duplicate values, aiming to ensure successful insertion and ban duplicate values in the avl tree.', 'duration': 65.506, 'highlights': ['The public facing method for the insert method in AVL tree returns true or false, based on the successful insertion of a value.', 'The private recursive insert method handles the base case of a null node by returning a new instance of the node with the value to insert.', 'Duplicate values are banned in the AVL tree to ensure uniqueness and maintain the structure of the tree.']}, {'end': 26230.947, 'start': 25370.927, 'title': 'Avl tree removal and source code', 'summary': 'Explains the update and balance methods for avl tree, the process of removing elements from an avl tree, including finding and replacing nodes, and the augmentation of the binary search tree removal algorithm for avl trees. it also provides insights into the source code of a recursive avl tree implementation in java, emphasizing the use of generic type arguments and the structure of the node subclass.', 'duration': 860.02, 'highlights': ['The chapter explains the update and balance methods for AVL tree', 'The process of removing elements from an AVL tree, including finding and replacing nodes', 'Augmentation of the binary search tree removal algorithm for AVL trees', 'Insights into the source code of a recursive AVL tree implementation in Java']}, {'end': 26484.595, 'start': 26231.713, 'title': 'Avl tree implementation', 'summary': 'Explains the implementation of an avl tree, including the structure, methods for insertion and display, and the use of interfaces for tree printing and debugging.', 'duration': 252.882, 'highlights': ['The node class implements the tree printer printable node interface, allowing the display of the tree on the terminal, which is useful for debugging.', "The AVL tree class includes instance variables for the root node and node count, used for testing and tracking the tree's size.", "The public facing method contains the logic to check if a certain value exists inside the tree, utilizing comparison to determine the node's position.", 'The private insert method handles the insertion of a new node, using comparator function to determine the insertion position within the tree.']}, {'end': 27032.178, 'start': 26485.336, 'title': 'Avl tree update and remove methods', 'summary': 'Covers the implementation of the update and remove methods in an avl tree, detailing the process of updating the balance factor and height of a node, rebalancing the tree, and efficiently removing nodes based on various cases.', 'duration': 546.842, 'highlights': ['The update method recalculates the height and balance factor of a node by considering the heights of the left and right subtrees, and then invokes the balance method to ensure the tree remains balanced if necessary.', 'The remove method efficiently handles the removal of nodes by considering cases where the node has no children, one child, or two children, and employs a heuristic to determine which subtree to remove nodes from.', 'The chapter emphasizes the importance of calling the update and rebalance methods to maintain a balanced AVL tree structure even after node removal, ensuring the integrity of the tree is preserved.']}], 'duration': 1727.598, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM25304580.jpg', 'highlights': ['The remove method efficiently handles the removal of nodes by considering cases where the node has no children, one child, or two children, and employs a heuristic to determine which subtree to remove nodes from.', 'The update method recalculates the height and balance factor of a node by considering the heights of the left and right subtrees, and then invokes the balance method to ensure the tree remains balanced if necessary.', 'The public facing method for the insert method in AVL tree returns true or false, based on the successful insertion of a value.', 'The private recursive insert method handles the base case of a null node by returning a new instance of the node with the value to insert.', 'The process of removing elements from an AVL tree, including finding and replacing nodes', 'The chapter emphasizes the importance of calling the update and rebalance methods to maintain a balanced AVL tree structure even after node removal, ensuring the integrity of the tree is preserved.', 'The node class implements the tree printer printable node interface, allowing the display of the tree on the terminal, which is useful for debugging.', "The AVL tree class includes instance variables for the root node and node count, used for testing and tracking the tree's size.", "The public facing method contains the logic to check if a certain value exists inside the tree, utilizing comparison to determine the node's position.", 'The private insert method handles the insertion of a new node, using comparator function to determine the insertion position within the tree.', 'Duplicate values are banned in the AVL tree to ensure uniqueness and maintain the structure of the tree.', 'Insights into the source code of a recursive AVL tree implementation in Java', 'Augmentation of the binary search tree removal algorithm for AVL trees']}, {'end': 28990.735, 'segs': [{'end': 27132.631, 'src': 'embed', 'start': 27082.099, 'weight': 0, 'content': [{'end': 27085.22, 'text': 'So what exactly is an indexed priority queue??', 'start': 27082.099, 'duration': 3.121}, {'end': 27092.501, 'text': "Well, it's a traditional priority queue variant which, on top of having all the regular priority queue operations,", 'start': 27085.82, 'duration': 6.681}, {'end': 27096.642, 'text': 'also supports quick updates and deletions of key value pairs.', 'start': 27092.501, 'duration': 4.141}, {'end': 27107.444, 'text': 'One of the big problems that the index priority queue solves is being able to quickly look up and dynamically change the values in your priority queue on the fly,', 'start': 27097.422, 'duration': 10.022}, {'end': 27109.104, 'text': 'which is often very useful.', 'start': 27107.444, 'duration': 1.66}, {'end': 27111.499, 'text': "Let's look at an example.", 'start': 27110.478, 'duration': 1.021}, {'end': 27118.323, 'text': 'Suppose a hospital has a waiting room with n people, which need different levels of attention.', 'start': 27112.079, 'duration': 6.244}, {'end': 27123.145, 'text': 'Each person in the waiting room has a certain condition that needs to be dealt with.', 'start': 27119.483, 'duration': 3.662}, {'end': 27127.808, 'text': 'For instance, Mary is in labor, so she has a priority of 9.', 'start': 27123.806, 'duration': 4.002}, {'end': 27129.069, 'text': 'Akarsh has a paper cut.', 'start': 27127.808, 'duration': 1.261}, {'end': 27131.07, 'text': 'He has a priority of 1.', 'start': 27129.289, 'duration': 1.781}, {'end': 27132.631, 'text': 'James has an arrow in his leg.', 'start': 27131.07, 'duration': 1.561}], 'summary': 'An indexed priority queue allows quick updates and deletions of key value pairs, solving the problem of quickly looking up and dynamically changing values in a priority queue.', 'duration': 50.532, 'max_score': 27082.099, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM27082099.jpg'}, {'end': 27236.884, 'src': 'embed', 'start': 27210.449, 'weight': 4, 'content': [{'end': 27214.731, 'text': 'The index priority queue is a data structure which lets us do this efficiently.', 'start': 27210.449, 'duration': 4.282}, {'end': 27224.216, 'text': 'The first step to using an index priority queue is to assign index values to all the keys, thus forming a bidirectional mapping.', 'start': 27215.551, 'duration': 8.665}, {'end': 27229.859, 'text': 'If we use an index priority queue to track who should get served next in our hospital,', 'start': 27224.716, 'duration': 5.143}, {'end': 27236.884, 'text': 'we need to assign each person a unique key index value between 0 and n.', 'start': 27229.859, 'duration': 7.025}], 'summary': 'Index priority queue efficiently assigns unique key index values to track serving order.', 'duration': 26.435, 'max_score': 27210.449, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM27210449.jpg'}, {'end': 28021.129, 'src': 'embed', 'start': 27993.316, 'weight': 2, 'content': [{'end': 28000.678, 'text': 'Then I update the position map and the inverse map to reflect the fact that a new key value pair has been inserted into the priority queue.', 'start': 27993.316, 'duration': 7.362}, {'end': 28007.08, 'text': 'Finally, I move the node up the heap until the heap invariant is satisfied.', 'start': 28001.358, 'duration': 5.722}, {'end': 28012.462, 'text': "Let's take a closer look at this swim method to see how that happens.", 'start': 28007.34, 'duration': 5.122}, {'end': 28015.684, 'text': 'Here we are looking at the swim method.', 'start': 28013.742, 'duration': 1.942}, {'end': 28021.129, 'text': "you'll notice that it has two supporting functions swap and less.", 'start': 28015.684, 'duration': 5.445}], 'summary': 'Method updates position map and inverse map for new insertion, then moves node up the heap.', 'duration': 27.813, 'max_score': 27993.316, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM27993316.jpg'}, {'end': 28134.804, 'src': 'embed', 'start': 28109.532, 'weight': 3, 'content': [{'end': 28116.577, 'text': 'So we can do a straightforward swap by indexing into the inverse map to find the key index values and swap indices i and j.', 'start': 28109.532, 'duration': 7.045}, {'end': 28123.548, 'text': 'Followed by this simply update the key index values associated with nodes i and j in the inverse map.', 'start': 28117.719, 'duration': 5.829}, {'end': 28127.295, 'text': 'To do this, this is just a simple straightforward exchange.', 'start': 28123.709, 'duration': 3.586}, {'end': 28134.804, 'text': 'Next up, I want to talk about polling and removing elements from an indexed priority queue.', 'start': 28128.82, 'duration': 5.984}], 'summary': 'Swapping key index values using inverse map for nodes i and j, followed by updating those values. also discusses polling and removing elements from an indexed priority queue.', 'duration': 25.272, 'max_score': 28109.532, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM28109532.jpg'}], 'start': 27032.718, 'title': 'Indexed priority queue data structures', 'summary': 'Introduces indexed priority queue data structures for quick updates and deletions, discusses dynamic priority queues with examples, explains implementation with a binary heap, and covers operations and java implementation.', 'chapters': [{'end': 27107.444, 'start': 27032.718, 'title': 'Indexed priority queue data structure', 'summary': 'Introduces the indexed priority queue data structure, which provides quick updates and deletions of key value pairs, solving the problem of quickly looking up and dynamically changing values in a priority queue.', 'duration': 74.726, 'highlights': ['Indexed priority queue allows quick updates and deletions of key value pairs', 'Solves the problem of quickly looking up and dynamically changing values in a priority queue', 'Introduction to indexed priority queue as a useful data structure']}, {'end': 27450.697, 'start': 27107.444, 'title': 'Dynamic priority queue with indexing', 'summary': 'Discusses the concept of a dynamic priority queue with examples from a hospital setting, emphasizing the need for dynamically updating priorities and the implementation of an index priority queue with efficient operations, achieving constant or logarithmic time complexities.', 'duration': 343.253, 'highlights': ['The hospital example illustrates the need for dynamically updating priorities based on changing conditions, where patients with higher priority are served first, and the index priority queue efficiently facilitates this dynamic updating.', 'The index priority queue is a data structure that efficiently facilitates dynamically updating priorities, with operations such as deleting keys, checking key existence, and specialized update operations with constant or logarithmic time complexities.', 'The implementation of the index priority queue involves assigning index values to keys, forming a bidirectional mapping, and supporting various operations, such as getting the smallest value, inserting and updating key value pairs, and specialized update operations.']}, {'end': 27992.715, 'start': 27451.604, 'title': 'Implementing indexed priority queue with binary heap', 'summary': 'Explains the insertion and removal process in a traditional priority queue and the implementation of an indexed priority queue with a binary heap, highlighting the steps and data structures involved, such as swapping nodes, searching, creating a min indexed priority queue, and maintaining position maps and inverse maps.', 'duration': 541.111, 'highlights': ['The process of inserting a new value into the priority queue involves assigning a unique key index value, inserting the new value at the insertion position, and then bubbling up the value until the heap invariant is satisfied.', 'The removal process in a traditional priority queue requires searching for the element, swapping it with the last node, performing the removal, and then bubbling up or down the swapped value.', 'Creating a min indexed priority queue involves assigning each person a unique index value between zero and n non-inclusive and giving each person an initial value to place inside the index priority queue.', 'To access the value for a given key in the index priority queue, one needs to find its key index and then perform a lookup in the values array maintained by the index priority queue.', 'Maintaining a position map allows for determining the index of a node in the heap for any given key index.', 'The process of inserting a new key value pair in the index priority queue includes assigning a unique key index value, inserting the new key value pair at the insertion position, and then updating the position map and the inverse map.']}, {'end': 28508.958, 'start': 27993.316, 'title': 'Indexed priority queue operations', 'summary': 'Covers the swim and poll methods, which allow for inserting and removing elements from the indexed priority queue in logarithmic time. it also explains the swap function and the process for updating key value pairs in the min index binary heap.', 'duration': 515.642, 'highlights': ['The swim method facilitates inserting elements into the priority queue by moving the node up the heap until the heap invariant is satisfied, allowing for a logarithmic operation for adding elements.', 'The process of polling and removing elements from the indexed priority queue is explained, demonstrating how polling is a logarithmic operation, while removal is improved from linear to logarithmic time complexity.', "The sync method is described as a process for selecting the child with the smallest value and defaulting to the left child if there's a tie, providing insight into the updating process of the min index binary heap.", 'The chapter covers the increase and decrease key operations, which are convenience methods for updating a value associated with a key, providing a more restrictive form of update operation.']}, {'end': 28990.735, 'start': 28509.838, 'title': 'Indexed priority queue in java', 'summary': 'Discusses the implementation of a min indexed binary heap in java, covering key concepts like the structure, methods such as insert, delete, update, and the underlying logic of sinking and swimming nodes within the heap.', 'duration': 480.897, 'highlights': ['The chapter discusses the implementation of a min indexed binary heap in Java', 'Methods such as insert, delete, update are covered', 'The underlying logic of sinking and swimming nodes within the heap is explained']}], 'duration': 1958.017, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/RBSGKlAvoiM/pics/RBSGKlAvoiM27032718.jpg', 'highlights': ['Indexed priority queue allows quick updates and deletions of key value pairs', 'The hospital example illustrates the need for dynamically updating priorities based on changing conditions', 'The swim method facilitates inserting elements into the priority queue by moving the node up the heap', 'The process of polling and removing elements from the indexed priority queue is explained', 'The implementation of the index priority queue involves assigning index values to keys']}], 'highlights': ['Data structures are crucial for efficient algorithms and product excellence', 'Understanding data structures is fundamental for efficient data management', 'Abstract data types provide only the interface for a data structure', 'Binary search algorithm has logarithmic time complexity', 'Big O notation standardizes time and space requirements for algorithms', 'Dynamic arrays can grow and shrink in size as needed', 'Linked lists are used in abstract data types and real-world object modeling', 'Stacks exhibit last in first out (LIFO) behavior', 'Priority queues are used in various algorithms and operations', 'Union find data structure has linear construction time and amortized constant time operations', 'Binary search trees have logarithmic time complexity for average case operations', 'Hash tables achieve constant time complexity for insertion, removal, and search on average', 'Fenwick trees enable constant time range queries and linear time construction', 'Suffix arrays and LCP arrays provide efficient substring and duplicate substring identification', 'Balanced binary search trees maintain logarithmic height for fast operations', 'AVL trees allow for logarithmic insertion, deletion, and search operations', 'Indexed priority queues allow quick updates and deletions of key value pairs']}