Problem Detail: This is a homework problem but I am awfully confused. The problem reads as follows: If $L_1$ is recursively enumerable but not recursive, and $L_2$ is recursive, then which of the following is the strongest true statement about the Read More …
Author: ignougroup
[Solved]: Why is b-tree search O(log n)?
Problem Detail: B-tree is a data structure, which looks like this: If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I need to Read More …
[Solved]: Deleting useless (dead) states from a finite automaton
Problem Detail: A useless state in a finite automaton is one from which no path leads to a final state, hence no (piece of a string) is recognized out of this state. Theoretically, the algorithm to determine the useful states is Read More …
[Solved]: Shannon-Fano puzzle
Problem Detail: I was playing around with Shannon-Fano (SF) entropy encoding when I ran into this issue. I am aware that the compression that can be achieved with SF is sometimes inferior to that of Huffman encoding, but I just though Read More …
[Solved]: A text-classifier that explains its decisions
Problem Detail: I am building a text categorizer for short sentences. In addition to telling the user “the category of the text you entered is C”, I want to be able to explain why I made this decision, in a short Read More …
[Solved]: How append, prepend, and generally insertAt work in RRB-tree
Problem Detail: I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can’t get is how insertion at an index should be performed step by step. Can anyone proficient in this data Read More …
[Solved]: Is the “data path cycle” the same thing of the “fetch-decode-execute cycle”?
Problem Detail: I am reading the book Structured Computer Organization (5th edition) by Tanenbaum and at a certain point, in the second chapter, he talks about data path cycle and fetch-decode-execute cycle, and I am not understanding if they are really Read More …
[Solved]: Top Down Insertion in a B Tree
Problem Detail: I have a B-Tree of order 5. So the keys are between $lceil n/2 rceil- 1 leq keys leq n – 1$ and children are between $lceil n/2 rceil leq children leq n $. Am I doing it right? Read More …
[Solved]: Bin packing problem or not?
Problem Detail: Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items): Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want Read More …
[Solved]: Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?
Problem Detail: Given a directed graph with the following attributes: – a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. – additionally a set of nodes having bidirectional vertices to at least two Read More …
