# All Questions

47,702 questions
Filter by
Sorted by
Tagged with
696 views

### Is Determining the Number of Prime Factors Polynomial?

Our current understanding of prime factorization states that it is hard to solve. The problem asks us to find the list of prime factors for an integer. For example, 18's prime factors are 3, 3, and 2. ...
61 views

### Finding the Depth-First Index of a Child Given the Parent's Depth First Index Index in Complete k-ary Tree

I have a complete k-ary tree with a depth of $d$. If I'm given a node's depth-first index, I'd like a closed-form formula for calculating both the nodes children's depth-first indexes along with a ...
1 vote
70 views

### Union of non regular and regular language

So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not. Since I found counterexamples for both cases I want to look at more ...
27 views

### How does a regular expression match .+x?

A quick test shows what I'm describing: > const text = 'foobarhelloworld' > const pattern = /.+or/ > text.match(pattern) //=> 'foobarhellowor' What is ...
59 views

### In Johnson's algorithm for enumerating elementary circuits in a directed graph, why do B-lists have a different structure than the adjacency list?

I have a question on the implementation of the Johnson's algorithm in C that is actually at the interface of theory and practice. Link to Johnson's paper I already implemented this algorithm in R ...
1 vote
89 views

### Maximizing sum and product of an array

Given an array of positive numbers with allowed replication, what is the algorithm to find the max amount possible only with summing or multiplying elements? All numbers must be involved in some ...
39 views

### Union of non-regular and finite language

So i got this problem where should prove whether the union of a non regular language $L$ and a finite Language $L'$ is regular or not. My Idea was to show that any regular Language $L_r$ cannot be ...
31 views

17 views

### Same Address and Write signal for two block of RAM?

I don't know if I asked the question in correct way but I will try to explain what's the thing I am not getting. I am currently reading book titled "Code: The Hidden Language of Computer Hardware ...
9 views

### What is a good appropriate algorithm for localization for images?

Assume that you have an image that you going to classify its class ID. One good option is to use interest points e.g FAST that can find coners/edges inside an image. From these points you could ...
1 vote
10 views

### Auxiliary Space Complexity of Dictionaries whose Keys are Iterables of Variable Size

Recently, I began delving into complexity analysis with dictionaries. More specifically, I have been looking at auxiliary space complexity. For the most part, this type of analysis has been ...
22 views

### What happens for hardware Interrupts in non-preemptive scheduling?

In non-preemptive scheduling, the running process cant be interrupted .But what will when the CPU receive a hardware interrupt such as the an interrupt from the printer indicating that the current ...
47 views

### Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time

Suppose I have a dynamic table supporting $Insert$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $q > 1$....
618 views

### What is practically preventing us from applying set-theoretic types in engineering?

I know the title is sort of misleading because we do have set-theoretic types in several languages:) From a theoretic view, set-theoretic types such as intersection, union, and negation may bring some ...
1 vote
39 views

### How to evaluate the complexity of a code

Here is my code for computing the product of sequences of matrices ...
1 vote
83 views

### Algorithm for optimal item selections

I'm trying to find an algorithm for this problem: I'm going to the shop and need to buy X grams of an ingredient. The shop does not necessarily have an "X grams of ingredient" product. But ...
27 views

### Lookup Using Path Matrix in Floyd Warshall Algorithm

How is the path matrix created by the Floyd Warshall algorithm used for path lookup? The 2 images show the graph (b) and the path matrix (c). Both are taken from the book: Foundations of Algorithms by ...
88 views

### Finding all stable matchings in stable marriage problem

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
13 views

### Finding all stable matchings in stable marriage problem [duplicate]

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
706 views

### Representing binary functions with a finite gate set without exponential blow-up?

It is pretty well taught that any binary function can be represented using CNF. But conversion to CNF can take an exponential number of gates. The truth table is exponentially sized relative to the ...
1 vote
44 views

### Converting encrypted messages to unencrypted results of an equally hard to reverse function

If we have some function, $f$ with an exponentially sized domain, mapping the set $\{0, 1\}^N$ to $\{0, 1\}$, could we do something like this: For ease, let's say $E(x) = x^e (\text{mod} \; n)$. This ...
27 views

### What are the steps to create an intuitive and straightforward proof of the optimality of Huffman coding?

I am having great difficulty following the proof in class. I assume "optimal" means it minimizes the Average bit length to encode an alphabet with known frequencies. My understanding of how ...
37 views

### fast estimation of the amount of unique combinations

Let's say I have a set of two columns - Name, Surname. I have a list of possible values for Name -> Jacob, John Surname -> Mayerson, Kindle. I want to generate a set of unique combinations for ...
1 vote
89 views

### Is there an efficient algorithm for this ecommerce optimization problem?

Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules: There are $n \gt 0$ distinct products in our shopping basket. Each product is ...
1 vote
76 views

### Number of decycling sets in a 3-regular planar graph

