Preface of the Algorithm Design Manual

  • Designing correct, efficient, and implementable algorithms for real-world problems requires access to two distinct bodies of knowledge:
    • Techniques:
      • Good algorithm designers understand several fundamental algorithm design techniques, including data structures, dynamic programming, depth-first search, backtracking, and heuristics. Perhaps the single most important design technique is modeling, the art of abstracting a messy real-world application into a clean problem suitable for algorithmic attack.
    • Resources:
      • Good algorithm designers stand on the shoulders of giants. Rather than laboring from scratch to produce a new algorithm for every task, they can figure out what is known about a particular problem. Rather than re-implementing popular algorithms from scratch, they seek existing implementations to serve as a starting point. They are familiar with many classic algorithmic problems, which provide sufficient source material to model most any application.
  • Find resources of book in book website.

 

Dynamic Programming

  • Matroid theory is used to determine if greedy algorithm will give a efficient solution
  • Amortized analysis is a tool for analyzing algorithms that perform similar sequence of operations
  • Programming here refers to a tabular method not writing computer code
  • Dynamic programming is applied if the subproblems and dependent
  • DP is applied to optimization problems, in which many solution appear
  • Development of DP could be broken into four steps:

    • Characterize the structure of the optimal solution
    • Recursively define the value of an optimal solution
    • Compute the value of an optimal solution in bottom-up fashion
    • Construct an optimal solution for computed information
  • Assembly Line Problem:

  • The brute force solution would take:
  • Solve it using DP:

  • Step #1: the structure of the fastest way through the factory

    • Optimal Substructure
    • We can construct an optimal solution to a problem from optimal solutions to subproblems
  • Step # 2: Recursive Solution

    • Define the equations of solving the subproblems
  • Step # 3: Computing the fastest times:
  • Step # 4: Constructing the fastest way trough the factory

Notes About Analyzing Algorithms

– We typically use probabilistic analysis to determine the running time of an algorithm in cases in which,
due to the presence of an inherent probability distribution, the running time may differ on different

inputs of the same size. In some cases, we assume that the inputs conform to a known

probability distribution, so that we are averaging the running time over all possible inputs. In

other cases, the probability distribution comes not from the inputs but from random choices

made during the course of the algorithm. We can use randomized algorithms to enforce a probability
distribution on the inputs-thereby ensuring that no particular input always causes poor performance-
or even to bound the error rate of algorithms that are allowed to produce incorrect results on a limited
basis .

– Sorting Algorithms criteria :

  1. Number of items to be sorted : عدد النقاط التي سوف تُرتب
  2. the extent to which the items are already somewhat sorted : طول ترتيب المنقاط
  3. possible restrictions on the item values : القيوم التي على الترتيب
  4. Kind of storage device to be used: main memory, disks, or tapes. : مكان التخزين

– An algorithm is said to be correct if, for every input instance, it halts with the correct output

– We say that a correct algorithm solves the given computational problem

– Incorrect algorithms can sometimes be useful, if their error rate can be controlled

– NP-Complete Problem : problem that no efficient solution is known

– Insertion sort has an order of C1 * n2

– Merge sort has an order of C2 * n * log2(n)

– Insertion sort is advised when n is small and Merg is advised when n is large

– C1 and C2 depends on the programming language level. High level language is slower that low level

– Uses of algorithms :

  1. hardware with high clock rates, pipelining, and superscalar architectures
  2. easy-to-use, intuitive graphical user interfaces (GUIs)
  3. object-oriented systems
  4. local-area and wide-area networking

– The numbers that we wish to sort are also known as the keys

– What separates pseudo code from "real" code is that in pseudo code, we employ whatever expressive

method is most clear and concise to specify a given algorithm. Another difference between pseudo code and
real code is that pseudo code is not typically concerned with issues of software engineering. Issues of data
abstraction, modularity, and error handling are often ignored in order to convey the essence of the algorithm more
concisely.

Analyzing Algorithms

    Analyzing an algorithm has come to mean predicting the resources that the algorithm requires model analyses are usually excellent predictors of performance on actual machines.

    Analyzing even a simple algorithm in the RAM model can be a challenge. The mathematical tools required may include combinatorics, probability theory, algebraic dexterity, and the ability to identify the most significant terms in a formula. Because the behavior of an algorithm may be different for each possible input

    The time taken by the INSERTION-SORT procedure depends on the input: sorting a thousand numbers takes longer than sorting three numbers. Moreover, INSERTION-SORT can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are. In general, the time taken by an algorithm grows with the size of the input, so it is traditional

    The best notion for input size depends on the problem being studied. For many problems

    The running time of an algorithm on a particular input is the number of primitive operations or "steps" executed

    A constant amount of time is required to execute each line of our pseudocode. 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

    When a for or while loop exits in the usual way (i.e., due to the test in the loop header), the test is executed one time more than the loop body. We assume that comments are not executable statements, and so they take no time

    we separate the process of calling the subroutine-passing parameters to it, etc.-from the process of executing the subroutine  Insertion sort uses an incremental approach

    One advantage of divide-and-conquer algorithms is that their running times are often easily determined using techniques that will be introduced in Chapter 4

    Many useful algorithms are recursive in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems. These algorithms typically follow a divide-and-conquer approach: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem

    The divide-and-conquer paradigm involves three steps at each level of the recursion:

    • Divide the problem into a number of subproblems
    • Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner
    • Combine the solutions to the subproblems into the solution for the original problem

    The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows:

    • Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each
    • Conquer: Sort the two subsequences recursively using merge sort
    • Combine: Merge the two sorted subsequences to produce the sorted answer

    The key operation of the merge sort algorithm is the merging of two sorted sequences in the

    "combine" step. To perform the merging, we use an auxiliary procedure MERGE(A, p, q, r),

    where A is an array and p, q, and r are indices numbering elements of the array such that p q < r. The procedure assumes that the subarrays A[pà q] and A[q + 1 à r] are in sorted order. It merges them to form a single sorted subarray that replaces the current subarray A[p à r]

    Merge Sort has: Time Θ(n), where n = r – p + 1( is the number of elements being Merged) When an algorithm contains a recursive call to itself, its running time can often be described by a recurrence equation or recurrence, which describes the overall running time on a problem of size n in terms of the running time on smaller inputs. We can then use mathematical tools to solve the recurrence and provide bounds on the performance of the  algorithm

The Role of Algorithms in Computing

  • an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.
  • An input sequence is called an instance of the sorting problem
  • Which algorithm is best for a given application depends on-among other factors

    • the number of items to be sorted
    • the extent to which the items are already somewhat sorted
    • possible restrictions on the item values
    • The kind of storage device to be used
  • An algorithm is said to be correct if, for every input instance, it halts with the correct output
  • Why are NP-complete problems interesting?

    • First, although no efficient algorithm for an NP-Complete problem has ever been found, nobody has ever proven that an efficient algorithm for one cannot exist.
    • Second, the set of NP-Complete problems has the remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exists for all of them. This relationship among the NP-Complete problems makes the lack of efficient solutions all the more tantalizing

Third, several NP-Complete problems are similar, but not identical, to problems for which we do know of efficient algorithms. A small change to the problem statement can cause a big change to the efficiency of the best known algorithm.