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.

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.

So, we'll discuss a few topics.

We'll discuss
some basic data structures,

uh, what processes are.

We'll discuss a little bit about
computer architecture,

and then, um, a little bit
of math with Big O notation,

basic probability

and a few other
miscellaneous topics.

So, let's get started here.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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?

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.

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.

Therefore, the
worst case performance

involves N operations,

and the number of operations involved is < c* N, where c=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,

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.

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.

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.

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.

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.

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.

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.

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.

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.

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?

Sometimes we use these
inequalities to upper bound,

uh, the, uh, probabilities
of the, um, uh, disjunctions,

as we see here.

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.

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.

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.

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.

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.