# All Questions

31,820 questions
Filter by
Sorted by
Tagged with
0answers
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, ...
0answers
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 ...
2answers
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:...
0answers
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 😅
0answers
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 ...
2answers
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 ...
0answers
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.
0answers
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 ...
0answers
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 ...
0answers
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?
1answer
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 ...
1answer
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 ...
0answers
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 ...
2answers
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 ...
1answer
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, ...
0answers
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 ...
1answer
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 ...
0answers
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 ...
0answers
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 ...
0answers
15 views

### Promise problems in $NP$?

Is there a good examples of promise problems in $NP$, $coNP$ and $NP\cap coNP$?
0answers
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 ...
0answers
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 ...
0answers
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-...
2answers
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 ...
1answer
20 views

### Getting erros on a Get&Set but don't understand why [closed]

Hi I have spent the past few hours researching what could be the problem with these errors I have been getting. Does anyone know what it could be? Initialization: ...
0answers
18 views

I'm working on the same exercise as described in this post: How to show that hard-to-compute Boolean functions exist? In the answer there I don't understand how the number of circuits with at most $... 1answer 28 views ### Why is it not always possible to compute the centroid of feature vectors? Hi in the data mining and machine learning course that I'm taking there is a subject on feature spaces and there is this part about feature vector aggregation and metric spaces that I don't really ... 1answer 22 views ### Is there a way to modify Kadane's Algorithm such that we know the resulting subarray? Kadane's Algorithm is an algorithm that solves the maximum subarray problem by clever dynamic programming. Is there a way to further modify the algorithm so that we would get to know the resulting ... 1answer 57 views ### Problem in downvote system Problem For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated ... 1answer 27 views ### Student Course Allocation Problem with Many Constraints [closed] Problem statement In an university, there are$t$course categories,$m$courses,$n$sections,$p$students.$i$-th section has: A student capacity:$cap_i$. Two lecture timings. (Formally, each ... 0answers 11 views ### How to compare objects which are having multiple comparable field-values? [closed] ... 2answers 21 views ### Isn't ZKP is a reduction to a hard problem, rather than true zero knowledge? Take for example "Hamiltonian cycle for a large graph". The proof works by starting with a graph G that contains a hamiltonian cycle, then constructing an isomorphic graph H, and then either showing ... 1answer 11 views ### Where is the original literature for the specification of an Associative Array ADT? I'm looking for the formal specification for the Abstract Data Type Algebra for the Associative Array, Associative List (AKA multimap), and other similar ADT to cite for use in a data specification ... 1answer 74 views ### Intersection of O(n) expanding circles with line from the origin I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution. Consider yourself as a point located on the origin$(0,0)$of an infinite two-... 1answer 11 views ### What does Bootstrapping approach means in terms of information extraction/ontology population? What does Bootstrapping approach means in terms of information extraction/ontology population? 3answers 94 views ### Is the P vs NP problem, an NP or co-NP problem? A few years ago, a youtube channel named hackerdashery, made an extraordinary youtube video explaining P vs NP, in a semi-vulgarized way : https://www.youtube.com/watch?v=YX40hbAHx3s At 7 minutes ... 1answer 35 views ### Conway game of life optimal state [closed] Recently I wrote a Java program to simulate Conway game of life. Generation starts in 250*250 cell completely random. Every time I tried, after 7th or 8th generation game was over. Anyway I want to ... 0answers 37 views ### Explain the process of formation of word senses in WordNet Regarding the word sense disambiguation problem, read the following fact written on Knowledge-based Word Sense Disambiguation using Topic Models: Note that although WordNet is the most widely used ... 1answer 24 views ### What is the time complexity of a binary multiplication using Karatsuba Algorithm? My apologies if the question sounds naive, but I'm trying wrap my head around the idea of time complexity. In general, the Karatsuba Multiplication is said to have a time complexity of ... 0answers 15 views ### Design a greedy algorithm by intermingling two sequences [duplicate] I find myself solving problems for a test and the next problem I still can't solve it. There are n ordered sequences,$S_1$to$S_n$. It is requested to intermingling them to obtain a single sequence,... 0answers 13 views ### In normative order evaluation, is there distinction between call by value, call by reference, call by sharing, etc? Consider different ways of evaluating a procedure call and its arguments. Essentials of Programming Languages says All the parameter-passing mechanisms (natural parameter passing, call by value, ... 1answer 22 views ### Union and Difference of languages generated by grammar [closed] So I have two languages$L = \{ w \in \{a, b \}^{\ast} \ | \ w \ \text{contains an odd number of a's} \}$and$L^{\prime} = \{ w \in \{a, b \}^{\ast} \ | \ w \ \text{contains at least two a's} \}$. ... 1answer 33 views ### CLIQUE$\leq_p$SAT i'm trying to reduce CLIQUE to SAT: Given: Graph G=(Vertices V, Edges E) and$k \in \mathbb{N}$Output: Formular F such that if G contains a complete subgraph of size k, the formular is satisfiable (... 0answers 18 views ### How well do multi objective optimization algorithms such NSGAii scale when there are many objectives (for example 10 or more)? What I'm trying to figure out is what happens when using a multi objective optimization algorithm such as NSGA-ii and instead of trying to find the usual 2/3 objectives, I use 10 or many more ... 0answers 13 views ### I couldn't find chapter 1 of JMU open source textbook of cs361 course on computer systems fundamentals [closed] Please help me find this , I need to find this chapter 1 , this is the link https://w3.cs.jmu.edu/kirkpams/OpenCSF/Books/cs361/html/index.html 0answers 11 views ### Constraint programming scheduling problem [closed] I am trying to find a programmatic solution to the following problem: There are 6 teachers for this room Each teacher must work for 8 hours a day Each teacher must have a 30 minute lunch break ... 1answer 62 views ### Can a CPU be replaced without interrupting the processes running on it? When I need to replace the CPU of my computer, I turn it off, replace the hardware, then reboot it. But what if you need to replace the CPU (in a single CPU machine) without stopping the processes ... 0answers 41 views ### Counting number of apples in an apple tree with given number of layers This problem comes from a competitive programming question, and it seems to require dynamic programming. There are several layers of apples arranged in a formation with each apple having a value ... 2answers 68 views ### how to prove that log(n!) >= c n log(n) for some c >0? as reading the book Algorithms by Dasgupta, C.H Papadimitriou. on Page 63. And it is well known that$\log(n!)≥c\cdot n\cdot\log n$for some$c > 0$. There are many ways to see this. The ... 1answer 24 views ### Is the reduction for HAMPATH to HAMCYCLE and UHAMPATH to UHAMCYCLE the same? HAMPATH/UHAMPATH is A directed / undirected graph G and 2 nodes s and t and is there a hamilton path from s to t? Likewise with HAMCYCLE/UHAMCYCLE but has a hamilton cycle on$G'\$ The reduction ...

15 30 50 per page