Skip to content

Introduction to Algorithms

Introduction to Algorithms, third edition

Metadata

Highlights

An algorithm is thus a sequence of computational steps that transform the input into the output. — location: 464 ^ref-37712

algorithm as a tool for solving a well-specified computational problem. — location: 465 ^ref-57034

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 architecture of the computer, and the kind of storage devices to be used: main memory, disks, or even tapes. — location: 477 ^ref-44337

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. In other words, no one knows whether or not efficient algorithms exist for NP-complete problems. 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 exist 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. — location: 567 ^ref-46429

This problem is the well-known “traveling-salesman problem,” and it is NP-complete. — location: 579 ^ref-41755

Suppose computers were infinitely fast and computer memory was free. Would you have any reason to study algorithms? The answer is yes, if for no other reason than that you would still like to demonstrate that your solution method terminates and does so with the correct answer. — location: 600 ^ref-27331

constant factors can have far less of an impact on the running time than the dependence on the input size n. — location: 615 ^ref-33621

We use loop invariants to help us understand why an algorithm is correct. We must show three things about a loop invariant: Initialization: It is true prior to the first iteration of the loop. Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration. Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct. — location: 777 ^ref-53298

The RAM model contains instructions commonly found in real computers: arithmetic (such as add, subtract, multiply, divide, remainder, floor, ceiling), data movement (load, store, copy), and control (conditional and unconditional branch, subroutine call and return). Each such instruction takes a constant amount of time. — location: 885 ^ref-45927

2.2-4 How can we modify almost any algorithm to have a good best-case running time? — location: 1030 ^ref-38730

Last update : 25 mai 2024
Created : 21 septembre 2023