An Introduction to the Analysis of Algorithms
eBook - ePub

An Introduction to the Analysis of Algorithms

Michael Soltys

Share book
  1. 328 pages
  2. English
  3. ePUB (mobile friendly)
  4. Available on iOS & Android
eBook - ePub

An Introduction to the Analysis of Algorithms

Michael Soltys

Book details
Book preview
Table of contents
Citations

About This Book

-->

A successor to the first and second editions, this updated and revised book is a leading companion guide for students and engineers alike, specifically software engineers who design algorithms. While succinct, this edition is mathematically rigorous, covering the foundations for both computer scientists and mathematicians with interest in the algorithmic foundations of Computer Science.

Besides expositions on traditional algorithms such as Greedy, Dynamic Programming and Divide & Conquer, the book explores two classes of algorithms that are often overlooked in introductory textbooks: Randomised and Online algorithms — with emphasis placed on the algorithm itself. The book also covers algorithms in Linear Algebra, and the foundations of Computation.

The coverage of Randomized and Online algorithms is timely: the former have become ubiquitous due to the emergence of cryptography, while the latter are essential in numerous fields as diverse as operating systems and stock market predictions.

While being relatively short to ensure the essentiality of content, a strong focus has been placed on self-containment, introducing the idea of pre/post-conditions and loop invariants to readers of all backgrounds, as well as all the necessary mathematical foundations. The programming exercises in Python will be available on the web (see http://www.msoltys.com/book for the companion web site).

-->
--> Contents:

  • Preliminaries
  • Greedy Algorithms
  • Divide and Conquer
  • Dynamic Programming
  • Online Algorithms
  • Randomized Algorithms
  • Algorithms in Linear Algebra
  • Computational Foundations
  • Mathematical Foundations

-->
--> Readership: Students of undergraduate courses in algorithms and programming and associated professionals. -->
Keywords:Algorithms;Greedy;Dynamic Programming;Online;Randomized;Loop InvariantReview:0

Frequently asked questions

How do I cancel my subscription?
Simply head over to the account section in settings and click on “Cancel Subscription” - it’s as simple as that. After you cancel, your membership will stay active for the remainder of the time you’ve paid for. Learn more here.
Can/how do I download books?
At the moment all of our mobile-responsive ePub books are available to download via the app. Most of our PDFs are also available to download and we're working on making the final remaining ones downloadable now. Learn more here.
What is the difference between the pricing plans?
Both plans give you full access to the library and all of Perlego’s features. The only differences are the price and subscription period: With the annual plan you’ll save around 30% compared to 12 months on the monthly plan.
What is Perlego?
We are an online textbook subscription service, where you can get access to an entire online library for less than the price of a single book per month. With over 1 million books across 1000+ topics, we’ve got you covered! Learn more here.
Do you support text-to-speech?
Look out for the read-aloud symbol on your next book to see if you can listen to it. The read-aloud tool reads text aloud for you, highlighting the text as it is being read. You can pause it, speed it up and slow it down. Learn more here.
Is An Introduction to the Analysis of Algorithms an online PDF/ePUB?
Yes, you can access An Introduction to the Analysis of Algorithms by Michael Soltys in PDF and/or ePUB format, as well as other popular books in Ciencia de la computación & Algoritmos de programación. We have over one million books available in our catalogue for you to explore.

Information

Publisher
WSPC
Year
2018
ISBN
9789813235922

Chapter 1

Preliminaries

It is commonly believed that more than 70% (!) of the effort and cost of developing a complex software system is devoted, in one way or another, to error correcting.
Algorith., pg. 107 [Harel (1987)]

1.1What is correctness?

To show that an algorithm is correct, we must show somehow that it does what it is supposed to do. The difficulty is that the algorithm unfolds in time, and it is tricky to work with a variable number of steps, i.e., while-loops. We are going to introduce a framework for proving algorithm (and program) correctness that is called Hoare’s logic. This framework uses induction and invariance (see Section 9.1), and logic (see Section 9.4) but we are going to use it informally. For a formal example see Section 9.4.4.
We make two assertions, called the pre-condition and the post-condition; by correctness we mean that whenever the pre-condition holds before the algorithm executes, the post-condition will hold after it executes. By termination we mean that whenever the pre-condition holds, the algorithm will stop running after finitely many steps. Correctness without termination is called partial correctness, and correctness per se is partial correctness with termination. All this terminology is there to connect a given problem with some algorithm that purports to solve it. Hence we pick the pre and post condition in a way that reflects this relationship and proves it true.
These concepts can be made more precise, but we need to introduce some standard notation: Boolean connectives: ∧ is “and,” ∨ is “or” and ¬ is “not.” We also use as Boolean implication, i.e., x → y is logically equivalent to ¬xy, and is Boolean equivalence, and α ↔ β expresses ((α → β) ∧ (β →α)). ∀ is the “for-all” universal quantifier, and ∃ is the “there exists” existential quantifier. We use “⇒” to abbreviate the word “implies,” i.e., 2|xx is even, while “⇏” abbreviates “does not imply.”
Let A be an algorithm, and let
inline
be the set of all well-formed inputs for A; the idea is that if I
inline
then it “makes sense” to give I as an input to A. The concept of a “well-formed” input can also be made precise, but it is enough to rely on our intuitive understanding—for example, an algorithm that takes a pair of integers as input will not be “fed” a matrix. Let O = A(I) be the output of A on I, if it exists. Let αA be a precondition and βA a post-condition of A; if I satisfies the pre-condition we write αA(I) and if O satisfies the post-condition we write βA(O). Then, partial correctness of A with respect to pre-condition αA and post-condition βA can be stated as:
In words: for any well formed input I, if I satisfies the pre-condition and A(I) produces an output (i.e., terminates), then this output satisfies the post-condition.
Full correctness is (1.1) together with the assertion that for all I
inline
, A(I) terminates (and hence there exists an O such that O = A(I)).
Problem 1.1. Modify (1.1) to express full correctness.
A fundamental notion in the analysis of algorithms is that of a loop invariant; it is an assertion that stays true after each execution of a “while” (or “for”) loop. Coming up with the right assertion, and proving it, is a creative endeavor. If the algorithm terminates, the loop invariant is an assertion that helps to prove the implication αA(I) → βA(A(I)).
Once the loop invariant has been shown to hold, it is used for proving partial correctness of the algorithm. So the criterion for selecting a loop invariant is that it helps in proving the post-condition. In general many different loop invariants (and for that matter pre and post-conditions) may yield a desirable proof of correctness; the art of the analysis of algorithms consists in selecting them judiciously. We usually need induction to prove that a chosen loop invariant holds after each iteration of a loop, and usually we also need the pre-condition as an assumption in this proof.

1.1.1Complexity

Given an algorithm
inline
and an input x, the running time of
inline
on x is the number of steps it takes
inline
to terminate on input x. The delicate issue here is to define a “step,” but we are going to be informal about it: we assume a Random Access Machine (a machine that can access memory cells in a single step), and we assume that an assignment of the type x ← y is a single step, and so are arithmetical operations, and the testing of Boolean expressions (such as x ≥ yy ≥ 0). Of course this simplification does not reflect the true state of affairs if for example we manipulate numbers of 4,000 bits (as in the case of cryptographic algorithms). But then we redefine steps appropriately to the context.
We are interested in worst-case complexity. That...

Table of contents