21 May 2015

Nanotechnology: An Introduction


Nanotechnology! Nowadays, almost any student claims to have an interest in becoming a scientist, working in laboratories, playing with atoms, fiddling with molecules, and on and on. Well, let me tell you one thing. If you fall in that 'almost any kid' category, then you might just end up finding nanotechnology exciting.

Nowadays in nanotechnology, things that were only “dreamt of”, are turning into a reality. But before we delve into the science of nanotechnology, let me point to you some exciting ways in which nanotechnology is being used today.

Have you ever “dreamt of” an invisibility cloak? Well if you have, then I suggest you stop dreaming because now invisibility cloaks have become a reality.

One other recent cutting edge invention is the “Ultra Ever Dry” product. And what this does, is that it does not allow any liquid irrespective of its viscosity to stain a substance on which the product has been sprayed on. The “Ultra Ever Dry” coating, creates a thin barrier of air at the nano scale, which prevents the coated substance from getting wet or dirty. And to see this mind-boggling product in action, you can take a look at:



Apart from this, there is also some interesting work going on in the field of medicine involving nanotechnology, where medical researchers are on the verge of creating an almost harmless cancer therapy which could possibly become a substitute to the standard chemotherapy.

There has been a quantum leap in the development of nanotechnology in the last five years. And from here, things only get better.

So let's get started with nanotechnology.

What is nanotechnology?

At a very high level, I would take nanotechnology as the science, engineering and technology practiced at the atomic or molecular level.

But going slightly deeper, it is a branch of science, which involves the manipulation of at least one dimension of a substance within the nano scale range of 1 to 100 nanometers (1 nanometer = 10-9 meters).

What is unique about nanotechnology?

There are many things that are unique to nanotechnology, though I feel the truly convincing answer to this, lies in the unusual behavioral-changes of substances at the nano scale.

What I mean by this is that substances show rather abnormal properties at the nano scale, which violate the norms of the Physics that we know so well as Classical Physics. We will understand and discuss this in greater detail a bit later.

Interesting concepts in nanotechnology

With this much of a background, I think we all are quite ready to take a look at some of the interesting concepts of nanotechnology!

Two main concepts are:
• Simple to Complex
• Larger to Smaller

Simple to Complex--

One of the most mind blowing concepts in which extensive research is being carried out is the ‘Simple to Complex’ also known as the ‘bottom-up approach’ concept. This concept involves molecular self assembly. In other words, scientists are trying to make molecules automatically arrange themselves into a desirable system.

Some of the fields where this is trying to be developed, is in the field of synthetic chemistry where scientists are trying to achieve self assembly of molecules into substances such as polymers, micro-computing where scientists are almost at the brink of having self assembled microcomputers and biology where substances like enzymes have already been self created!

Two main advantages of developing this Simple to Complex concept are:
• Production will become faster and more efficient.
• Both the purchasers as well as manufacturers will incur less cost.

Larger to Smaller--

As we had discussed earlier, the physical properties of substances begin to be different as the size of these substances start to enter the nano scale. These include differences in mechanical, thermal, electronic and catalytic properties of the substances. These changes, which occur in substances as their sizes are brought down from the macroscopic to the nano scale, constitute the major part of the ‘Larger to Smaller’ concept.

Some examples to give you a flavour of these ‘abnormal phenomena’, which occur among substances at the nano scale are:
• Plastic at the nano scale conducts electricity,
• Gold particles begin to appear red and purple,
• Particles of certain substances turn spontaneously from solid to liquid,
• Copper turns transparent,
• Platinum and Gold become catalysts, and so much more.

Why do substances begin to show these aberrant properties?

This can be explained by the drastic increase in the surface area to volume ratio, which exists at the nano scale. For example let us take a cube of side 8 units, which we will reduce thrice consecutively to an edge length of 6, 4 and then 2 units, and then observe the surface area to volume ratio. Then—

Edge length Surface Area Volume S.A. to V ratio
8 units 384 units2 512 units3 3/4 = 0.75 units-1
6 units 216 units2 216 units3 3/3 = 1 units-1
4 units 96 units2 64 units3 3/2 = 1.5 units-1
2 units 24 units2 8 units3 3/1 = 3 units-1

Now we can clearly see, that by reducing the dimensions of the cube, the surface area to volume ratio is increasing. This is also the case with any other three dimensional object. May it be a sphere, cylinder or cone. But, the more relevant question is how does the surface area to volume ratio cause an alteration in the behaviour of particles at the nano scale?

