AAMU CS CMP507 Data Structure & Algorithm Dr. Peter Wang Homework #2 Due:2/9/98 1. What is the Boehm's COCOMO equation relating the size of a software system to the person-months required to built it ? Boehm's COCOMO model works by starting with a baseline estimate of the number of person-months(PM) that it willl take to complete the most familiar class of software project of a given estimated size measured in Kilo-Delivered Source Instruction (KDSI), according to the relationship, PM=2.4*(KDSI)**1.05 2. Name two ways that a priority queue can be represented. a. Unsorted array. b. Linked list. 3. What is abstract data type ? Abstracted data type is a way of packaging some intermediate-level data structures and their operations into a useful collection whose properties have been carefully studied and with clean and simple interface. The ADT define "WHAT" and not "HOW" to implement. 4. What is encapsulation ? The combining of data structures and methods is called encapsulation. If encapsulation is performed correctly, the user of the object should never need to access the data of object directly. 5. What is procedure abstraction ? When we organized a sequence of statement into a named procedure, P(A1,..,An), we have created a named unit of action. We seperate the "what" from the "how". In general, the proper use of the abstraction can help control complexity and can improve modifiability. 6. What is object-oriented programming (OOP) ? OOP: Object + operation. (Two major ingredians are Top-Down design & Modualrity) The components of object-oriented programs are: Object: The object in OOP includes the basic data or data structure and the related procedures and functions required to keep the object complete. To make the object like an abstracted data type. Method: A method is a procedure or function that becomes part of the object. It provides the abstraction to the object's data. Encapsulation: The combining of data structures and methods is called encapsulation. If encapsulation is performed correctly, the user of the object should never need to access the data of object directly. 7. What is visual programming ? Visual programming provides the graphics user interface to improve the productivity of Programmer/Engineer/Designer. The V.P. provides an graphics-based environment which allows the designer to use mouse to select components and specifies commands to the language. ex. Visual C++, Visual Basic, Visual J++. 8. What is bottom-up implementation ? We first create the functions before using calls on them in other higher level function. This gives the datails of the bottom layers of overall program before designing the higher levels that use the functions we have designed. 9. What are the requirements for binary search ? The list must in a specific sorted order. 10. Under what algorithm and situation, you can achieve search at O(1) ? By using the hash function and direct access method. 11. Why sorting and searching is important in computer science ? Almost every real world application uses searching and sorting functions. The data structure and algorithm used in searching and sorting affects the efficiency of the applications. 12. What is the difference between top-down and buttom-up programming ? The top-down programming decomposes the overall program into subproblems and perform stepwise refinement. While the bottom up programming provides all the bottom layer function definitions before using calls on them and works upward layer by layer until the problem solved. 13. What does it mean to postpone the choice of data representations and algorithms ? Design the interface and overall functionality to solve a problem and consider the underlining data struction and implementation details. 14. What is loop invariants ? A loop invariant assertion is an assertion which is always true no matter how many times you have executed the loop. 15. What is functional programming ? A functional programming language is one which achieves its effects by applying functions, either recursively or through composition, and for which all of its expressions obey the principle of referential transparency. 16. What is program transformation ? Program transformations can be thought of as exchange laws that permit us to replace one form of a program with an equivalent form -- or replace a subexpression inside a program with an equivalent one. The purpose of program transformation is to improve the efficiency of program. Both of the data structure and algorithm can be dramatically improved if program transformation is done properly. 17. What is regression test ? After a modification is made to a piece of software, an implementer must verify that all the working test cases still work properly. 18. What is factory acceptance test (FAT) ? FAT is the test performed by the customer engineers before the software is release to the market. 19. What are stubs and test drivers ? In the top down programming, when we testing the higher level functions, we must provide faked functions to filled the lower level functions. Those faked dammy functions are called stubs. In the bottom up programming, when we test the related functions to form the solution to a subproblem, we often need to create a higher level function to test them. The higher level function for testing the lower level functions is called the test driver. 20. Explain the philosophy of measurement and tuning ? In order to improve the performance/efficiency of a program, a tool such as profiler is needed to measure the percentage of time spent on each function. Based on the report, the appropriate action can be taken to improve the program by redesigning some of the critical function or using different algorithm.