All Questions

Filter by
Sorted by
Tagged with
0
votes
2answers
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 ...
0
votes
1answer
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?
1
vote
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
0answers
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....
1
vote
3answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
13 views

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

Σ(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 ...
0
votes
0answers
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, ...
1
vote
1answer
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 ...
0
votes
0answers
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’, ...
2
votes
0answers
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, ...
1
vote
1answer
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)$...
0
votes
0answers
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: ...
0
votes
2answers
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 ...
-1
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
-1
votes
0answers
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.
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
6
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
2answers
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.
-2
votes
0answers
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 ...
3
votes
2answers
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?
2
votes
2answers
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 ...
5
votes
2answers
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, ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
-1
votes
0answers
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: ...
0
votes
0answers
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 ...
4
votes
0answers
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 ...
0
votes
1answer
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.
0
votes
0answers
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 ...
1
vote
0answers
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: ...
-1
votes
1answer
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 ...
-2
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
2k views

difference between programmed I/O and interrupt driven I/O

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 ...
1
vote
1answer
62 views

Concrete example of Vertex Cover to Subset Sum reduction

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

15 30 50 per page