DSA

ref paper: Primegean Frontend Masters course A common sense guide to DSA Introduction to the design and Analysis of Algorithms MIT Introduction to Algorithms Fall 2011

The most valuable acquisitions in a scientific or technical education are the general purpose mental tools which remain servicable for a life-time
Any problem in computer science can be solved using indirection

Introduction

  • This is a sequence of unambiguous instructions for solving a problem...i.e given a legitimate input, it returns an output in finite time.
  • Algorithms are well-defined procedures for solving problems.
  • Reason for using DSA
    • Efficiency
    • Abstraction
    • Reusability
  • Should also be able to design and analyze new algorithms.
  • Specific algorithmic design techniques can be interpreted as problem solving strategies useful regardless if a computer is present.

General approaches in Algo Design

  • Randomized algorithms
    • rely on the statistical properties of random numbers.
  • Divide and conquer algorithms
    • rely on divide, conquer and combine.
  • Dynamic programming solutions
    • subproblems are not independent of one another.
  • Greedy algorithms
    • make decisions that look best at the moment, locally optimal in the hope that they will lead to globally optimal solutions.
  • Approximation algorithms
    • do not compute optimal solutions, just solutions that are good enough, computationally expensive problems

Design and Analysis of Algorithms.

  • Algorithm design techniques.
  • Classification of algorithm around design ideas.
  • Utility in general problem solving techniques.

Fundamentals of Algorithmic Problem Solving

  • Understanding the problem.
  • Ascertaining the capabilities of the computational device
  • Choosing between exact and appropriate problem solving.
  • Algorithm design techniques
    • an algo' design technique is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.
  • Designing an algorithm and data structures
  • Methods of specifying an algorithm
  • Proving an algorithm's correctness
  • Analyzing an algorithm
  • Coding it up

Important Problem Types

  • Sorting
  • Searching
  • String Processing
  • Graph problems
  • Combinatorial problems
  • Geometric problems
  • Numerical problems

Fundamental Data Structures

def: a particular scheme of organizing related data items. nature of data items depend on the problem at hand.

  • Linear Data Structures

    • Array
      • used to implement a variety of other data structures, i.e string(sequence of characters from an alphabet terminated by special character indicating character end)
    • Linked List
    • Array and Linked list are the two principal choices in representing a more abstract data structure i.e
    • Linear lists
      • Stacks
        • insertions and deletions only done at the end
      • Queues
        • front and back insertions and deletions, FIFO.
        • priority queue

  • Graphs

    • non-empty set of vertices and pairs of edges
    • graph representations
      • adjacency matrix
        • 1 if vertices intersect, 0 if absent.
      • adjacency list
        • collection of linked list, one for each of the vertices
    • weighted graphs
      • graph with numbers assigned to its edges.
    • paths and cycles
      • connectivity and acyclicity.
      • directed path

  • Trees

    • tree is a connected acyclic graph
    • graph that has no cycles but it is not necessarily connected is called a forest.
    • number of edges in a tree is one less than the number of its vertices.
    • rooted trees
    • state space trees: backtracking and branch-and-bound
    • Height of tree
    • ordered trees
      • binary trees

  • Sets and Dictionaries

    • can be represented as bit vector
    • also represented as a list

Computational Thinking

  • Decomposition - break problem down into subproblems.
  • Pattern Recognition - notice similarities, differences, properties or trends in data.
  • Pattern Generalization - define a concept or idea in general terms via doing away with the unnecessary. Abstraction.
  • Algorithm design - repeatable, step-by-step process to solve a particular problem.

A procedure that has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a computational method.

Important features

  • Finiteness - algorithm must always terminate after a finite number of steps.
  • Definiteness - Each step must be precisely defined, actions must be rigorously and unambiguously specified for each case. Programming languages used to achieve this.
  • Input - has zero or more inputs. Given as algo begins or dynamically as it runs.
  • Outputs - zero or more quantities that have a relation to the inputs.
  • Effectiveness - operations must be sufficiently basic

Algorithmic Analysis

  • Length of time taken to perform the algorithm, wrt running time and memory space.
  • Adaptability of algorithm to different kind of computers.
  • Quantitative behaviour of algorithms.
  • Framework for algorithm analysis
    • Measuring an input's size.
      • time and space efficiencies measured as functions of input size.
    • Units for measuring running time.
      • rely on a measure that does not depend on extraneous factors, machine, network, compiler
      • identify the basic operation, one which contributes the most to the running time, and compute number of times its executed.
      • orders of growth
        • n, log n, nlogn, n^2, n^3, 2^n
      • worst, best and average case efficiencies
        • use basic operation to better explain this statistic.
      • amortized efficiency
        • not applied to single run of an algorithm but a sequence of operations performed on same ds.
        • entire sequence of n is better than worst-case multiplied by n.
  • Asymptotic Notations and Basic efficiency classes
    • Big Oh, Big Omega, Big Theta.
    • Using limits for comparing orders of growth
  • Analyzing nonrecursive algorithms
    • decide on a parameter indicating an input size.
    • identify the algo's basic operation
    • check whether number of times its executed depends on the input size, if it depends on another property, different calculations for efficiencies for both.
    • set up a sum expressing number of times algo's basic operation is executed.
    • establish order of growth.
  • Analyzing recursive algorithms
    • decide on a parameter indicating an input size.
    • identify the algo's basic operation
    • check whether the number of times the basic operation is executed can vary on different inputs of the same size.
    • set up a recurrence relation, with an appropriate initial condition for the number of times the basic operation is executed.
    • solve the recurrence or at least ascertain order of growth of its solution.
  • Empirical Analysis of Algorithms
    • overcome challenges of mathematical analysis.
    • General plan for this
      • Understand the experiment's purpose.
      • Decide on the efficiency metric M to be measured and the measurement unit(operation count vs a time unit)
      • Decide on characteristics of the input sample(range, size, etc)
      • Prepare a program implementing the algorithm for the experimetation
      • Generate a sample of units
      • Run the algorithms on the sample inputs and record the data observed
      • Analyze the data observed.
    • Different goals one can pursue in emprical analysis
      • checking the accuracy of a theoretical assertion about the algorithm's efficiency.
      • comparing efficiency of sevaral algorithms of solving the same problem, different implmentations of the same algorithms
      • develop hypothesis of algorithms efficiency class.
      • efficiency of program implementing algo' in a particular machine.
      • profiling
      • use random number generator for sample generation, linear congruential method.

Misc

  • Sometimes we find that many questions have a similar structure and are instances of the same problem.