7.7 Important Threads

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

7.7 Important Threads

In the last two chapters, we have mentioned several topics in passing that are important not only in problem solving but also in computing in general. Let’s review some of the common threads discussed in these chapter.

Information Hiding

We have mentioned the idea of deferring the details several times. We have used it in the context of giving a name to a task and not worrying about how the task is to be implemented until later. Deferring the details in a design has distinct advantages. The designer sees just those details that are relevant at a particular level of the design. This practice, called information hiding, makes the details at a lower level inaccessible during the design of the higher levels.

This practice must seem very strange! Why shouldn’t the details be accessible while the algorithm is being designed? Shouldn’t the designer know everything? No. If the designer knows the low-level details of a module, he or she is more likely to base the module’s algorithm on these details—and it is precisely these low-level details that are more likely to change. If they do, then the entire module has to be rewritten.

Abstraction

Abstraction and information hiding are two sides of the same coin. Information hiding is the practice of hiding details; abstraction is the result with the details hidden. As we said in Chapter 1, an abstraction is a model of a complex system that includes only the details that are essential for the viewer to know. Take, for example, Daisy, the English spaniel. To her owner, she is a household pet; to a hunter, she is a bird dog; and to the vet, she is a mammal. Her owner watches Daisy’s wagging tail, hears her yelp when she gets left outside, and sees the hair she leaves everywhere. The hunter sees a finely trained helper who knows her job and does it well. The vet sees all of the organs, flesh, and bones of which she is composed. See FIGURE 7.17.

Three photographs of the same dog are shown in different views of the same concept as the dog is playing with a ball, the dog is walking on grass, and the skeleton of the dog. — FIGURE 7.17 Different views of the same concept

In computing, an algorithm is an abstraction of the steps needed to implement it. The casual user of a program that includes the algorithm, who sees only the description of how to run the program, is like the dog owner: He or she sees only the surface. The programmer, who incorporates another’s algorithm in her program, is like the hunter who uses the well-trained dog: He or she uses the algorithm for a purpose. The implementer of the algorithm, who must understand it thoroughly, is like the vet: He or she must see the inner workings to implement the algorithm.

In computing, various kinds of abstraction are apparent. Data abstraction refers to the view of data; it is the separation of the logical view of data from its implementation. For example, your bank’s computer may represent numbers in two’s complement or one’s complement, but this distinction is of no concern to you as long as your bank statements are accurate.

Procedural abstraction refers to the view of actions; it is the separation of the logical view of an action from its implementation. For example, when we gave a name to a subprogram, we were practicing procedural abstraction.

A third kind of abstraction in computing is called control abstraction. Control abstraction refers to the view of a control structure; it is the separation of the logical view of a control structure from its implementation. A control structure lets us alter this sequential flow of control of an algorithm. WHILE and IF are control structures. How these control structures are implemented in the languages into which we might translate an algorithm is immaterial to the design of the algorithms.

Abstraction is the most powerful tool people have for managing complexity. This statement is true in computing as well as real life.

Naming Things

When we write algorithms, we use shorthand phrases to stand for the tasks and data with which we are dealing. We give names to data and processes. These names are called identifiers. For example, we used newBase and decimalNumber in the base-changing algorithm. We also gave names to tasks. For example, we used Split to name the task of splitting an array in the Quicksort algorithm. Our identifiers for data values were created from a combination of the words, using uppercase to make the meaning clearer. We left the names of tasks as phrases. Eventually the task names must be converted to a single identifier.

When we get to the stage where we translate an algorithm into a program in a language that a computer can execute, we may have to modify the identifiers. Each language has its own rules about forming identifiers. So there is a two-stage process: Data and actions are given names in the algorithm, and then these names are translated into identifiers that meet the rules of the computer language. Notice that giving identifiers to data and actions is a form of abstraction.

Testing

We have demonstrated testing at the algorithm phase using algorithm walk-throughs. We have shown how to design test plans and implemented one in assembly language. Testing is important at every stage in programming. There are basically two types of testing: clear-box testing, which is based on the code itself, and black-box testing, which is based on testing all possible input values. Often, a test plan incorporates both types of testing.

