Skip to main content

Basics of Data Structures and Algorithms

Data Structure:
Data Structure is a particular way of storing and organizing data in a computer. So, that it can be used efficiently. We can also say in the way of data structure is a special format for organizing and storing data. General data structure types include arrays, files, linked list, stacks, queues, trees, graphs and so on.
Depending on the organization of the elements, data structures are classified into two types.
  1. Linear Data Structures: Elements are accessed in a sequential order. But, it not compulsory to store all elements in sequentially. Ex: Linked List, stacks and Queues.
  2. Non-Linear Data Structures: Elements of this data structures are sorted/accessed in a non-linear order. Ex: Trees and Graphs.
Algorithms:
The formal definition of an algorithm is the step-by-step instructions to solve a given problem. Let us consider the problem of preparing an omelet. For preparing omelet, general steps we follow are:
    1. Get the frying pan
    2. Get the oil
a. Do we have oil?
i. If yes, put it in the pan
ii. If no, do we want to buy oil?
1. If yes, then go out and buy.
2. If no, we can terminate.
  •  Turn on the stove, etc…


What we are doing is, for a given problem (preparing an omelet), giving step-by-step procedure for solving it.
Why analysis of Algorithm?
To go from city ‘A’ to city ‘B’, there can be many ways of accomplishing this: by flight, by bus, by train and also by bicycle. Depending on the availability and convenience we choose the one that suits us. Similarly in computer science multiple algorithms are available solving the same problem.
Ex: sorting problem has many algorithms like insertion sort, quick sort, selection sort and many more. Algorithm analysis helps us determining which of them is efficient in terms of time and space consumed.
Goal of analysis of Algorithms:
The goal of analysis of algorithms is to compare algorithms mainly in terms of running time but also in terms of other factors. Ex: memory, developers effort, etc..
What is Running Time Analysis?
It is the process of determining how processing time increases as the size of the problem (input size) increases. Input size is the number of elements in the input and depending on the problem type the input may be of different types. The following are the common types of inputs.
  1. Size of an Array
  2. Polynomial degree
  3. Number of elements in a matrix
  4. Number of bits in binary representation of the input
  5. Vertices and edges in a graph
How to compare Algorithms?
To compare algorithms, let us define few objective measures.
Execution Times? Not a good measure as execution times are specific to a particular computer.
Number of statements executed? Not a good measure, since the number of statements varies with the programming language as well as the style of the individual programmer.
Ideal Solution? Let us assume that we expressed running time of given algorithm as a function of the input size n(i.e. f(n)) and compare these different functions corresponding to running times. This kind of comparison is independent of machine time, programming style, etc.

Popular posts from this blog

JNDI configuration for Tomcat 9 with Oracle

In this article, I am going to place the required source code to get data from the table by using the JNDI configuration. Below are the environment details that I have configured currently. Windows - 7 Oracle - 10g Tomcat - 9 JDK - 8 Eclipse Oxygen Ojdbc6 jar required First, we need to create the Dynamic Web Project. If you don't know how to do <Click Here>. I have faced a lot of issues before getting the output like 405, No driver class to load, etc. I am using JSP & Servlets in the current explanation. Before started writing the application logic, we need to do the below configuration in the installed tomcat directory. Place OJDBC6.jar in the Tomcat LIB directory. Add this Resource under <GlobalNamingResources> in Server.xml file which is present under the conf directory in Tomcat. < Resource name = "jdbc/myoracle" global= "jdbc/myoracle" auth = "Container" type= "javax.sql.DataSource" driverClass...

Prime, Fibonacci and Factorial number with example in java

Prime number, Fibonacci series and Factorial number programs are most commonly asked questions in interview. Read this article to know what is and how to write programs for prime number, fibonacci series and factorial number. Prime Number: prime number is natural number greater than 1 that has no positive divisor other than 1 and itself. A natural number greater than 1 is not a prime number, is called Composite number . For example, 7 is a prime number. Because it can divide with 1 and 7 only. Where as 8 is composite number. Since it has the divisor 2 and 4 in addition to the 1 and 8. The below example represents the finding the passing number is prime number or not. If the passing number is prime number it will print true otherwise it will print false. package com . javatbrains . practice ; public class PrimeNumber { public boolean isPrimeNumber ( int number ) { if ( number <= 1 ) return false ; // There's only one ...

Multithreading in java with example

Multithreading  is one of the most important concept in core java. In this article we will learn what is multithreading? , what is the use of it? and What is the use of Synchronization and when to use it?  with detailed examples. At a time, two or more threads are accessing the same object is called as Multithreading  in Java .  First, we will create two threads for two objects. It is also possible to run two or more threads on a single class object. In this case, there is a possibility to get unreliable results. If the two threads are perform same task, then they need same object to be executed each time. For your better understanding, take an example of any reservations like, railway, movie ticket booking,etc. Let us think only one berth is available in a train and two passengers are asking for that berth. The first person has sent a request to allocate that ticket/berth to him. At the same time, the second person also sent a request to allocate that ...