0:23

So we'll be covering several of the basics that are considered to be basics

Â in computer science.

Â Typically some of these concepts are concepts that computer science

Â students learn in their first couple of years in a computer science degree,

Â undergraduate degree program.

Â So for those of you who are already familiar with this material this could be

Â a refresher, or you could just, skip it if you already know the stuff.

Â In any case you can always use this orientation lecture as a reference

Â to keep coming back to if you encounter a term in regular

Â lectures that doesn't make sense to you, or that you'd like to be reminded about.

Â 1:17

So basically, the instructions will discuss two 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 any data types.

Â In this example here, I have elements that are integers, so

Â in this example right now, the queue has five elements, 3, 5, 8, 0, 7.

Â This is an ordered list of elements.

Â When you remove and element from the queue,

Â you remove it from the head of the queue.

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

Â When you insert a new element, you insert it at the tail of the queue which means

Â that if I insert a new element,

Â say 1, it's going to get inserted right after 7 in this queue.

Â 2:00

So, for instance, given this particular queue, consisting of five elements.

Â If you, if you dequeue or remove an item then that item will be 3.

Â 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 5.

Â After that the queue will cut to 8, 0, and 7.

Â And then the next item dequeued will be 8 and so on and so forth.

Â Dequeues or removals as well as insertions can occur concurrently.

Â You can remove an element while at the same time also insert

Â an element at the table.

Â 2:36

So, that's a queue, which is a first-in, first-out datastructure.

Â A different data structure is the stack,

Â which is a First-in Last-out datastructure.

Â Imagine a stack of dishes that you place on your table.

Â The dish that you put on the top, that you add the last,

Â will be the first one that you can remove.

Â All right, and that's essentially a stack.

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

Â An inserter push also happens at the top.

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

Â particular stack say 9, then 9 will go above 3.

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

Â that's going to be the last element that you added, which is 9 in this case.

Â The next pop after that will get 3 because 9 was just removed and

Â 3 is now the top of the stack.

Â 3:21

After you're able to move three the next pop or removal will get you 5, 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 insertion or a 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 in fact, we'll be using the notion of the stack right away when we discuss

Â processes soon in this particular orientation lecture itself.

Â 3:51

What is a process?

Â A process is essentially a program in action.

Â For instance, you might write a program in a language like C, C++, Java.

Â Are you know Python or Ruby on Rails.

Â Whatever it is, it doesn't matter what the language is.

Â And when you execute that program, say from the command line or

Â from a gui, that executing program is called a process.

Â For instance here I have C like program.

Â Which has a function main.

Â Which in turn call a method f1.

Â Which in turn call a method f2.

Â This is shown pictorially here.

Â A main calling f1, calling f2.

Â When you instant shared this program and

Â execute it, it becomes a process, which in this case is labeled as P1.

Â So this code part showing here is only the program itself,

Â the process itself consists of multiple other components.

Â The code typically doesn't change but the other components might change.

Â What are these other components?

Â Let's look at them one by one.

Â First of all there is a program counter,

Â which is an index into the code which says where the program is right now, what is

Â the exact line number within the code where the program is executing right now.

Â Next you have a stack,

Â which is used by the functions to pass arguments and return values.

Â For instance when main,

Â main function calls F1 any arguments that it needs to pass to F1 are call,

Â are passed by the stack by pushing an element on top of the stack.

Â F1 can then pawn that element off and

Â obtain the arguments that are passed to it.

Â Similarly when F1 calls F2 it then pushes on top of the stack, the arguments that

Â it has for f2 and f2 can retrieve these arguments by popping the top of the stack.

Â When f2 is done, it can return the return values to f1 also by pushing

Â the return values on top of the stack.

Â So that when f1 resumes,

Â it can pop the top of the stack to obtain the return values from f2.

Â Similarly, f1 returns its return values to me by pushing on top of the stack.

Â Now, the functions themselves might declare variables.

Â Some variables will be local variables.

Â And local variables are also to begin maintaining on top of the stack.

Â I'm not showing them here.

Â And this is the reason why when a functional method is completed

Â in its execution, any local variables that are declared inside are then gone,

Â because that part of this tack has been popped.

Â In addition function, but also create new memory by, for instance,

Â calling malup or new.

Â In this case I'm showing such a variable x.

Â And such variables are stored in a separate data structure,

Â associated with the process known as the heap.

Â 6:14

Also associated with a, a heap are also registers, which typically refer to

Â the recently accessed variables in the in the process itself.

Â So, for instance, this variable x is is present in the heap.

Â Such or new variables need to be explicitly freed in most cases.

Â However some programming languages have automatic garbage collection.

Â Now the reason we are discussing a process here is

Â really the main reason is that when we talk of distributed systems,

Â we are going to talk of multiple processes communicating with each other.

Â And we'll mostly focus on a process to process communication,

Â although later on we'll also talk about how procedure calls or

Â function calls can cross process boundaries.

Â In addition, the other reason we are discussing a process here is that when you

Â take a snapshot of a process, when I say a process takes its own snapshot,

Â this essentially includes everything that I'm showing here on the slide and

