8.1
\nA Balanced Introduction to Computer Science, 3\/E
\nDavid Reed \u00a9Pearson Prentice Hall, 2011
\nChapter 8 Review Question Solutions
\n1. TRUE or FALSE? An algorithm is a step-by-step sequence of instructions for carrying
\nout some task.
\nTRUE
\n2. TRUE or FALSE? A sequence of instructions for assembling a bookcase does not
\nqualify as an \u201calgorithm\u201d since the instructions are not written in formal, mathematical
\nnotation.
\nFALSE
\n3. TRUE or FALSE? For a precise, clearly-stated problem, there can be only one algorithm
\nthat solves that problem.
\nFALSE
\n4. TRUE or FALSE? Big-Oh notation is used to measure the exact number of seconds
\nrequired by a particular algorithm when executing on a particular computer.
\nFALSE
\n5. TRUE or FALSE? Suppose you have been given a sorted list of 100 names and need to
\nfind a particular name in that list. Using sequential search, it is possible that you might
\nhave to look at every location in the list before finding the desired name.
\nTRUE
\n6. TRUE or FALSE? Suppose you have been given a sorted list of 100 names and need to
\nfind a particular name in that list. Using binary search, it is possible that you might have
\nto look at every location in the list before finding the desired name.
\nFALSE
\n7. TRUE or FALSE? Binary search is an example of an O(log N) algorithm, where the
\nnumber of items in the list to be searched is N.
\n8.2
\nTRUE
\n8. TRUE or FALSE? One advantage of assembly languages over machine languages is that
\nthey enable the programmer to use words to identify instructions instead of using binarynumber
\nsequences.
\nTRUE
\n9. TRUE or FALSE? JavaScript, C++, and Java are all examples of high-level
\nprogramming languages.
\nTRUE
\n10. TRUE or FALSE? When a Web page is loaded into a Web browser, JavaScript code in
\nthat page is executed by a JavaScript interpreter that is embedded in the browser.
\nTRUE
\n11. An algorithm must be clear to its intended executor in order to be effective. Give an
\nexample of a real-world algorithm that you have encountered and felt was not clear. Do
\nyou think that the algorithm writer did a poor job, or do you think that the algorithm was
\nformalized with a different audience in mind? Explain your answer. Then, give an
\nexample of a real-world algorithm that you felt was clearly stated. What features of this
\nalgorithm allow you to understand it more easily?
\nStudent responses will vary.
\n12. Write an algorithm for directing a person to your house, apartment, or dorm from a
\ncentral location. For example, if you live on campus, the directions might originate at a
\ncampus landmark. Assume that the person following the directions is familiar with the
\nneighborhood or campus.
\nStudent responses will vary.
\n13. Write an alternative algorithm for directing a person to your residence, but this time,
\nassume that the person is unfamiliar with the area. How does this condition affect the
\nway you describe the algorithm?
\nStudent responses will vary.
\n14. Suppose that you were asked to arrange a group of people in sequence from oldest to
\nyoungest. You must organize a line that begins with the oldest person and continues in
\ndescending order according to age. Describe an algorithm for completing this task.
\n8.3
\nStudent responses will vary. One possible solution is to apply the algorithm from the
\nbook for finding the oldest person repeatedly. That is, find the oldest person using the
\nalgorithm, and place that person at the front of a line. Then, repeat the process on the
\nremaining people, placing the next oldest second in line, and so on until all people have
\nbeen placed.
\n15. Suppose that you have been given an O(N) algorithm that averages student grades, where
\nN is the number of grades. If it takes 1 minute to average 100 grades using the algorithm,
\nhow long would you expect it to take to average 200 grades? 400 grades? Justify your
\nanswer.
\nSince the algorithm is O(N), doubling the size of the problem should roughly double the
\ntime required for a solution. Thus, 200 grades would require roughly 2 minutes, and 400
\ngrades would require roughly 4 minutes.
\n16. Suppose you needed to look up a number in your local phone book. Roughly, what is the
\npopulation of your city? How many checks would be required, in the worst case, to find
\nthe phone number using sequential search? How many checks would be required, in the
\nworst case, to find the phone number using binary search?
\nStudent answers will depend upon local population. For sequential search: In the best
\ncase, the name will appear first in the book, requiring only 1 inspection. In the worst
\ncase, the name will appear last in the book, requiring all entries to be inspected. For
\nbinary search: In the best case, the name will appear in the exact middle of the book,
\nrequiring only 1 inspection. There are many worst case positions, including the first and
\nlast positions in the book, requiring log2 N inspections, where N is the number of entries
\nin the book.
\n17. Consider the list of states from Figure 8.5. Which state in the list is the “easiest” to find
\nusing binary search? That is, which state could be located in the fewest number of
\nchecks? Generalize your answer so that it applies to any sorted list of items.
\nThe easiest state to find would be “Missouri” since it appears at the middle position in the
\nlist. In general, the middle position is the easiest since it is the first place inspected.
\n18. Again, consider the list of states from Figure 8.5. Which state in the list is the “hardest”
\nto find using binary search? That is, which state would require the largest number of
\nchecks to be located? Generalize your answer so that it applies to any sorted list of items.
\nOne of the hardest states would be “WY”, which appears at the end of the list. Since the
\nsearch always checks the middle of the range, the end will only be reached when the
\nrange is reduced to size 1.
\n19. Refer to the Newton.html page. How many refinements does Newton’s algorithm
\nrequire to compute the square root of 900? 10,000? 152,399,025?
\n8.4
\n900 converges to 300 in 10 refinements.
\n10,000 converges to 100 in 11 refinements.
\n152,399,025 converges to 12,345 in 18 refinements.
\n20. Imagine that, while you are using Newton’s algorithm, the approximations converge on
\nthe actual square root of the number. What would happen if you tried to further refine the
\nsquare root? Would the value change? Why or why not?
\nAttempting to further refine the actual square root will produce no change, since
\n( + N\/ ) \/ 2 = ( + ) \/ 2 = .
\n21. A disadvantage of machine languages is that they are machine dependent. That is, each
\nmachine language is specific to a particular computer, and different computers require
\ndifferent machine languages. Describe why this is the case.
\nMachine language instructions correspond to the low-level operations that can be
\nexecuted by the hardware of the machine. Since different computers have different
\nCPUS, register configurations, and ALU operations, their machine languages will differ.
\n22. Describe two advantages of high-level language programming over machine-language
\nprogramming.
\nHigh-level languages allow the programmer to code at a higher level of abstraction,
\nfocusing on problem-solving constructs such as conditionals and loops, instead of lowlevel
\nmachine details. In addition, high-level languages are not specific to the underlying
\ncomputer\u2019s hardware configuration, so programs are portable across computers.
\n23. What is the difference between a compiler and an interpreter? What characteristics of an
\ninterpreter make it better suited for executing JavaScript programs?
\nA compiler is a program that translates an entire high-level language program into its
\nequivalent machine-language instructions. In contrast, an interpreter translates and
\nexecutes the statements in the high-level language program one statement at a time.
\nWhile this can make the execution of programs slower, it does provide immediate
\nfeedback as the output of statements can be displayed as they are executed in turn.<\/p>\n","protected":false},"excerpt":{"rendered":"
8.1 A Balanced Introduction to Computer Science, 3\/E David Reed \u00a9Pearson Prentice Hall, 2011 Chapter 8 Review Question Solutions 1. TRUE or FALSE? An algorithm is a step-by-step sequence of instructions for carrying out some task. TRUE 2. TRUE or FALSE? A sequence of instructions for assembling a bookcase does not qualify as an \u201calgorithm\u201d […]<\/p>\n","protected":false},"author":274,"featured_media":0,"parent":1329,"menu_order":0,"comment_status":"closed","ping_status":"open","template":"","meta":{"_mi_skip_tracking":false},"_links":{"self":[{"href":"https:\/\/sites.evergreen.edu\/compcog15\/wp-json\/wp\/v2\/pages\/1360"}],"collection":[{"href":"https:\/\/sites.evergreen.edu\/compcog15\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.evergreen.edu\/compcog15\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.evergreen.edu\/compcog15\/wp-json\/wp\/v2\/users\/274"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.evergreen.edu\/compcog15\/wp-json\/wp\/v2\/comments?post=1360"}],"version-history":[{"count":0,"href":"https:\/\/sites.evergreen.edu\/compcog15\/wp-json\/wp\/v2\/pages\/1360\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/sites.evergreen.edu\/compcog15\/wp-json\/wp\/v2\/pages\/1329"}],"wp:attachment":[{"href":"https:\/\/sites.evergreen.edu\/compcog15\/wp-json\/wp\/v2\/media?parent=1360"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}