DEV Community: Shilpa Jain

Stacks in a (food)shell

Shilpa Jain — Wed, 21 Feb 2018 12:39:57 +0000

Welcome back, daredevils! I see you like to live dangerously.

If you’ve no idea about I am talking about, you should check out this post before reading this article.

The goal of this data structures series is to ruin your life(for good) by thinking and applying data structures to real life setting. It will not introduce you to the practical world of programming, but a mastery of the concepts will provide a start toward understanding the nature of computation.

Let me start this series with simplest of all yet among the most important data structure – ‘Stacks’. In recent times, this word is being used everywhere. Be it about companies looking for full stack developers to startups sharing their tech stacks.

So what is a stack, exactly?

Before I proceed with the explanation, let me give a fair warning. This article is not advised for people who are on dieting.

Food appears in many of our examples for simple reasons:

First, food is easier to visualize than complex codes & abstract symbols.
Second, I want to provide you with a little distraction. They can get on your nerve at times, and a little distraction will help you keep your sanity.

** Prerequisite For This Article** :

The reader must be comfortable reading English and must be pro at controlling food cravings.

What the heck is Stack?

Although the word has different meanings — in programming, the stack is a collection of objects(data) that are inserted( pushed ) and removed( popped ) according to the last-in, first-out ( LIFO ) principle.

I hear you say this was a bit complicated. Don’t worry, brace yourself for (food) example to simply this.

Source: Pringles Website

Let’s talk about Pringles tube today. If you observe closely, Pringles tube is nothing but a stack of potato chips. The last chip to go in the tube during packaging is the first chip to go in our stomach while eating.

You simply can’t have chips at the bottom of the potato tube before eating the chips present at the top as the tube has a single opening at the top.

You see what I did there?

Well, resisted the urge for having the Chips and taught you crucial concepts of Stacks.

If you go back and see the definition of the stack earlier, you’ll see I have bolded few terms push, pop and LIFO. Let’s try to connect the dots now.

Additions (push) & Removals(pop)

Just like we add(push) and remove chips(pop) from the top of the Pringles tube, in Stacks you add and remove just from one end i.e. from the top only.

Last item In is the First item Out (LIFO)

Just like you can’t have chips at the bottom without finishing the upper ones, the item which was pushed in the stack last will be the first one to be taken out.

The fundamental operations of Stack are as follows:

push(element) — Adding new elements at the top of the stack
pop()— Removing/Returning element from the top of the stacks
peek()/top() — Returns a reference to the top element of the stack
is_empty() — Returns Boolean true is the stack has no elements
len(stack)– Returns the number of elements in the stack.

Yes, Yes…I hear you say I just explained first two methods to you.

Let’s take another example to understand rest of them.

Say you have a stack of pancakes(an organized pile, one on top of another).

Peek/top :

One should eat one pancake at a time. Any more than that at once, and you don’t get enough syrup on them.

So, you’ll use peek/top function on the stack to get the topmost pancake.

Is_empty :

I am sure you are wondering who eats one pancake at a time. Together (stacked), with a layer of syrup applied to the top of each one is a proper way to eat this stack of cakes. Let’s say I ate the entire pancake in one go. Now, if someone asks me is there any pancake left, I’ll turn my head to say no.

Similarly, this is_empty function tells us the status of elements in the stack. If the stack is empty, it will return true otherwise false.

len(stack) :

If I call this function on our pancake stack, it will merely return a number of pancakes (5 in our case).

And here we are. At the bottom of the stack.

There are two ways to implement a stack:

Using array
Using linked list

Like I mentioned at the beginning of the article, this article aimed at covering concepts of the stack. I will cover the code implementation with this data structures in future articles.

That being said you can go ahead and get your bellies full now.

See you soon!

Thanks for reading! If you liked this post, you can check out my other writings here or please consider entering your email here if you’d like to be added to my once-weekly email list or follow me on Twitter

The Ultimate Beginners Guide To Analysis of Algorithm

Shilpa Jain — Tue, 06 Feb 2018 16:45:58 +0000

The other day, I came across a post on StackOverflow which read “Is theoretical computer science(TCS) useful?”. I was completely caught off guard because, well, I was in the middle of a learning about asymptotic behavior complex math notations and couldn’t think of one use-case where I could apply it to my day-to-day coding. This post made me think “Why do I even need to know about theoretical CS if it is not used practically. Especially when my natural interests and abilities lie more in programming than in mathematical analysis.

So over the weekend, I did some research. Why is this important? Is the scope of the concepts I am learning everyday restricted only to answering algorithms complexity interview questions? What about their application after that?

There has to be more!

Is Theoretical Computer Science(TCS) useful?

