SE 3M04 T1 2002
Answers

Material for final

Here is the answer for the make up test.

Material for first midterm

• What does CMM stand for ?
• Capability Maturity Model
• What are the 7 components of the Software Process?
• Is abbbaa a string of (b*a*) ? What about a+b*a* ?
• No. Yes.
• Is pop(pop(push(2,empty))) a valid expression from (int stack) ?
• Yes.
• Give 4 characteristics unique to the XP development process
• Write out the type ('a x ('b seq -> 'a seq)) -> 'a set in english.
• A function from a tuple of type 'a and a function from type a sequence of type 'b to a sequence of type 'a, to a set of type 'a.

• [Hard] Give the BNF for the set of all strings on alphabet {a,b,c} that start with 2 a's, always contain accb as a substring, and ends with b ?
• (aa(a|b|c)*accb(a|b|c)*b | aacb(a|b|c)*b | aa(a|b|c)*accb | aaccb)
  or
  aa((a|b|c)*a)?ccb((a|b|c)*b)?
• [Easy] Give the BNF for the set of all strings on alphabet {a,b,c} that start with 2 b's, always contain accb as a substring, and ends with a ?
• (bb(a|b|c)*accb(a|b|c)*a
• Write out the type ('c x 'b) -> ('a x ('b seq -> 'a set)) in english.

Material for second midterm

• Define 'module'
• What is a 'secret' ?
• What is an MIS ? [What does the acronym stand for, and what does it mean]
• What are the characteristics of good modules?
• Is it possible to tell (externally) if the implementation of a language is through an interpreter or a compiler ?
• No.
• Name 5 kinds of software structures
• What does MVC stand for, and where would it be encountered?
• Model-View-Controller. It is the abstract architecture of any (good) Graphical User Interface.
• What are the elements of a Design ?
• What are the 4 purposes of an MID ?
• What is litterate programming?
• Joining Design (MID) and code in a single document.
• Given the Heap MIS (p.90), with Data being 'integer', simulate the following execution:
  1. put(1, 1)
  2. get()
  3. init(4)
  4. get()
  5. put(1,1)
  6. put(1,2)
  7. put(4,17)
  8. get()
  9. num(2)
  10. num(1)

• Call	State	Output	Exception
  put(1,1)	s=?, Max_size=?, out=?		* not_init
  get()	s=?, Max_size=?, out=?		* not_init
  init()	s=<>, Max_size=4, out=?
  get()	s=<>, Max_size=4, out=?		empty
  put(1,1)	s=<(1,1)>, Max_size=4, out=?
  put(1,2)	s=<(1,1)>, Max_size=4, out=?		not_unique
  put(4,17)	s=<(1,1),(4,17)>, Max_size=4, out=?
  get()	s=<(1,1)>, Max_size=4, out=4	4
  num(2)	s=<(1,1)>, Max_size=4, out=4	{}
  num(1)	s=<(1,1)>, Max_size=4, out=4	{(1,1)}

  Remark: not_init was missed from this MIS.
• Write an MIS for searching. In other words, given an indexable data structure, find if a given element x is in that structure and if so return (an) index of its location. How does it differ from the Binary Search MIS (5.2.6) ?
• Is your previous MIS deterministic ? Should it be ?