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

---

Shashank Yadav (KIET-Ghaziabad)

Unit-1
1
...
1 Data: Data are simply values or set of values
...

 Data items are divided into sub-items are called group items; those that are not called
elementary items
...
g
...

 Collections of data are organized into a hierarchy of fields, records and files
...

 A record is the collection of field values of a given entity
...


1
...
The
values may be either numeric or nonnumeric
...
g
...
These two attributes
can be assigned as Name- Raj Kumar Singh
roll number-1200310015
 Entities with similar attributes form an entity set (All students in the class)
...
3 Information: Processed or meaningful data is called Information
...


1
...

 It is a logical way of storing data and it also defines a mechanism of retrieve data
...

1) Linear data structure:
 A data structure is said to be linear if its elements form a linear list
...
g
...

 There are two basic ways of representing such linear structure in memory
...
Sequential memory locations (Array)
ii
...

E
...
records, trees, tables of contents
For representing such data structure in memory, Pointers are used
...

2) Searching:- Finding the location of the record with a given key value
...

4) Deletion:- Removing a record from the structure
...

1) Sorting:- Arranging the records in some logical order
...


2
...

 The algorithm is defined as the collection of unambiguous instructions occurring in some
specific sequence and such an algorithm should produce output for given set of input in
finite amount of time
...
1 Properties of Algorithm:





Input: The input should be taken from specified set of objects
...

Finiteness: An algorithm must always terminate after a finite number of steps
...


2
...
The algorithm is correct with respect to
the specification, if it produces the desired results for all the inputs defined by the specification
...

1
...
Total Correctness

2
...
1 Partial Correctness: The partial correctness of the algorithm defines that for every legal
input when an algorithm terminates, the result produced will be valid
...

2|Page

Shashank Yadav (KIET-Ghaziabad)

2
...
2 Total Correctness: The total correctness of an algorithm defines that for every legal
input, the algorithm halts and then output produced will be valid
...
3 Analysis of Algorithm:
 The analysis of algorithm is the determination of the amount of resources (such as space
and time) necessary to execute them
...
They will have different
characteristics that will determine how efficiently each will operate
...

 Analyzing an algorithm determines the amount of “time” that algorithm takes to execute
...
The number of
operations is related to the execution time, so we will sometimes use the word time to
describe an algorithm’s computational complexity
...
We can then compare two algorithms by
comparing the rate at which their equations grow
...
4 Complexity of Algorithm:
2
...
1 Space Complexity: The space complexity of an algorithm is the amount of memory it
needs to run to completion
...
4
...
Time complexity of algorithm is calculated in three ways
...
Best Case Time Complexity
ii
...
Average Case Time Complexity
2
...
2
...

2
...
2
...

2
...
2
...


3|Page

Shashank Yadav (KIET-Ghaziabad)

2
...

1
...

key = A[j]
3
...

4
...

while i>0 and A[i] > key do
6
...

i=i-1
8
...
One line
may take a different amount of time than another line, but we shall assume that each
execution of the ith line takes time ci, where ci is a constant
...
of statement
1
...

3
...

5
...


c6

7
...


c8

times
n
n-1
n-1
n-1
∑
∑
∑

n-1

Running time of insertion sort: The running time of the algorithm is the sum of running times
for each statement executed
...
For each j=2, 3
...
Thus tj=1 for j=2, 3
...
It is a linear function of n
...
We must compare each element A[j] with each element
in the entire sorted sub-array A[1…j-1], so tj= j for j= 2, 3, …, n
...
This is a
quadratic function
...
Growth of Function:
The order of growth of the running time of an algorithm gives a simple characterization of the
algorithm's efficiency and also allows us to compare the relative performance of alternative
algorithms
...
Rate of growth of standard functions
...
1 Asymptotic Notation:
The notations we use to describe the asymptotic running time of an algorithm are defined in
terms of functions whose domains are the set of natural numbers N = {0, 1, 2,
...
1
...

e
...
f(n)= 6n2 + 5n + 4
The higher term of f(n) is n2, Let g(n)= n2
According to O notation’s condition
f(n) ≤ c g(n)
6n2 + 5n +4 ≤ c n2
6 + 5/n + 4/n2 ≤ c
For n= 1, c= 6 +5 +4 = 15
n=2, c= 6+2
...
5
n=3, c= 6+1
...
44= 8
...
The maximum value of c is15
for n=1
...
The
complexity of algorithm is O(n2)
...
1
...


4
...
Time-space tradeoff is a way of
solving a problem in less time by using more storage space, or by solving a problem in very little
space by spending a long time
...
1 An example of Time –Space tradeoff:

6|Page

Shashank Yadav (KIET-Ghaziabad)

 Suppose a file of records contains names, social security numbers and much additional
information
...

 On the other hand, suppose we are given only the social security number of the person
...

 How can we solve such a problem?
 One way is to have another file which is sorted numerically according to social security
number
...

 Another way is to have the main file sorted numerically by social security number and to
have an auxiliary array with only two columns, the first column containing an
alphabetized list of the names and the second column containing pointers which give the
locations of the corresponding records in the main file
...
Abstract Data Type:
 A set of data values and associated operations that are precisely specified independent of
any particular implementation
...

 Common examples of abstract data types are the built-in primitive types in C is, Integer
and Float
...

 An abstract stack could be defined by two operations: PUSH (inserts some data
item onto the stack), POP (extracts top item from it)
...

 Most Object Oriented Languages provide the feature of user-defined abstract data types
...


7|Page



---