CSE452 Exam II Review



CSE452 Exam II Review

Logic Programming and Data Abstraction:

1. Explain the purpose of the cut (!) in Prolog. How does it relate to not?

2. (Textbook problem, 14.8) Write Prolog rules to define a version of the member predicate that will generate all members of a list during backtracking, but without generating duplicates. Note that the cut and not based versions of Section 14.19 (pg. 529) will not suffice; when asked to look for an uninstantiated member, they find only the head of the list.

3. Explain the difference between row-major and column-major layout for contiguously allocated arrays. Why does a programmer need to know which layout the compiler uses? Why do most language designers consider row-major layout to be better?

Control Flow and Subroutines

4. (6.21) Given the following description for binary search:

[Bentley] “We are to determine whether the sorted array X[1..N] contains the element T. Binary search solves the problem by keeping track of a range within the array in which T must be if it is anywhere in the array. Initially, the range is the entire array. The range is shrunk by comparing its middle element to T and discarding half the range. The process continues until T is discovered in the array or until the range in which it must lie is known to be empty.”

a. In your favorite programming language, write the code to produce the binary search according to the above requirements:

b. What looping construct was the most useful for your program?

c. Give the loop invariant(s) for your solution (indicate where you placed the invariant(s))?

5. (8.8) Write (in a language of your choice) a function or a procedure that will produce 4 different effects depending on whether the parameters are passed by value, by reference, by value-result, or by name.

6. (8.16) Why do you suppose that variable-length argument lists are so seldom used in high-level programming languages?

OO and Concurrency

7. Name three important benefits of abstraction.

8. What happens to the implementation of a class if we redefine a data member? For example, suppose we have:

class foo {

public:

int a;

char *b;

};

…

class bar : public foo {

public:

float c;

int b;

};

Does the representation of a bar object contain one b field or two? If two, are both accessible, or only one? Under what circumstances?

9. What is interrupt-driven I/O? What does it have to do with concurrency?

10. What is a critical section? Name two factors that must be satisfied to ensure the integrity of the critical section.

Test Your Understanding: (excerpted from the book)

1. The 3 main elements of object-orientation.

2. What does it mean for an expression to be referentially transparent?

3. What is the difference between a value model of variables and a reference model of variables? Why is the distinction important?

4. What is an l-value? An r-value?

5. Why is the distinction between mutable and immutable values important in the implementation of a language with a reference model of variables?

6. What does it mean for a language to be expression-oriented?

7. Why do most languages leave unspecified the order in which the arugments of an operator or function are evaluated?

8. What is short-circuit Boolean evaluation? Why is it useful?

9. Describe three common uses of the goto statement, and show how to avoid them using structured control- ow alternatives.

10. Why is sequencing a comparatively unimportant form of control ow in Lisp?

11. What does it mean for a function to be idempotent?

12. Explain why it may sometimes be useful for a function to have side effects.

13. Describe the jump code implementation of short-circuit Boolean evaluation.

14. Why do imperative languages commonly provide a case statement in addition to if. . . then. . . else?

15. Describe three different search strategies that might be employed in the implementation of a case statement, and the circumstances in which each would be desirable.

16. What is a tail recursive function? Why is tail recursion important?

17. Explain the difference between applicative and normal order evaluation of expressions. Under what circumstances is each desirable?

18. Describe three common pitfalls associated with the use of macros.

19. What is lazy evaluation? What are promises? What is memoization?

20. Give two reasons why lazy evaluation may be desirable.

21. Name a language in which parameters are always evaluated lazily.

22. Give two reasons why a programmer might sometimes want control ow to be nondeterministic.

Data Typing

23. What purpose(s) do types serve in a programming language?

24. What does it mean for a language to be strongly typed? Statically typed? What prevents, say, C from being strongly typed?

25. Name two important programming languages that are strongly but dynamically typed.

26. What is a type clash?

27. Discuss the differences between the denotational, constructive, and abstraction-based views of types.

28. What is the difference between discrete and scalar types?

29. Give two examples of languages that lack a Boolean type. What do they use instead?

30. In what ways may an enumeration type be preferable to a collection of named constants? In what ways may a subrange type be preferable to its base type? It what ways may a string be preferable to an array of characters?

31. What does it mean for a set of language features (e.g., a type system) to be orthogonal?

32. What are aggregates?

33. What is the difference between type equivalence and type compatibility?

34. Discuss the comparative advantages of structural and name equivalence for types. Name three languages that use each approach.

35. Explain the difference between strict and loose name equivalence.

36. Summarize the ways in which one dereferences a pointer in various programming languages.

37. What is the difference between a pointer and an address?

38. Discuss the advantages and disadvantages of the interoperability of pointers and arrays in C.

39. 45. What are dangling references? How are they created, and why are they a problem? Discuss the comparative advantages of tombstones and locks and keys as a means of solving the problem.

40. What is garbage? How is it created, and why is it a problem? Discuss the comparative advantages of reference counts and tracing collection as a means of solving the problem.

41. Summarize the differences among mark-and-sweep, stop-and-copy, and generational garbage collection.

42. What is pointer reversal? What problem does it address?

43. What is the difference between formal and actual parameters?

44. Describe four common parameter-passing modes. How does a programmer choose which one to use when?

