– 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 :

- Number of items to be sorted : عدد النقاط التي سوف تُرتب
- the extent to which the items are already somewhat sorted : طول ترتيب المنقاط
- possible restrictions on the item values : القيوم التي على الترتيب
- 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 C_{1} * n^{2}

– Merge sort has an order of C_{2} * n * log_{2}(n)

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

– C_{1} and C_{2} depends on the programming language level. High level language is slower that low level

– Uses of algorithms :

- hardware with high clock rates, pipelining, and superscalar architectures
- easy-to-use, intuitive graphical user interfaces (GUIs)
- object-oriented systems
- 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.