Kloumann, L. Adamic, J. Kleinberg, S. The Lifecycles of Apps in a Social Ecosystem. Cheng, L.
|Published (Last):||2 September 2008|
|PDF File Size:||18.60 Mb|
|ePub File Size:||19.95 Mb|
|Price:||Free* [*Free Regsitration Required]|
A pair of weaverbirds work together on their nest in Africa. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps. The programs and applications presented in this book have been included for their instructional value.
They have been tested with care, but are not guaranteed for any particular purpose. The publisher does not offer any warranties or representations, nor does it accept any liabilities with respect to the programs or applications. Includes bibliographical references and index. ISBN alk. Computer algorithms. Data structures Computer science I.
A43K54 For information on obtaining permission for use of material in this work, please submit a written request to Pearson Education, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or any toher media embodiments now known or hereafter to become known, without the prior written permission of the publisher.
Printed in the United States of America. He received his Ph. Kleinbergs research is centered around algorithms, particularly those concerned with the structure of networks and information, and with applications to information science, optimization, data mining, and computational biology.
His work on network analysis using hubs and authorities helped form the foundation for the current generation of Internet search engines. She received her Ph. Tardoss research interests are focused on the design and analysis of algorithms for problems on graphs or networks.
She is most known for her work on network-flow algorithms and approximation algorithms for network problems. Her recent work focuses on algorithmic game theory, an emerging area concerned with designing systems and algorithms for selfish users.
See the Preface for more information about the relationships among the chapters and sections. Contents Contents 8. Packet Routing Some of the major shifts in Internet routing standards can be viewed as debates over the deficiencies of one shortest-path algorithm and the relative advantages of another. The basic notions used by biologists to express similarities among genes and genomes have algorithmic definitions. The concerns voiced by economists over the feasibility of combinatorial auctions in practice are rooted partly in the fact that these auctions contain computationally intractable search problems as special cases.
And algorithmic notions arent just restricted to well-known and longstanding problems; one sees the reflections of these ideas on a regular basis, in novel issues arising across a wide range of areas.
The scientist from Yahoo! So was the former student, now a management consultant working on staffing protocols for large hospitals, whom we happened to meet on a trip to New York City.
The point is not simply that algorithms have many applications. The deeper issue is that the subject of algorithms is a powerful lens through which to view the field of computer science in general. Algorithmic problems form the heart of computer science, but they rarely arrive as cleanly packaged, mathematically precise questions. Rather, they tend to come bundled together with lots of messy, application-specific detail, some of,it essential, some of it extraneous.
As a result, the algorithmic enterprise consists of two fundamental components: the task of getting to the mathematically clean core of a problem, and then the task of identifying the appropriate algorithm design techniques, based on the structure of the problem. These two components interact: the more comfortable one is with the full array of possible design techniques, the more one starts to recognize the clean formulations that lie within messy xiv Preface XV problems out in the world.
The goal of our book is to convey this approach to algorithms, as a design process that begins with problems arising across the full range of computing applications, builds on an understanding of algorithm design techniques, and results in the development of efficient solutions to these problems.
We seek to explore the role of algorithmic ideas in computer science generally, and relate these ideas to the range of precisely formulated problems for which we can design and analyze algorithms.
In other words, what are the underlying issues that motivate these problems, and how did we choose these particular ways of formulating them? How did we recognize which design principles were appropriate in different situations?
In keeping with this, our goal is to offer advice on how to identify clean algorithmic problem formulations in complex issues from different areas of computing and, from this, how to design efficient algorithms for the resulting problems. Sophisticated algorithms are often best understood by reconstructing the sequence of ideas--including false starts and dead ends--that led from simpler initial approaches to the eventual solution. The result is a style of exposition that does not take the most direct route from problem statement to algorithm, but we feel it better reflects the way that we and our colleagues genuinely think about these questions.
The notion of computational intractability, and NP-completeness in particular, plays a large role in the book. This is consistent with how we think about the overall process of algorithm design. Some of the time, an interesting problem arising in an application area will be amenable to an efficient solution, and some of the time it will be provably NP-complete; in order to fully address a new algorithmic problem, one should be able to explore both of these ol tions with equal familiarity.
Since so many natural problems in computer science are NP-complete, the development of methods to deal with intractable problems has become a crucial issue in the study of algorithms, and our book heavily reflects this theme. The discovery that a problem is NPcomplete should not be taken as the end of the story, but as an invitation to begin looking for approximation algorithms, heuristic local search techniques, or tractable special cases.
We include extensive coverage of each of these three approaches. Problems and Solved Exercises An important feature of the book is the collection of problems. Across all chapters, the book includes over problems, almost a! We view the problems as a crucial component of the book, and they are structured in keeping with our overall approach to the material. Most of them consist of extended verbal descriptions of a problem arising in an application area in computer science or elsewhere out in the world, and part of the problem is to practice what we discuss in the text: setting up the necessary notation and formalization, designing an algorithm, and then analyzing it and proving it correct.
The ideas for these problems come in large part from discussions we have had over the years with people working in different areas, and in some cases they serve the dual purpose of recording an interesting though manageable application of algorithms that we havent seen written down anywhere else. To help with the process of working on these problems, we include in each chapter a section entitled "Solved Exercises," where we take one or more problems and describe how to go about formulating a solution.
This material can thus be treated either as a review or as new material; by including it, we hope the book can be used in a broader array of courses, and with more flexibility in the prerequisite knowiedge that is assumed. In keeping with the approach outlined above, we develop the basic algorithm design techniques by drawing on problems from across many areas of computer science and related fields.
To mention a few representative examples here, we include fairly detailed discussions of applications from systems and networks caching, switching, interdomain routing on the Internet , artificial xvi Preface Preface login and password, search the site for either "Kleinberg or "Tardos" or contact your local Addison-Wesley representative. Finally, we would appreciate receiving feedback on the book. In particular, as in any book of this length, there are undoubtedly errors that have remained in the final version.
Comments and reports of errors can be sent to us by e-mail, at the address algbook cs. Rather, as with the rest of the text, the discussions in these sections should be viewed as trying to give a sense of the larger process by which one might think about problems of this type, culminating in the speci. It is worth mentioning two points concerning the use of these problems as homework in a course. First, the problems are sequenced roughly in order of increasing difficulty, but this is only an approximate guide and we advise against placing too much weight on it: since the bulk of the problems were designed as homework for our undergraduate class, large subsets of the problems in each chapter are really closely comparable in terms of difficulty.
Second, aside from the lowest-numbered ones, the problems are designed to involve some investment of time, both to relate the problem description to the algorithmic techniques in the chapter, and then to actually design the necessary algorithm. In our undergraduate class, we have tended to assign roughly three of these problems per week. Chapter-by-Chapter Synopsis Chapter I starts by introducing some representative algorithmic problems.
We begin immediately with the Stable Matching Problem, since we feel it sets up the basic issues in algorithm design more concretely and more elegantly than any abstract discussion could: stable matching is motivated by a natural though complex real-world issue, from which one can abstract an interesting problem statement and a surprisingly effective algorithm to solve this problem.
The remainder of Chapter 1 discusses a list of five "representative problems" that foreshadow topics from the remainder of the course. The fact that closely related problems can vary greatly in complexity is an important theme of the book, and these five problems serve as milestones that reappear as the book progresses. Chapter 2 introduces the key mathematical definitions and notations used for analyzing algorithms, as wel!
It begins with an informal overview of what it means for a problem to be computationally tractable, together with the concept of polynomial time as a formal notion of efficiency. It then discusses growth rates of functions and asymptotic analysis more formally, and offers a guide to commordy occurring functions in algorithm analysis, together with standard applications in which they arise.
Chapter 3 covers the basic definitions and algorithmic primitives needed for working with graphs, which are central to so many of the problems in the book. In particular, we discuss basic graph definitions, graph traversal techniques such as breadth-first search and depth-first search, and directed graph concepts including strong connectivity and topological ordering. Pedagogical Features and Supplements In addition to the Problems and solved exercises, the book has a number of further pedagogical features, as well as additional supplements to facilitate its use for teaching.
As noted earlier, a large number of the sections in the book axe devoted to the formulation of an algorithmic problem--including its background and underlying motivation--and the design and analysis of an algorithm for this problem. To reflect this style, these sections are consistently structured around a sequence of subsections: "The Problem," where the problem is described and a precise formulation is worked out; "Designing the Algorithm," where the appropriate design technique is employed to develop an algorithm; and "Analyzing the Algorithm," which proves properties of the algorithm and analyzes its efficiency.
These subsections are highlighted in the text with an icon depicting a feather. In cases where extensions to the problem or further analysis of the algorithm is pursued, there are additional subsections devoted to these issues. The goal of this structure is to offer a relatively uniform style of presentation that moves from the initial discussion of a problem arising in a computing application through to the detailed analysis of a method to solve it.
A number of supplements are available in support of the book itself. An instructors manual works through al! A set of lecture slides, developed by Kevin Wayne of Princeton University, is also available; these slides follow the order of the books sections and can thus be used as the foundation for lectures in a course based on the book.
These files are available at wunv. For instructions on obtaining a professor Preface Preface Chapters 2 and 3 also present many of the basic data structures that will be used for implementing algorithms throughout the book; more advanced data structures are presented in subsequent chapters. Our approach to data structures is to introduce them as they are needed for the implementation of the algorithms being developed in the book.
Chapters 4 through 7 cover four major algorithm design techniques: greedy algorithms, divide and conquer, dynamic programming, and network flow. With greedy algorithms, the challenge is to recognize when they work and when they dont; our coverage of this topic is centered around a way of classifying the kinds of arguments used to prove greedy algorithms correct.
This chapter concludes with some of the main applications of greedy algorithms, for shortest paths, undirected and directed spanning trees, clustering, and compression. For divide and conquer, we begin with a discussion of strategies for solving recurrence relations as bounds on running times; we then show. Next we develop dynamic programming by starting with the recursive intuition behind it, and subsequently building up more and more expressive recurrence formulations through applications in which they naturally arise.
This chapter concludes with extended discussions of the dynamic programming approach to two fundamental problems: sequence alignment, with applications in computational biology; and shortest paths in graphs, with connections to Internet routing protocols. Finally, we cover algorithms for network flow problems, devoting much of our focus in this chapter to discussing a large array of different flow applications. To the extent that network flow is covered in algorithms courses, students are often left without an appreciation for the wide range of problems to which it can be applied; we try to do iustice to its versatility by presenting applications to load balancing, scheduling, image segmentation, and a number of other problems.
Chapters 8 and 9 cover computational intractability. We devote most of our attention to NP-completeness, organizing the basic NP-complete problems thematically to help students recognize candidates for reductions when they encounter new problems. We find this is a valuable way to emphasize that intractability doesnt end at NP-completeness, and PSPACE-completeness also forms the underpinning for some central notions from artificial intelligence--planning and game playing-that would otherwise not find a place in the algorithmic landscape we are surveying.
Chapters 10 through 12 cover three maior techniques for dealing with computationally intractable problems: identification of structured special cases, approximation algorithms, and local search heuristics.
Algorithm Design - John Kleinberg - Éva Tardos.pdf
Lecture Slides for Algorithm Design