To do a union, use the addAll method to add one set's contents to the other. To do an intersection, use the retainAll method to remove elements not common to both sets. You can examine every key of a Map by calling the keySet method and then iterating or for-eaching over the keySet.
You can examine every value of a Map by calling the values method and then iterating or for-eaching over that collection of values, or by looking up each associated value using the keys from the keySet. Recursion is a technique where an algorithm is expressed in terms of itself. A recursive method differs from a regular method in that it contains one or more calls to itself within its body.
A base case is a situation where a recursive method does not need to make a recursive call to solve the problem. A recursive case is a situation where the recursive method does call itself. Recursive methods need both cases because the recursive case is called repeatedly until the base case is reached, stopping the chain of recursive calls. A call stack is the structure of information about all methods that have currently been called by your program.
Recursion produces a tall call stack in which each recursive call is represented. The new code shown would cause infinite recursion, because each recursive call just makes another recursive call and doesn't progress toward the base case. The version of the pow method shown does not have any base case, so the recursive calls will never stop. The second version of the pow method is more efficient than the first because it requires fewer recursive calls.
Both versions are recursive. The base case if statement has a bug: It should test for numbers less than 10, not greater.
The following is the correct line:. When the parameters needed for recursion don't match those that make sense for the client to pass, use a public method with the signature desired by the client and a private helper method with the signature needed for the recursion. A fractal is an image that is recursively constructed to contain smaller versions of itself. Recursive methods are useful when drawing fractal images because they can elegantly express the recursive nature of the images.
Recursion is an effective way to implement a backtracking algorithm because the memory of decisions and points to go back to are represented by the recursive call stack. The pattern of "choose, explore, un-choose is elegantly represented by recursive calls for each individual choice. A decision tree is a description of the set of choices that can be made by a recursive backtracking method at any point in the algorithm.
Decision tree that would have resulted for Figure If the solution had explored NE first instead of last, the solutions would have been printed in this order:. There are 64 entries at the second level of the full tree. There are entries at the third level of the full tree. Our algorithm avoids such a huge number of choices by only placing one queen in each column of the board. The 8 Queens explore method stops once it finds one solution to the problem.
This is because the code has the following lines around its recursive call:. The code could be modified so that it would find and output every solution to the problem by changing that code to the following:. You can perform a sequential search over the array using a loop, or you can sort the array using Arrays.
Closest value to the number of elements that the binary search algorithm will need to examineon an array of one million integers:. A sequential search must be used on an array of Point objects because they do not implement Comparable.
To change the order, you could pass a Comparator that defines a different order. To make it work, you could pass a Comparator that defines an ordering for Point s. We could easily reverse the order of our LengthComparator by using the built-in method Collections. Binary search requires a sorted dataset because it uses the ordering to jump to the next index. If the elements are out of order, the search isn't guaranteed to find the target element.
A binary search of 60 elements examines at most 6 elements, because log 2 60 when rounded up equals 6. The algorithm will examine indexes 4, 6, and 5 and will return The algorithm doesn't work properly because the input array isn't sorted.
The binary search algorithm will examine the following indexes and return the following values for each search:. The parameter array type should be changed to double. Also, a new swap method will be needed that accepts a double[] as the first parameter. Here's the new code:. After a single pass of the selection sort algorithm a single swap , the state of the array is:. A merge sort of 32 elements will generate 63 total calls to mergeSort and will perform the merge operation 31 times.
State of the elements after five passes of the outermost loop of selection sort have occurred:. A real-world example of a queue is the waiting line at a fast-food restaurant.
When you push onto a stack, the new element is added to the top. When you pop from a stack, the top element is removed and returned. When you add to a queue, the new element is added to the back. When you remove from a queue, the front element is removed and returned.
The problem with the code is that Queue is an interface, so it cannot be instantiated. Instead, construct a LinkedList object:. In many cases, it's important to save the removed elements somewhere so that you can put them back into the stack or queue when you are done.
Stacks and queues are still useful despite their limited functionality because they are simple and easy to use, and because their operations are all efficient to execute. Many common operations are also naturally represented as a stack or queue. The problem with the code is that the size of the queue is changing while the loop goes over it. Another problem with the code is that it destroys the contents of the queue being examined.
The following version of the code fixes both problems:. The problem with the code is that it calls the remove method twice on each element, which double-removes it and therefore skips elements. Another problem with the code is that it destroys the contents of the stack being examined. The problem with the code is that it puts the odd elements back at the top of the stack each time, so it will never make progress down the stack toward the bottom.
If the stack contains any odd elements, the code will get stuck in an infinite loop. The following version of the code fixes the problem:. An array list's size is the number of elements that have been added to it. Its capacity is the length of its internal array. The size is always less than or equal to the capacity. The ArrayIntList class keeps at least two fields: an array of elements and a size.
The array is necessary because it is where we store the data inside the collection. The size is necessary because some of the elements at the end of the array may not be meaningful values.
If we removed the size field, we would not know how many elements were meaningful. If the fields were static, all lists would share the same array and size. Any modification to one list would also be seen in all other lists. The client's output would be the following:.
In this section's version of the list class, if the client tries to add too many values, the code crashes with an out of bounds exception. We use a toString method because this is the standard way of printing objects in Java. It is also more versatile than a print method because it can print the text representation of the list to any target, such as a file or GUI.
Having accessor methods such as size is better than making the fields public because it preserves the encapsulation of the object. As discussed in Chapter 8, this improves the cleanliness of the abstraction of the object and would allow us to change the implementation later if so desired. It is most expensive to insert or remove at the beginning of the list, because all elements must be shifted to the right by one index.
The preconditions are that the client will not try to construct a list with a negative capacity, and that the client will never pass an index that is negative or outside the size of the list.
The checkIndex method tests whether a given index is between 0 and the size of the list, and if not, throws an exception. If the client passes an invalid index by mistake, the method will halt the program's execution. The checkCapacity method tests whether the array's size will exceed the length of the internal array capacity , and if so, throws an exception.
If the client adds too many elements to the list, the method will halt the program's execution. We can also assume all index parameters passed to various methods are valid once they get through the checkIndex test. These methods are provided as a convenience to the client, to give the list object a more simple and pleasant external interface to use. The list doubles in size when it exceeds its capacity. This is done instead of resizing by a constant amount so that the overall cost of adding elements to the end of a list will be amortized to be O 1 , constant time.
The iterator keeps track of the list to examine, the current index in the list, and whether it is safe to remove an element from the list using the iterator. The iterator knows there are more elements to examine if its current index is below the size of the list. If there is no such element but the client calls next, an exception is thrown. The precondition of remove is that the method next has been called and that next was called more recently than any other call to remove.
The precondition is enforced by a boolean flag in the iterator whose value is changed on every call to next or remove. If the precondition is violated, an exception is thrown.
Java does not allow the construction of arrays of generic types. To work around this, we instead create an array of Object[] and cast it to type E[].
An annotation is a special directive to the compiler with additional information about a class, method, or other structure. Annotations help us when writing our generic list because we can instruct the compiler not to warn us about potentially unsafe casting operations. When the iterator is an inner class, it can directly access the fields of the enclosing list object.
This makes it easier for the iterator to do its work without keeping track of as much state. The difference between a linked list and an array list is that while an array list stores all of its elements in a single large array, a linked list stores each element inside its own container object called a node.
The nodes are connected linked to each other by references. The two kinds of lists are similar in that they both implement the same external operations to clients, such as methods for adding, removing, accessing, and locating elements. A node is a small object that stores a single element of a linked list.
The list object stores reference s to a small number of nodes, perhaps only the front of the list. The front contains a chain of references that connect to the other elements of the list. The next field of the last node of a list, as well as any unspecified next field, stores null. When the client tries to go past the end of a linked list, there will be a null pointer exception. The two ways to change an object of our linked list class are to change its front reference or to change the next or data field of an existing node.
Inserting and removing is most expensive at the end of the list, because the code must loop through all of the next references to reach the end. The loop should stop and index i - 1 , the index before the one to add or remove. This is so that you can adjust the preceding node's next reference.
Note which values change and which ones stay the same. Write a complete Java program to draw the stairs. Use your table from the previous slide to help you find the correct expressions. The values that change for each stair should become expressions in terms of the loop counter variable, i. Modify your stairs program to draw one or all of the following outputs. Modify only the body in your for loop. You may want to make a new table to find the expressions for x, y, width, and height.
When you want to divide a graphical program into multiple drawing methods, you must pass Graphics g as a parameter in addition to any other parameters. Modify your previous Face program to draw the following output.
Write a parameterized method that allows you to draw a face at different positions. Suppose you have an existing program that draws the "face" figure at right. Let's modify the program using methods and parameters so that we can draw several faces at different locations. Modify the Face program to draw the following output. Write a parameterized method that draws a face at different positions. Modify your previous Java program to draw the following output.
Use a for loop with your parameterized method to draw faces at different positions. If you finish all the exercises, try out our Practice-It web tool. Teaching a novice to program is like building a house of cards. Each new card has to be placed carefully. If you rush the process and try to place too many cards at once, the entire structure collapses. Please also visit Addison Wesley's official promotional web site about our book, linked below.
I believe this book delivers on its title. It is a well written book that focuses on the basics of learning a programming language without getting lost among "hot" topics like OO, IDE's, or GUI's.
I will be switching my classes to this book. It is obvious that the authors teach the course and understand the needs of the students. I like [the authors'] story-telling writing style, which is very appropriate for the novices. Important concepts are gradually introduced with an appropriate logic of precedence. Concepts are discussed in a crystal clear fashion so students should be able to answer questions.
The liberal use of graphics, including those created with text, is a powerful technique for helping learners to understand algorithms, concepts, etc The figures greatly enhance the corresponding narrative I like the carefully done examples [and] that previous examples are repeated so the reader doesn't have to page back to find it.
The author[s have] chosen wisely to present enough material without trying to include everything.
0コメント