Â maybe a few more elements.

Â It includes the code, the program counter, the current status of the stack.

Â The current status of the heap and the registers and then a few other elements.

Â Essentially, this information is enough to resume this process from here onwards.

Â Okay speaking of computer architecture,

Â let's discuss a simplified version of computer architecture.

Â Computer architectures today can be very complicated but typically when we,

Â when we think of how a process executes on a computer architecture.

Â Again, think of a simplified view.

Â So there's a CPU which executes the actual instructions which are present in

Â your code.

Â There are also a bunch of registers that are co-located with the CPU.

Â These are small pieces of memory that can be accessed very quickly by the CPU.

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

Â Typically not more than a few tens of registers.

Â There's also a cache which is a slightly larger memory than the collection of

Â registers.

Â And the larger a mem, piece of memory is the slower it is to access it, so

Â accessing a cache is slower than registers.

Â Than accessing registers, but accessing the cache is still pretty fast.

Â Then beyond the cache there is the main memory or the random access memory or

Â the RAM which is even larger than the cache and the ca, and the memory itself,

Â therefore, is slower than the cache, but still it's pretty fast.

Â And then finally, there's a hard disk, or if you would like,

Â a solid stave, state drive, a flash drive or whatever.

Â Which is a lot more memory than the main memory 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 storage space that you have decreases.

Â 8:35

So when you write a program such as C++ or Java or C and you compile it,

Â it get compiled to low-level machine instructions.

Â The machine instructions might be specific to the architecture the machine on which

Â you are running or it might be a virtual machine like a JVM kind of code.

Â Any case these low-level instructions are the executable version of your program.

Â And this is stored in file system in the file system, on, on you desk.

Â When your program starts executing, when it becomes a process.

Â The CPU loads instructions in batches or in a simplified,

Â more simplified way, it loads instructions, one by one.

Â 9:47

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

Â that you have 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 you may want to write those updates to the file onto the disk.

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

Â Computer architectures can be far more complex than this today, but for

Â our practical purposes in this course and as far as explaining how processes work.

Â This will suffice.

Â 10:20

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 come up with, at the least a Big O notation and

Â analysis of that algorithm.

Â The, the Big O notation describes and upper bound and

Â the behavior of an algorithm as some variable is scaled or

Â increased in value to all the way to infinity.

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

Â Maybe the number of input elements.

Â 11:36

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

Â A takes less than c times foo time to complete, as you mean time is the metric

Â we are measuring, for some constant c, a fixed constant c, beyond sum input size N.

Â Okay, typically this foo that is the present of this definition is

Â some function of input size N.

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

Â which means that the algorithm A takes less than C times N, time to complete for

Â some constant C be on some input size N.

Â So the algorithm might be order N squared which means that.

Â It is quadratic in time.

Â And it takes time less than c times n squared for some constant c.

