Advanced Data Structures and Algorithms

Advanced Data Structures and Algorithms

 

Advanced Data Structures and Algorithms

Algorithm:

 

Algorithm is a finite sequence of abstract steps which will halt on all inputs.An algorithm is said to be correct if,for every input instances,it halt with the correct output. An incorrect algorithm might not halt at all on some input instances or it might halt with an incorrect answer.

 

Data Structures: Data structure is an abstract data type (ADT) which allows to store and organize data to facilitate access and modifications.


Example : Stack , Queue , Tree , Search Tree etc

Behavior of an algorithm


The behavior of an algorithm is characterized by the following three parameters. 

                           Time, Space and the Communication Complexity.

Time includes  Creation time , Query Response time, update time , Running time

Creation time: Data structure creation time(or setup time) of the data structure being used.

Query Response time : Example: Is there a path from a vertex Vi to another Vertex Vj in a given graph? The time it require to respond to this query is called response time.

Update Time: For example time required to destroy a data structure.

Running Time: Total time require to execute the algorithm from the first statement to termination.

 


Note
-------
In  this tutorial we will cover advanced concepts in data structures and  we will do analysis of algorithms in terms of running time.

Prerequisites:

----------------
Knowledge of basic data structures. Basic knowledge of random variables, expectation, and  combinatorics.