The Algorithm Design Manual Second Edition

Programming Challenges

These programming challenge problems with robot judging are available at

http://www.programming-challenges.com or http://online-judge.uva.es.

1-1. “The 3n + 1 Problem” – Programming Challenges 110101, UVA Judge 100.

1-2. “The Trip” – Programming Challenges 110103, UVA Judge 10137.

1-3. “Australian Voting” – Programming Challenges 110108, UVA Judge 10142.

---

2

Algorithm Analysis

Algorithms are the most important and durable part of computer science because

they can be studied in a language- and machine-independent way. This means that

we need techniques that enable us to compare the efficiency of algorithms without

implementing them. Our two most important tools are (1) the RAM model of

computation and (2) the asymptotic analysis of worst-case complexity.

Assessing algorithmic performance makes use of the “big Oh” notation that,

proves essential to compare algorithms and design more efficient ones. While the

hopelessly practical person may blanch at the notion of theoretical analysis, we

present the material because it really is useful in thinking about algorithms.

This method of keeping score will be the most mathematically demanding part

of this book. But once you understand the intuition behind these ideas, the for-

malism becomes a lot easier to deal with.