dsa1

• Data structure and algorithm


  Provide a set of techniques to the programmer for handling the data efficiently
• Data structure


  • Study of Various ways of organizing data in a computer
  • Programmatic way of storing data so that data can be used efficiently
  • A systematic way to organize data in order to use it efficiently
• Why data structures and algorithm is important to learn


  • Adding structure to our data can make the algorithms much simpler, easier to maintain, and often faster
• Programs are comprised of two things: data and algorithms
• Data


  Information processed or stored by a computer
• Algorithms


  Describe the way the data is to be transformed
• Interface


  Represents the set of operations that a data structure supports
• Implementation


  Provides the internal representation of a data structure and the definition of the algorithms used in the operations
• Characteristics of a data structure

  • Correctness
  • Time Complexity
  • Space Complexity
• Correctness


  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
• Need for data structure

  • Data Search
  • Processor Speed
  • Multiple requests
• Data Search


  As data grows, search will become slower
• Processor Speed


  Falls limited if the data grows to billion records
• Multiple requests


  Even the fast server fails while searching the data
• Execution time cases


  • Worse Case
  • Average Case
  • Best Case
• 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
• Algorithm


  A step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output
• Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language
• Categories of algorithms from data structure point of view

  • Search
  • Sort
  • Insert
  • Update
  • Delete
• Characteristics of an algorithm

  • Unambiguous
  • Input
  • Output
  • Finiteness
  • Feasibility
  • Independent
• Unambiguous


  Algorithm should be clear and . Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning
• Input


  Algorithm should have 0 or more well-defined inputs
• Output


  Algorithm should have 1 or more well-defined outputs and should match the desired output
• Finiteness


  Algorithms must terminate after a finite number of steps
• Feasibility


  It should be feasible with the available resources
• Independent


  Algorithm should have step-by-step directions, which should be independent of any programming code
• There are no well-defined standards for writing algorithms. Rather, it is problem and resource dependent. Algorithms are never written to support a particular programming code
• Algorithm to add two numbers and display the result

  1. Read the two numbers

  2. Add the two numbers

  3. Display the result
• Writing step numbers is optional. Algorithms tell the programmers how to code the program
• Stages of algorithm analysis

  • A Priori Analysis
  • A Posterior Analysis
• A Priori Analysis


  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


  Empirical analysis of an algorithm. The selected algorithm is implemented using programming language and executed on target computer machine. Actual statistics like running time and space required are collected
• Factors deciding the efficiency of an algorithm

  • Time Factor
  • Space Factor
• Time Factor


  Time is measured by counting the number of key operations such as comparisons in the sorting algorithm
• Space Factor


  Space is measured by counting the maximum memory space required by the algorithm
• Algorithm Complexity


  The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data