Big YES!

TCS isn’t only about mathematical analysis or should be learned by programmers only for a job interview. If you plan to make a career as a programmer, your job will probably involve not just building coolest and most useful software today, but building it in a way that makes it useful and most efficient to use. You will also have to think about how and why what you are doing works, as well as in which bounds it operates.

It’s like in the Karate Kid movie scene with Jackie Chan and Jaden Smith. Here, Jackie Chan tells Dre to put on and take off his jacket, over and over again.

So, do you think Jackie was teaching him how to put on his jacket and take it off? NO! He was teaching him the skills necessary to become highly successful in kung-fu.

This is what TCS does for us. It lays a solid foundation of fundamental abstract concepts which help us make the right choices as a developer.

In this article, targeted at programmers who know all about coding but who don’t have any TCS background, I present to you one of the most important theoretical concepts of computer science: After reading this post, you will be able to understand all the common terms computer scientists use such as “algorithms”, “algorithm complexity analysis”, “Big Θ”, “asymptotic behavior” and “worst-case analysis”.

This post does not have any mathematical prerequisites and I plan to build a firm basics background needed to study different algorithms with a firmer understanding of the theory behind them.

Let’s get started!

A) What is an Algorithm?

An Algorithm can be defined as a list of steps that you can follow to complete a task.

You might be thinking, well, that was a bouncer. Didn’t the title read something like a beginners guide to study of algorithms?

Okay! Let’s take an example to simplify the definition. Let’s say I want to shop for a book online. Read the definition again after going through the below example.

BuyBook(bookname){
 1. Open Amazon
 2. Search for the bookname
 3. If in stock, add to the cart
 4. Proceed with checkout process
 5. Wait dearly for your book to be shipped
}

BuyBook('Into The Water')

So, I want to buy a book named ‘Into The Water’ online. So, the first thing I did was visited Amazon. I searched on Amazon for my book, ‘Into the Water’ and found it was in stock. I proceeded with adding to the cart and with the final checkout process. Done!

Can you try to connect the dots with the definition now?

What I did above was followed a series of steps in order to achieve some goal(buying book in our case). This is what algorithm primary purpose is

or see the below graphic! 😉

Source: 1stWebDesigner

Okay then.

B) What is an analysis of algorithm? Why do we even have to analyze them?

Analysis of algorithms can be defined as a theoretical study of computer-program performance and resource usage.

So, I’ve written word performance in above definition in bold words. Simply because our main focus throughout this article would be about computer program performance.

But, before we start talking about it, can you think of any other thing more important than the performance in programming?

Um, like the program maybe super-duper fast, but gives wrong output?

Will this work? No!

There are many things like correctness, simplicity, maintainability, robustness, security, functionality and most important user-friendliness which is way more important than the performance of the program.

Example: Snapchat CEO Evan Spiegel plans to redesign Snapchat.

The Snapchat app works as it is supposed to be, but still, Evan Spiegel plans to redesign it. Because based on feedback, they found out the app was a little hard to understand and they plan to improve it by making it easier to use. Here, user-friendliness clearly outweighs algorithms.

So, clearly, performance lies at the bottom of the heap as compared to above -mentioned features. Then, why am I writing a post about performance then?

Because sometimes user-friendliness is directly related to performance.

I’ll just wait here. (Source:imgflip.com)

Imagine sitting in front of the website which takes forever to load. Often, performance measures the line between feasible and in-feasibility. In real time setting, if an application is not fast enough, it is simply not functional. Or if it uses too much memory, it is not going to work for us.

Armed with this knowledge, let’s try to analyze a simple problem of sorting:

Now, we are going to use an algorithm called Bubble Sort. I’ll write this algorithm in pseudo-code(kind of programming language written in English)

Bubblesort( var a as array )
    for i from 1 to N
        for j from 0 to N - i
           if a[j] > a[j + 1]
              swap( a[j], a[j + 1] )
end func

Here, the input will have a sequence of numbers and output will give a sorted list of numbers. The function Bubblesort accepts an array of data as input and will generate a sorted list of numbers.

Difficult to comprehend? Let’s take a simple example

Here our input to our BubbleSort function is {6, 5,3}. We want our algorithm to give us our desired output, sorted list like this {3,5,6}

How our algorithms works:

Round 1:

# Our aim to to sort our list from smallest to largest. If we find numbers out of order, we swap them.

# Start with first element and compare it with next.
{ **6, 5** , 3}

# Compare 6 and 5. Since 6 > 5 -> Perform swap
{5, 6, 3}

# Now,look at second and third element and compare.
{5, **6, 3** }

# Compare 6 and 3. Since 6 > 3 -> Perform swap
{5, 3, 6}

