All Questions

Filter by
Sorted by
Tagged with
0
votes
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, ...
0
votes
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 ...
1
vote
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:...
-2
votes
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 😅
1
vote
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 ...
1
vote
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 ...
0
votes
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.
0
votes
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 ...
0
votes
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 first-order logic with equality. It is an implementation of the E-hyper ...
1
vote
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?
1
vote
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 ...
2
votes
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 ...
0
votes
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 ...
2
votes
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 ...
3
votes
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, ...
0
votes
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 ...
0
votes
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 ...
-1
votes
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 ...
0
votes
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 ...
-1
votes
0answers
15 views

Promise problems in $NP$?

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

Number of circuits with at most $m$ logic gates

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 $...
1
vote
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 ...
1
vote
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 ...
3
votes
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
4
votes
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-...
0
votes
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?
2
votes
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 ...
-1
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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,...
0
votes
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, ...
0
votes
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} \}$. ...
2
votes
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 (...
0
votes
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 ...
-4
votes
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
0
votes
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 ...
3
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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