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.