Why it is important to study data structures?

-
What are the benefits and why we use to study Data structure and algorithms.

Why it is important to study data structures?

Sometimes it is difficult for students to view where they can apply knowledge that they get during studies. When we (software engineers, developers and etc) were in bachelor degree we learnt a lot of different kind of data structures. Binary Search Tree (BST), AVL Tree, Queue, Stack, Red-Black Tree are the only small part of data structures that we passed.
But after finals most of those data structures, or even all of them will be forgotten. Even if we didn't forget them, we still lack the experience to use them in real application.
Why we need to bother about abstract data structure when we already have implemented array list, vectors, hashmaps in Java (or any other high developed language). 
In this post I would like to give 3 reasons why it is important to learn complex data structures.

Reason #1: Job Interviews

Almost every company, that is hiring a software engineer would ask about data structures or ask you to implement an efficient algorithm for given problem, which will require you to know the needed data structure. And this is where the second reason is coming.

Reason #2: Implement Efficient Algorithms

Choosing the right data structure for the algorithm is one of the key components. Is it better to use array, ArrayList, Vector, or Heap? Depending on what kind of data structure you have chosen, the run time of the algorithm will change drastically.
Consider the problem:
Provide a code for an efficient procedure runningMedian that takes a double parameter and returns a double. Every time runningMedian is called, it returns the median of all the parameters with which it has been called, up to and including the current call. For example, calling runningMedian(5), runningMedian(2), runningMedian(9), runningMedian(12), runningMedian(1) should produce the following return values: 5.0, 3.5, 5.0, 7.0, 5.0
The first and obvious solution that come to mind is to use array to store all previous values, and every time when the runningMedian is called we need to add the input to the array and resort it, then return the median. But the problem is that adding new value to the array requires O(n) time (if you don't have enough space) and the fastest sort algorithm to sort the array  requires O(nlogn) time. At total you will require: O(n) + O(nlogn) time to return the median. Of course you can improve the performance by using dynamic array such as ArrayList or Vector. Despite all of these tweaks (fixes) in worst case you will still need: O(n) + O(nlogn) time.
So what you can do to create  efficient algorithm for the given problem? One effective solution is to use to 1 max-heap and 1 min-heap. Which will give you worst case O(logn) runtime for runningMedian. 
PS: try to solve it by yourself.
PSS: I will write about 3rd reason in another post.
Thank you so much.....

Comments

Post a Comment

Popular posts from this blog

Cloud Computing?

-
Image
                What is Cloud Computing?       Learn the basic of cloud computing terminology and its uses. Simply, cloud computing is the delivery of computing services - Softwares, servers, storage, databases, networking, analytics and more -- over the internet ("The cloud"). Companies offering these computing services are called providers and typically charge for cloud computing services based on usage, similar to how you are billed for water or electricity at home. Still foggy on how cloud computing works and what it is for? This blog is designed to demonstrate the basic cloud computing jargon and concepts and quickly bring you up to speed. Use of cloud computing you are probably using cloud computing right now, even if don't realize it. If you use online service to send email, edit documents, watch movies or TV, listen to music, play games or store picture and other files, it is likely that cloud computing i...
Read more
-
Image
Robotics? Five factors supporting the rapid growth of robotics through 2022 The robotics industry growth has been tremendously high in the recent years. But the next few years are going to buzz with stupendous advancements in the robotic technology. With technological advancements, the robotics industry growth has gone up tremendously. Earlier, the interaction between a machine and a human was boring and limited. But, recent trends have it that a world full of robots can be a lot of fun. Today, robots can verbally interact, lend a helping hand, and also save lives, which probably makes robots more human-like with every passing day. Realizing the potential of robotics, many organizations have taken significant steps to bring robotics into application in diverse and unique fields. For instance, MIT has introduced the world to a soft robotic fish called SoFi to help save the ocean, whereas NASA is all set to send a  swarm of robots to Mars , similar to a swarm of bee...
Read more

C And C++ Programming Languages — Biggest Differences

-
Image
C And C++ Programming Languages — Biggest Differences And Comparison April 14, 2016 Short Bytes:  C vs C++ — which one is better? What is a procedural programming language and what is a modular programming language? Which one should be used for better and faster output? Well, we answer all the aspects of using C vs C++ against each other in this article. C Programming language is said to be the mother of most of the most famous languages. However, the next generations and child languages took over C very easily. Among all the programming languages, C is the most talked language against all. Let’s take a deeper look into the same and know why and how these languages are different. C vs C++: Comparison and differences Structural or procedural C is a structural or procedural programming language whereas C++ is a modular or an object-oriented programming language. Let’s look at it this way: Let’s imagine, you are building up a house in...
Read more