Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Data Structure and Algorithms Tutorial
Effective data utilization is made possible by the use of data
structures in programmatic data storage
...
You will get a thorough grasp of data structures in this
course, which is essential to comprehending the complexity of
enterprise-level systems and the need for algorithms and data
structures
...

•

•

•

Data Search − Consider an inventory of 1 million(106)
items of a store
...
As data grows, search
will become slower
...

Multiple requests − As thousands of users can search
data simultaneously on a web server, even the fast
server fails while searching the data
...
It may not be necessary to search
through every item in a data structure since the necessary data
can be found fairly immediately
...
Algorithms may be implemented in a variety of
computer languages since they are often created independently
of the underlying languages
...

Sort − Algorithm to sort items in a certain order
...

Update − Algorithm to update an existing item in a data
structure
...


The following computer problems can be solved using Data
Structures −
•
•
•
•
•
•

Fibonacci number series
Knapsack problem
Tower of Hanoi
All pair shortest path by Floyd-Warshall
Shortest path by Dijkstra
Project scheduling
Data Structures & Algorithms - Overview

Data Structure is a systematic way to organize data in order to
use it efficiently
...

Interface − Each data structure has an interface
...
An interface only provides the list
of supported operations, type of parameters they can
accept and return type of these operations
...

Implementation also provides the definition of the
algorithms used in the operations of the data structure
...

• Time Complexity − Running time or the execution time
of operations of data structure must be as small as
possible
...

Need for Data Structure
•

As applications are getting complex and data rich, there are
three common problems that applications face now-a-days
...
If the application is to search an item,
it has to search an item in 1 million(106) items every
time slowing down the search
...


•

•

Processor speed − Processor speed although being
very high, falls limited if the data grows to billion
records
...


Data structures come to the rescue in order to address the
aforementioned issues
...

Execution Time Cases
There are three cases which are usually used to compare various
data structure's execution time in a relative manner
...
If an operation's worst case time is ƒ(n) then this
operation will not take more than ƒ(n) time where ƒ(n)
represents function of n
...
If an operation takes ƒ(n) time in execution,
then m operations will take mƒ(n) time
...
If an operation takes ƒ(n) time in execution,
then the actual operation may take time as the random
number which would be maximum as ƒ(n)
...

• Data Item − Data item refers to single unit of values
...

• Elementary Items − Data items that cannot be divided
are called as Elementary Items
...

• Entity Set − Entities of similar attributes form an entity
set
...

• Record − Record is a collection of field values of a given
entity
...


Data Structures - Environment Setup
Local Environment Setup
If you are still willing to set up your environment for C
programming language, you need the following two tools
available on your computer, (a) Text Editor and (b) The C
Compiler
...
Examples of few editors
include Windows Notepad, OS Edit command, Brief, Epsilon,
EMACS, and vim or vi
...
For example, Notepad will be used on
Windows, and vim or vi can be used on Windows as well as Linux
or UNIX
...
The source files for C programs are
typically named with the extension "
...

Before starting your programming, make sure you have one text
editor in place and you have enough experience to write a
computer program, save it in a file, compile it, and finally execute
it
...
It must be "compiled," or
translated into machine language, in order for your CPU to carry
out the program's instructions
...
We
presumingly grasp the fundamentals of a compiler for a
programming language
...
Otherwise, you can have compilers either from HP or
Solaris if you have respective Operating Systems (OS)
...
We are mentioning C/C++ together
because GNU GCC compiler works for both C and C++
programming languages
...

Target: i386-redhat-linux
Configured with:
...

Thread model: posix
gcc version 4
...
2 20080704 (Red Hat 4
...
2-46)
If GCC is not installed, then you will have to install it yourself
using
the
detailed
instructions
available
at https://gcc
...
org/install/
This tutorial has been written based on Linux and all the given
examples have been compiled on Cent OS flavor of Linux system
...
Once you
have Xcode setup, you will be able to use GNU compiler for
C/C++
...
apple
...
To install
MinGW, go to the MinGW homepage, www
...
org, and
follow the link to the MinGW download page
...
exe
...

Add the bin subdirectory of your MinGW installation to
your PATH environment variable, so that you can specify these
tools on the command line by their simple names
...


Data Structures - Algorithms Basics
An algorithm is a step-by-step process that specifies a list of
instructions to be carried out in a specific order in order to get
the intended result
...

The following are some significant categories of algorithms from
the perspective of data structures −
Search − Algorithm to search an item in a data
structure
...

• Insert − Algorithm to insert item in a data structure
...

• Delete − Algorithm to delete an existing item from a
data structure
...
An algorithm
should have the following characteristics −
•

•

•

Unambiguous − Algorithm should be clear and
unambiguous
...

Input − An algorithm should have 0 or more welldefined inputs
...


Finiteness − Algorithms must terminate after a finite
number of steps
...

• Independent − An algorithm should have step-by-step
directions, which should be independent of any
programming code
...

Rather, it is problem and resource dependent
...

As we know that all programming languages share basic code
constructs like loops (do, for, while), flow-control (if-else), etc
...

We write algorithms in a step-by-step manner, but it is not
always the case
...
That is, we should
know the problem domain, for which we are designing a
solution
...

Problem − Design an algorithm to add two numbers and display
the result
...

