# Algorithm Design

## Jon Kleinberg, Éva Tardos

Language: English

Pages: 432

ISBN: 0321295358

Format: PDF / Kindle (mobi) / ePub

** Algorithm Design** introduces algorithms by looking at the real-world problems that motivate them. The book teaches a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.

Review:

The flow in this book is excellent. The authors do a great job in organizing this book in logical chapter. The chapters are organized into techniques to find solutions to particular problems, like for example, Greedy Algorithms, Divide and Conquer, and Dynamic Programming.

Each chapter contains a few representative problems of the technique or topic discussed. These are discussed in great detail, which is helpful to initially grasp the concepts. Furthermore, the end of each chapter contains a number of solved exercises. These are written up in less detail than the chapter problems, because they are usually slight variations or applications of the representative problems. I found these to be very helpful to me, as to build up a stronger grasp of the problem at hand.

Furthemore, the progressive search for a solution, such as for the Weighted Interval Scheduling problem using dynamic programming, is essential to understanding the process through which we can find such algorithms. The book is well written, in a clear, understandable language. The supplementary chapters on Basics of Algorithm Analysis and Graph Theory are a great started for people who have not been exposed to those concepts previously.

Network flows are covered extensively with their applications. I suppose this section of the course was enhanced because our instructor's research interests are Network Flows and she threw example after example at us. There are a great number of problems at the end of this chapter to practice.

(...)

One of the strenghs of this book, is that when the authors determine the running time of a particular algorithm, they write about how to implement it, with which data structures and why. Although it is assumed that data structures are common knowledge for the reader, this type of analysis is helpful for further understanding of such structures.

All in all, this is a great textbook for an introductory course in the design of algorithms.

given P, the closest pair in the recursive calls is computed correctly by induction. By (5.!0) and (5.9), the remainder of the algorithm correctly determines whether any pair of points in S is at distance less than 8, and if so returns the closest such pair. Now the closest pair in P either has both elements in one of Q or R, or it has one element in each. In the former case, the closest pair is correctly found by the recursive call; in the latter case, this pair is at distance less than 8, and

Distance Vector Protocols Chapter 6 Dynamic Programming naturally nonnegative, so one could use Dijkstra’s Algorithm to compute the shortest path. However, Dijkstra’s shortest-path computation requires global knowledge of the network: it needs to maintain a set S of nodes for which shortest paths have been determined, and make a global decision about which node to add next to S. While reuters can be made to run a protocol in the background that gathers enough global information to implement

the opposite gender) in some order, and its next n - k are the bad people (of the opposite gender) in some order. Show that in every stable matching, every good man is married to a good woman. Solution A natural way to get started thinking about this problem is to assume the claim is false and try to work toward obtaining a contradiction. What would it mean for the claim to be false? There would exist some stable matching M in which a good man m was married to a bad woman w. Now, let’s consider

about how their resource requirements--the amount of time and space they use--will scale with increasing input size. We begin this chapter by talking about how to put this notion on a concrete footing, as making it concrete opens the door to a rich understanding of computational tractability. Having done this, we develop the mathematical machinery needed to talk about the way in which different functions scale with increasing input size, making precise what it means for one function to grow

prefers every one of its accepted applicants to A; or (ii) A prefers her current situation over working for employer E. If this holds, the outcome is stable: individual self-interest will prevent any applicant/employer deal from being made behind the scenes. Gale and Shapley proceeded to develop a striking algorithmic solution to this problem, which we will discuss presently. Before doing this, let’s note that this is not the only origin of the Stable Matching Problem. It turns out that for a