Blog

1. Suppose that a list contains the values

20 44 48 55 62 66 74 88 93 99

at index positions 0 through 9. Trace the values of the variables left, right, and midpoint in a binary search of this list for the target value 90. Repeat for the target value 44.

2. The method we usually use to look up an entry in a phone book is not exactly the same as a binary search because, when using a phone book, we don’t always go to the midpoint of the sublist being searched. Instead, we estimate the position of the target based on the alphabetical position of the first letter of the person’s last name. For example, when we are looking up a number for “Smith,” we….

1. Which configuration of data in a list causes the smallest number of exchanges in a selection sort? Which configuration of data causes the largest number of exchanges?

2. Explain the role that the number of data exchanges plays in the analysis of selection sort and bubble sort. What role, if any, does the size of the data objects play?

3. Explain why the modified bubble sort still exhibits O(n2) behavior on the average.

4. Explain why insertion sort works well on partially sorted lists.

Jack decides to rework the banking system, which already includes the classes BankView, Bank, SavingsAccount, and RestrictedSavingsAccount. He wants to add another class for checking accounts. He sees that savings accounts and checking accounts both have some common attributes and behaviors that they can inherit from a superclass named Account. The bank contains zero or more instances of each of the three types of accounts. Draw a class diagram that shows the relationships among the classes in this new version of the system

1. Which configuration of data in a list causes the smallest number of exchanges in a selection sort? Which configuration of data causes the largest number of exchanges?

2. Explain the role that the number of data exchanges plays in the analysis of selection sort and bubble sort. What role, if any, does the size of the data objects play?

3. Explain why the modified bubble sort still exhibits O(n2) behavior on the average.

4. Explain why insertion sort works well on partially sorted lists.

1 Explain the difference between black-box testing and white-box testing.

2 List three advantages of a unit test tool.

3 What is the purpose of the method setup in a unit test?

4 UML class diagrams show

a the interactions among objects

b the relationships among classes

5 Aggregation is a relationship in which

a an instance of one class can contain instances of another

b one class inherits data and operations from another

1. What advantage does a circular linked structure with a dummy header node give the programmer? 2 Describe one benefit and one cost of a doubly linked structure, as compared to a singly linked structure.

3. Examples of linear collections are

a sets and trees

b lists and stacks

4. Examples of unordered collections are

a queues and lists

b sets and dictionaries

5 .A hierarchical collection can represent a

a line of customers at a bank

b a file directory system

Add the methods insert and remove to the Array class. These methods should use the strategies discussed in this chapter, including adjusting the length of the array, if necessary. The insert method expects a position and an item as arguments and inserts the item at the given position. If the position is greater than or equal to the array’s logical size, the method inserts the item after the last item currently available in the array. The remove method expects a position as an argument and removes and returns the item at that position. The remove method’s precondition is 0 <= index=””>< size().=”” the=”” remove=”” method=”” should=”” also=”” reset=”” the=”” vacated=”” array=”” cell=”” to=”” the=”” fill=””>

1. Data in a singly linked structure are contained in

a cells

b nodes

2.  Most operations on singly linked structures run in

a constant time

b linear time

3.  It requires constant time to remove the first item from a(n)

a array

b singly linked structure

4. Add an instance variable _logicalSize to the Array class. This variable is initially 0, and will track the number of items currently available to users of the array. Then add the method size() to the Array class. This method should return the array’s logical size. The method __len__ should still return the array’s capacity or physical size.

1. Jill tells Jack that he should now remove the current implementation of the __iter__ method from the Array class, if it’s really behaving like a list. Explain why this is a good suggestion. Also explain how the __str__ method should be modified at this point.

2. A Matrix class can be used to perform the some of the operations found in linear algebra, such as matrix arithmetic. Develop a Matrix class that uses the built-in operators for arithmetic in a manner similar to the Rational number class discussed in Chapter 8. The Matrix class should extend the Grid class.

The next four projects ask you to define some functions for manipulating linked structures. You should use the Node and TwoWayNode classes, as defined in this chapter. Create….