0:07

Welcome, uh, to this, uh, cloud computing concepts course.

Â In this, uh, lecture we'll be covering several, uh, concepts,

Â uh, that are assumed as a part of, uh, the topics

Â that we'll be discussing

Â in the cloud computing concepts, uh, course.

Â 0:23

So, we'll be covering several of the basics, uh,

Â they're considered to be basics in computer science.

Â Uh, typically,

Â some of these concepts, are concepts that, uh,

Â computer science students learn in their first couple of years

Â in, uh, a computer science degree,

Â undergraduate degree program.

Â So for those of you,

Â who are already familiar with this material,

Â uh, this could be a refresher or you could just, uh, skip it,

Â if you already know, uh, this stuff.

Â In any case, uh, you can always use this

Â orientation lecture as a reference,

Â uh, to keep coming back to if, you encounter a, uh, term in,

Â uh, during the regular lectures that doesn't make sense to you,

Â or that you'd like to be reminded about.

Â 1:17

So, bas-basic data structures,

Â we'll discuss two di-different data structures.

Â The first one is a queue.

Â A queue, is essentially,

Â a First-in First-out data structure.

Â Elements of the queue could be, uh, any data types.

Â In this example, here, I have elements that are in tiers.

Â So, in this, uh, example right now, the queue has 5 elements,

Â 3, 5, 8, 0, 7.

Â This is an ordered, list of elements.

Â When you remove an element from the queue,

Â you remove it from the head of the queue.

Â In this case, the head is the element three.

Â Uh, when you insert a new element,

Â you insert it in the tail of the queue, which means that,

Â if, I insert a new element, say one,

Â it's going to get inserted right after seven in this queue.

Â 1:56

So removal always comes from the head,

Â while insertion always happens at the tail.

Â Uh, so, for instance, given this particular queue,

Â consisting of five elements, if you-if you,

Â dequeue or remove an item, uh, then that item will be three.

Â At that point of time the queue will only consist

Â of 5, 8, 0, and 7, with the head pointing to 5.

Â The next item that you dequeue or remove will be five, okay?

Â After that the queue will consist of only 8, 0, and 7.

Â Then, uh, the next item that you dequeue will be eight,

Â um, and so on and so forth.

Â Uh, dequeues and, or removals, as well as, insertions,

Â uh, can occur, uh, concurrently, so you can,

Â uh, remove an element,

Â but at the same time also insert an element at the tail.

Â 2:36

So, that's a queue,

Â which is a First-in First-out data structure.

Â A different data structure is the stack,

Â which is the First-in Last-out data structure.

Â Uh, imagine a stack of dishes that you, uh,

Â place on your table.

Â Uh, the dish that you put on the top,

Â that you add the last,

Â will be the first one that you can remove, right?

Â And that's essentially a stack.

Â So, uh, remove or also known, as a pop happens from the top.

Â An insert or a push also happens at the top.

Â Okay, so in this case, um, uh, if you, uh, push a new element

Â into this particular stack, um, uh, say nine.

Â The nine will go above three.

Â After that, if you pop, or remove an element,

Â that's going to be the last element that you added,

Â which is nine, in this case.

Â The next pop after that will get three,

Â because nine was just removed.

Â And three is now the top of the, uh, stack.

Â Uh, after you've removed three,

Â the next pop or removal will get you five,

Â uh, and so on and so forth.

Â After that you'll get 8 and then 0 and 7.

Â Okay, so, once again, the removal always returns you

Â the last item that was added.

Â And, uh, insertion or push adds an item

Â right to the top, of the stack.

Â So these two data structures, queue and stack

Â are used very widely in computer science

Â and, um, in fact, we'll be using the notion of a stack, uh,

Â right away when we'll discuss, uh, uh, processes, um,

Â uh, soon in this particular orientation lecture, itself.

Â 3:51

So, speaking of processes, um, let's discuss a process next.

Â Uh, a process is essentially a program in action.

Â Uh, you may write a program in a language,

Â programming language, such as, C or C++.

Â And that's sh- an example is shown here.

Â This example code, here, uh, consists of a main function,

Â which, uh, calls a function, uh, called f1.

Â F1 itself has a local integer variable x,

Â and then, f1 itself calls a different function, f2.

Â 4:18

Okay, this is shown pictorially here, in the circle,

