1 00:00:07,374 --> 00:00:11,044 Welcome, uh, to this, uh, cloud computing concepts course. 2 00:00:11,044 --> 00:00:14,247 In this, uh, lecture we'll be covering several, uh, concepts, 3 00:00:14,247 --> 00:00:19,018 uh, that are assumed as a part of, uh, the topics 4 00:00:19,018 --> 00:00:20,220 that we'll be discussing 5 00:00:20,220 --> 00:00:22,389 in the cloud computing concepts, uh, course. 6 00:00:23,656 --> 00:00:25,792 So, we'll be covering several of the basics, uh, 7 00:00:25,792 --> 00:00:28,128 they're considered to be basics in computer science. 8 00:00:28,128 --> 00:00:29,295 Uh, typically, 9 00:00:29,295 --> 00:00:31,564 some of these concepts, are concepts that, uh, 10 00:00:31,564 --> 00:00:33,933 computer science students learn in their first couple of years 11 00:00:33,933 --> 00:00:36,035 in, uh, a computer science degree, 12 00:00:36,035 --> 00:00:38,271 undergraduate degree program. 13 00:00:38,271 --> 00:00:39,072 So for those of you, 14 00:00:39,072 --> 00:00:41,207 who are already familiar with this material, 15 00:00:41,207 --> 00:00:44,043 uh, this could be a refresher or you could just, uh, skip it, 16 00:00:44,043 --> 00:00:46,479 if you already know, uh, this stuff. 17 00:00:46,479 --> 00:00:48,648 In any case, uh, you can always use this 18 00:00:48,648 --> 00:00:50,617 orientation lecture as a reference, 19 00:00:50,617 --> 00:00:54,954 uh, to keep coming back to if, you encounter a, uh, term in, 20 00:00:54,954 --> 00:00:57,957 uh, during the regular lectures that doesn't make sense to you, 21 00:00:57,957 --> 00:00:59,459 or that you'd like to be reminded about. 22 00:01:01,127 --> 00:01:02,529 So, we'll discuss a few topics. 23 00:01:02,529 --> 00:01:04,364 We'll discuss some basic data structures, 24 00:01:04,364 --> 00:01:06,065 uh, what processes are. 25 00:01:06,065 --> 00:01:08,468 We'll discuss a little bit about computer architecture, 26 00:01:08,468 --> 00:01:11,905 and then, um, a little bit of math with Big O notation, 27 00:01:11,905 --> 00:01:13,273 basic probability 28 00:01:13,273 --> 00:01:15,175 and a few other miscellaneous topics. 29 00:01:15,175 --> 00:01:16,009 So, let's get started here. 30 00:01:17,410 --> 00:01:18,778 So, bas-basic data structures, 31 00:01:18,778 --> 00:01:20,246 we'll discuss two di-different data structures. 32 00:01:20,246 --> 00:01:22,015 The first one is a queue. 33 00:01:22,015 --> 00:01:22,916 A queue, is essentially, 34 00:01:22,916 --> 00:01:25,385 a First-in First-out data structure. 35 00:01:25,385 --> 00:01:27,687 Elements of the queue could be, uh, any data types. 36 00:01:27,687 --> 00:01:31,157 In this example, here, I have elements that are in tiers. 37 00:01:31,157 --> 00:01:34,694 So, in this, uh, example right now, the queue has 5 elements, 38 00:01:34,694 --> 00:01:37,197 3, 5, 8, 0, 7. 39 00:01:37,197 --> 00:01:39,799 This is an ordered, list of elements. 40 00:01:39,799 --> 00:01:41,768 When you remove an element from the queue, 41 00:01:41,768 --> 00:01:43,503 you remove it from the head of the queue. 42 00:01:43,503 --> 00:01:46,406 In this case, the head is the element three. 43 00:01:46,406 --> 00:01:48,107 Uh, when you insert a new element, 44 00:01:48,107 --> 00:01:50,510 you insert it in the tail of the queue, which means that, 45 00:01:50,510 --> 00:01:52,212 if, I insert a new element, say one, 46 00:01:52,212 --> 00:01:54,914 it's going to get inserted right after seven in this queue. 47 00:01:56,316 --> 00:01:58,017 So removal always comes from the head, 48 00:01:58,017 --> 00:02:00,420 while insertion always happens at the tail. 49 00:02:00,420 --> 00:02:02,555 Uh, so, for instance, given this particular queue, 50 00:02:02,555 --> 00:02:04,557 consisting of five elements, if you-if you, 51 00:02:04,557 --> 00:02:07,961 dequeue or remove an item, uh, then that item will be three. 52 00:02:07,961 --> 00:02:09,863 At that point of time the queue will only consist 53 00:02:09,863 --> 00:02:13,733 of 5, 8, 0, and 7, with the head pointing to 5. 54 00:02:13,733 --> 00:02:16,803 The next item that you dequeue or remove will be five, okay? 55 00:02:16,803 --> 00:02:19,639 After that the queue will consist of only 8, 0, and 7. 56 00:02:19,639 --> 00:02:23,009 Then, uh, the next item that you dequeue will be eight, 57 00:02:23,009 --> 00:02:25,545 um, and so on and so forth. 58 00:02:25,545 --> 00:02:29,349 Uh, dequeues and, or removals, as well as, insertions, 59 00:02:29,349 --> 00:02:31,851 uh, can occur, uh, concurrently, so you can, 60 00:02:31,851 --> 00:02:33,286 uh, remove an element, 61 00:02:33,286 --> 00:02:35,088 but at the same time also insert an element at the tail. 62 00:02:36,990 --> 00:02:38,224 So, that's a queue, 63 00:02:38,224 --> 00:02:40,193 which is a First-in First-out data structure. 64 00:02:40,193 --> 00:02:42,095 A different data structure is the stack, 65 00:02:42,095 --> 00:02:44,664 which is the First-in Last-out data structure. 66 00:02:44,664 --> 00:02:47,100 Uh, imagine a stack of dishes that you, uh, 67 00:02:47,100 --> 00:02:48,201 place on your table. 68 00:02:48,201 --> 00:02:49,736 Uh, the dish that you put on the top, 69 00:02:49,736 --> 00:02:51,371 that you add the last, 70 00:02:51,371 --> 00:02:53,840 will be the first one that you can remove, right? 71 00:02:53,840 --> 00:02:55,475 And that's essentially a stack. 72 00:02:55,475 --> 00:02:58,912 So, uh, remove or also known, as a pop happens from the top. 73 00:02:58,912 --> 00:03:01,214 An insert or a push also happens at the top. 74 00:03:01,214 --> 00:03:05,318 Okay, so in this case, um, uh, if you, uh, push a new element 75 00:03:05,318 --> 00:03:08,655 into this particular stack, um, uh, say nine. 76 00:03:08,655 --> 00:03:10,456 The nine will go above three. 77 00:03:10,456 --> 00:03:12,659 After that, if you pop, or remove an element, 78 00:03:12,659 --> 00:03:14,294 that's going to be the last element that you added, 79 00:03:14,294 --> 00:03:15,762 which is nine, in this case. 80 00:03:15,762 --> 00:03:17,463 The next pop after that will get three, 81 00:03:17,463 --> 00:03:18,765 because nine was just removed. 82 00:03:18,765 --> 00:03:21,768 And three is now the top of the, uh, stack. 83 00:03:21,768 --> 00:03:23,069 Uh, after you've removed three, 84 00:03:23,069 --> 00:03:24,938 the next pop or removal will get you five, 85 00:03:24,938 --> 00:03:26,639 uh, and so on and so forth. 86 00:03:26,639 --> 00:03:28,541 After that you'll get 8 and then 0 and 7. 87 00:03:28,541 --> 00:03:31,444 Okay, so, once again, the removal always returns you 88 00:03:31,444 --> 00:03:33,146 the last item that was added. 89 00:03:33,146 --> 00:03:35,181 And, uh, insertion or push adds an item 90 00:03:35,181 --> 00:03:37,584 right to the top, of the stack. 91 00:03:37,584 --> 00:03:39,185 So these two data structures, queue and stack 92 00:03:39,185 --> 00:03:40,820 are used very widely in computer science 93 00:03:40,820 --> 00:03:44,424 and, um, in fact, we'll be using the notion of a stack, uh, 94 00:03:44,424 --> 00:03:47,927 right away when we'll discuss, uh, uh, processes, um, 95 00:03:47,927 --> 00:03:50,029 uh, soon in this particular orientation lecture, itself. 96 00:03:51,397 --> 00:03:54,701 So, speaking of processes, um, let's discuss a process next. 97 00:03:54,701 --> 00:03:58,571 Uh, a process is essentially a program in action. 98 00:03:58,571 --> 00:04:00,673 Uh, you may write a program in a language, 99 00:04:00,673 --> 00:04:03,476 programming language, such as, C or C++. 100 00:04:03,476 --> 00:04:05,445 And that's sh- an example is shown here. 101 00:04:05,445 --> 00:04:08,648 This example code, here, uh, consists of a main function, 102 00:04:08,648 --> 00:04:12,251 which, uh, calls a function, uh, called f1. 103 00:04:12,251 --> 00:04:14,253 F1 itself has a local integer variable x, 104 00:04:14,253 --> 00:04:17,624 and then, f1 itself calls a different function, f2. 105 00:04:18,625 --> 00:04:20,692 Okay, this is shown pictorially here, in the circle, 106 00:04:20,692 --> 00:04:23,596 where main calls f1 and f1 calls f2. 107 00:04:23,596 --> 00:04:24,964 'Kay, this is the code that you would write, 108 00:04:24,964 --> 00:04:26,499 and then, y'know, you would compile the code 109 00:04:26,499 --> 00:04:28,368 and then, uh, execute it. 110 00:04:28,368 --> 00:04:31,137 And when you're executing it, when your program is in action, 111 00:04:31,137 --> 00:04:33,139 that is a process. 112 00:04:33,139 --> 00:04:35,041 So, a process consists of your code, 113 00:04:35,041 --> 00:04:38,611 but also several other elements that, uh, help your code 114 00:04:38,611 --> 00:04:41,280 to execute on the computer, on which you are executing it. 115 00:04:41,280 --> 00:04:43,483 So, we are going to discuss some, uh, elements 116 00:04:43,483 --> 00:04:45,451 o-of a process which are critical. 117 00:04:46,319 --> 00:04:47,520 Here, are some of these elements. 118 00:04:47,520 --> 00:04:50,156 First, um, uh, let's look at the code. 119 00:04:50,156 --> 00:04:52,392 The code itself, uh, is, uh, static. 120 00:04:52,392 --> 00:04:54,894 Once you write the code, um, nothing changes it, 121 00:04:54,894 --> 00:04:57,664 uh, we are not considering the variable values 122 00:04:57,664 --> 00:04:59,032 to be a part of the code. 123 00:04:59,032 --> 00:05:00,433 I'll talk about that in a little bit. 124 00:05:00,433 --> 00:05:01,601 But the code itself, is static; 125 00:05:01,601 --> 00:05:04,037 it does not change once you write it. 126 00:05:04,037 --> 00:05:06,339 Uh, but, uh, there is a program counter, 127 00:05:06,339 --> 00:05:08,141 which is typically maintained by the computer 128 00:05:08,141 --> 00:05:10,943 on which you're running your, uh, process, uh, 129 00:05:10,943 --> 00:05:11,944 which points to 130 00:05:11,944 --> 00:05:14,113 which is the line number inside the code, 131 00:05:14,113 --> 00:05:16,215 where the program is currently executing, 132 00:05:16,215 --> 00:05:18,618 or rather where, the process is currently executing. 133 00:05:18,618 --> 00:05:21,020 'Kay, this is called a Program Counter, or the PC. 134 00:05:21,020 --> 00:05:22,055 Okay, this is a part, 135 00:05:22,055 --> 00:05:24,290 an important part of the process state. 136 00:05:24,290 --> 00:05:25,725 So, if you were to take a core dump, 137 00:05:25,725 --> 00:05:27,226 or stop the process right now, 138 00:05:27,226 --> 00:05:28,895 and take a snapshot of that process. 139 00:05:28,895 --> 00:05:31,164 That snapshot must include, the program counter, 140 00:05:31,164 --> 00:05:33,399 because it says, where in the code is, 141 00:05:33,399 --> 00:05:35,168 uh, the execution currently at. 142 00:05:36,769 --> 00:05:40,406 Next, uh, when, um, er-r, um, functions call each other, 143 00:05:40,406 --> 00:05:44,544 um, or in an object oriented, um, uh, program, 144 00:05:44,544 --> 00:05:47,213 uh, methods call each other, they use a stack. 145 00:05:47,213 --> 00:05:49,215 So every process contains, uh, a stack. 146 00:05:49,215 --> 00:05:51,884 Uh, more specifically, um, a proce- 147 00:05:51,884 --> 00:05:54,087 a process might contain multiple threads. 148 00:05:54,087 --> 00:05:56,222 Each thread will contain its own stack. 149 00:05:56,222 --> 00:05:57,090 But, let's just say 150 00:05:57,090 --> 00:05:58,691 there is one thread in this process. 151 00:05:58,691 --> 00:06:00,660 Uh, so, a process contains one stack, 152 00:06:00,660 --> 00:06:03,463 and this stack is used by these functions or methods, 153 00:06:03,463 --> 00:06:07,066 to pass arguments and return, uh, the result values. 154 00:06:07,066 --> 00:06:09,402 So, for instance, when main calls f1, 155 00:06:09,402 --> 00:06:13,339 main will push the arguments, uh, to f1, on top of the stack. 156 00:06:13,339 --> 00:06:15,141 When f1 starts executing 157 00:06:15,141 --> 00:06:16,409 it will pop, or remove, 158 00:06:16,409 --> 00:06:17,744 the elements from the top of the stack 159 00:06:17,744 --> 00:06:20,113 and use it to, uh, execute. 160 00:06:20,113 --> 00:06:23,516 Uh, similarly, uh, when f1 calls f2, 161 00:06:23,516 --> 00:06:28,354 um, f1 will push the arguments on top of the stack, for f2, 162 00:06:28,354 --> 00:06:31,390 and then f2 will, um, uh, pop them, execute, 163 00:06:31,390 --> 00:06:34,260 and then push the result values on top of the stack. 164 00:06:34,260 --> 00:06:36,162 The result values then popped by f1. 165 00:06:36,162 --> 00:06:39,132 This is the way in which f1 gets back the result, 166 00:06:39,132 --> 00:06:42,635 um, the final int return value from f2, to itself. 167 00:06:42,635 --> 00:06:46,506 And finally when f-f1 needs to return a resolved value to, 168 00:06:46,506 --> 00:06:48,775 uh, main, it pushes it on top of the stack 169 00:06:48,775 --> 00:06:51,010 when the execution returns to main, 170 00:06:51,010 --> 00:06:52,545 uh, main, uh, pops it 171 00:06:52,545 --> 00:06:54,347 or removes it from the top of the stack 172 00:06:54,347 --> 00:06:57,717 and main has the final return value from f1. 173 00:06:57,717 --> 00:06:59,018 'Kay, so, the stack 174 00:06:59,018 --> 00:07:00,720 is an important part of the process state as well, 175 00:07:00,720 --> 00:07:02,989 because it tells you where in the program execution 176 00:07:02,989 --> 00:07:05,091 you are, with respect to functions calling each other. 177 00:07:06,859 --> 00:07:08,094 Finally, uh, y'know, uh, 178 00:07:08,094 --> 00:07:09,729 functions have local variable, like x. 179 00:07:09,729 --> 00:07:12,031 There might also be global variables, um, 180 00:07:12,031 --> 00:07:13,933 uh, and of course in object oriented programs, 181 00:07:13,933 --> 00:07:15,434 you have, uh, objects, 182 00:07:15,434 --> 00:07:17,403 which store a lot of fields in them. 183 00:07:17,403 --> 00:07:19,071 A lot of these, uh, pieces of data, 184 00:07:19,071 --> 00:07:20,940 are stored in, what is known as a heap. 185 00:07:20,940 --> 00:07:23,442 Okay, so, uh, a heap is essentially a lot of data, 186 00:07:23,442 --> 00:07:26,312 uh, that was created by functions or methods, 187 00:07:26,312 --> 00:07:29,382 uh, or, uh, um, by objects, um. 188 00:07:29,382 --> 00:07:33,119 And it holds all of the data and, y'know, when an object, 189 00:07:33,119 --> 00:07:34,687 when a function's executing, 190 00:07:34,687 --> 00:07:36,322 uh, say f1 is executing, 191 00:07:36,322 --> 00:07:39,158 uh, the object x might be created inside the heap, 192 00:07:39,158 --> 00:07:40,326 when f1 is done executing. 193 00:07:40,326 --> 00:07:43,930 X, uh, the object of x will be removed from the heap. 194 00:07:43,930 --> 00:07:45,398 Similarly, there're also registers, 195 00:07:45,398 --> 00:07:46,632 and I'll talk more about registers 196 00:07:46,632 --> 00:07:48,201 when we discuss computer architecture, 197 00:07:48,201 --> 00:07:49,869 but registers hold some of the, uh, recent values 198 00:07:49,869 --> 00:07:52,805 that have been accessed, uh, by the process, 199 00:07:52,805 --> 00:07:53,472 p1, in this case. 200 00:07:55,441 --> 00:07:57,310 Okay, uh, speaking of computer architecture. 201 00:07:57,310 --> 00:07:58,511 Let's discuss a simplified version 202 00:07:58,511 --> 00:07:59,846 of computer architecture. 203 00:07:59,846 --> 00:08:02,615 Computer architectures today, uh, can be very complicated. 204 00:08:02,615 --> 00:08:04,517 But, um, typically when we ta- 205 00:08:04,517 --> 00:08:06,786 when we think of how a process executes, 206 00:08:06,786 --> 00:08:08,487 in a computer architecture, 207 00:08:08,487 --> 00:08:10,022 we can think of a simplified view. 208 00:08:10,022 --> 00:08:11,023 So there is a CPU, 209 00:08:11,023 --> 00:08:12,625 which executes the action instructions, 210 00:08:12,625 --> 00:08:14,794 which are present in your, uh, code. 211 00:08:14,794 --> 00:08:16,162 There're also a bunch of registers, 212 00:08:16,162 --> 00:08:18,064 that are co-located, uh, with the CPU. 213 00:08:18,064 --> 00:08:20,199 These are, uh, small pieces of memory, 214 00:08:20,199 --> 00:08:22,835 that can be accessed very quickly by the CPU. 215 00:08:22,835 --> 00:08:25,471 Typically, uh, there's only a small number of registers. 216 00:08:25,471 --> 00:08:27,773 Typically, not more than a few tens of registers. 217 00:08:27,773 --> 00:08:29,308 Uh, there's also a cache, 218 00:08:29,308 --> 00:08:31,043 which is, a slightly larger memory 219 00:08:31,043 --> 00:08:32,678 than the collection of registers. 220 00:08:32,678 --> 00:08:34,746 And the larger a map piece of memory is, 221 00:08:34,746 --> 00:08:36,482 uh, the slower it is to access it. 222 00:08:36,482 --> 00:08:38,717 So accessing a cache is slower than registers, 223 00:08:38,717 --> 00:08:40,318 uh, than accessing registers. 224 00:08:40,318 --> 00:08:43,389 But accessing a cache is still pretty fast. 225 00:08:43,389 --> 00:08:45,524 Uh, then beyond the cache there is the main memory, 226 00:08:45,524 --> 00:08:47,960 or the Random Access Memory, or the RAM. 227 00:08:47,960 --> 00:08:49,829 Uh, which is even larger than the cache, 228 00:08:49,829 --> 00:08:51,664 uh, and the ca- the memory itself, 229 00:08:51,664 --> 00:08:53,232 therefore, is slower than the cache, 230 00:08:53,232 --> 00:08:54,700 but still, it's pretty fast. 231 00:08:54,700 --> 00:08:56,002 And then finally, there's hard disk, 232 00:08:56,002 --> 00:08:58,738 or if you would like, a solid stave-state drive, 233 00:08:58,738 --> 00:09:00,406 a flash, uh, drive, or whatever, 234 00:09:00,406 --> 00:09:03,376 which is, a lot more memory than, uh, the main memory, 235 00:09:03,376 --> 00:09:05,378 uh, but of course, it's much slower. 236 00:09:05,378 --> 00:09:08,547 So, as you go up from disk, to memory, to cache, registers, 237 00:09:08,547 --> 00:09:09,749 the speed increases, 238 00:09:09,749 --> 00:09:11,384 the total amount of, uh, storage space 239 00:09:11,384 --> 00:09:12,418 that you have, decreases. 240 00:09:14,687 --> 00:09:15,788 So, when you write a program, 241 00:09:15,788 --> 00:09:19,025 such as, C++, or Java, or C, and you compile it, 242 00:09:19,025 --> 00:09:21,560 it gets compiled to low level machine instructions. 243 00:09:21,560 --> 00:09:22,628 These machine instructions, 244 00:09:22,628 --> 00:09:24,630 uh, might be specific to the architecture, 245 00:09:24,630 --> 00:09:25,898 the machine on which you are running, 246 00:09:25,898 --> 00:09:27,633 or it might be a, um, 247 00:09:27,633 --> 00:09:30,670 ah, virtual machine, like a JVM, kind of, um, code. 248 00:09:30,670 --> 00:09:33,039 In any case, uh, these low level machine instructions 249 00:09:33,039 --> 00:09:35,808 are the executable version of your, uh, program, 250 00:09:35,808 --> 00:09:38,778 and this is stored in file system, um, uh, 251 00:09:38,778 --> 00:09:41,280 in the file system on- on your disk. 252 00:09:41,280 --> 00:09:42,648 When your program starts executing, 253 00:09:42,648 --> 00:09:44,116 when it becomes a process, 254 00:09:44,116 --> 00:09:46,852 uh, the CPU loads instructions in batches, 255 00:09:46,852 --> 00:09:48,821 or, m-, in a simplifi- more simplified way, 256 00:09:48,821 --> 00:09:51,457 it loads instructions one by one. 257 00:09:51,457 --> 00:09:52,959 Uh, it loads them into memory, 258 00:09:52,959 --> 00:09:55,261 and then into cache, and into registers. 259 00:09:55,261 --> 00:09:57,163 Typically, the cache and the registers contain 260 00:09:57,163 --> 00:09:59,398 the last few accessed instructions. 261 00:09:59,398 --> 00:10:01,600 Um, so they are, uhm, 262 00:10:01,600 --> 00:10:02,568 they follow what is known as, 263 00:10:02,568 --> 00:10:04,937 the least recently used principle. 264 00:10:04,937 --> 00:10:07,673 Now, as it executes y- each instruction, the CPU, 265 00:10:07,673 --> 00:10:09,842 which is executing the process, loads the data, 266 00:10:09,842 --> 00:10:11,610 that is necessary for the instruction, 267 00:10:11,610 --> 00:10:13,312 into the memory and then if necessary 268 00:10:13,312 --> 00:10:15,348 into the cache and the registers. 269 00:10:15,348 --> 00:10:18,217 Um, and if there are any necessary, uh, changes 270 00:10:18,217 --> 00:10:20,019 that happen to a variable like, x, 271 00:10:20,019 --> 00:10:23,356 then, these are stored into a memory, um, um, 272 00:10:23,356 --> 00:10:25,191 uh, first into cache and then into memory. 273 00:10:26,692 --> 00:10:28,761 Once in a while, you may need to store something on disks, 274 00:10:28,761 --> 00:10:31,530 so that you have, um, a permanent storage. 275 00:10:31,530 --> 00:10:33,499 So in case, the process goes offline, 276 00:10:33,499 --> 00:10:35,501 then you still have some data. 277 00:10:35,501 --> 00:10:37,403 Say for instance, the program might open a file 278 00:10:37,403 --> 00:10:38,571 and write something into the file. 279 00:10:38,571 --> 00:10:40,773 So, in this case, uh, you may want to write those, 280 00:10:40,773 --> 00:10:42,508 uh, updates to the file onto the disk. 281 00:10:43,509 --> 00:10:45,311 Now, of course this is a very highly simplified picture. 282 00:10:45,311 --> 00:10:46,946 Computer architectures can be far more, 283 00:10:46,946 --> 00:10:48,914 uh, complex than this, today, 284 00:10:48,914 --> 00:10:52,251 but for our practical purposes, in this course, and as far as, 285 00:10:52,251 --> 00:10:55,955 uh, explaining how processes work, um, this will suffice. 286 00:10:58,758 --> 00:11:00,593 So next, we move on to a few mathematical topics. 287 00:11:00,593 --> 00:11:03,429 The first mathematical topic is, a Big O notation. 288 00:11:03,429 --> 00:11:04,363 A Big O notation is, 289 00:11:04,363 --> 00:11:06,465 one of the most basic ways of analyzing algorithms. 290 00:11:06,465 --> 00:11:07,600 When I give you an algorithm, 291 00:11:07,600 --> 00:11:10,002 and I say analyze the algorithm mathematically, 292 00:11:10,002 --> 00:11:12,471 essentially, I expect you to, uh, come up with, 293 00:11:12,471 --> 00:11:14,440 at least a Big O notation, 294 00:11:14,440 --> 00:11:17,109 uh, and an analysis of that algorithm. 295 00:11:17,109 --> 00:11:18,044 The-the Big O notation, 296 00:11:18,044 --> 00:11:20,646 describes an upper bound in the behavior of an algorithm. 297 00:11:20,646 --> 00:11:23,315 Um, as some variable is scaled 298 00:11:23,315 --> 00:11:25,885 or increased in value all the way to infinity. 299 00:11:25,885 --> 00:11:28,888 Typically, this variable is a size of the input. 300 00:11:28,888 --> 00:11:30,823 Um, maybe the number of input elements, 301 00:11:30,823 --> 00:11:33,159 um, you'll see-sa-you'll see a few examples of this. 302 00:11:34,393 --> 00:11:38,197 So, essentially, this, uhh-oah, Big O analysis tells us, 303 00:11:38,197 --> 00:11:40,199 how does the, uh, algorithm itself 304 00:11:40,199 --> 00:11:43,769 scale as the size of the input is increased? 305 00:11:43,769 --> 00:11:45,638 Um, this analyzes the run time, 306 00:11:45,638 --> 00:11:47,573 or typically, another performance metric, as well. 307 00:11:47,573 --> 00:11:49,041 Most of the time, we analyze run time, 308 00:11:49,041 --> 00:11:50,543 sometimes, as you'll see in the course, 309 00:11:50,543 --> 00:11:52,845 we'll analyze things like number of messages, 310 00:11:52,845 --> 00:11:55,781 um, uh, even, uh, bandwidth, um, 311 00:11:55,781 --> 00:11:59,185 uh, that is exchanged i-in the total network itself. 312 00:11:59,185 --> 00:12:00,619 The important thing about Big O notation is that, 313 00:12:00,619 --> 00:12:03,122 i-it captures worst case performance. 314 00:12:03,122 --> 00:12:04,890 Okay, so this is not expected performance 315 00:12:04,890 --> 00:12:06,258 or best case performance. 316 00:12:06,258 --> 00:12:07,960 Big O is worst case performance. 317 00:12:07,960 --> 00:12:09,028 Given this algorithm, 318 00:12:09,028 --> 00:12:11,630 what is the worst that it can do in terms of, uh, 319 00:12:11,630 --> 00:12:13,099 this performance metric that we're measuring? 320 00:12:15,301 --> 00:12:18,737 So, essentially, when I say, an algorithm A is order of foo, 321 00:12:18,737 --> 00:12:19,438 this means that, 322 00:12:19,438 --> 00:12:23,642 Algorithm A takes < c foo time to complete, 323 00:12:23,642 --> 00:12:25,444 assuming time is the metric we are measuring, 324 00:12:25,444 --> 00:12:27,980 for some constant c, a fixed constant c, 325 00:12:27,980 --> 00:12:30,583 uh, beyond some input size N. 326 00:12:30,583 --> 00:12:31,951 Okay? Typically, this foo 327 00:12:31,951 --> 00:12:33,919 that is, uh, present in the definition is s-, 328 00:12:33,919 --> 00:12:36,255 uh, uh, some function of input size N. 329 00:12:36,255 --> 00:12:38,924 For instance, I could say that an algorithm is order N, 330 00:12:38,924 --> 00:12:41,961 which means that algorithm A takes less than c times N 331 00:12:41,961 --> 00:12:44,530 time to complete for some constant c, 332 00:12:44,530 --> 00:12:46,432 beyond some input size N. 333 00:12:46,432 --> 00:12:48,300 Similarly the algorithm might be order N^2. 334 00:12:48,300 --> 00:12:51,337 Which means, that, uh, it is quadratic in time, 335 00:12:51,337 --> 00:12:53,405 and it takes time less than c times N squared 336 00:12:53,405 --> 00:12:56,242 for some constant c. 337 00:12:56,242 --> 00:12:58,844 Once again, when we say order N^2 or order N, 338 00:12:58,844 --> 00:13:00,880 notice that we do not include the constant c, 339 00:13:00,880 --> 00:13:01,881 in the definition itself. 340 00:13:01,881 --> 00:13:03,516 This is because, the constant is irrelevant, 341 00:13:03,516 --> 00:13:05,384 as long as there is a fixed constant, 342 00:13:05,384 --> 00:13:06,986 some fixed constant. 343 00:13:06,986 --> 00:13:09,054 That is good enough for us as far as Big O notation 344 00:13:09,054 --> 00:13:11,023 is, uh, concerned. 345 00:13:11,023 --> 00:13:12,892 Okay, so we do not state the constants in Big O notation. 346 00:13:14,059 --> 00:13:15,261 So let's see a couple of examples. 347 00:13:15,261 --> 00:13:18,297 Um, so first, I give you an unsorted list 348 00:13:18,297 --> 00:13:19,665 o-of, say, integers. 349 00:13:19,665 --> 00:13:21,467 And I ask you to search for a specific element 350 00:13:21,467 --> 00:13:22,768 in the list. 351 00:13:22,768 --> 00:13:24,436 This essentially means, that you have to iterate through 352 00:13:24,436 --> 00:13:25,971 the list, one item at a time. 353 00:13:25,971 --> 00:13:28,040 And search for the element by trying to match it 354 00:13:28,040 --> 00:13:30,643 with each element quality present, in the list. 355 00:13:30,643 --> 00:13:32,478 What is the worst case performance? 356 00:13:32,478 --> 00:13:34,280 That's what we need, for Big O notation, right? 357 00:13:34,280 --> 00:13:35,414 So, the worst case performance happens when, 358 00:13:35,414 --> 00:13:38,050 either element is not there, at all, in the list, 359 00:13:38,050 --> 00:13:39,385 so, you return a false. 360 00:13:39,385 --> 00:13:42,588 Uh, or the element is the very last one, in the list. 361 00:13:42,588 --> 00:13:43,856 The very last one, that you match against. 362 00:13:44,924 --> 00:13:45,891 Therefore, the worst case performance 363 00:13:45,891 --> 00:13:47,259 involves N operations, 364 00:13:47,259 --> 00:13:52,064 and the number of operations involved is < c* N, where c=2, 365 00:13:52,064 --> 00:13:53,766 because the number of operations is N, 366 00:13:53,766 --> 00:13:54,833 where N is the size of the list. 367 00:13:55,968 --> 00:13:58,103 Okay, so, the time as well as, the number of operations, 368 00:13:58,103 --> 00:14:01,040 uh, assuming each operation takes one unit of time. 369 00:14:01,040 --> 00:14:05,578 Both the time taken for this, uh, um, uh, for this algorithm, 370 00:14:05,578 --> 00:14:06,478 which iterates through the list. 371 00:14:06,478 --> 00:14:09,949 As a list number of operations are both order N. 372 00:14:09,949 --> 00:14:11,217 That's why we see order N over here. 373 00:14:13,285 --> 00:14:14,253 Let's take a different, uh, example 374 00:14:14,253 --> 00:14:16,522 to see how Big O notation works. 375 00:14:16,522 --> 00:14:18,958 This leads with insertion sorting of an unsorted list. 376 00:14:18,958 --> 00:14:21,760 So suppose I give you a list of elements, uh, say integers, 377 00:14:21,760 --> 00:14:25,297 and this is unsorted and I ask you to sort them, 378 00:14:25,297 --> 00:14:29,001 say in increasing order of, uh, the, uh, elements. 379 00:14:29,001 --> 00:14:30,836 The insertion sorter algorithm works as follows; 380 00:14:30,836 --> 00:14:33,272 first, you create a new list, that is empty. 381 00:14:33,272 --> 00:14:34,974 Then, you iterate through the elements 382 00:14:34,974 --> 00:14:36,775 in the unsorted original list, 383 00:14:36,775 --> 00:14:38,210 you remove one element at a time, 384 00:14:38,210 --> 00:14:39,778 and you insert the element, 385 00:14:39,778 --> 00:14:41,714 in the new list at the appropriate position. 386 00:14:41,714 --> 00:14:45,384 Essentially, you sort through the new list, uh, linearly, 387 00:14:45,384 --> 00:14:46,752 uh, searching for the right position 388 00:14:46,752 --> 00:14:49,088 where this element, should be. 389 00:14:49,088 --> 00:14:50,322 So, if you do this, 390 00:14:50,322 --> 00:14:52,458 the first element, of course, takes one operation to insert. 391 00:14:52,458 --> 00:14:54,059 That's one insert operation. 392 00:14:54,059 --> 00:14:55,694 The second element, in the worst case, 393 00:14:55,694 --> 00:14:57,129 takes two operations to insert. 394 00:14:57,129 --> 00:14:58,530 One operation for the comparison, 395 00:14:58,530 --> 00:15:00,399 with the one element that's already present, 396 00:15:00,399 --> 00:15:01,834 in the new sorted list 397 00:15:01,834 --> 00:15:03,369 and one more operation to insert. 398 00:15:03,369 --> 00:15:05,104 Imagine the case, the worst case, 399 00:15:05,104 --> 00:15:06,772 where, this second element, 400 00:15:06,772 --> 00:15:08,574 is inserted right at the very end, of the list. 401 00:15:09,775 --> 00:15:11,577 Similarly, the third element, will take, uh, 402 00:15:11,577 --> 00:15:12,578 three operations to insert, 403 00:15:12,578 --> 00:15:13,612 where the first two elements, 404 00:15:13,612 --> 00:15:15,848 compared with the two already existing elements, 405 00:15:15,848 --> 00:15:18,050 the third, uh, uh, operation, 406 00:15:18,050 --> 00:15:21,987 uh, inserts it at the very end of, uh, the, ah, 407 00:15:21,987 --> 00:15:23,322 uh, of the list. 408 00:15:23,322 --> 00:15:24,223 If, you go on like this 409 00:15:24,223 --> 00:15:26,292 and the i-th element takes i operations to insert, 410 00:15:26,292 --> 00:15:28,894 and you can calculate that the total time required 411 00:15:28,894 --> 00:15:32,665 to insert all the, m, elements is 1+2+3, so on until N. 412 00:15:32,665 --> 00:15:36,769 And this is a well-known sum which comes to N(N+1)/2, 413 00:15:36,769 --> 00:15:39,405 which is, uh, <1*N^2. 414 00:15:39,405 --> 00:15:42,074 So, with a value of C equals one, uh, this, uh, 415 00:15:42,074 --> 00:15:44,276 insertion sorting example, 416 00:15:44,276 --> 00:15:47,579 is an algorithm that takes order N^2 in time, 417 00:15:47,579 --> 00:15:49,815 and also order N^2 in number of operations. 418 00:15:55,020 --> 00:15:57,022 Next, we look at a little bit of basic probability, 419 00:15:57,022 --> 00:15:58,424 uh, before probability, 420 00:15:58,424 --> 00:15:59,825 we need to discuss, few definitions. 421 00:15:59,825 --> 00:16:01,994 Uh, the first definition is a set. 422 00:16:01,994 --> 00:16:04,396 A set is, essentially, a collection of things. 423 00:16:04,396 --> 00:16:06,632 So for instance, a set S might be the set of all humans, 424 00:16:06,632 --> 00:16:09,368 who live in this world, at this current moment. 425 00:16:09,368 --> 00:16:12,004 A subset, is another set, which is a collection of things, 426 00:16:12,004 --> 00:16:14,173 that is a part of the larger set. 427 00:16:14,173 --> 00:16:17,042 So, I might design a-, uh, da, uh, describe a set S2, 428 00:16:17,042 --> 00:16:18,110 which says, 429 00:16:18,110 --> 00:16:21,146 a set of all humans who live, currently, in Europe, today. 430 00:16:21,146 --> 00:16:22,514 S2 is a subset of S, 431 00:16:22,514 --> 00:16:25,117 because every element that is present in S2 432 00:16:25,117 --> 00:16:26,452 is also present in S, 433 00:16:26,452 --> 00:16:28,053 but the reverse is not necessarily true. 434 00:16:30,989 --> 00:16:33,859 Okay, so now, um, probability, 435 00:16:33,859 --> 00:16:37,029 any-any event, uh, has a probability of happening. 436 00:16:37,029 --> 00:16:40,199 Okay, so, umm, let me give you an example. 437 00:16:40,199 --> 00:16:42,368 If you wake up at a random hour of the day, 438 00:16:42,368 --> 00:16:44,937 um, so you just wake up at some random hour of the day, 439 00:16:44,937 --> 00:16:46,338 say you're jet lagged or something. 440 00:16:46,338 --> 00:16:49,375 Uh, and, uh, I ask you, what is the probability, 441 00:16:49,375 --> 00:16:52,244 that the event at that time is between 10 a.m. and 11 a.m.? 442 00:16:52,244 --> 00:16:53,045 Let's try to calculate this. 443 00:16:54,179 --> 00:16:55,881 Well, there are 24 hours in a day, 444 00:16:55,881 --> 00:16:58,884 so you have a set that consists of 24 elements, 445 00:16:58,884 --> 00:17:01,854 one for each hour, 12 a.m., 1 a.m., 2 a.m., 446 00:17:01,854 --> 00:17:04,990 all the way til, 10 a.m., 11 a.m., 11 p.m. 447 00:17:04,990 --> 00:17:07,559 'Kay, so when I say an element like, uh, 1 a.m. 448 00:17:07,559 --> 00:17:10,996 I mean, the hour between 1 a.m. and 1:59 am. 449 00:17:10,996 --> 00:17:14,133 Similarly, 10 a.m. means, 10 a.m. and 10:59 a.m. 450 00:17:15,267 --> 00:17:18,470 Out of the set of 24 elements, you pick one, at random. 451 00:17:18,470 --> 00:17:20,071 And the probability that you're going to pick 10 a.m., 452 00:17:20,071 --> 00:17:22,007 is essentially, 1 divided by 24, 453 00:17:22,007 --> 00:17:24,108 because you're picking one element at random 454 00:17:24,108 --> 00:17:26,744 and there are 24 elements, uh, in the set, 455 00:17:26,744 --> 00:17:28,747 and the probability that you pick, 456 00:17:28,747 --> 00:17:32,518 um, that one special element, 10 a.m., is 1 over 24, 457 00:17:32,518 --> 00:17:34,720 because you-you wanna pick, you wanna be lucky, 458 00:17:34,720 --> 00:17:37,289 o-of that, uh, to pick that, uh, 10. 459 00:17:37,289 --> 00:17:38,690 Okay, so, the probability that you, 460 00:17:38,690 --> 00:17:40,192 if you wake up at a random hour of the day, 461 00:17:40,192 --> 00:17:42,261 the time is between 10 a.m. and 11 a.m., 462 00:17:42,261 --> 00:17:43,796 the-that probability is 1 over 24. 463 00:17:46,765 --> 00:17:48,567 Now, uh, there might be multiple events 464 00:17:48,567 --> 00:17:50,569 that you might need to calculate the probability of, 465 00:17:50,569 --> 00:17:52,638 uh, conjunctions or disjunctions of these events. 466 00:17:52,638 --> 00:17:53,806 I'll describe what these are, soon. 467 00:17:53,806 --> 00:17:56,208 So say, E1 is one event and E2 is another event, 468 00:17:56,208 --> 00:17:58,644 and E1 and E-E2 are independent of each other. 469 00:17:58,644 --> 00:17:59,678 This means that, 470 00:17:59,678 --> 00:18:02,381 E1 does not influence E2, E2 does not influence E1. 471 00:18:02,381 --> 00:18:04,850 Then the probability that E1 and E2 both happen, 472 00:18:04,850 --> 00:18:06,185 is essentially, 473 00:18:06,185 --> 00:18:08,053 the multiplication of these probabilities. 474 00:18:08,053 --> 00:18:09,721 So you take the probability of E1, 475 00:18:09,721 --> 00:18:11,423 multiply it by the probability of E2, 476 00:18:11,423 --> 00:18:12,424 and that gives you, 477 00:18:12,424 --> 00:18:15,227 the probability that both E1 and E2 are true. 478 00:18:15,227 --> 00:18:16,495 Let's discuss an example of this. 479 00:18:16,495 --> 00:18:17,930 Suppose you have three shirts. 480 00:18:17,930 --> 00:18:20,065 They're colored blue, green, and red. 481 00:18:20,065 --> 00:18:23,101 And also you wake up at a random hour and blindly pick a shirt, 482 00:18:23,101 --> 00:18:25,504 you put your, uh, hand into your, uh, closet, 483 00:18:25,504 --> 00:18:27,606 and you blindly pick out a shirt. 484 00:18:27,606 --> 00:18:28,640 What is the probability that, 485 00:18:28,640 --> 00:18:30,776 he woke up between 10 a.m. and 11 a.m. 486 00:18:30,776 --> 00:18:34,046 and, that he picked a green shirt to wear? 487 00:18:34,046 --> 00:18:36,181 Well, the first probability of the first event, 488 00:18:36,181 --> 00:18:37,483 that he woke up between 10 and 11, 489 00:18:37,483 --> 00:18:38,951 is essential, 1 over 24, 490 00:18:38,951 --> 00:18:40,853 like we calculated on the previous slide. 491 00:18:40,853 --> 00:18:43,055 The probability that you pick the green shirt, is essentially, 492 00:18:43,055 --> 00:18:45,390 one out of three, because there are three colors of shirts, 493 00:18:45,390 --> 00:18:46,525 uh, you have three shirts 494 00:18:46,525 --> 00:18:48,660 and, uh, you want to pick the green one, 495 00:18:48,660 --> 00:18:49,862 you want to be lucky, to pick the green one, 496 00:18:49,862 --> 00:18:51,296 so that's one over three. 497 00:18:51,296 --> 00:18:53,499 And so, the probability that both these events are true, 498 00:18:53,499 --> 00:18:54,867 that you woke up between 10 and 11, 499 00:18:54,867 --> 00:18:56,869 and that you wore the green shirt 500 00:18:56,869 --> 00:18:58,370 is the multiplication of the probabilities 501 00:18:58,370 --> 00:18:59,538 of those events. 502 00:18:59,538 --> 00:19:03,542 So it's (1/24)*(1/3)=1/72. 503 00:19:05,010 --> 00:19:05,744 One of the things, 504 00:19:05,744 --> 00:19:06,712 that you have to be careful about here, 505 00:19:06,712 --> 00:19:09,548 is that, uh, if E1 and E2 are not independent, 506 00:19:09,548 --> 00:19:11,683 meaning that they influence each other in some way, 507 00:19:11,683 --> 00:19:15,420 uh, then, you cannot multiply, uh, the, uh, probabilities 508 00:19:15,420 --> 00:19:16,288 with, uh, each other. 509 00:19:16,288 --> 00:19:20,459 Okay, so, for instance, um, if, uh, 510 00:19:20,459 --> 00:19:22,461 the shirts that you have in your closet, 511 00:19:22,461 --> 00:19:25,030 uh, change from one hour to another, because, uh, 512 00:19:25,030 --> 00:19:26,431 um, say, uh, 513 00:19:26,431 --> 00:19:28,300 someone in your house changes them around, 514 00:19:28,300 --> 00:19:30,602 then you can't necessarily multiply these probabilities, 515 00:19:30,602 --> 00:19:31,436 as they are here. 516 00:19:32,771 --> 00:19:34,139 A different thing that we need to do 517 00:19:34,139 --> 00:19:36,875 with two event probabilities is, uh, to OR them. 518 00:19:36,875 --> 00:19:38,944 So, if, I give you two events, E1 and E2 519 00:19:38,944 --> 00:19:40,546 and I ask you the probability that, 520 00:19:40,546 --> 00:19:43,248 uh, of either E1 or E2 happening 521 00:19:43,248 --> 00:19:46,285 then, you can say that Prob(E1 OR E2)= 522 00:19:46,285 --> 00:19:51,290 Prob(E1)+Prob(E2)- Prob(E1 AND E2). 523 00:19:51,290 --> 00:19:53,458 Okay, so, this is the intersection probability here. 524 00:19:53,458 --> 00:19:55,827 If, you do not know probability of E1 and E2, 525 00:19:55,827 --> 00:19:57,162 this last term over here, 526 00:19:57,162 --> 00:20:00,599 than, you can write the inequality Prob(E1 OR E2)<= 527 00:20:00,599 --> 00:20:03,402 the sum of the constituent probabilities, okay? 528 00:20:04,570 --> 00:20:06,872 Sometimes we use these inequalities to upper bound, 529 00:20:06,872 --> 00:20:10,676 uh, the, uh, probabilities of the, um, uh, disjunctions, 530 00:20:10,676 --> 00:20:11,677 as we see here. 531 00:20:13,545 --> 00:20:14,980 Okay, let's disces-discuss a couple of-of, 532 00:20:14,980 --> 00:20:16,214 a few miscellaneous topics. 533 00:20:16,214 --> 00:20:18,116 The first miscellaneous topic is, a Domain Name System, 534 00:20:18,116 --> 00:20:19,184 or known as DNS. 535 00:20:19,184 --> 00:20:20,185 This is a collection of servers, 536 00:20:20,185 --> 00:20:22,220 that are spread throughout the world and, uh, 537 00:20:22,220 --> 00:20:23,221 the DNS is very critical 538 00:20:23,221 --> 00:20:25,591 to the operation of the, uh, web. 539 00:20:25,591 --> 00:20:26,692 Uh, typically the input 540 00:20:26,692 --> 00:20:30,095 to the DU-to the DNS system is a URL, say coursera.org. 541 00:20:30,095 --> 00:20:31,563 Uh, the URL is a name, 542 00:20:31,563 --> 00:20:32,764 it's a human readable string, 543 00:20:32,764 --> 00:20:35,000 that uniquely identifies the object. 544 00:20:35,000 --> 00:20:36,468 Uh, typically, when you go to your browser, 545 00:20:36,468 --> 00:20:39,504 whether it's Safari, Chrome, Internet Explorer, Netscape, 546 00:20:39,504 --> 00:20:41,840 Firefox, or whatever your favorite browser is. 547 00:20:41,840 --> 00:20:44,576 Uh, you might enter a URL like coursera.org, 548 00:20:44,576 --> 00:20:46,178 the moment you hit Enter on your browser, 549 00:20:46,178 --> 00:20:49,081 your browser goes off and contacts a DNS, the DNS, 550 00:20:49,081 --> 00:20:52,250 the DNS system, and, uhm, uh, gives the DNS system 551 00:20:52,250 --> 00:20:55,721 the name of this URL, which is coursera.org. 552 00:20:55,721 --> 00:20:57,289 What does the DNS give back to your browser? 553 00:20:57,289 --> 00:20:59,224 It gives back the IP address of a web server, 554 00:20:59,224 --> 00:21:01,793 that hosts that content, so that your machine, 555 00:21:01,793 --> 00:21:04,296 your browser can tho- then go and send a request, 556 00:21:04,296 --> 00:21:05,631 to that IP address, 557 00:21:05,631 --> 00:21:08,634 and fetch the actual content of that web page. 558 00:21:08,634 --> 00:21:09,935 So, the IP address is an ID, 559 00:21:09,935 --> 00:21:12,371 it's a unique string that points to that particular object. 560 00:21:12,371 --> 00:21:14,706 For instance, the coursera.org, uh, web page. 561 00:21:14,706 --> 00:21:18,577 Uh, and the, um, the ID itself may not be human readable. 562 00:21:18,577 --> 00:21:20,912 So, essentially, a DNS is a system that translates 563 00:21:20,912 --> 00:21:22,914 between a human readable name, 564 00:21:22,914 --> 00:21:25,884 such as, a URL, to, uh, to, uh, unique ID, 565 00:21:25,884 --> 00:21:27,986 um, which may or may not be human readable, 566 00:21:27,986 --> 00:21:29,454 like the IP address. 567 00:21:30,656 --> 00:21:32,224 Uh, in this case, IP address may refer to either, 568 00:21:32,224 --> 00:21:33,959 the actual web server that is storing the content, 569 00:21:33,959 --> 00:21:35,527 or maybe an indirection server 570 00:21:35,527 --> 00:21:37,162 such as, a content distribution network server, 571 00:21:37,162 --> 00:21:40,132 or, uh, such as, an Akamai server that is, 572 00:21:40,132 --> 00:21:42,834 uh, hosting or, uh, caching the content on your behalf. 573 00:21:45,470 --> 00:21:46,605 Uh, graphs, 574 00:21:46,605 --> 00:21:48,840 um, so when we say graphs, in computer science, 575 00:21:48,840 --> 00:21:51,943 we don't necessarily mean plots, which have x and y axes. 576 00:21:51,943 --> 00:21:54,079 Uh, a graph, is essentially, a network. 577 00:21:54,079 --> 00:21:57,149 So here I am showing you a graph of some cities, 578 00:21:57,149 --> 00:22:00,318 um, Amsterdam, Boston, Chicago, Delhi, and Edmonton, 579 00:22:00,318 --> 00:22:03,689 and the travel times, uh, between those cities by air, 580 00:22:03,689 --> 00:22:06,291 um, rounded up to the nearest hour. 581 00:22:06,291 --> 00:22:08,894 Okay, so, uh, traveling from Amsterdam to Boston 582 00:22:08,894 --> 00:22:09,961 takes about six hours. 583 00:22:09,961 --> 00:22:11,496 Traveli-traveling from Chicago to Delhi 584 00:22:11,496 --> 00:22:12,831 takes about 14 hours. 585 00:22:12,831 --> 00:22:14,499 Say these are the flights that are available 586 00:22:14,499 --> 00:22:16,468 on some particular airline. 587 00:22:16,468 --> 00:22:17,736 Right? 588 00:22:17,736 --> 00:22:19,304 So, you see both cities here, as well as, 589 00:22:19,304 --> 00:22:21,406 uh, connections between, uh, pairs of cities, 590 00:22:21,406 --> 00:22:25,577 uh, and also, um, some values along those connections, 591 00:22:25,577 --> 00:22:27,579 which are, the number of hours it takes to transit 592 00:22:27,579 --> 00:22:28,346 between those cities. 593 00:22:29,581 --> 00:22:31,183 Uh, these all have names, in the terms, 594 00:22:31,183 --> 00:22:32,217 in the world of graphs. 595 00:22:32,217 --> 00:22:35,253 So, each city, would be a node or a vertex. 596 00:22:35,253 --> 00:22:38,123 Uh, each connection between a pair of nodes, 597 00:22:38,123 --> 00:22:40,158 would be called an edge, 598 00:22:40,158 --> 00:22:44,096 and the value along an edge is called the edge weight. 599 00:22:44,096 --> 00:22:46,832 Also, when I say that A is adjacent to B, 600 00:22:46,832 --> 00:22:51,636 this means that A has an edge that connects it to B, directly. 601 00:22:51,636 --> 00:22:53,405 Typically, an edge only goes between, 602 00:22:53,405 --> 00:22:55,941 uh, uh two nodes or two vertices. 603 00:22:55,941 --> 00:22:58,076 An edge does not cross three, uh, nodes. 604 00:22:58,076 --> 00:23:03,181 So here, for instance, I have, um, uh, 1, 2, 3, 4, 5 vertices, 605 00:23:03,181 --> 00:23:04,483 and how many edges do I have? 606 00:23:04,483 --> 00:23:08,987 I have an A-E edge, an A-B edge, a B-E edge, a B-C edge 607 00:23:08,987 --> 00:23:09,888 and a C-D edge, 608 00:23:09,888 --> 00:23:12,457 so, I also have, uh, five, uh, different edges, 609 00:23:12,457 --> 00:23:14,626 each with its own, uh, edge weight. 610 00:23:17,662 --> 00:23:19,331 So, in this, uh, lecture, we have covered, 611 00:23:19,331 --> 00:23:22,000 the basic data structure, such as, uh, queue and a stack, 612 00:23:22,000 --> 00:23:24,436 we have seen that processes are programs in action, 613 00:23:24,436 --> 00:23:26,805 and that they consist of multiple different pieces, 614 00:23:26,805 --> 00:23:28,940 uh, processes of course are under computer architecture, 615 00:23:28,940 --> 00:23:30,041 and it's important for you to know, 616 00:23:30,041 --> 00:23:32,744 at least, a simplified version of the computer architecture, 617 00:23:32,744 --> 00:23:35,080 so that you know what's, ah, operating where, 618 00:23:35,080 --> 00:23:36,648 uh, when you run a process. 619 00:23:36,648 --> 00:23:37,816 We've seen some mathematical topics, 620 00:23:37,816 --> 00:23:38,950 such as, Big O notation 621 00:23:38,950 --> 00:23:40,418 which, analyzes the worst case performance 622 00:23:40,418 --> 00:23:41,920 of any given algorithm, 623 00:23:41,920 --> 00:23:43,588 and then some basic probability. 624 00:23:43,588 --> 00:23:46,057 And finally, we have seen a few miscellaneous topics. 625 00:23:46,057 --> 00:23:48,093 I hope you can come back- keep coming back to this, 626 00:23:48,093 --> 00:23:49,494 as a reference, whenever you need it, 627 00:23:49,494 --> 00:23:51,329 uh, throughout, uh, the, uh, course.