Â Once again, when we say O(N2) or O(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, concerned.

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

Â 12:35

So let's see a couple of examples.

Â So first I give you an unsorted list, 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 element at a time, and search for

Â the element by trying to match it with each element already present in the list.

Â What is the worst case performance?

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

Â So the worst case performance happens either when the element is not there,

Â at all in the list, so you return a false.

Â Or the element the very last one in the list,

Â the very last one that you match against.

Â Therefore the worst case performance involves N operations, and

Â the number of operations involved is less than C times N.

Â Where c equals 2,

Â because the number of operations is N, where N is the size of the list.

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

Â assuming each operation takes one unit of time, both the time taken for

Â this, for this algorithm, which I trace through the list.

Â As number of operations are both order N.

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

Â 13:34

Let's take a different 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 say integers, and this is unsorted and

Â I ask you to solve them say, in increasing order of the elements.

Â The insertion sort 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 that element in the new list at the appropriate position.

Â Essentially, you sort through the new list linearly, searching for

Â the right position where this element should be.

Â 14:31

Similarly the third element will take three operations to insert.

Â Where the first two elements compared with the two already existing elements.

Â And the third operation inserts it at the very end of the of the list.

Â If you go on like this and the i-th element takes i operations to insert.

Â And you can calculate the total time required.

Â To insert all the elements as 1 plus 2 plus 3, so on til N.

Â And this is a well-known sum which comes to N times N plus 1 divided by 2.

Â Which is, less than 1 times N squared.

Â So with the value c equals 1, this,

Â insertion sorting example is an algorithm that takes order N squared in time and

Â also order N squared in number of operation.

Â 15:15

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

Â Before probability, we need to discuss a few definitions.

Â The first definition is a set.

Â A set is essentially a collection of things.

Â So, for instance, a set, S,

Â might be a set of all humans who live in this world at this current point.

Â A subset is another set,

Â which is a collection of things that is a part of the larger set.

Â So I might design, describe a set S two which says a set of all humans

Â who live currently in Europe today.

Â S two is a subset of S because, every element that is present in S two is

Â also present in S but the reverse is not necessarily true.

Â 15:52

Okay, so now probability.

Â Any, any event has a probability of happening, 'kay?

Â So let me give you an example.

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

Â So you just wake at some random hour of the day.

Â Say you have jet lag or something.

Â And I ask you what is a property that the event at the time is between 10 a.m.,.

Â . and 11 a.m.

Â Let's try to calculate this.

Â 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 to 10 a.m.,

Â . 11 a.m.,.

Â . 11 p.m.

Â Okay, so when I say, and I limit like 1 a.m.,

Â . I mean the hour between 1 a.m.,.

Â . and 1:59 a.m.

Â Similarly, 10 a.m.

Â Means between 10 a.m.

Â And 10:59 a.m.

Â Out of the set upgrade for 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 in the set.

Â And the probability that you pick that one special element 10 a.m.

Â Is one over 24 because you, you want to pick, you want to be lucky.

Â Of that, to pick that ten.

Â So the probability that if you wake up at a random hour of the day and

Â the time is between 10 a.m.

Â And 11 a.m.

Â Then that probability is 1 over 24.

Â Now there will be multiple events and you might need to calculate the probability of

Â 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 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 hand into your closet and you blindly pick out a shirt.

Â What is the probability that you woke up between 10 a.m.

Â And 11 a.m.

Â And that you picked a green shirt to wear?

Â Well the probability that you woke up between 10 and

Â 11 is essentially 1 over 24.

Â Like we calculated on the previous slide.

Â The probability that you picked the green shirt is essentially one out of three

Â because there are three colors of shirts.

Â You have three shirts.

Â And you want to pick the green one.

Â You want to be lucky to build the green one so that's one over three.

Â So the probability that both these elements 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 over 24 times 1 over 3.

Â And that gives you 1 over 72.

Â One of the things that you have to be careful about here is that if E1 and

Â E2 are not independent, meaning that they influence each other in some way.

Â Then you can not multiply the probabilities with each other.

Â Okay, so for instance if

Â 18:54

A different thing that we need to do with two event probabilities is to OR them.

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

Â I ask you the probability that of either E1 or E2 happening.

Â Then you can see that the probability of E1 or E2 is the probability of E1 plus

Â the probability of E2 minus the probability of E1 and E2.

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

Â If you do not now the probability of E1 or E2.

Â This last term over here.

Â Then you can write the inequality probability of E1 or E2 is less than or

Â equal to the constituent probabilities.

Â Okay.

Â Sometimes we use these inequalities to upper bound the,

Â properties of the of these junctions as we see here.

Â DNS refers to Domain Name System.

Â It's essentially a named resolution system.

Â It is run as a collection of servers throughout the world,

Â and it helps you to translate URLs, actually domain names into IP addresses.

Â So the input to the DNS is a domain name so just Coursera.org and

Â this is human readable string that uniquely identifies the object.

Â So we humans can easily remember a name like Coursera.org.

Â Actually we do need to remember URLs like class.coursera.org/foo and when you enter

Â this into your browser, your browser extracts the domain name from this URL and

Â then sends this off as a query to the DNS system.

Â 20:11

The DNS system then returns to you the IP address of a web server

Â that potentially hosts that content.

Â And an IP address is essentially a target, or an address, or

Â an ID, and it is a unique string that points to the object.

Â The difference between an ID and a name.

Â The output and the input to a name resolution system like DNS is

Â essentially that IDs are harder to remember.

Â It's harder for us human beings to remember IP addresses.

Â It's much easier for us to remember names.

Â Also, IP addresses change, but names don't.

Â Now, IP addresses might refer, might refer to a actual web server,

Â a unique web server that actually hosts content, so that now your client.

Â A browser can send a, DCPN ACDP request to that server.

Â Or it might refer to an indirect server or even a group of servers,

Â such as in a content distribution network, as it is from Akamai.

Â The fun thing about name resolution systems is that they can be changed, so

Â the ID or the address obtained from one name,

Â named resolution system can be given as a name to another named resolution system,

Â and that can return a different address, and so on and so forth.

Â And you can keep doing this until you, reach your final object itself.

Â 21:14

Graphs.

Â So when we say graphs in computer science, we don't necessarily mean plots,

Â which have x and y axes.

Â A graph is essentially a network.

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

Â Chicago, Delhi, and Edmonton.

Â And the travel times between those cities by air.

Â Rounded out to the nearest hour.

Â Okay, so travelling from Amsterdam to Boston takes about six hours.

Â Travelling from Chicago to Delhi takes about 14 hours.

Â Say these are the flights available on some particular airline.

Â 22:12

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 two nodes or two vertices.

Â An edge does not cross three nodes.

Â So here for instance I have one, two, three, four,

Â five, vertices and how many edges do I have?

Â I have an AE edge, an AB edge, a BE edge, a BC edge and a CD edge,

Â so I also have five, different edges each with its own, edge weight.

Â 22:46

So, in this lecture, we have covered the basic datastructures,

Â such as a cube and a stack.

Â We have seen that processes are programs in action, and

Â that they consist of multiple different pieces.

Â Processes, of course, are done 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 operating where when you run a process.

Â We've seen some mathematical topics such as big O notation which analyses the worst

Â case performance of any given algorithm, and in 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 throughout the course.

Â [MUSIC]

Â