Â where main calls f1 and f1 calls f2.

Â 'Kay, this is the code that you would write,

Â and then, y'know, you would compile the code

Â and then, uh, execute it.

Â And when you're executing it, when your program is in action,

Â that is a process.

Â So, a process consists of your code,

Â but also several other elements that, uh, help your code

Â to execute on the computer, on which you are executing it.

Â So, we are going to discuss some, uh, elements

Â o-of a process which are critical.

Â 4:46

Here, are some of these elements.

Â First, um, uh, let's look at the code.

Â The code itself, uh, is, uh, static.

Â Once you write the code, um, nothing changes it,

Â uh, we are not considering the variable values

Â to be a part of the code.

Â I'll talk about that in a little bit.

Â But the code itself, is static;

Â it does not change once you write it.

Â Uh, but, uh, there is a program counter,

Â which is typically maintained by the computer

Â on which you're running your, uh, process, uh,

Â which points to

Â which is the line number inside the code,

Â where the program is currently executing,

Â or rather where, the process is currently executing.

Â 'Kay, this is called a Program Counter, or the PC.

Â Okay, this is a part,

Â an important part of the process state.

Â So, if you were to take a core dump,

Â or stop the process right now,

Â and take a snapshot of that process.

Â That snapshot must include, the program counter,

Â because it says, where in the code is,

Â uh, the execution currently at.

Â 5:36

Next, uh, when, um, er-r, um, functions call each other,

Â um, or in an object oriented, um, uh, program,

Â uh, methods call each other, they use a stack.

Â So every process contains, uh, a stack.

Â Uh, more specifically, um, a proce-

Â a process might contain multiple threads.

Â Each thread will contain its own stack.

Â But, let's just say

Â there is one thread in this process.

Â Uh, so, a process contains one stack,

Â and this stack is used by these functions or methods,

Â to pass arguments and return, uh, the result values.

Â So, for instance, when main calls f1,

Â main will push the arguments, uh, to f1, on top of the stack.

Â When f1 starts executing

Â it will pop, or remove,

Â the elements from the top of the stack

Â and use it to, uh, execute.

Â Uh, similarly, uh, when f1 calls f2,

Â um, f1 will push the arguments on top of the stack, for f2,

Â and then f2 will, um, uh, pop them, execute,

Â and then push the result values on top of the stack.

Â The result values then popped by f1.

Â This is the way in which f1 gets back the result,

Â um, the final int return value from f2, to itself.

Â And finally when f-f1 needs to return a resolved value to,

Â uh, main, it pushes it on top of the stack

Â when the execution returns to main,

Â uh, main, uh, pops it

Â or removes it from the top of the stack

Â and main has the final return value from f1.

Â 'Kay, so, the stack

Â is an important part of the process state as well,

Â because it tells you where in the program execution

Â you are, with respect to functions calling each other.

Â 7:06

Finally, uh, y'know, uh,

Â functions have local variable, like x.

Â There might also be global variables, um,

Â uh, and of course in object oriented programs,

Â you have, uh, objects,

Â which store a lot of fields in them.

Â A lot of these, uh, pieces of data,

Â are stored in, what is known as a heap.

Â Okay, so, uh, a heap is essentially a lot of data,

Â uh, that was created by functions or methods,

Â uh, or, uh, um, by objects, um.

Â And it holds all of the data and, y'know, when an object,

Â when a function's executing,

Â uh, say f1 is executing,

Â uh, the object x might be created inside the heap,

Â when f1 is done executing.

Â X, uh, the object of x will be removed from the heap.

Â Similarly, there're also registers,

Â and I'll talk more about registers

Â when we discuss computer architecture,

Â but registers hold some of the, uh, recent values

Â that have been accessed, uh, by the process,

Â p1, in this case.

Â 7:55

Okay, uh, speaking of computer architecture.

Â Let's discuss a simplified version

Â of computer architecture.

Â Computer architectures today, uh, can be very complicated.

Â But, um, typically when we ta-

Â when we think of how a process executes,

Â in a computer architecture,

Â we can think of a simplified view.

Â So there is a CPU,

Â which executes the action instructions,

Â which are present in your, uh, code.

Â There're also a bunch of registers,

Â that are co-located, uh, with the CPU.

Â These are, uh, small pieces of memory,