Alternatively, the algorithm can be written as −
Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP
In design and analysis of algorithms, usually the second method
is used to describe an algorithm
...
He
can observe what operations are being used and how the
process is flowing
...

We design an algorithm to get a solution of a given problem
...


Hence, many solution algorithms can be derived for a given
problem
...

Algorithm Analysis
Efficiency of an algorithm can be analyzed at two different
stages, before implementation and after implementation
...
Efficiency of an algorithm is measured by
assuming that all other factors, for example, processor
speed, are constant and have no effect on the
implementation
...
The selected algorithm is implemented
using programming language
...
In this analysis, actual
statistics like running time and space required, are
collected
...
Algorithm
analysis deals with the execution or running time of various
operations involved
...

Algorithm Complexity
Suppose X is an algorithm and n is the size of input data, the time
and space used by the algorithm X are the two main factors,
which decide the efficiency of X
...

Space Factor − Space is measured by counting the
maximum memory space required by the algorithm
...

Space Complexity
Space complexity of an algorithm represents the amount of
memory space required by the algorithm in its life cycle
...
For example, simple variables and
constants used, program size, etc
...
For example,
dynamic memory allocation, recursion stack space, etc
...
Following is a simple
example that tries to explain the concept −
Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10

Step 3 - Stop
Here we have three variables A, B, and C and one constant
...
Now, space depends on data types of given
variables and constant types and it will be multiplied accordingly
...
Time
requirements can be defined as a numerical function T(n), where
T(n) can be measured as the number of steps, provided each step
consumes constant time
...

Consequently, the total computational time is T(n) = c ∗ n, where
c is the time taken for the addition of two bits
...


Data Structures - Asymptotic Analysis
Asymptotic analysis of an algorithm refers to defining the
mathematical boundation/framing of its run-time performance
...

Asymptotic analysis is input bound i
...
, if there's no input to the
algorithm, it is concluded to work in a constant time
...

Asymptotic analysis refers to computing the running time of any
operation in mathematical units of computation
...
This means the
first operation running time will increase linearly with the
increase in n and the running time of the second operation will
increase exponentially when n increases
...

Usually, the time required by an algorithm falls under three types
−
Best Case − Minimum time required for program
execution
...

• Worst Case − Maximum time required for program
execution
...

Ο Notation
• Ω Notation
• θ Notation
Big Oh Notation, Ο
•

The notation Ο(n) is the formal way to express the upper bound
of an algorithm's running time
...


For example, for a function f(n)
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c
...
}
Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound
of an algorithm's running time
...


For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c
...
}

Theta Notation, θ
The notation θ(n) is the formal way to express both the lower
bound and the upper bound of an algorithm's running time
...
}
Common Asymptotic Notations
Following is a list of some common asymptotic notations −
constant

−

Ο(1)

logarithmic

−

Ο(log n)

linear

−

Ο(n)

n log n

−

Ο(n log n)

quadratic

−

Ο(n2)

cubic

−

Ο(n3)

polynomial

−

nΟ(1)

exponential

−

2Ο(n)

Data Structures - Greedy Algorithms
An algorithm is designed to achieve optimum solution for a given
problem
...
As being greedy, the closest
solution that seems to provide an optimum solution is chosen
...

However, generally greedy algorithms do not provide globally
optimized solutions
...
If we are provided coins of ₹ 1, 2,
5 and 10 and we are asked to count ₹ 18 then the greedy
procedure will be −
•
•
•
•

1 − Select one ₹ 10 coin, the remaining count is 8
2 − Then select one ₹ 5 coin, the remaining count is 3
3 − Then select one ₹ 2 coin, the remaining count is 1
4 − And finally, the selection of one ₹ 1 coins solves the
problem

Though, it seems to be working fine, for this count we need to
pick only 4 coins
...

For the currency system, where we have coins of 1, 7, 10 value,
counting coins for value 18 will be absolutely optimum but for
count like 15, it may use more coins than necessary
...
Whereas the same problem could be solved by using
only 3 coins (7 + 7 + 1)
Hence, we may conclude that the greedy approach picks an
immediate optimized solution and may fail where global
optimization is a major concern
...
Here is a
list of few of them −
•
•
•
•
•
•
•
•

Travelling Salesman Problem
Prim's Minimal Spanning Tree Algorithm
Kruskal's Minimal Spanning Tree Algorithm
Dijkstra's Minimal Spanning Tree Algorithm
Graph - Map Coloring
Graph - Vertex Cover
Knapsack Problem
Job Scheduling Problem

There are lots of similar problems that uses the greedy approach
to find an optimum solution
...
When we keep on dividing the subproblems into
even smaller sub-problems, we may eventually reach a stage
where no more division is possible
...
The solution of all
sub-problems is finally merged in order to obtain the solution of
an original problem
...

Divide/Break
This step involves breaking the problem into smaller subproblems
...
This step generally takes a recursive approach to divide
the problem until no sub-problem is further divisible
...

Conquer/Solve
This step receives a lot of smaller sub-problems to be solved
...

Merge/Combine
When the smaller sub-problems are solved, this stage recursively
combines them until they formulate a solution of the original
problem
...

Examples
The following computer algorithms are based on divide-andconquer programming approach −
•
•
•
•
•

Merge Sort
Quick Sort
Binary Search
Strassen's Matrix Multiplication
Closest pair (points)

There are various ways available to solve any computer problem,
but the mentioned are a good example of divide and conquer
approach

---