3. corrupted text. you are given a string of n characters s[1..n], which you believe to be a corrupted text document in which all punctuation has vanished (so that it looks something like ""). you wish to reconstruct the document using a dictionary, which is available in the form of a boolean function dict(·): for any string w, dict(w) = true if w is a valid word, and dict(w) = false otherwise. give an algorithm that determines whether or not the string s can be reconstituted as a sequence of valid words. the running time should be at most o(n2), assuming calls to dict take unit time. hint: use dynamic programming. approach the problem as in problem 2: first design a recursive algorithm, identify the subproblems, and then memoize (you don’t need to give an iterative algorithm).

Consider a direct-mapped cache with 216 words in main memory. the cache has 16 blocks of 8 words each. it is a word-addressable computer (rather than a byte-addressable computer which we normally discuss). (a) how many blocks of main memory are there? (b) what is the format of a memory address as seen by the cache, that is, what are the sizes of the tag, cache block, and block offset fields (if they apply)? (c) to which cache block will the memory reference db6316 map?

Consider a slotted aloha system, where the time slot equals the fixed duration of each packet. assume that there are 4 stations a, b,c, d sharing the medium. (a) stations a, b,c, d receive one packet each from higher layers at times 1.3, 1.5, 2.6,5.7 respectively. show which transmissions take place when, according to the slottedaloha protocol; describe all transmissions until all four packets have been successful. when needed, each station has access to the following sequence of random number, provided by a random number generator and drawn uniformly between 0 and 1: (1) station a draws numbers: 0.31, 0.27, 0.78, 0.9, 0.9, 0.11, 0. (2) station b draws numbers: 0.45, 0.28, 0.11, 0.83, 0.37, 0.22, 0. (3)station c draws numbers: 0.1, 0.2, 0.3, 0.4, 0. (4) station d draws numbers: 0.36, 0.77, 0.9, 0.1, 0.1, 0.1, 0.1, 0. (b) in slotted aloha, a station transmits in each time slot with a given probability. what probabilities would you assign to each of the four stations so as to: (i) maximize the efficiency of the protocol? (ii) maximize fairness among the four stations? (c) will the efficiency increase or decrease if we modify slotted aloha as follows: (i) get rid of slots and allow stations to transmit immediately? (ii) implement carrier sensing? (iii) implement collision detection? (iv) implement collision avoidance?

Assume that minutes is an int variable whose value is 0 or positive. write an expression whose value is "undercooked" or "soft-boiled" or "medium-boiled" or "hard-boiled" or "overcooked" based on the value of minutes. in particular: if the value of minutes is less than 2 the expression's value is "undercooked"; 2-4 would be a "soft-boiled", 5-7 would be "medium-boiled", 8-11 would be "hard-boiled" and 12 or more would be a "overcooked".