Â that can be accessed very quickly by the CPU.

Â Typically, uh, there's only a small number of registers.

Â Typically, not more than a few tens of registers.

Â Uh, there's also a cache,

Â which is, a slightly larger memory

Â than the collection of registers.

Â And the larger a map piece of memory is,

Â uh, the slower it is to access it.

Â So accessing a cache is slower than registers,

Â uh, than accessing registers.

Â But accessing a cache is still pretty fast.

Â Uh, then beyond the cache there is the main memory,

Â or the Random Access Memory, or the RAM.

Â Uh, which is even larger than the cache,

Â uh, and the ca- the memory itself,

Â therefore, is slower than the cache,

Â but still, it's pretty fast.

Â And then finally, there's hard disk,

Â or if you would like, a solid stave-state drive,

Â a flash, uh, drive, or whatever,

Â which is, a lot more memory than, uh, the main memory,

Â uh, but of course, it's much slower.

Â So, as you go up from disk, to memory, to cache, registers,

Â the speed increases,

Â the total amount of, uh, storage space

Â that you have, decreases.

Â 9:14

So, when you write a program,

Â such as, C++, or Java, or C, and you compile it,

Â it gets compiled to low level machine instructions.

Â These machine instructions,

Â uh, might be specific to the architecture,

Â the machine on which you are running,

Â or it might be a, um,

Â ah, virtual machine, like a JVM, kind of, um, code.

Â In any case, uh, these low level machine instructions

Â are the executable version of your, uh, program,

Â and this is stored in file system, um, uh,

Â in the file system on- on your disk.

Â When your program starts executing,

Â when it becomes a process,

Â uh, the CPU loads instructions in batches,

Â or, m-, in a simplifi- more simplified way,

Â it loads instructions one by one.

Â Uh, it loads them into memory,

Â and then into cache, and into registers.

Â Typically, the cache and the registers contain

Â the last few accessed instructions.

Â Um, so they are, uhm,

Â they follow what is known as,

Â the least recently used principle.

Â Now, as it executes y- each instruction, the CPU,

Â which is executing the process, loads the data,

Â that is necessary for the instruction,

Â into the memory and then if necessary

Â into the cache and the registers.

Â Um, and if there are any necessary, uh, changes

Â that happen to a variable like, x,

Â then, these are stored into a memory, um, um,

Â uh, first into cache and then into memory.

Â 10:26

Once in a while, you may need to store something on disks,

Â so that you have, um, a permanent storage.

Â So in case, the process goes offline,

Â then you still have some data.

Â Say for instance, the program might open a file

Â and write something into the file.

Â So, in this case, uh, you may want to write those,

Â uh, updates to the file onto the disk.

Â 10:43

Now, of course this is a very highly simplified picture.

Â Computer architectures can be far more,

Â uh, complex than this, today,

Â but for our practical purposes, in this course, and as far as,

Â uh, explaining how processes work, um, this will suffice.

Â 10:58

So next, we move on to a few mathematical topics.

Â The first mathematical topic is, a Big O notation.

Â A Big O notation is,

Â one of the most basic ways of analyzing algorithms.

Â When I give you an algorithm,

Â and I say analyze the algorithm mathematically,

Â essentially, I expect you to, uh, come up with,

Â at least a Big O notation,

Â uh, and an analysis of that algorithm.

Â The-the Big O notation,

Â describes an upper bound in the behavior of an algorithm.

Â Um, as some variable is scaled

Â or increased in value all the way to infinity.

Â Typically, this variable is a size of the input.

Â Um, maybe the number of input elements,

Â um, you'll see-sa-you'll see a few examples of this.

Â 11:34

So, essentially, this, uhh-oah, Big O analysis tells us,

Â how does the, uh, algorithm itself

Â scale as the size of the input is increased?

Â Um, this analyzes the run time,

Â or typically, another performance metric, as well.

Â Most of the time, we analyze run time,

Â sometimes, as you'll see in the course,

Â we'll analyze things like number of messages,

Â um, uh, even, uh, bandwidth, um,

Â uh, that is exchanged i-in the total network itself.

Â The important thing about Big O notation is that,

Â i-it captures worst case performance.

Â Okay, so this is not expected performance

Â or best case performance.

Â Big O is worst case performance.

Â Given this algorithm,

