CMP 507
Home Work #5
1. How can information hiding promote ease of program modification?
With information hiding technology, the programmer only deal with the interface of the function not detail
of the function, which make job much easier.
2. What dose it means to say that efficiency trades off against generality?
In computer science, we find that more general we make a language or system, the less efficient it becomes,
whereas the more limited we make a system, the more efficiently it can be made to run.
3. What is a client/server mode processing?
The module or function is organized specifically to provide a group of services to its users. In such a case,
we speak of the module as a server and the user as clients.
4. How do you make reusable components available to software design?
A software project that first attempts to build general purpose, reusable software components, and that later
uses these components in system construction employs a bottom-up software implementation process.
5. Explain the concepts of regression testing and acceptance testing.
Regression test makes sure that everything that used to work still works in updated new system. Acceptance
test is a practice, in which a completed software system must pass a specified test in order to be accepted for
delivery.
6. Explain the philosophy of measurement and tuning.
The philosophy of measurement and tuning is a method for improving the efficiency of actual running
program. It is very hard to predict where the inefficiencies happen so that it makes sense first to measure
the running program and find out in which regions the program is spending most of its time. In order to
improve you program, you may use better algorithm or code to replace the bad one in these critical regions.
Next, you measure the results to see how much improvement has been achieved. You might need to iterate
the process of introducing trail improvements and measuring their effects. The latter step is tuning.
7. What is an execution-time profile tool (or a profile)?
Execution time profile tool is used to measure where a program is spending it time. You can turn on the
profiler and conduct a trial run of the program you are measuring. The profile them give you a break down
of what percentage of the total time was spent in different places in the code for the program.
8. Why does making use of reusable software components reduce the effort required to build a given
software system?
The cost of software development depends on the Lines of the Instruction Code. Reusable components can
reduce the efforts on the module development and test, which saves money.
9. What is bottom-up programming? When might it be useful to plan to implement a software system
using bottom-up programming.
Start programming with very basic function and combine the basic function to a higher level function until
all the process constructed. The bottom-up implementation is used in reusable components and standard
library functions available the project.
10. List at least ten programming proverbs.
1. Use meaningful names for your variables.
2. Define named constants once at beginning of your program.
3. Avoid using goto’s and never write spaghetti code.
4. Write short functions that do just one thing and do it well.
5. Modularize your programs so the parts interact cleanly and simply
6. Use reusable components and standard function.
7. Make general module, which can be used in the future.
8. Using loops that exit in the middle.
9. Using natural control structures.
10. Finding bugs.
11. What is the common sense behind the programming proverb that advocates minimizing the use of
global variables in a program to help communicate inputs and outputs between function.
It is because the input and output of a function are the interface of the module. If global variables are used,
the function interface is not clear and function is not reusable.
12. Given the O-notation corresponding to the following adjective names for various complexity classes:
constant, logarithmic, linear, nlogn, quadratic, cubic, and exponential.
Constant: T (n) = A O (1)
Logarithm: T (n) = A*lg(n) +B O (lg (n))
Linear: T (n) = A*n + B O (n)
n lg n: T (n) = A*n*lg (n) + B*n + C*lg(n) + D O ( n lg n )
quadratic: T (n) = A*n2 + B*n + C O (n2)
Cubic: T (n) = A*n3 + B*n2 + C*n + D O (n3)
Exponential T (n) = A*2n +B or A* 10n+B O (2n)/O (10n)
13. Given T(0) = c, T(n) = an + T(n-1), Find the O-notation of T(n).
T(n) = an + T (n-1)
= an + an + T(n-2)
= an2 + c
= O (n2).
14. Given T(1) = a, T(n) = bn + T(n/2), Find the O-notation of T(n).
T(n) = b + T (n/2)
= b + b + T (n/4)
= b + b ....+ b + T (n/(n/2))
= b log2 n +a
= O (log 2 n)
15. When it is inappropriate to apply the conclusions normally derived from O-notation analysis to an
algorithm’s running-time equation.
An algorithm O-notation holds only for large problem size. For small problem size, O-notation usually fails
to describe what happens and comparative performance of algorithm depends on the constants in the
running time equations that fit the actual running time data.
16. What is Push-Down Automation? Why are stacks useful for processing nested structures?
The image of a push-down stack with its top remaining in a fixed position, and with the whole stack being
push down under the addition of a new item, and rising up under the removal of an item is an image
associated with an idealized machine, called a push-down automation.
17. List ten applications for stack and queue each.
Stack:
1. Process nested structure. 2. Parsing.
3. Evaluation. 4. Backtracking.
5. Postfix calculator. 6. Address storage at function called.
7. Maze problem . 8. Coloring problem.
9. Finding strong connected components. 10.Eight queens problem.
Queue:
1. Priority queue. 2. Printer buffer.
3. Printer spooler. 4. Input buffer.
5. Memory buffer. 6. Data receiver buffer.
7. Automatic phone answering system. 8. System simulation
9. System modeling. 10. Linked representation.
18. Why is a stack useful for evaluating postfix expressions? Would a queue work as well?
In postfix calculator programming, after an operator detected, two data will be pop out from stack and do
evaluation then the result push back to the stack. A queue is not convenience to be used in this case.
19. What is an activation record or call frame?
The activation record contains space for information needed during the time the function call is being
processed, and it contains information for how to resume the execution of its caller after its own execution is
finished.
20. Why is it wise to implement formatted debugging aids before implementing a system?
A formatted debugging aid is simply a function that prints a data structure. It was discovered the debugging
time for a software project could often be cut to half if formatted debugging aids were implement first,
before implementing and testing the rest of the system.