All Questions

Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...

And if it is not true, what are the problem classes or characteristics for which genetic algorithms are superior?

Given a general branching program, is there an algorithm which can find an equivalent branching program $P$ of minimal length. That is $|P| \leq |P'|$ for all equivalent branching program $P'$. If ...

I read a statement that was unclear to me, and was hoping to get some clarification. It said that given a full binary tree with $n > 2$ leaves, there exists some internal node such that one third ...

I need help with the following practice problem on network flow: A cohort of $k$ spies resident in a certain country needs escape routes in case of emergency. They will be travelling using the ...

I had this question on my homework for a class and don't understand the solution at all. Assume there is no direct link between A and B. There exists one router C and two hops: Link A-C and link C-B....

Can you suggest me a good book with illustrative examples and problems with solutions for finite languages and automata theory? I tried Hopcroft's but it has mostly theory and not many problems with ...

It's an old question: "Generate All Balanced Parentheses." The problem statement in short: given n pairs of parentheses, generate all combinations of well-formed parentheses strings of length 2n. A ...

I'm performing some correlation assessment à la NIST Recommendation for the Entropy Sources Used for Random Bit Generation, § 5.1. You take a test sequence and compress it with a standard ...

Write, in table form, a three-state PDA that accepts the input string ab and crashes for every other input string. Here's my attempt. Is it correct since it doesn't push an initial state or pop the ...

Σ(alphabet) contains 3x1 column matrices [[0],[0],[0]], [[0],[0],[1]] , [[0],[1],[0]]... [[1],[1],[1]] such that each element in the language is a THREE SET of the columns where the bottom row is ...

How can I generate all palindromic substrings in a string using trie in O(k^2) time complexity where k = length of the string. ie, there's the string, ededmdeff. The palindromes include ede, ded, ...

Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$. For finite $n$, it is always possible to find a regular ...

A Forgetful Turing Machine (FTM) operates just like a normal Turing machine except that, in every instruction (i.e., transition), the letter written in the tape cell is always the letter ‘a’, ...

I know some algorithms which compute the convex hull in a continuous space. Are there efficient algorithms to compute it in a discrete domain? For example in 3D discrete space, given the blue points, ...

I'm confused between these two terms as for example - the Auxiliary space of merge sort, heapsort and insertion sort is $O(1)$ whereas Space complexity of merge sort, insertion sort, heapsort is $O(n)$...

I have a Java implementation of the Principal Variation Search algorithm, and it looks like that: ...

Suppose we have a circular radar that scans for ships in an area enclosed by $x^2+y^2 \leq z^2$ (a circle). We wish to design a hash function $h$ such that, we can order the $n$ ships from closest to ...

Problem: Write a program which generates Deterministic finite automaton which accepts given language. Language is defined with alphabet and start/end sub strings. For example: Alphabet={a,b,c}; start ...

This term I am writing an exam on boolean and IEEE arithmetic at university. As the exam will mostly consist on doing computations, I would like to do think about practice problems and verify the ...

I'm taking a course about Information Retrieval and we had a quiz involving the evaluation of search engines. We had a problematic question regarding "Query Logs" (basically recording the queries ...

L2= { W E {a I b} * : no prefix of w starts with b} = { W E {a, b} * : the first character of w is a} U {e} Why is it in union with an empty string? If an empty string from b can also be a prefix.

I'm sure there are standard test cases of hard, combinatorial, NP problems, ... (like knapsack, bin packing, partitioning, ...) that practitioners or algorithm developers use when they compare a new ...

As far as I understand from PCY (Park, Chen, and Yu) algo is that the algo uses hashing during the first pass to reduce the number of CANDIDATE pairs that are considered in the second pass. I have 2 ...

So i understand how to use radix-sort in base 10 and utilize mod 10 to go through the numbers. But not sure about 2,8 or 16. Does it follow the same idea? and i read somewhere that i need to pass ...

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...

Given an array, generate all combinations For example: Input: {1,2,3} Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} I am ...

For a language L $\subseteq$ $\Sigma$* , define LOG(L) = { u $\epsilon$ $\Sigma$* | $\exists$ u s.t. |v| = $2^|$$^u$$^|$ and uv $\epsilon$ L}. Show that if L is regular so is LOG(L). I was trying to ...

In the use case diagram, we draw use cases as an ellipse. Are the use cases the same as functions? I mean by functions, those functions which we write in the program.Thank you in advance.

Write an events ticket booking System and prompts the user to make a choice as well as the number of tickets required. It then displays the total cost of the order. The menu options and cost per ...

Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?

I am working on a problem of whose complexity is unknown. By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use. Finally, I have decided ...

Hello I have a slightly unusual question which relates to a definition of filtration structure. The following is my current state of the definition: $ \mathcal{M} = (W, R, L) $, W is a set of worlds, ...

In the definition of PDA, it is allowed for the machine's reading head to stay where it is, i.e., only perform a stack operation without (reading a symbol and moving right on the tape); this is ...

I have a high level understanding of formal languages and grammars, and I'm familiar with the four major types of grammars in Chomsky hierarchy. I was interested in knowing the classification of ...

I am going over some practice questions for the Major field exam and it asks: A processor with a word-addressable memory has a two-way set-associative cache. A cache line is one word, so a cache ...

Using the definition of Θ-notation, prove that $(3 n+13)(7 n+2)\left(\log \left(1024 n^{2}+100\right)\right) \in \Theta\left(n^{2} \log n\right)$ I also found a useful example in Stack exchange: ...

Are Turing's "m-configurations" the same as the "means" in his original definition of "computable"? In the first line of Turing's paper "On Computable Numbers...", he defines a "computable" number as ...

I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P? The language ...

I am a physicist learning a bit of Information theory. I have encountered a word ("Symbol codes") on Wikipedia and cannot find what it means. Please let me know what does a symbol code mean.

Given a matrix $[A|B]$ I want to find a minimal matrix $[A'|B'] \subseteq [A|B]$ (i.e. the rows in $[A'|B']$ are also in $[A|B]$) such that $A'x < B' \Rightarrow Ax < B$. Geometrically, I want ...

Assume we want to solve the so-called "Super-G" problem from Jean-Claude Constantin. The goal of the puzzle is to get the ring off the other components. Here is a picture of the problem: Source: ...

I recently encountered a coding interview question which is broken down as follows. You are given an array N which consists of pairs n which consist of a reward and a cost. You are also given m which ...

I have a mini laptop running Windows 7 Starter. It started having problems some months ago and hasn't been used since then. It starts normally and after some minutes it freezes completely, which means ...

In my lecture we learned: If X is NPC and X in Co-NP => NP = Co-NP Would it be enough to prove NP = Co-NP if I reduce a ...

It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or ...

As a part of my masters thesis research I came across Security Core Ontology and I would like to dig deep into it. But, no matter how/where/what I search, I can't seem to find any way to access the ...

I have a exam task with 3 parts. (b) is no problem. I got a solution for (a) but the way (c) is asked makes me wonder if I even understood (a) (a) L := { < A > | A is a DFSA, where all states are ...

i was trying to understand the difference between programmed I/O and interrupt driven I/O can anyone show me a good read or explain the above concept it is not given in layman words anywhere please ...

In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line ...