Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.826 Principles of Computer SystemsFebruary 1, 2000 Due: Tuesday, February 8, 2000Problem Set 1Instructions: There are six problems in this problem set; please turn in each problem on a separatesheet of paper. Also give the amount of time you spend on each problem.Problem 1(a) Write an expression in SPEC whose value is the factorial function defined on the range[0, ∞) and that is undefined outside that range.(b) Let fact denote the value of the expression from Part 1. Write an expression, using afunction constructor, whose value is a function that returns fact on the range [0, ∞)and0at−1.Problem 2Given the following SPEC code:TYPE S = SEQ STRINGVAR s0, s1, s2 |s0 := {‘‘pat’’, ‘‘sam’’, ‘‘leslie’’, ‘‘chris’’}s1 := {‘‘leslie’’, ‘‘leslie’’, ‘‘jean’’, ‘‘jean’’, ‘‘chris’’}s2 := {‘‘chris’’, ‘‘leslie’’}(a) Give a sequence p such that p==s0-s1.(b) Is it always true that s0-s1==s0-s2?(c) Is it always true that s0-s1=s0-s2?Problem 3A tree of integers has the heap property if the keys of all children of every node x are less thanor equal to the key of node x. Assume that trees are represented with two functions, parent,oftype Int → Int,andchildren, of type Int → Set[Int].(a) In SPEC, write a specification for a heapify function that takes as input a tree (representedby parent and children functions) and produces as output a tree whose root has the heapproperty.(b) Also in SPEC, write an implementation of module you specified in Part 1.1Problem 4For each of the following SPEC programs, list all of the possible final values of x.(a) << VAR x: INT := 0, y: INT |IFy>0=>x:=1[] y < 10 => x := 2[*]x:=3FI >>(b) << VAR x: INT := 0, y: INT |IFy>0=>x:=1[] y < 10 => x := 2FI >>(c) << VAR x: INT := 0, y: INT |IFy>0=>x:=y+1[]y<0=>x:=y-1[*]x:=y>>Problem 5An array partitioning routine takes an array of integers and partitions the array about one of itselements.(a) What should the type of the partitioning routine be? (FUNC, APROC,orPROC?)(b) Write a specification for the partitioning routine. Be careful not to over-constrain yourspecification.(c) Write an implementation for the module you specified in Part 2. Your implementationshould partition the array about a randomly-chosen element.Problem 6Consider a routine that takes a REAL-valued function func,aREAL parameter tol,andastartingguess x0, that uses Newton’s Method to find a zero of func with tolerance tol.(a) What type should the routine be? (FUNC, APROC,orPROC?)(b) Write a specification in SPEC of the routine.Note that in some circumstances Newton’s method may fail to converge. You should choosea subset of functions on which you are able to specify conditions for convergence, and writeyour specification accordingly.(c) Write an implementation in SPEC of the module you specified in Part
View Full Document
Unlocking...