SUMMARY

Polya, in his classic book How to Solve It, outlined a problem-solving strategy for mathematical problems. This strategy can be applied to all problems, including those for which a computer program is to be written. These strategies include asking questions, looking for familiar things, and dividing and conquering; when these strategies are applied, they should lead to a plan for solving a problem. In computing, such a plan is called an algorithm.

Two categories of loops are distinguished: count controlled and event controlled. A count-controlled loop executes the loop a predetermined number of times. An event-controlled loop executes until an event within the loop changes.

Data comes in two forms: atomic (simple) and composite. An array is a homogeneous structure that gives a name to a collection of items and allows the user to access individual items by position within the structure.

Searching is the act of looking for a particular value in an array. In this chapter we examined the linear search in an unsorted array, the linear search in a sorted array, and the binary search in a sorted array. Sorting is the act of putting the items in an array into some kind of order. The selection sort, bubble sort, insertion sort, and Quicksort are four commonly used sorting algorithms.

Recursive algorithms are algorithms for which the name of a subprogram appears in the subprogram itself. The factorial and binary search are naturally recursive algorithms.

ETHICAL ISSUES

Open-Source Software^4,5

If an application you purchased from a proprietary software vendor breaks, you cannot pop open the hood, tinker with the source code, and continue working away. The source code is owned and copyrighted by the manufacturer, and modifying, copying, or reselling it to others is illegal.

Open-source software offers an alternative to this proprietary arrangement. Open-source applications allow users to modify the source code in any way they like. They can add to it, change it, or extend it. They can also copy it, give it away to others, or even sell it. The only proviso is that those to whom the revised code is further distributed have the same freedoms to access the source code, copy, or sell the software. This passing along of the freedoms of use is sometimes referred to as “copyleft” and is highly prized by open-source supporters.

When proprietary software made its first appearance, some parties in the computing community saw it as a threat to the freedom of intellectual collaboration. They believed that software is essentially an intellectual product and, therefore, is best served by being treated as an idea: Anyone is welcome to join the debate, add an opinion, and bring friends into the conversation. Furthermore, if a person cannot gain access to software except by purchasing it from a proprietary vendor, then that individual is barred from joining the discussion until he or she hands over cash to the owner of the “idea.”

In response to the changing landscape of computing in the 1980s, some MIT computer scientists formed the Free Software Foundation (FSF) to promote the open use and sharing of software. The Boston-based group developed the General Public License (GPL), which outlines the rules under which users can share, distribute, and collaborate on developing software products. For those who feel “free” might be an erroneous name, FSF points out, it means “free as in free speech, not free as in free beer.”

So what makes this seemingly simple idea so controversial? If anyone can upgrade or improve the product, doesn’t this increase its value to users? Not according to opponents of the open-source ethic. Microsoft and other proprietary software producers view open-source code as a threat to their businesses. If people can fix and modify the source code on their own, they will not want to pay the licensing fees required to use the proprietary products, nor will they want to purchase upgrades. Even more important, opponents claim, is the danger to intellectual property rights posed by the open-source model.

Open-source supporters point to the more cost-effective aspects of the model. Even if users initially pay for the software, the freedoms granted under the licensing agreement do not lock them into that choice. They can mix and match software to best suit the needs of their mission. Fans of the open-source model also note that such software tends to be more reliable, causing less downtime and requiring internal IT departments and engineers to spend less time fixing low-level problems that might otherwise cause great disruption. Those opposed to the use of software that allows anyone access to the source code claim that it poses much greater security risks than proprietary packages. For example, if airlines, hospitals, and municipal infrastructures are using it, they leave themselves much more vulnerable to attack than if they use packages where only the maker has access to the source code.

Perhaps the most famous example of open-source software is the Linux operating system, which is licensed under the Free Software Foundation’s General Public License. The success of Linux has given great hope to the open-source community. This operating system is extremely popular and is even used, if somewhat sparingly, by government agencies. Versions of Linux are sold by a variety of vendors, including Red Hat, the best-known Linux distributor. Such examples serve as confirmation that the open-source model is commercially viable.