Â what is the worst that it can do in terms of, uh,

Â this performance metric that we're measuring?

Â 12:15

So, essentially, when I say, an algorithm A is order of foo,

Â this means that,

Â Algorithm A takes < c foo time to complete,

Â assuming time is the metric we are measuring,

Â for some constant c, a fixed constant c,

Â uh, beyond some input size N.

Â Okay? Typically, this foo

Â that is, uh, present in the definition is s-,

Â uh, uh, some function of input size N.

Â For instance, I could say that an algorithm is order N,

Â which means that algorithm A takes less than c times N

Â time to complete for some constant c,

Â beyond some input size N.

Â Similarly the algorithm might be order N^2.

Â Which means, that, uh, it is quadratic in time,

Â and it takes time less than c times N squared

Â for some constant c.

Â Once again, when we say order N^2 or order N,

Â notice that we do not include the constant c,

Â in the definition itself.

Â This is because, the constant is irrelevant,

Â as long as there is a fixed constant,

Â some fixed constant.

Â That is good enough for us as far as Big O notation

Â is, uh, concerned.

Â Okay, so we do not state the constants in Big O notation.

Â 13:14

So let's see a couple of examples.

Â Um, so first, I give you an unsorted list

Â o-of, say, integers.

Â And I ask you to search for a specific element

Â in the list.

Â This essentially means, that you have to iterate through

Â the list, one item at a time.

Â And search for the element by trying to match it

Â with each element quality present, in the list.

Â What is the worst case performance?

Â That's what we need, for Big O notation, right?

Â So, the worst case performance happens when,

Â either element is not there, at all, in the list,

Â so, you return a false.

Â Uh, or the element is the very last one, in the list.

Â The very last one, that you match against.

Â 13:55

Okay, so, the time as well as, the number of operations,

Â uh, assuming each operation takes one unit of time.

Â Both the time taken for this, uh, um, uh, for this algorithm,

Â which iterates through the list.

Â As a list number of operations are both order N.

Â That's why we see order N over here.

Â 14:13

Let's take a different, uh, example

Â to see how Big O notation works.

Â This leads with insertion sorting of an unsorted list.

Â So suppose I give you a list of elements, uh, say integers,

Â and this is unsorted and I ask you to sort them,

Â say in increasing order of, uh, the, uh, elements.

Â The insertion sorter algorithm works as follows;

Â first, you create a new list, that is empty.

Â Then, you iterate through the elements

Â in the unsorted original list,

Â you remove one element at a time,

Â and you insert the element,

Â in the new list at the appropriate position.

Â Essentially, you sort through the new list, uh, linearly,

Â uh, searching for the right position

Â where this element, should be.

Â So, if you do this,

Â the first element, of course, takes one operation to insert.

Â That's one insert operation.

Â The second element, in the worst case,

Â takes two operations to insert.

Â One operation for the comparison,

Â with the one element that's already present,

Â in the new sorted list

Â and one more operation to insert.

Â Imagine the case, the worst case,

Â where, this second element,

Â is inserted right at the very end, of the list.

Â 15:09

Similarly, the third element, will take, uh,

Â three operations to insert,

Â where the first two elements,

Â compared with the two already existing elements,

Â the third, uh, uh, operation,

Â uh, inserts it at the very end of, uh, the, ah,

Â uh, of the list.

Â If, you go on like this

Â and the i-th element takes i operations to insert,

Â and you can calculate that the total time required

Â to insert all the, m, elements is 1+2+3, so on until N.

Â And this is a well-known sum which comes to N(N+1)/2,

Â which is, uh, <1*N^2.

Â So, with a value of C equals one, uh, this, uh,

Â insertion sorting example,

Â is an algorithm that takes order N^2 in time,

Â and also order N^2 in number of operations.

Â 15:55

Next, we look at a little bit of basic probability,

Â uh, before probability,

Â we need to discuss, few definitions.

Â Uh, the first definition is a set.

Â A set is, essentially, a collection of things.

Â So for instance, a set S might be the set of all humans,

Â who live in this world, at this current moment.

Â A subset, is another set, which is a collection of things,

Â that is a part of the larger set.

Â So, I might design a-, uh, da, uh, describe a set S2,

Â which says,

Â a set of all humans who live, currently, in Europe, today.

Â S2 is a subset of S,

Â because every element that is present in S2

