Introduction To The Analysis Of Algorithms, An (2nd Edition)

by Michael Soltys-kulinicz

Overview

A successor to the first edition, this updated and revised book is a great companion guide for students and engineers alike, specifically software engineers who design reliable code. While succinct, this edition is mathematically rigorous, covering the foundations of both computer scientists and mathematicians with interest in algorithms.Besides covering the traditional algorithms of Computer Science such as Greedy, Dynamic Programming and Divide & Conquer, this edition goes further by exploring two classes of algorithms that are often overlooked: Randomised and Online algorithms — with emphasis placed on the algorithm itself. The coverage of both fields are timely as the ubiquity of Randomised algorithms are expressed through the emergence of cryptography while Online algorithms 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. Containing programming exercises in Python, solutions will also be placed on the book's website.

Product Details

ISBN-13:	9789814401159
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	09/07/2012
Pages:	212
Product dimensions:	6.10(w) x 9.00(h) x 0.80(d)

Table of Contents

Preface vii

1 Preliminaries 1

1.1 Induction 1

1.2 Invariance 4

1.3 Correctness of algorithms 6

1.3.1 Division algorithm 7

1.3.2 Euclid's algorithm 8

1.3.3 Palindromes algorithm 10

1.3.4 Further examples 12

1.3.5 Recursion and fixed points 15

1.3.6 Formal verification 18

1.4 Stable marriage 21

1.5 Answers to selected problems 24

1.6 Notes 37

2 Greedy Algorithms 39

2.1 Minimum cost spanning trees 39

2.2 Jobs with deadlines and profits 46

2.3 Further examples and problems 49

2.3.1 Make change 49

2.3.2 Maximum weight matching 50

2.3.3 Shortest path 51

2.3.4 Huffman codes 54

2.4 Answers to selected problems 56

2.5 Notes 60

3 Divide and Conquer 63

3.1 Mergesort 64

3.2 Multiplying numbers in binary 65

3.3 Savitch's algorithm 68

3.4 Further examples and exercises 70

3.4.1 Extended Euclid's algorithm 70

3.4.2 Finite automata 71

3.5 Answers to selected problems 74

3.6 Notes 75

4 Dynamic Programming 77

4.1 Longest monotone subsequence problem 77

4.2 All pairs shortest path problem 79

4.2.1 Bellman-Ford algorithm 80

4.3 Simple knapsack problem 81

4.3.1 Dispersed knapsack problem 84

4.3.2 General knapsack problem 85

4.4 Activity selection problem 86

4.5 Jobs with deadlines, durations and profits 88

4.6 Further examples and problems 90

4.6.1 Consecutive subsequence sum problem 90

4.6.2 Regular expressions 91

4.6.3 Context free grammars 93

4.7 Answers to selected problems 96

4.8 Notes 100

5 Online Algorithms 101

5.1 List accessing problem 102

5.2 Paging 106

5.2.1 Demand paging 107

5.2.2 FIFO 110

5.2.3 LRU 110

5.2.4 Marking algorithms 114

5.2.5 FWF 115

5.2.6 LFD 116

5.3 Answers to selected problems 120

5.4 Notes 122

6 Randomized Algorithms 123

6.1 Perfect matching 124

6.2 Pattern matching 128

6.3 Primality testing 129

6.4 Public key cryptography 133

6.4.1 Diffie-Hellman key exchange 134

6.4.2 ElGamal 136

6.4.3 RSA 139

6.5 Further exercises 140

6.6 Answers to selected problems 142

6.7 Notes 148

Appendix A Number Theory and Group Theory 151

A.1 Answers to selected problems 156

A.2 Notes 156

Appendix B Relations 157

B.1 Closure 158

B.2 Equivalence relation 160

B.3 Partial orders 161

B.4 Lattices 163

B.5 Fixed point theory 165

B.6 Answers to selected problems 169

B.7 Notes 171

Appendix C Logic 173

C.1 Propositional Logic 173

C.2 First Order Logic 178

C.3 Peano Arithmetic 183

C.4 Answers to selected problems 184

C.5 Notes 186

Bibliography 187

Index 191