LESON 1.1

• Interface


  Represents the set of operations that a data structure supports. An interface only provides the list of supported operations, type of parameters they can accept and return type of these operations
• Implementation


  Provides the internal representation of a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure
• Data structure implementation should implement its interface correctly
• Time Complexity


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


  • Memory usage of a data structure operation should be as little as possible
• Processor speed although being very high, falls limited if the data grows to billion records
• Multiple Requests - As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data
• Worse Case


  Scenario where a particular data structure operation takes maximum time it can take
• Average Case


  Scenario depicting the average execution time of an operation of a data structure
• Best Case


  Scenario depicting the least possible execution time of an operation of a data structure
• 1. Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases),

  and their inputs/outputs should be clear and must lead to only one meaning.
• b. Input − Algorithm should have 0 or more well-defined inputs.
• c. Output − Algorithm should have 1 or more well-defined outputs and should match the desired

  output.
• d. Finiteness − Algorithms must terminate after a finite number of steps.
• e. Feasibility – It should be feasible with the available resources
• f. Independent − Algorithm should have step-by-step directions, which should be independent of

  any programming code.
• CHARACTERISTICS OF A DATA STRUCTURE:

  Correctness

  Time Complexity

  Space Complexity
• NEED FOR DATA STRUCTURE:

  Data Search

  Processor Speed

  Multiple requests
• CATEGORIES OF ALGORITHMS FROM DATA STRUCTURE POINT OF VIEW:

  Search

  Sort

  Insert

  Update

  Delete
• CHARACTERISTICS OF AN ALGORITHM

  Unambiguous

  Input

  Output

  Finiteness

  Feasibility

  Independent
• A Priori Analysis − a theoretical analysis of an algorithm. 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.
• A Posterior Analysis −an empirical analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.
• TIME COMPLEXITY - measures how long it takes to execute an algorithm as a function of input size n. It is expressed in terms of number of operations performed by the algorithm.
• SPACE COMPLEXITY - measures amount of memory used by an algorithm as a function of input size n. It is expressed in terms of number of variables needed or storage units occupied.