To understand this, let us continue with the example of a cube. If we take two identical sugar cubes of side = 10 units, and divide one of them into a 1000 equal blocks of 1 unit3 each, and leave the other one untouched, then the volume of the uncut and cut sugar cubes will remain the same. But, the surface area of the cut cube will be clearly larger than the surface area of the uncut cube. Now, if we were to dissolve both the cut and uncut sugar cubes, then the cut cubes will definitely dissolve quicker, as they share a greater contact area with the water as compared to the uncut cube.

It is this same kind of change that takes place in nanoparticles too, but the changes are much more drastic as the surface area to volume ratio in nanoparticles is much larger. Just for example’s sake, let us take a cube of side = 10-9metres or 1 nanometer. Then—

Surface Area = (10-9)2 x 6
=> (6 x 10-18)nm2

Volume = (10-9)3
=> 10-27nm3

Therefore the surface area to volume ratio = 6 x (10(-18)/10(-27))
=> 6 x 10(-18+27)
=> 6 x 109
=> 6,000,000,000 or Six billion nm-1!

And it is this huge surface to volume ratio, which causes abnormal properties in nanoparticles.

All of this is just the beginning of our understanding of the fast evolving field of nanotechnology. Some of the references I have provided below can help you understand more about this exciting field. If you have found anything interesting in the space and would like to share it, post a comment!

References:
1. http://www.nano.gov/nanotech-101/what/definition
2. http://science.howstuffworks.com/nanotechnology.htm
3. http://www.livescience.com/33816-quantum-mechanics- explanation.html
4. http://www.gizmag.com/invisibility-cloak-hides-macroscopic-objects/37542/
5. http://www.nano.gov/nanotech-101/special

12 May 2015

Coding Contests: Everything you need to know

What in the world is a Coding Contest??

It's a contest where you write code.
Okay, it's a contest where you're given a question, then you type your code and send it to the organizers. Then, your program is tested with different input to make sure you got it right.

What do you mean by "tested"?

The contest organizers have their own programs called graders, which run your program multiple times with different inputs. If the output of your program matches the correct answer in all cases, your program is correct!

But I thought a human tests my program. I even gave helpful output hints for the user like "Enter the number here: "!

Nope, humans usually don't test the code. In fact, if you display those "helpful output hints for the user", your program is wrong. Your program's output should match the answer exactly.


How do I know what my output should look like?

Read the question again. Usually, everything you need is specified in the question.
For example, look at SRS 008.

SRS 008

The questions specifies both how the input will be typed, and how the output should look.
If the answer is 2 and 4, like in the Sample Output, display only that. If there's anything else in the output, that answer is wrong.

Your program is being graded by a computer. You don't need to be nice to them! If you still want to include extra comments in your output, be prepared for a "WRONG ANSWER" comment from the grader.

Fine, I got the idea. But how do I take the input? Should I accept the input before anything else in the program is done?

No, you don't have to. The graders separate your input and output into two separate "streams". All the output is collected in one 'file', and the input is from another 'file'.
You can collect the necessary input from anywhere in the program. But you need to accept it in the right order, exactly as it is specified in the question.

Think of it this way. After you send me your code for SRS 008, I first compile it and get an executable. I have some input in input.txt, which I feed into your program. 

input.txt looks like this:
5

I specify that whatever your program displays is saved into a file called output.txt. Then I run your program.

I compare your output from output.txt to the answer output in answer.txt. If they match exactly, then your program worked properly.

You don't actually need to worry about any of this. Contest graders automatically take this into consideration. You can continue to use cin, cout, print, display and any other commands you usually use.

Cool. Can I get started now?

Well, you also need to know about test cases, constraints and time-limits.

[*Sigh*] What are test cases?

The graders test your program with different input. This is to make sure that your program works for every single type of input.
For example, the grader for SRS 008 would test your code with different input numbers, just to make sure that you didn't cheat and make the program display the same output every time. Graders also use multiple input to check if you took care of the constraints.

This is annoying. What are constraints?

The range of the input. For example:

Sample Question
When you submit your code, the grader will test your program for different values of A and B. You know the ranges of the two numbers. You shouldn't have made B an "unsigned int" because it needs to hold negative numbers too. Also, you need to make sure that you use a large enough data-type to accommodate large values of B.