Â is also present in S,

Â but the reverse is not necessarily true.

Â 16:30

Okay, so now, um, probability,

Â any-any event, uh, has a probability of happening.

Â Okay, so, umm, let me give you an example.

Â If you wake up at a random hour of the day,

Â um, so you just wake up at some random hour of the day,

Â say you're jet lagged or something.

Â Uh, and, uh, I ask you, what is the probability,

Â that the event at that time is between 10 a.m. and 11 a.m.?

Â Let's try to calculate this.

Â 16:54

Well, there are 24 hours in a day,

Â so you have a set that consists of 24 elements,

Â one for each hour, 12 a.m., 1 a.m., 2 a.m.,

Â all the way til, 10 a.m., 11 a.m., 11 p.m.

Â 'Kay, so when I say an element like, uh, 1 a.m.

Â I mean, the hour between 1 a.m. and 1:59 am.

Â Similarly, 10 a.m. means, 10 a.m. and 10:59 a.m.

Â 17:15

Out of the set of 24 elements, you pick one, at random.

Â And the probability that you're going to pick 10 a.m.,

Â is essentially, 1 divided by 24,

Â because you're picking one element at random

Â and there are 24 elements, uh, in the set,

Â and the probability that you pick,

Â um, that one special element, 10 a.m., is 1 over 24,

Â because you-you wanna pick, you wanna be lucky,

Â o-of that, uh, to pick that, uh, 10.

Â Okay, so, the probability that you,

Â if you wake up at a random hour of the day,

Â the time is between 10 a.m. and 11 a.m.,

Â the-that probability is 1 over 24.

Â 17:46

Now, uh, there might be multiple events

Â that you might need to calculate the probability of,

Â uh, conjunctions or disjunctions of these events.

Â I'll describe what these are, soon.

Â So say, E1 is one event and E2 is another event,

Â and E1 and E-E2 are independent of each other.

Â This means that,

Â E1 does not influence E2, E2 does not influence E1.

Â Then the probability that E1 and E2 both happen,

Â is essentially,

Â the multiplication of these probabilities.

Â So you take the probability of E1,

Â multiply it by the probability of E2,

Â and that gives you,

Â the probability that both E1 and E2 are true.

Â Let's discuss an example of this.

Â Suppose you have three shirts.

Â They're colored blue, green, and red.

Â And also you wake up at a random hour and blindly pick a shirt,

Â you put your, uh, hand into your, uh, closet,

Â and you blindly pick out a shirt.

Â What is the probability that,

Â he woke up between 10 a.m. and 11 a.m.

Â and, that he picked a green shirt to wear?

Â Well, the first probability of the first event,

Â that he woke up between 10 and 11,

Â is essential, 1 over 24,

Â like we calculated on the previous slide.

Â The probability that you pick the green shirt, is essentially,

Â one out of three, because there are three colors of shirts,

Â uh, you have three shirts

Â and, uh, you want to pick the green one,

Â you want to be lucky, to pick the green one,

Â so that's one over three.

Â And so, the probability that both these events are true,

Â that you woke up between 10 and 11,

Â and that you wore the green shirt

Â is the multiplication of the probabilities

Â of those events.

Â So it's (1/24)*(1/3)=1/72.

Â 19:05

One of the things,

Â that you have to be careful about here,

Â is that, uh, if E1 and E2 are not independent,

Â meaning that they influence each other in some way,

Â uh, then, you cannot multiply, uh, the, uh, probabilities

Â with, uh, each other.

Â Okay, so, for instance, um, if, uh,

Â the shirts that you have in your closet,

Â uh, change from one hour to another, because, uh,

Â um, say, uh,

Â someone in your house changes them around,

Â then you can't necessarily multiply these probabilities,

Â as they are here.

Â 19:32

A different thing that we need to do

Â with two event probabilities is, uh, to OR them.

Â So, if, I give you two events, E1 and E2

Â and I ask you the probability that,

Â uh, of either E1 or E2 happening

Â then, you can say that Prob(E1 OR E2)=

Â Prob(E1)+Prob(E2)- Prob(E1 AND E2).

Â Okay, so, this is the intersection probability here.

Â If, you do not know probability of E1 and E2,

Â this last term over here,

Â than, you can write the inequality Prob(E1 OR E2)<=

