taro_curly

I solved #66 in a not entirely rigorous way. We are given that L1 contains L as a substring. Since we know L is regular, by Pumping Lemma, we can split L into xy^nz where we can n can be any integer and xy^nz will still be regular. Since every string in L1 contains L as a substring, we can have a situation like this: (w1)L(w2) where w1 and w2 are strings. Even here, we can write L1 = (w1)xy^nz(w2) and pump n. Therefore, if L is regular, then by Pumping Lemma, L1 is regular. therefore, I) is true Using similar logic, we can show II) is true If we look at the options, if I and II are both true, the answer can only be E) I, II, III are true. Thus, we would not need to evaluate III. Incidentally, I do not know how to prove or disprove that statement. :p Can anyone help?

A regular language is a language that can be recognized using some finite state machine (FSM), either a DFA or an NFA. Neither of them has any memory. Therefore, neither can count. (to see why, try to construct a FSM that will accept whenever it receives exactly n inputs, where n is a variable). In the absence of any memory, it is impossible to keep track of whether equal numbers of a and b have been seen so far. Hence, a^nb^n is not a regular language.

The O notation is an order of growth notation. It helps you to concisely represent how fast a function will "grow" w.r.t. some input. Therefore, when you say that the order of growth of a function is f(n) is O(n), what you are saying is that as n increases, f(n) will increase linearly. A crude way of putting it would be, if the order of growth is O(n^2), then f(n) is proportional to n^2 i.e. f(n) = kn^2 When you are talking about the order of growth of a function f, you are talking about the magnitude of the function. Let us say that the time to required f for input n is given by f_t(n) Whereas, when you are talking about the growth of the running time, you are talking about f_t grows with n. Hope this makes sense...

Yes, you are correct. The number of entries in the page table is determined by the number of virtual pages available and not the number of page frames. However, if you are using inverted page tables, then you would have one entry per page frame. This is the case with some 64-bit systems, where the size of the virtual memory is enormous. Any good OS textbook will have a decent description of inverted page tables. I use Modern Operating Systems - Andrew Tannenbaum

So least restrictive means that condition which imposes the least restrictions on the variables involved (duhhh!!!). Am feeling very silly for not realizing that earlier. :blush:

@gttts23 Your reasoning is any day better than the b****** that I came up with. :) Thanks for that. Looks like I will have to work a lot harder on Theory. ;)

@iamdaisy, Yes you are right, my expression will not accept the empty string. Thanks for pointing it out. :)

Here's my take on this question... I. Allocate more main memory for buffers I don't see how this can do much good. More memory means more data to be recovered, but it does not necessarily allow the system to recover into a consistent state II. Duplication of buffers in memory III. Atomic write of multiple buffers These two would have to go hand-in-hand. Having II) without III) is asking for trouble, and having III) without II) is pointless. In the absence of any better reasoning, I would go with C) II and III but I am not convinced at all. Actually, I am at a loss to understand what crash means here. If the crash means a driver failing, then I don't see how even II) and III) would help. Can anyone shed some light on this. Perhaps there is something that I am missing.

Suppose one wishes to be certain that after execution of the statement the value of x will equal the value of a. Of the following, which is the weakest (least restrictive) condition that must necessarily hold before execution of that statement? (A)(x=a) OR (a>b) (B) (a>b) AND (x=a) © a>b (D) x >b (E) x = a What does "least restrictive" mean?

I think the answer is B) III only Since L is not recursive, L' may be recursive, so I is not true Since L is not recursive, it is not contained in a recursive set, so II is also not true

In the case of radix sort, the key invariant would be: At iteration i, The elements of the array would be sorted on all bits 0,1...,i-1 : where bit b_0 is the LSB and b_{n-1} is the MSB. Thus, before the loop is encountered for the first time, i = 0, and the array is sorted on the -1th bit, i.e. it is unsorted. At the end of the last iteration, i = n, and the array is sorted on the basis of all bits 0,1,...n-1, i.e. it is entirely sorted.

In the case of Dijkstra's algorithm, I think the key invariant would be: At step i, if we are at node k_i, the path p = p_1 p_2 ... p_{i-1} obtained so far is the shortest path from the source node K_0 to k_i

Q12) If two algorithms A and B are bounded by Theta(n) and Theta(n^2), respectively, and A takes 128 ns when n = 1024 whereas B takes 16 ns, then at approximately what n does algorithm A begin to outperform algorithm B? Let k be some integer such that at n = 1024 * k, the performance of A and B are equal. Since A = theta (n), for n = 1024k, A will take 128k ns. Similarly, since B = theta (n^2), it will take 16 * k^2 ns. For equal performance, 16*K^2 = 128*k which gives k = 8. Therefore, at n = 8192, A starts to outperform B. Q14) How long does it take to find a key in a linked list, a sorted linked list, a linear array, a sorted array, an AVL tree, and a hash table? Linked list = O(n) Sorted linked list = O(n) - can't use binary search here Linear array = O(n) Sorted array = O(log n) AVL tree = O(log n) --> am I right about this Hash table = O(1) Q16) How many 1's are there in the binary representation of the hexidecimal number DB93? DB93 = 1101 1011 1001 0011 No. of ones = 10 Q17) What is the maximum number of edges in a cycle-free directed graph? How about undirected? Directed graph = nC2 = n! / ((n - 2)! * 2!) It is possible to construct a complete directed graph with no cycles. Undirected graph = |V| - 1 It has to be a tree. In a tree, |E| = |V| - 1 Q20) Sort in order of bigness: O(lg n), O(sqrt n), O(n), O(n*n), O(sqrt(2^n)), O(2^(sqrt n)) O(lg n)