In some problems, where the constraints are extremely large, the contest questions might try to make your life more difficult by adding time-limits...

Come on! What are time-limits?

Calm down! Time-limits just tell you how long your program has to give the right answer. Don't bother too much about this to begin with.
If you ever get a grader error saying "TIME LIMIT EXCEEDED", then your algorithm (the way you solved the problem) was too slow. You'll have to find a way to reduce the number of loops, and optimize your algorithm.

But for now, don't worry too much about it.

Okay, got it. Are we done now?

Yes, we're done.

Finally! Now I'm going to try out SRS 008.

Great! Message me if you have any questions.


1 May 2015

Algorithims:The Basics

Hello people of the internet !! Today You're going to learn a little (if not anything) about algorithms.
So let's start from the basics.....

What exactly is an Algorithm ?

Well Informally it is a computational procedure that takes in a few inputs and throws out another set of outputs. It's basically a bunch of steps that a computer does, which takes in some input data and transforms it into output data.

Algorithms can also be considered a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired Input/Output (I/O) relationship. An algorithm defines a certain procedure for achieving the I/O relationship expected. 

For example let's consider the age old Sorting Problem.
Basically the input is a bunch of numbers given in a random order, and the job of the Algorithm is to SORT these numbers into either ascending or descending order.

In this case what the problem is giving us as inputs is just a random bunch of numbers and asks the Algorithm to weave it's magic and spew these numbers out in a proper ascending or descending order.
This of course is  on the simpler side of this topic but there are many famous implementations of Algorithms.

But why are Algorithms used ?

When we are developing applications,What technologies do we normally prioritize  over others ?
  •  Devs  prioritize GUIs and focus on it's components 
  •  Manufacturers  focus on better fabrication technologies 
  • Some programmers  might even focus on implementing Object-Oriented Systems in their Software life cycle
These technologies are really important for the successful development of an application.

So why implement Algorithms in the first place?

  • The main reason algorithms are prioritized is because they themselves are (explicitly or not), required by applications for certain features. For example a travel web based service will require loads of hardware, refined GUIs and so on....
  • But they would also require certain features such as finding the shortest routes, sorting based on user reviews and other criteria. These are best implemented by using standard algorithms (or something better if you can think of something.)
Not only on an application level are they important, Algorithms are also used to design the hardware required, the working of the GUI itself uses algorithms. In fact even the processing of the code itself by the compiler, interpreter or the assembler requires algorithms.

With the ever increasing capacities of computers, we now have to solve larger problems than ever before, It helps to get the job done quicker and more efficiently and algorithms work much better than just plain brute force methods



let's go over Sort algorithms

Again these algorithms take input data and returns them  in a numerically ascending order or Alphabetical order. For simplicity's sake we will look over numerical examples only

There are many sorting algorithms.Each algorithm is fundamentally different from each other by the way they work. Normally an algorithm is chosen depending on the given data as some algorithms are better for a certain organization of data than others.(this will be explained later)

Three commonly used sorting algorithms are

1)Merge Sort

2)Quick Sort

3)Bubble Sort


Merge Sort:

Merge-sort-example-300px.gif 

Conceptually, a merge sort works as follows:

  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Quick Sort:

http://upload.wikimedia.org/wikipedia/commons/9/9c/Quicksort-example.gif 

Conceptually, a Quick sort works as follows:

  1. Pick an element, called a pivot, from the array.
  2. Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Bubble Sort:


http://upload.wikimedia.org/wikipedia/commons/0/06/Bubble-sort.gif

Conceptually, a bubble sort works as follows:


  1.  Take the first 2 elements and sort them
  2. Then take the 2nd and 3rd elements and sort them
  3. Repeat these steps until the end of the elements are reached
  4. Repeat the following steps until the elements are fully sorted




So these algorithms are basically doing the same thing but in different ways. But one thing that differentiates between algorithms is the efficiency of the algorithm

So how do we determine the efficiency of an algorithm ? This is called the analysis of run time complexity (the words are just fancy, the concept is simple)

We normally consider 3 main representations of Time taken by the Algorithm to Sort in this case