Defintitions: A graph is said to be r-regular if every of its vertex has a degree $r$. A graph is planar if it can be drawn in a plane without any of its edges intersecting each other except at their ...
39 views

### Implementing algorithms from online courses in code to solidify understanding

I came across the online course Design And Analysis Of Algorithms and the assignments have several questions that ask you to design algorithms, but you are not asked to implement them in code. I think ...
43 views

### Reductions to perfect matching

Can we reduce any well-known problems to deciding whether a (possibly non-bipartite) graph $G$ has a perfect matching? I'm particularly interested in finding a reduction from deciding whether a ...
46 views

### Turing machine for a^n b^m c^n d^m

The state diagram for the initial part of this turing machine given as: Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
89 views

### On a table there are $N$ stacks. Stack $i$ contains $i$ tokens. Minimum number of moves to make all stacks empty

On a table there are $n$ stacks (numbered $1$ to $n$). Stack $i$ contains $i$ tokens ($1 \leq i \leq n$). During a move, a set of stacks can be chosen and the same number of chips can be drawn from ...
33 views

### Computability = Enumerating a sequence in the particular order?

In the paper "Computability by Probabilistic Machines" by K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro (in Claude E. Shannon: Collected Papers , IEEE, 1993, pp.742-771), a ...
1k views

### Algorithmic Complexity of Recognizing Claw-Free Graphs

Let $H=\left(V_H, E_H\right)$ and $G=(V, E)$ be graphs. A subgraph isomorphism from $H$ to $G$ is a function $f: V_H \rightarrow V$ such that if $(u, v) \in E_H$, then $(f(u), f(v)) \in E$. $f$ is an ...
1 vote
30 views

### function is computable iff its graph is recursively enumerable?

How do I show that a (possibly partial) function is computable iff its graph is recursively enumerable?
32 views

### Round-robin tournament scheduling, with teams that may share their home field

I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in ...
1 vote
57 views

### (how) is assignment or binding possible in purely functional languages?

i can't seem to find much info on the following question: how (if at all) is the fixing of names to values (by binding or assignment) possible in a purely functional system like the lambda calculus? i'...
56 views

### Representation of pairs in System F

System F defines the data type pair as: $$X\times Y := \Pi Z. (X\to Y \to Z)\to Z$$ with: $$\langle x,y \rangle := \Lambda Z. \lambda p^{X\to Y\to Z}.p \text{ }x\text{ } y$$ Projections are defined: ...
199 views

### Showing this scheduling problem is NP-hard

I've been reading up on scheduling problems and the class of them that is NP-complete. Specifically, this is a foundational text on such problems, but the reductions are not clear to me. Can someone ... 1 vote
22 views

I would like to model linked lists using set theory similar to that in Scheme and LISP. There is a set theoretic definition of the ordered pair: $p = \{\{a, 1\}, \{b, 2\}\}$ My question is how does ...
30 views

### Prove (w')^R=(w^R)'

W can be any set you want....prove (w^R)'=(w')^R
1 vote
19 views

### Is $\Sigma_n^p$-SAT a complete problem for the $\Sigma_n^p$ class with polytime or with logspace reductions?

Here I define $\Sigma_n^p$-SAT to be the problem of deciding if a boolean formula in prenex normal form with $n$ alternating quantifiers, starting with $\exists$, is satisfiable. I found several ...
1 vote
46 views

### What is point of calling syscalls in the kernel?

If syscalls are meant to transition into kernel mode from user mode, what is the point of calling syscalls in the kernel? Reference: https://stackoverflow.com/questions/15841327/can-we-call-system-...
14 views

### Which queue does wait() suspended process goes into?

According to javatpoint, ready and wait queue are different. But according to wikipedia they are synonymous, in this context. Now I am more confused. What I want to know is, when the parent process ...
17 views

### If the register size and the address bus are equal so do we need those segementation register to segment our memory?

In 8086, as i know we need those segementation register to segment our memory because the address bus is 20 bit and register size is 16. So, If the register size and the address bus are equal and we ...
26 views

### Processes with communication exclusive from the OS

Most OSes use the message passing system to let 2 processes communicated with each other.This works by a shared mailbox between the OS and each process loaded in the RAM however are there processes ...
1 vote
19 views

### Parsing expression grammar for a language consisting of sentences with one character added or removed anywhere

Given a parsing expression grammar for a language, is there a way to make a parsing expression grammar for a new language that consists of the valid strings from the original language, plus the ...
99 views

### Finding the error probability of a Monte Carlo algorithm

Let's say I have a Monte Carlo algorithm $A$ that gives the correct answer with a probability $p$ > $1/2$. I don't have any information on if it's decisional or not. I understand that I can make ...
74 views

### Calculating cells encompassing points in a grid

I have a sequence of points over time, and a grid of X by Y cells to which I need to calculate the cells in which the points fall, as depicted in the diagram below Another point now arrives (as ...