# Round 1 output:{5, 3, 6}
# The list is still not sorted.

Here, we start off by comparing first and second number, 6 and 5 in our case and swap them as they are out of order. We proceed with comparing 2nd and 3rd element,6 and 3 and swap them too as 3 is a smaller number than 6. We continue this till we reach the last element and we get a list {5,3,6} like this.

The list is still not sorted and we continue with the similar approach till the entire list gets sorted.

Round 2:

# First round gave us list {5, 3, 6}. We continue with our steps of comparing and swapping if we find elements out of order.

# Start with first element and compare it with next.
{ **5, 3** , 6}

# Compare 5 and 3. Since 5 > 3-> Perform swap
{3, 5, 6}

# Now,look at second and third element and compare.
{3, **5, 6** }

# Compare 5 and 6. Since 5 < 6 -> NO SWAPPING
{3, 5, 6}

# The list is sorted now. We got our desired output.

Our List is finally sorted.

Simple, right? (In case, you are finding it difficult to understand Bubble Sort or want to know more about it, I’ve covered all its nitty-gritty in this post

C) Let’s analyze the above algorithm

Every developer has time running on their mind. How long will my program take to give me my desired output?

But the running time of the algorithm is dependent on many things:

Depends on Input :

Now let’s say the input list({3, 5 , 6})given to our Bubble sort was already sorted. In this case, Bubble sort doesn’t have much to do. But, what if the input list(6,5,3) is reverse sorted. Bubble sort will have to do a lot of work to give us a sorted list as each element needs to be swapped.

Depends on the Input size :

Now imagine sorting a list with 6 elements vs a list having 6 * 10⁹ elements. Which program will give us a faster-sorted list?

So, when we talk about analyzing an algorithm with running time, we generally look at the upper bound. For example, If I say this algorithm will not take more than 3 seconds to execute, we have a max limit and we know how this will work in real life setting. This upper bound gives a guarantee to the user that time taken to accomplish this task will be no more than this amount.

Different Type of Analysis Done :

In analyzing an algorithm, rather than a piece of code, we will try and predict the number of times “the principle activity” of that algorithm is performed. For example, if we are analyzing sorting algorithm like Bubble Sort, we might count the number of comparisons performed.

Worst case (Done usually):

In the worst case analysis, we calculate upper bound on running time of an algorithm. It is generally a case that causes a maximum number of operations to be executed over all inputs of size n. For example, in Bubble sort, a maximum number of comparisons takes place when the array list is reverse sorted.

2) Average case: ( Sometimes done )

Arguably, average case is the most useful measure. Unfortunately, this is typically a difficult thing to measure. In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by a total number of inputs. We must know (or predict) distribution of cases throughout all data sets of size n.

3) Best Case : (Not Generally Used)

In the best case analysis, we calculate lower bound on running time of an algorithm. It is a case that causes a minimum number of operations to be executed from an input of size n. For example, we might get the best behavior from Bubble sort algorithm if the input to it is already sorted.

Algorithm Complexity:

So, let’s try to calculate Bubble Sort worst-case time? Let’s try to formally measure how fast this algorithm runs.

But where should I run this algorithm? Your computer or mine? Wait, if I run it on a supercomputer, it will run super-duper fast.

BIG PROBLEM!

We clearly need something which compares two algorithms at the idea level ignoring low-level details such as the implementation programming language, the hardware the algorithm runs on etc.

Showtime! Asymptotic Analysis!

Here, we ignore machine dependent constants and instead of looking at the actual running time look at the growth of running time.

Wait! Whaaaaaat?

Trust me read this definition again after going through the below example.

The following 3 asymptotic notations are mostly used to represent time complexity of algorithms.

1) Θ Notation (Theta notation)

2) Big O Notation

3) Ω Notation (Omega notation)

Let’s take a look at Θ Notation to understand how it solves our problem.

The Θ Notation notation follows simple two rules:

Drop low order terms
Ignore leading constants.

Consider this example:

3n³ + 40n² - 10n + 409

# Let's look at Θ Notation first point, drop lower order terms
# Here, n^3 is a bigger term then n2. So we drop all lower order n terms and 409

# Now, our equation looks like 3n³. Let's look at second point now. Ignore leading constants. So, we drop 3 too.

#so, we finally get n³

3n³ + 40n² - 10n + 409 = Θ(n³) #Theta of n cube

# This is an engineering way of manipulating theta notation. 
# There is a mathematical way too

We call this function, i.e. what we put within Θ( here ), the time complexity or just complexity of our algorithm.

