Classic Computer Science Problems in Java
eBook - ePub

Classic Computer Science Problems in Java

David Kopec

Share book
  1. 264 pages
  2. English
  3. ePUB (mobile friendly)
  4. Available on iOS & Android
eBook - ePub

Classic Computer Science Problems in Java

David Kopec

Book details
Book preview
Table of contents
Citations

About This Book

Sharpen your coding skills by exploring established computer science problems! Classic Computer Science Problems in Java challenges you with time-tested scenarios and algorithms. Summary
Sharpen your coding skills by exploring established computer science problems! Classic Computer Science Problems in Java challenges you with time-tested scenarios and algorithms. You'll work through a series of exercises based in computer science fundamentals that are designed to improve your software development abilities, improve your understanding of artificial intelligence, and even prepare you to ace an interview. As you work through examples in search, clustering, graphs, and more, you'll remember important things you've forgotten and discover classic solutions to your "new" problems! Purchase of the print book includes a free eBook in PDF, Kindle, and ePub formats from Manning Publications. About the technology
Whatever software development problem you're facing, odds are someone has already uncovered a solution. This book collects the most useful solutions devised, guiding you through a variety of challenges and tried-and-true problem-solving techniques. The principles and algorithms presented here are guaranteed to save you countless hours in project after project. About the book
Classic Computer Science Problems in Java is a master class in computer programming designed around 55 exercises that have been used in computer science classrooms for years. You'll work through hands-on examples as you explore core algorithms, constraint problems, AI applications, and much more. What's inside Recursion, memoization, and bit manipulation
Search, graph, and genetic algorithms
Constraint-satisfaction problems
K-means clustering, neural networks, and adversarial search About the reader
For intermediate Java programmers. About the author
David Kopec is an assistant professor of Computer Science and Innovation at Champlain College in Burlington, Vermont. Table of Contents 1 Small problems
2 Search problems
3 Constraint-satisfaction problems
4 Graph problems
5 Genetic algorithms
6 K-means clustering
7 Fairly simple neural networks
8 Adversarial search
9 Miscellaneous problems
10 Interview with Brian Goetz

Frequently asked questions

How do I cancel my subscription?
Simply head over to the account section in settings and click on ā€œCancel Subscriptionā€ - itā€™s as simple as that. After you cancel, your membership will stay active for the remainder of the time youā€™ve paid for. Learn more here.
Can/how do I download books?
At the moment all of our mobile-responsive ePub books are available to download via the app. Most of our PDFs are also available to download and we're working on making the final remaining ones downloadable now. Learn more here.
What is the difference between the pricing plans?
Both plans give you full access to the library and all of Perlegoā€™s features. The only differences are the price and subscription period: With the annual plan youā€™ll save around 30% compared to 12 months on the monthly plan.
What is Perlego?
We are an online textbook subscription service, where you can get access to an entire online library for less than the price of a single book per month. With over 1 million books across 1000+ topics, weā€™ve got you covered! Learn more here.
Do you support text-to-speech?
Look out for the read-aloud symbol on your next book to see if you can listen to it. The read-aloud tool reads text aloud for you, highlighting the text as it is being read. You can pause it, speed it up and slow it down. Learn more here.
Is Classic Computer Science Problems in Java an online PDF/ePUB?
Yes, you can access Classic Computer Science Problems in Java by David Kopec in PDF and/or ePUB format, as well as other popular books in Computer Science & Computer Science General. We have over one million books available in our catalogue for you to explore.

Information

Publisher
Manning
Year
2020
ISBN
9781638356547

1 Small problems

To get started, we will explore some simple problems that can be solved with no more than a few relatively short functions. Although these problems are small, they will still allow us to explore some interesting problem-solving techniques. Think of them as a good warm-up.

1.1 The Fibonacci sequence

The Fibonacci sequence is a sequence of numbers such that any number, except for the first and second, is the sum of the previous two:
0, 1, 1, 2, 3, 5, 8, 13, 21...
The value of the first Fibonacci number in the sequence is 0. The value of the fourth Fibonacci number is 2. It follows that to get the value of any Fibonacci number, n, in the sequence, one can use the formula
fib(n) = fib(n - 1) + fib(n - 2)

1.1.1 A first recursive attempt

The preceding formula for computing a number in the Fibonacci sequence (illustrated in figure 1.1) is a form of pseudocode that can be trivially translated into a recursive Java method. (A recursive method is a method that calls itself.) This mechanical translation will serve as our first attempt at writing a method to return a given value of the Fibonacci sequence.
1-1

Figure 1.1 The height of each stickman is the previous two stickmenā€™s heights added together.
Listing 1.1 Fib1.java
package chapter1; public class Fib1 {  // This method will cause a java.lang.StackOverflowError private static int fib1(int n) { return fib1(n - 1) + fib1(n - 2); }
Letā€™s try to run this method by calling it with a value.
Listing 1.2 Fib1.java continued
 public static void main(String[] args) {  // Don't run this! System.out.println(fib1(5)); } }
Uh-oh! If we try to run Fib1.java, we generate an exception:
Exception in thread "main" java.lang.StackOverflowError
The issue is that fib1() will run forever without returning a final result. Every call to fib1() results in another two calls of fib1() with no end in sight. We call such a circumstance infinite recursion (see figure 1.2), and it is analogous to an infinite loop.
1-2

Figure 1.2 The recursive function fib(n) calls itself with the arguments n-1 and n-2.

1.1.2 Utilizing base cases

Notice that until you run fib1(), there is no indication from your Java environment that there is anything wrong with it. It is the duty of the programmer to avoid infinite recursion, not the compiler. The reason for the infinite recursion is that we never specified a base case. In a recursive function, a base case serves as a stopping point.
In the case of the Fibonacci sequence, we have natural base cases in the form of the special first two sequence values, 0 and 1. Neither 0 nor 1 is the sum of the previous two numbers in the sequence. Instead, they are the special first two values. Letā€™s try specifying them as base cases.
Listing 1.3 Fib2.java
package chapter1; public class Fib2 { private static int fib2(int n) { if (n < 2) { return n; } return fib2(n - 1) + fib2(n - 2); }
Note The fib2() version of the Fibonacci method returns 0 as the zeroth number (fib2(0)), rather than the first number, as in our original proposition. In a programming context, this kind of makes sense because we are used to sequences starting with a zeroth element.
fib2() can be called successfully and will return correct results. Try calling it with some small values.
Listing 1.4 Fib2.java continued
 public static void main(String[] args) { System.out.println(fib2(5)); System.out.println(fib2(10)); } }
Do not try calling fib2(40). It may take a very long time to finish executing! Why? Every call to fib2() results in two more calls to fib2() by way of the recursive calls fib2(n - 1) and fib2(n - 2) (see figure 1.3). In other words, the call tree grows exponentially. For example, a call of fib2(4) results in this entire set of calls:
fib2(4) -> fib2(3), fib2(2) fib2(3) -> fib2(2), fib2(1) fib2(2) -> fib2(1), fib2(0) fib2(2) -> fib2(1), fib2(0) fib2(1) -> 1 fib2(1) -> 1 fib2(1) -> 1 fib2(0) -> 0 fib2(0) -> 0
1-3

Figure 1.3 Every non-base-case call of fib2() results in two more calls of fib2().
If you count them (and as you will see if you add some print calls), there are 9 calls to fib2() just to compute the 4th element! It gets worse. There are 15 calls required to compute element 5, 177 calls to compute element 10, and 21,891 calls to compute element 20. We can do better.

1.1.3 Memoization to the rescue

Memoization is a technique in which you store the results of computational tasks when they are completed so that when you need them again, you can look them up instead of needing to compute them a second (or millionth) time (see figure 1.4).1
1-4

Figure 1.4 The human memoization machine
Letā€™s create a new version of the Fibonacci method that utilizes a Java map for memoization purposes.
Listing 1.5 Fib3.java
package chapter1; import java.util.HashMap; import java.util.Map; public class Fib3 {  // Map.of() was introduced in Java 9 but returns  // an immutable Map  // This creates a map with 0->0 and 1->1  // which represent our base cases static Map<Integer, Integer> memo = new HashMap<>...

Table of contents