(a+b)a*(ab)*a* should also do the trick. It will allow the expression to start and end with b in addition to a.

@f2003800 Do you know of a more analytical way in which this problem can be approached? Relying on an example can be misleading... @ethanph If the array was at least 2-ordered, the answer should be atleast as large as the answer to Q1.

An array A[1...n] is said to be k-ordered if A[i - k] \leq A \leq A[i + k] for all i such that k For example, the array A = [1, 4, 2, 6, 3, 7, 5, 8] is 2 ordered. Q1. In a 2-ordered array of 2n elements, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered? a) 2n-1 b) 2 c) n/2 d) 1 e) n Q2. In an array of 2n elements, which is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered? a) 2n-1 b) 2 c) n/2 d) 1 e) n

There is a slight problem in grabanca's solution to L2. It should read L2 = 1* (01*01*01*01*0)*1* The + sign is used to denote "or" which in this case is not correct. What is needed is a concatenation. Also there are only 4 zeros, whereas the question requires number of zeros to be divisible by 5.

Actually, you can even use the email Id provided on their site and mail your list to them. Just prepare a table similar to the one that is there on your correction stub. I did that and I got a confirmation in less than a week.

6) Here are my thoughts on each of the options: A. Unrolling short loops This would ensure that the pipeline doesn't stall because of branches B. Writing short code segments with lot of subroutines This would result in a lot of unconditional branches. Since an instruction would only be decoded a couple of stages into the pipeline, the pipeline would keep getting stalled. C. Using registers as far as possible. Using registers as far as possible is a good thing. For one, memory accesses are slower and take longer to decode anyway. This way, there are no delays while waiting for the memory to respond. D. Using direct/immediate modes of access Using direct access, you have the address from which to retrieve the data without having to make an additional access to a register to read the address. In immediate access, the operands are present in the instruction itself, so once again, the pipeline is not held up. E. Fixed-length integer instructions Using fixed-length integer instructions would lower the decoding time required. This is the same principle that is used in RISC processors. My answer would therefore be (b). However, there does not seem to be any consensus on this. Any other suggestions from anyone? --- 11. I'd go with --> B) I, III

I think the answer to the second question is (D) Θ(n) In the worst case, in a recursive DFS, the first successor of node k will be some node l which has not already been discovered. This will continue until you reach the last node. All successors of this node will necessarily have already been visited. Thus, no backtracking at all will have taken place upto this point. The depth of the recursion would thus be n. This can only occur in a complete graph

I'm sorry CalmLogic, but I am not so sure about your answer. k^h is the maximum number of leaves in a k-ary tree. The question asks for the max. number of nodes in the tree. Like zc0000 says, it should be the sum of all the nodes in the tree... i.e. 1 + k + k^2 + ... However, when you say "nodes" of a k-ary tree, do you include the "leaves" as well. Because nodes could be taken to mean internal nodes also... In that case, the max. number of nodes would be 1 + k + k^2 + ... + k^(h-1) = (k^h - 1) / (k - 1) Sadly, this still does not seem to match any of the answers :( So let me boil it down to a related question. When you say nodes, what should we take it to mean...internal (i.e. non-leaf) nodes only, or all nodes (including leaf nodes)?

I am a bit uncertain about the choices to your questions, but here is what I think. As far as this particular question is concerned, it does not really matter whether the stack grows up or down. Since all offsets mentioned are of the same sign (negative), we can afford to be concerned only about the value of the offset. The answer to 43. would be (B). It is quite clear what the LOAD instruction does from the example presented in the question. Since x is a local variable, it would be stored at an offset of 12 from the $fp. LOAD copies the word stored at the address specified in "Register+Offset" so at the end of the instruction, the value of x would be in register $t0. --------------- I shall tell you my answer to 44. Unfortunately, it does not seem to match any of the choices, although from the way the choices are presented here, I cannot be certain what they are in the first place :hmm: LOAD $t1, -8($fp) --> Loads the static link address into $t1 LOAD $t1, -12($t1) --> Loads the memory word of local variable a See CHAPTER TWELVE: PROCEDURES: ADVANCED TOPICS (Part 2) for a discussion on static links.

I think it is 2MB. This is how Since there are 64K colours, each would be represented by x bits where 2^x = 65536 i.e. x = 16. Since we have 16 bits per pixel, we need a total of 1280 * 800 * 16 = 16384000 bits = 2048000 bytes = 2048KB = 2 MB