Proprietary producers have been working to block proposals that would require governments to shift to using open-source products. For now, patent and copyright laws continue to favor proprietary software. Whether this continues to be the case remains to be seen. Microsoft has suggested limiting open-source software in various ways, but so far has not proved successful in its quest. For now, the debate continues over whether the open-source model is a benefit for all, or a danger to business and property rights.

In 2008, the open-source software community reached a legal milestone. The case in question centered on free software used in developing commercial software products for model trains. The software’s creator, open-source software group Java Model Railroad Interface, claimed that when Matthew Katzer used its software to create commercial products without following the terms of the software license associated with the software, he had infringed on copyright laws. The software license stated that anyone using the free code had to credit the author, emphasize the source of the files, and explain how the code had been adapted. After a lower court ruling sided with Katzer, a federal appeals court ruled that open-source artistic licensing agreements could be upheld by copyright laws, enforcing the rights of companies using open-source software to protect their ideas.

KEY TERMS

EXERCISES

For Exercises 1–6, match the problem-solving strategy with the definition or example.

Ask questions
Look for familiar things
Divide and conquer

1. The first strategy to use when given a problem
2. Don’t reinvent the wheel.
3. Strategy used in the binary search algorithms
4. Is a solution to a previous problem appropriate for the current one?
5. Strategy used in the Quicksort algorithm
6. There is an apparent contradiction in the problem statement.

For Exercises 7–10, match the phase with its output.

Analysis and specification phase
Algorithm development phase
Implementation phase
Maintenance phase

7. Working program
8. None
9. Problem statement
10. General solution

For Exercises 11–15, match the term with the definition.

Information hiding
Abstraction
Data abstraction
Procedural abstraction
Control abstraction

11. The practice of hiding the details of a module with the goal of controlling access to the details of the module.
12. A model of a complex system that includes only details that are essential to the viewer.
13. The separation of the logical view of an action from its implementation.
14. The separation of the logical view of a control structure from its implementation.
15. The separation of the logical view of data from its implementation.

For Exercises 16–36, mark the answers true or false as follows:

True
False

16. Count-controlled loops repeat a specific number of times.
17. Event-controlled loops repeat a specific number of times.
18. Count-controlled loops are controlled by a counter.
19. Event-controlled loops are controlled by an event.
20. An infinite loop is a loop that never terminates.
21. Loops can be nested, but selection structures cannot.
22. Selection structures can be nested, but loops cannot.
23. All control structures can be nested.
24. The square root algorithm uses a count-controlled loop.
25. An array is a homogeneous structure, but a record is not.
26. A record is a heterogeneous structure, but an array is not.
27. A record is a homogeneous structure; an array is a heterogeneous structure.
28. The bubble sort algorithm involves finding the smallest item in the unsorted portion of the array and swapping it with the first unsorted item.
29. Quicksort is not always quick.
30. A binary search can be applied to both a sorted array and an unsorted array.
31. A binary search is always faster than a linear search.
32. A selection sort puts one more item into its permanent place at each iteration.
33. An insertion sort puts one more item into its place with respect to the already sorted portion.
34. Recursion is another word for iteration.
35. Recursive algorithms use IF statements.
36. Iterative algorithms use WHILE statements.

Exercises 37–62 are short-answer questions.

37. List the four steps in Polya’s How to Solve It list.
38. Describe the four steps listed in Exercise 37 in your own words.
39. List the problem-solving strategies discussed in this chapter.
40. Apply the problem-solving strategies to the following situations.
1. Buying a toy for your four-year-old cousin
2. Organizing an awards banquet for your soccer team
3. Buying a dress or suit for an awards banquet at which you are being honored
41. Examine the solutions in Exercise 40 and determine three things they have in common.
42. What is an algorithm?
43. Write an algorithm for the following tasks.

Making a peanut butter and jelly sandwich
Getting up in the morning
Doing your homework
Driving home in the afternoon