1)Big Ω(Omega) notation(in terms of computer science) -This shows the least amount of time taken by an algorithm to complete. For example the Big  Ω notation of quick sort will be "cn log n" where "n" is the number of elements . This means that the least amount of steps taken by quick sort (most of the the time an already sorted bunch of elements) would be product of the number of elements and the log (base 2) of it and then this is multiplied time the time taken to perform each step 'c'.

2)Big Θ(Theta) notation - This shows the Maximum time taken by an algorithm (in the case of Sorting ones this is normally when the elements are in reverse order). Normally this is the best notation to design algorithms because this also shows that the algorithm is always gonna work in the given time frame and we can more or less decide how fast the algorithm is based on this. For example in quick sort the Big Θ is " cn2"  meaning that the time taken will be the time taken for each step times the number of elements squared.

3)Big O(Oh...) notation-This shows the Average time taken by an algorithm. This is the most common notation used and is considered the standard of viewing algorithms as it gives the viewer a basic idea of how the algorithm works on a normal case. This can also show the the best and worst case but this is beyond the scope of this article. Again in the case of quick sort the big O is "cn log n" (it's called quick sort for a reason. It is considered the most efficient because the average case is the best case).

As I have mentioned earlier  quick sort is the most efficient algorithm for most cases. The reason there are none quicker is because these algorithms are considered to be "stable". The whole process of checking whether an algorithm is stable is a tedious one. But It's a simple mechanic to explain.




So let's just say we are sorting a bunch of cards. Normally if we are taking just the numbers in mind, both the given arrangements are considered to be sorted but if we are also considering the suits also. We must consider that in this case the 5 of hearts must come before the 5 of spades and thus this case of sorting will be considered a 'stable' sort. This sort of sorting takes relatively longer time but gives this desired result and retains other properties also.







The above algorithms were only explained conceptually. Now I want to take it one step further and explain how algorithms are normally expressed by computer scientists. Pseudocode is a high level informal description of the algorithm following basic programming language conventions.


Here's the pseudocode for insertion sort:

 for i = 1 to length(A) - 1
    x = A[i]
    j = i
    while j > 0 and A[j-1] > x
        A[j] = A[j-1]
        j = j - 1
    end while
    A[j] = x
 end for 

This time instead of conceptually explaining The Sort,I will go through the pseudocode line by line 

for i = 1 to length(A) - 1
 
This statement states the starting of a loop which repeats the below statements as many times as the number of elements in the array (the below steps are done to all the elements in the array)

  x = A[i]
   j = i

This statement gives a variable X the value of the the ith term (the current index) and another variable j the value of i for the conditional loop later

    while j > 0 and A[j-1] > x
        A[j] = A[j-1]
        j = j - 1
    end while
    A[j] = x
 end for

Here's where most of the fun happens. so here basically it takes an element and checks whether it's bigger that it's previous element  and the element before that and so on until the first element. And in each iteration switches it the position of the present element with the previous element (if the value is greater).

And then again the whole process repeats with the next number on the array as the index value 


This marks the end of the article and hopefully you have leaned a little bit about algorithms.If anybody has any doubts or want to know more can surely IM me on my G+ account given below


References:
1)http://en.wikipedia.org/wiki/Sorting_algorithm
2)http://www.sorting-algorithms.com/
3)https://www.youtube.com/watch?v=SJwEwA5gOkM
4)Introduction to Algorithms-3rd Edition    



Attributions

  • "Insertion-sort-example-300px" by Swfung8 - Own work. Licensed under CC BY-SA 3.0 via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:Insertion-sort-example-300px.gif#/media/File:Insertion-sort-example-300px.gif 
  • "Sorting stability playing cards" by User:Dcoetzee, User:WDGraham - Own work, based on File:Cards-2-Heart.svg, File:Cards-7-Spade.svg, File:Cards-5-Spade.svg, File:Cards-5-Heart.svg. Licensed under CC0 via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:Sorting_stability_playing_cards.svg#/media/File:Sorting_stability_playing_cards.svg
  • "Bubble-sort-example-300px" by Swfung8 - Own work. Licensed under CC BY-SA 3.0 via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif#/media/File:Bubble-sort-example-300px.gif
  • "Quick-sort-example-300px" by Swfung8 - Own work. Licensed under CC BY-SA 3.0 via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif#/media/File:Bubble-sort-example-300px.gif
  • "Merge-sort-example-300px" by Swfung8 - Own work. Licensed under CC BY-SA 3.0 via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif#/media/File:Bubble-sort-example-300px.gif