45. Describe the algorithm used to identify an appropriate handler when an exception is raised in a language like Ada or C++.

46. Explain why it is useful to define exceptions as classes in C++, Java, and C#.

47. Name three important benefits of abstraction.

48. What is the purpose of the “private” part of an object interface? Why is it required?

49. What is the purpose of the :: operator in C++?

50. What is a container class?

51. Explain why in-line subroutines are particularly important in object-oriented languages.

52. What are constructors and destructors?

53. Explain the significance of the this parameter in object-oriented languages.

54. How do Java and C# make do without explicit class headers?

55. Explain the distinction between private, protected, and public class members in C++.

56. 17. Explain the distinction between private, protected, and public base classes in C++.

57. Explain the difference between static and dynamic method binding (i.e., between virtual and nonvirtual methods).

58. Summarize the fundamental argument for dynamic method binding. Why do C++ and C# use static method binding by default?

59. Explain the distinction between redefining and overriding a method.

60. Explain the connection between dynamic method binding and polymorphism.

61. What mathematical formalism underlies logic programming?

62. What is a Horn clause?

63. Briefly describe the process of resolution in logic programming.

64. What is a unification? Why is it important in logic programming?

65. What are clauses, terms, and structures in Prolog? What are facts, rules, and queries?

66. Explain how Prolog differs from imperative languages in its handling of arithmetic.

67. Describe the difference between forward chaining and backward chaining. Which is used in Prolog by default?

68. Describe the Prolog search strategy. Discuss backtracking and the instantiation of variables.

69. Explain the purpose of the cut (!) in Prolog. How does it relate to not?

70. Describe three ways in which Prolog programs can depart from a pure logic programming model.

71. Describe the generate-and-test programming idiom.

72. Summarize Prolog’s facilities for database manipulation. Be sure to mention assert, retract, and clause.

73. What sorts of logical statements cannot be captured in Horn clauses?

74. What is the closed world assumption? What problems does it cause for logic programming?

75. Explain the rationale for concurrency: why do people write concurrent programs? What

76. accounts for the increased interest in concurrency in recent years?

77. Describe the evolution of computer operation from stand-alone mode to batch processing, to

78. multiprogramming and timesharing.

79. What is interrupt-driven I/O? What does it have to do with concurrency?

80. What is a race condition?

81. What is a context switch? What is preemption?

82. What is a dispatch loop? What are its advantages and disadvantages?

83. Explain the distinction between a multiprocessor and a cluster.

84. Explain the coherence problem in the context of multiprocessor caches.

85. What is symmetric about a symmetric multiprocessor (SMP)?

86. Explain the difference between a coroutine, a thread, a lightweight process and a heavyweight process.

87. What is quasiparallelism?

88. Describe the bag of tasks programming model.

89. What is busy-waiting? What is its principal alternative?

90. Name four explicitly concurrent programming languages.

91. Why don’t message-passing programs require explicit synchronization mechanisms?

92. What are the tradeoffs between language-based and library-based implementations of concurrency?

93. Explain the difference between data parallelism and task parallelism.

94. What is collective communication?

95. Describe six different syntactic constructs commonly used to create new threads of control in a concurrent program.

96. In what sense is fork/join more powerful than co-begin?

97. What is a thread pool in Java? What purpose does it serve?

98. Why is meant by a two-level thread implementation?

99. What is a ready list?

100. Describe the progressive implementation of scheduling, preemption, and (true) parallelism on top of coroutines.

101. What is coscheduling? What is its purpose?

Lecture Notes:

1. Know how to program in Prolog – what are characteristics that distinguish it from languages in other paradigms?

2. Know the Design Issues surrounding the various types of programming constructs available in a given language.

Data Types:

3. Strongly typed language

4. Static typing

5. type equivalence vs type compatability

6. Data types (definition and examples)

7. Pointers: dangling pointers and memory leakage

Expressions:

1. Definition of expressions

2. Main types of expressions

3. Overloaded operators

4. Type conversions (narrowing vs widening; implicit vs explicit)

Control Flow:

1. Types of control statements

2. Levels of control flow

Subprograms:

1. Parameter passing techniques

2. Implementation of parameter passing (memory contents, stack content, etc.)

3. Subprograms as parameters

4. Overloaded subprograms vs generic subprograms

5. Subprogram linkage (call and return operations) – how implemented

6. Activation Record definition and use; contents of stack

7. Subprograms with and without recursion

8. Nested subprograms (static chain, activation record contents)

9. Buffer overflow attack (what is it? how can you prevent it?)

Java:

1. Understand how Java is implemented

2. Difference between a Java standalone program vs an applet

3. Key objectives in the design of Java

4. Basic language elements (control flow, variables)

5. Access control in Java (within and outside packages)

6. Interface vs extension

Data Abstraction and Concurrency:

1. Abstract data types

2. Key characteristics of OOP

3. 3 major categories of OO languages

4. Inheritance (single vs multiple)

5. Polymorphism

6. Role of messages in OOP

Concurrency:

1. Two main types of programming notation for concurrent programming (shared memory vs distributed memory)

2. Advantages/disadvantages to each architecture

3. Race conditions (definition and how to avoid)

4. Methods for synchronization

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download