44. List the phases of the computer problem-solving model.
45. How does the computer problem-solving model differ from Polya’s problem-solving model?
46. Describe the steps in the algorithm development phase.
47. Describe the steps in the implementation phase.
48. Describe the steps in the maintenance phase.
49. Look up a recipe for chocolate brownies in a cookbook and answer the following questions.

Is the recipe an algorithm? Justify your answer.
Organize the recipe as an algorithm, using pseudocode.
List the words that have meaning in computing.
List the words that have meaning in cooking.
Make the brownies and take them to your professor.

50. We said that following a recipe is easier than developing one. Go to the supermarket and buy a vegetable that you have not cooked (or eaten) before. Take it home and develop a recipe. Write up your recipe and your critique of the process. (If it is good, send it to the authors.)
51. Describe the top-down design process.
52. Differentiate between a concrete step and an abstract step.
53. Write a top-down design for the following tasks.

Buying a toy for your four-year-old cousin
Organizing an awards banquet for your soccer team
Buying a dress or suit for an awards banquet at which you are being honored

54. Write a top-down design for the following tasks.

Calculating the average of ten test scores
Calculating the average of an unknown number of test scores
Describing the differences in the two designs

55. Write a top-down design for the following tasks.

Finding a telephone number in the phone book
Finding a telephone number on the Internet
Finding a telephone number on a scrap of paper that you have lost
Describe the differences among these designs.

56. Distinguish between information and data.
57. Write a top-down design for sorting a list of names into alphabetical order.
58.

Why is information hiding important?
Name three examples of information hiding that you encounter every day.

59. An airplane is a complex system.

Give an abstraction of an airplane from the view of a pilot.
Give an abstraction of an airplane from the view of a passenger.
Give an abstraction of an airplane from the view of the cabin crew.
Give an abstraction of an airplane from the view of a maintenance mechanic.
Give an abstraction of an airplane from the view of the airline’s corporate office.

60. List the identifiers and indicate whether they named data or actions for the designs in Exercise 53.
61. List the identifiers and indicate whether they named data or actions for the designs in Exercise 54.
62. List the identifiers and indicate whether they named data or actions for the designs in Exercise 55.

Exercises 63–65 use the following array of values.

An array named ‘list’ of length 11 from the index [0] to [10] reads from left to right: 23, 41, 66, 20, 2, 90, 9, 34, 19, 40, and 99.

63. Show the state of the list when firstUnsorted is first set equal to the fourth item in the selection sort.
64. Show the state of the list when firstUnsorted is first set equal to the fifth item in the bubble sort algorithm.
65. Show the state of the list when the first recursive call is made in Quicksort using list[0] as the split value.

Exercises 66 and 67 use the following array of values.

An array named ‘list’ of length 11 from the index [0] to [10] reads from left to right: 5, 7, 20, 33, 44, 46, 48, 99, 101, 102, and 105.

66. How many comparisons does it take using a sequential search to find the following values or determine that the item is not in the list?

67. How many comparisons does it take using a binary search to find the following values or determine that the item is not in the list?

THOUGHT QUESTIONS

Top-down design creates scaffolding that is used to write a program. Is all of this scaffolding just a waste of effort? Is it ever used again? Of what value is it after the program is up and running?
Which of the problem-solving strategies do you use the most? Can you think of some others that you use? Would they be appropriate for computing problem solving?
There are several common examples of open-source software that many people use in their everyday lives. Can you name any?
Do you believe that the quality of an open-source software product is likely to be higher or lower than the quality of software produced by a large corporation? How do you think technical support for open-source software compares to that for proprietary software?
Daniel Bricklin (whose biography appears in Chapter 12) did not patent or copyright his software, believing that software should not be proprietary. As a result, he lost a great deal of money in the form of possible royalties. Do you consider his actions to be visionary or naive?
The Free Software Foundation is a tax-exempt charity that raises funds for work on the GNU Project. GNU software is free. Read about its philosophy on the Web. Compare GNU products with those of manufacturers such as Microsoft and Sun.
If you were to continue with computing and become a programmer, which side of the argument would you take: Should software be copyrighted or should it be free?

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 7.7 Important Threads

Create new playlist

Sign In

Sign Up

Table of Contents for
7.7 Important Threads