# All Questions

32,229 questions
Filter by
Sorted by
Tagged with
24 views

### Runtime complexity of a brute force factoring algorithm? (in terms of bits)

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 ...
15 views

### Is it true that for every genetic algorithm there exists a non-genetic algorithm that achieves the same results more efficiently?

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

### General algorithm to find a minimal branching program

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 ...
21 views

### Unique property of a full binary tree

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 ...
512 views

### Maxflow problem

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 ...
4 views

### Calculation of total delay for multiple packets and multiple hops

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....
274 views

### Books on finite languages and automata theory with examples, problems and solutions

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 ...
18 views

### Is this algorithm faster than any prior solution to “Generate All Balanced Parentheses”?

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 ...
9 views

### Is there any scenario whereby randomly shufflying a sequence improves it's compressibility?

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 ...
19 views

### three-state PDA that accepts the input string ab

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 ...
13 views

### How can I show this language is Regular? (Foundations of computing)

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

### How can I generate all palindromic substrings in a string using trie?

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, ...
48 views

### Fitting a regular grammar to strings from a PCFG: how big does it get?

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 ...
16 views

### Class of languages recognised by a Forgetful Turing Machine

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’, ...
14 views

### Convex hull in a discrete space

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, ...
242 views

### Difference between auxiliary space v/s space complexity

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)$...
5 views

### Principal variation search: how to keep track of the best move [on hold]

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

### Hash function orders ships from closest to furthest from the origin

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 ...
22 views

### How to generate Deterministic finite automaton for given language

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 ...
11 views

### Tool for practicing divison/multiplication ieee

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 ...
71 views

### Query Logs and evaluation of search engines

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 ...
15 views

### This theorem: L2= { W E {a I b} * : no prefix of w starts with b}

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.
58 views

### repository of test cases of hard, combinatorial, NP problems

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 ...
18 views

### How can I choose good hash function for PCY algorithm

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 ...
124 views

### radix-sort with different bases

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 ...
415 views

### Finding Shortest Paths of weighted graph using stacks

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 ...
38 views

### How to generate all combinations given an array of elements using backtracking?

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 ...
21 views

### Is LOG(L) Regular?

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 ...
56 views

### What is the difference between “use case” and “function”?

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.
9 views

### WHILE LOOP and SWITCH [on hold]

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 ...
42 views

### How to sort a large list of elements where everything is sorted but k elements?

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

### How to prove NP-hardness from scratch?

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 ...
175 views

### propositional Modal logic filtration definition

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, ...
22 views

### PDAs without λ-steps or popping more than one from stack

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 ...
23 views

### Is Python's Grammar in a known Category between CFG and CSG?

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 ...
223 views

### How many words of memory map to the same cache entry?

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 ...
27 views

### Using the definition of Θ-notation proof

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: ...
6 views

### Turing: Are the “m-configurations” in his original paper the same as the “means” in his definition of his “computable”?

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 ...
57 views

### Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

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 ...
17 views

### What is a symbol code?

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.
13 views

### Minimal subset of rows that generate smaller polyhedron

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 ...
15 views

### Algorithm to solve a physical ring removal puzzle

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: ...
15 views

### Maximize Reward with Cost Limit in a Fully Obserable Environment

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 ...
10 views

### Computer completely freezes(screen, mouse, keyboard) some minutes after starting [on hold]

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 ...
31 views

### Reducing from NPC to Co-NPC => NP = Co-NP?

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 ...
22 views

### Are models of computation closed under composition?

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 ...
10 views

### Access to SECCO ontology [on hold]

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 ...
48 views

### Decidability of the language of all deterministic LBA where all states are reachable

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 ...