Â the sum of the constituent probabilities, okay?

Â 20:13

Okay, let's disces-discuss a couple of-of,

Â a few miscellaneous topics.

Â The first miscellaneous topic is, a Domain Name System,

Â or known as DNS.

Â This is a collection of servers,

Â that are spread throughout the world and, uh,

Â the DNS is very critical

Â to the operation of the, uh, web.

Â Uh, typically the input

Â to the DU-to the DNS system is a URL, say coursera.org.

Â Uh, the URL is a name,

Â it's a human readable string,

Â that uniquely identifies the object.

Â Uh, typically, when you go to your browser,

Â whether it's Safari, Chrome, Internet Explorer, Netscape,

Â Firefox, or whatever your favorite browser is.

Â Uh, you might enter a URL like coursera.org,

Â the moment you hit Enter on your browser,

Â your browser goes off and contacts a DNS, the DNS,

Â the DNS system, and, uhm, uh, gives the DNS system

Â the name of this URL, which is coursera.org.

Â What does the DNS give back to your browser?

Â It gives back the IP address of a web server,

Â that hosts that content, so that your machine,

Â your browser can tho- then go and send a request,

Â to that IP address,

Â and fetch the actual content of that web page.

Â So, the IP address is an ID,

Â it's a unique string that points to that particular object.

Â For instance, the coursera.org, uh, web page.

Â Uh, and the, um, the ID itself may not be human readable.

Â So, essentially, a DNS is a system that translates

Â between a human readable name,

Â such as, a URL, to, uh, to, uh, unique ID,

Â um, which may or may not be human readable,

Â like the IP address.

Â 21:30

Uh, in this case, IP address may refer to either,

Â the actual web server that is storing the content,

Â or maybe an indirection server

Â such as, a content distribution network server,

Â or, uh, such as, an Akamai server that is,

Â uh, hosting or, uh, caching the content on your behalf.

Â 21:45

Uh, graphs,

Â um, so when we say graphs, in computer science,

Â we don't necessarily mean plots, which have x and y axes.

Â Uh, a graph, is essentially, a network.

Â So here I am showing you a graph of some cities,

Â um, Amsterdam, Boston, Chicago, Delhi, and Edmonton,

Â and the travel times, uh, between those cities by air,

Â um, rounded up to the nearest hour.

Â Okay, so, uh, traveling from Amsterdam to Boston

Â takes about six hours.

Â Traveli-traveling from Chicago to Delhi

Â takes about 14 hours.

Â Say these are the flights that are available

Â on some particular airline.

Â Right?

Â So, you see both cities here, as well as,

Â uh, connections between, uh, pairs of cities,

Â uh, and also, um, some values along those connections,

Â which are, the number of hours it takes to transit

Â between those cities.

Â 22:29

Uh, these all have names, in the terms,

Â in the world of graphs.

Â So, each city, would be a node or a vertex.

Â Uh, each connection between a pair of nodes,

Â would be called an edge,

Â and the value along an edge is called the edge weight.

Â Also, when I say that A is adjacent to B,

Â this means that A has an edge that connects it to B, directly.

Â Typically, an edge only goes between,

Â uh, uh two nodes or two vertices.

Â An edge does not cross three, uh, nodes.

Â So here, for instance, I have, um, uh, 1, 2, 3, 4, 5 vertices,

Â and how many edges do I have?

Â I have an A-E edge, an A-B edge, a B-E edge, a B-C edge

Â and a C-D edge,

Â so, I also have, uh, five, uh, different edges,

Â each with its own, uh, edge weight.

Â 23:17

So, in this, uh, lecture, we have covered,

Â the basic data structure, such as, uh, queue and a stack,

Â we have seen that processes are programs in action,

Â and that they consist of multiple different pieces,

Â uh, processes of course are under computer architecture,

Â and it's important for you to know,

Â at least, a simplified version of the computer architecture,

Â so that you know what's, ah, operating where,

Â uh, when you run a process.

Â We've seen some mathematical topics,

Â such as, Big O notation

Â which, analyzes the worst case performance

Â of any given algorithm,

Â and then some basic probability.

Â And finally, we have seen a few miscellaneous topics.

Â I hope you can come back- keep coming back to this,

Â as a reference, whenever you need it,

Â uh, throughout, uh, the, uh, course.

Â