All Questions

31,820 questions
Filter by
Sorted by
Tagged with
16 views

Can anyone provide proof of second equation of rod cutting problem in CLRS section 15.1

While going through ROD CUTTING problem of DP from CLRS, I noticed the optimal structure of the rod cutting problem is : 𝑟𝑗=max{𝑝𝑛,𝑟1+𝑟𝑘−1,𝑟2+𝑟𝑗−2,...,𝑟𝑗−1+𝑟1} In overhead approach, ...
23 views

Conditions for string substitution commutativity

Let's say I have two substitutions given [a:=b] and [c:=d]. What are some conditions that hold for a,b,c,d ∈Σ* iff forall s∈Σ* s[a:=b][c:=d]=s[c:=d][a:=b] Also you can assume that a,c≠𝜀 but you ...
34 views

RSA cryptosystem: Encrypting a signed message

I've started to read the section about the RSA cryptosystem in CLRS (page 958) and I don't understand the way it describes how to encrypt a signed message. If Bob wants to send a message $M$ to Alice:...
21 views

How to create a square root program without using math library in c++ [closed]

I need help to finish my activity in data structures and algorithms. Need help 😅
20 views

How to implement minimization of maximum regret?

We run a report, but for one of our big clients, it is taking too long. There is a loop where it loops for a list and fetches it upstream 1by1. We're making this a bulk operation now, but some items ...
76 views

TSP Variant — Colored Path

Recently I came up with a traveling-salesman-esque problem. As usual, we have $n$ vertices, and a weighted edge between any two vertices. However, each vertex is associated with a color, which may be ...
22 views

Is there a language that pumps, but is not regular? [duplicate]

I'm looking for a concrete language that can be pumped but is not regular. I understand that closure properties can be used to further test if a language is regular/nonregular.
19 views

How to write ^ (to the power) in regex in PFLAP [closed]

I am trying to convert this regex to NFA (3^+)(3*+2*)(1^+)(2+1)*3*(2^+ )(3+1)*(3+1)*2* but it says "Operators are poorly formatted!" So, the question is: does ...
41 views

What's the proof complexity of E-KRHyper (E-hyper tableau calculus)?

Before the question, let me explain better what is E-KRHyper: E-KRHyper is a theorem proving and model generation system for ﬁrst-order logic with equality. It is an implementation of the E-hyper ...
15 views

Why do we need volume as an abstraction on top of partition?

I'm curious about what do we need volume as an abstraction on top of hardware partition? What problem it tries to solve? What is the limitation of this concept?
21 views

What is the meaning of uniform distribution of elements in an array?

I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can ...
23 views

How to prove an implication about an upper bound mentioned in the proof of master theorem?

How can we prove rigorously the proposition "Suppose the if in case 1 is true, the equation 4.23 is true"? For given constant b and j, the implication in green makes sense. If the upper bound of j ...
27 views

Modifying relaxation for the Bellman-Ford algorithm [closed]

I'm using the Bellman-Ford algorithm to find the best path in my graph. However, instead of choosing the path with the lower value, I want to choose the path with the highest value. And instead of ...
39 views

Big-O Notation and Calculus?

I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
110 views
+50

Merging nodes of a DAG

I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them. After each merge operation, ...
28 views

Concatenative programming language based on the stack as a non-trivial virtual machine [on hold]

For a functional programming language project like Haskell, I design a VM whose intermediate language is stack-based, and focused on the concatenative paradigm: Functions / quotations / combinators ...
14 views

How many segments a process can have in operating system employing Segmentation for memory management

Some facts about "Segmented Paging" 1) Each process has one segment table. 2) There is one-page table per segment. Fact about "Paged segmentation" 3) Contains page table of segment table. Now ...
9 views

What are some of the ideal projects in Computer Science to address open problems in psychology? [closed]

Computer Science has a deep connection with the human mind in terms of cognition and analytical thinking. I am interested to explore all those areas in Psychology where algorithms can be used and ...
13 views

How to transform an arbitrary graph into a fixed vector representation?

Actuality I work in computer vision, specifically on a problem known as "scene graph modeling." This problem aims to convert an image $I$ in a graph $G=(V,E)$ where the nodes $V$ represent the objects ...
15 views

Promise problems in $NP$?

Is there a good examples of promise problems in $NP$, $coNP$ and $NP\cap coNP$?
12 views

Set Cover with multiple covers

In the Set Cover problem we need to cover each element at least once. I'm considering the case where I want each element to be covered at least $k$ times with constant $k$. I consider the classic LP ...
7 views

train mlp (input x, outpu y) with a blackbox labeling any x-y pair good/bad

Standard MLP (map x to y) is trained with a set of x-y data points. My question: What if there is no train data, the only supervisor lables any x-y pair with 0 or 1. The goal is that the x-y pair ...
13 views

Can many threads run in a parallel in many-to-one model?

The book I am reading suggests that in a many-to-one multi-threading model, the threads are unable to run in parallel in a multi-core system. I am thinking this is not the case because if we have many-...
80 views

How do i tell if a grammar is regular or not?

I know that a regular grammar has a definition \begin{align}S &\to aS\\ S &\to \lambda \end{align} But I dont really know how to apply this information to check whether or not a grammar ...