As n approaches infinity, Θ(n²) will always beat Θ(n³). It doesn’t matter what lower order terms or leading constants were. Even if you run Θ(n²) algorithm on slower computer and Θ(n³) algorithm on a faster computer, when we look at the growth, as the size of n increases, Θ(n²) algorithm will be faster.

In complexity analysis, we only care about how many times our the principle activity of our algorithm is performed as the program input (n) grows large. This is in line with our “worst-case scenario” behavior. If algo1 beats algo2 for a very large input number n in time, it’s obvious that it will do so even when the size of input n is small. So, considering this, we’ll drop all the terms that grow slowly and only keep the ones that grow fast as n becomes larger.

This filter of “dropping all factors” and of “keeping the largest growing term” as described above is what we call asymptotic behavior.

Oh Boy! How Big This Post Is!

Just concluding it. I have introduced two more notations Big O and Omega Notation in above section. Big O is highly popular as it deals with upper bound of an algorithm(Remember our worst-case time complexity). I’ve covered it in another post, do have a look!. (It isn’t as long as this post, I promise!)

Closing Notes:

Thanks for reading! After reading this post,(I hope)you understand terms like “algorithms”, “algorithm complexity analysis”, “Big Θ”, “asymptotic behavior” and “worst-case analysis”.

I publish things I learn daily here or you can follow me on Twitter .

Resources Used For This Article:

https://www.geeksforgeeks.org/analysis-of-algorithms-set-1-asymptotic-analysis/

http://discrete.gr/complexity/

https://www.youtube.com/watch?v=JPyuH4qXLZ0

Big-O Notation — Learning Through Examples

Shilpa Jain — Mon, 05 Feb 2018 15:11:18 +0000

Big O notation is used to describe or calculate time complexity (worst-case performance)of an algorithm. This post will show concrete examples of Big O notation.

After discovering that complexity of the algorithm won’t be taken into consideration on the exam. (Source: Reddit)

A few things to note

This article was written with intermediate developers in mind and assumes you already know a bit about time complexity, worst case behavior.
If this word doesn’t ring a bell, I wrote a comprehensive guide here (free article).

Real-Life Big-O

Many “operations” in real life can help us with finding what the order is. When analyzing algorithms/operations, we often consider the worst-case scenario. What’s the worst that can happen to our algorithm and when does our algorithm need the most instructions to complete the execution? Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.

Let’s assume I am standing in the front of a class of students and one of them has my bag. Here are few scenarios and ways in which I can find my bag and their corresponding order of notation.

O(n) — Linear Time:

Scenario: Only one student in my class who hid my bag knows about it.

Approach: I will have to ask each student individually in the class if they have my bag. If they don’t, I move on to ask the next student.

Worst-Case Scenario: In the worst case scenario, I will have to ask n questions.

Show me the code!

Explanation:

Here, given an input of size n, the number of steps required is directly related to the amount of data it is processing.
Single for loops, linear search are examples of linear time
In above example, an array size/input size increases, time to find desired value also increases.

O(1) — Constant Time

Scenario: Student who hid my bag name is known to me.

Approach : Since I know Joe has my bag, I’ll directly ask him to give it to me.

Show me the code!

Explanation:

Here, given an input of size n, it only takes a one step for the algorithm to accomplish the task.
An algorithm takes same time(constant time) to execute irrespective of the amount of data.
This algorithm is not affected by the array size either.

O(n²) — Quadratic Time:

Scenario: In the entire class, only one student knows on which student desk my bag is hidden.

Approach: I will start questioning each student individually and ask him about all the others students too. If I don’t get the answer from the first student, I will move on to the next one.

Worst-Case Scenario: In the worst case scenario, I will have to ask n2 questions, questioning each student about other students as well.

Show me the code!

Explanation:

Here, given an input of size n, the number of steps it takes to accomplish a task is square of n.
Each pass to outer loop O(n) requires going through entire list through the inner-loop.
Nested for-loops are example of quadratic time as we run a linear operation within other linear operation

O(log n) — Logarithmic time:

Scenario: Here, all the students know who has my bag but will only tell me if I guessed the right name.

Approach: I will divide the class in half, then ask: “Is my bag on the left side, or the right side of the class?” Then I take that group and divide it into two and ask again, and so on.

Worst Case Scenario: In the worst case, I will have to ask log n questions.

Show me the code!

Explanation:

Here, given an input of size n, the number of steps it takes to accomplish the task are decreased by roughly 50% each time through the algorithm.
O (log N) algorithms are very efficient because increasing amount of data has little effect at some point early on because the amount of data is halved on each run through.
Binary search is a perfect example of this.

Closing Notes:

Thanks for reading! I publish things I learn daily every single weekday here or you can follow me on Twitter .

Here are some helpful resources to learn more: