|
Appendix C: Graph Terminology and Notation. Graphs are a really useful structure, both in describing real-world
systems and in demonstrating how various algorithms work. This chapter gives you a tour of the basic concepts and
lingo, in case you haven’t dealt with graphs before.
Appendix D: Hints for Exercises. Just what the title says.
Summary
Programming isn’t just about software architecture and object-oriented design; it’s also about solving algorithmic
problems, some of which are really hard. For the more run-of-the-mill problems (such as finding the shortest path
from A to B), the algorithm you use or design can have a huge impact on the time your code takes to finish, and for
the hard problems (such as finding the shortest route through A–Z), there may not even be an efficient algorithm,
meaning that you need to accept approximate solutions.
This book will teach you several well-known algorithms, along with general principles that will help you create
your own. Ideally, this will let you solve some of the more challenging problems out there, as well as create programs
that scale gracefully with problem size. In the next chapter, we get started with the basic concepts of algorithmics,
dealing with terms that will be used throughout the entire book.
If You’re Curious …
This is a section you’ll see in all the chapters to come. It’s intended to give you some hints about details, wrinkles, or
advanced topics that have been omitted or glossed over in the main text and to point you in the direction of further
information. For now, I’ll just refer you to the “References” section, later in this chapter, which gives you details about
the algorithm books mentioned in the main text.
Exercises
As with the previous section, this is one you’ll encounter again and again. Hints for solving the exercises can be found
in Appendix D. The exercises often tie in with the main text, covering points that aren’t explicitly discussed there
but that may be of interest or that deserve some contemplation. If you want to really sharpen your algorithm design
skills, you might also want to check out some of the myriad of sources of programming puzzles out there. There are,
for example, lots of programming contests (a web search should turn up plenty), many of which post problems that
you can play with. Many big software companies also have qualification tests based on problems such as these and
publish some of them online.
Chapter 1
■
IntroduCtIon
7
Because the introduction doesn’t cover that much ground, I’ll just give you a couple of exercises here—a taste of
what’s to come:
1-1. Consider the following statement: “As machines get faster and memory cheaper, algorithms become less
important.” What do you think; is this true or false? Why?
1-2. Find a way of checking whether two strings are anagrams of each other (such as "debit card" and "bad credit").
How well do you think your solution scales? Can you think of a naïve solution that will scale poorly?
References
Applegate, D., Bixby, R., Chvátal, V., Cook, W., and Helsgaun, K. Optimal tour of Sweden.
www.math.uwaterloo.ca/tsp/sweden/
. Accessed April 6, 2014.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms, second edition. MIT Press.
Dasgupta, S., Papadimitriou, C., and Vazirani, U. (2006). Algorithms. McGraw-Hill.
Goodrich, M. T. and Tamassia, R. (2001). Algorithm Design: Foundations, Analysis, and Internet Examples.
John Wiley & Sons, Ltd.
Hetland, M. L. (2008). Beginning Python: From Novice to Professional, second edition. Apress.
Kleinberg, J. and Tardos, E. (2005). Algorithm Design. Addison-Wesley Longman Publishing Co., Inc.
Knuth, D. E. (1968). Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley.
———. (1969). Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley.
———. (1973). Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley.
———. (2011). Combinatorial Algorithms, Part 1, volume 4A of The Art of Computer Programming. Addison-Wesley.
Miller, B. N. and Ranum, D. L. (2005). Problem Solving with Algorithms and Data Structures Using Python.
Franklin Beedle & Associates.
9
Do'stlaringiz bilan baham: |
