All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
3 views

How process, file and memory management is implemented in Windows?

How Microsoft Windows Operating System handle process management, file and memory management? Or how process, file and memory management is implemented in Windows?
0
votes
0answers
5 views

Tensorflow Image segmentation [closed]

For my Image colorization project, I am trying to be able to get the class label for a given pixel in an image. For example, I want to be able to know if a given pixel of the image belongs to sky, ...
2
votes
1answer
65 views

Does it make sense to say Big Theta of 1? Or should we just use Big O?

Does saying $f(x) = \Theta(1)$ provide any extra information than saying $f(x) = O(1)$? Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying ...
3
votes
0answers
19 views

MST with possibly minimal diameter

I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph ...
0
votes
0answers
18 views

Can someone in Cyber Security or IT help answer this basic question on the change of today's malware? [closed]

1.) Before the most common types of malware were usually trojan horses and various other types of viruses derived from one’s own e-mail on a desktop. Given the timespan since those days, the game has ...
1
vote
1answer
14 views

Learning a specific functional form with machine learning

Suppose I have only three independent features (x, y, z) as the input to some machine learning routine (e.g. neural network). From some domain knowledge, I know ...
1
vote
1answer
19 views

Algorithm for optimal spacing in intervals

Is there an algorithm to optimally space points within multiple intervals? Optimal in this case means maximizing the smallest distance between any two points so that each pair of points has at least ...
1
vote
1answer
11 views

finding all cyclic substrings of a string

I have been stuck on this problem for a while now; any help would be appreciated. Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For ...
-1
votes
1answer
7 views

Find specific position in matrix

Consider a binary (i.e. over $\{0, 1\}$) matrix $A = (a_{ij})$ of size $n \times n$. It is known that there is exactly one $r \in [1; n]$ such that $a_{rj} = 0$ for all $j \in [1; n]$ and $a_{ir} = 1$ ...
1
vote
0answers
21 views

Is dijkstra's algorithm fastest possible algorithm for undirected graph with no additional data?

there are many similar questions, but I haven't found direct answer to this question. Consider I have undirected, weighted graph with positive weights, no additional data - hence no heuristic (so it ...
1
vote
0answers
13 views

“Visited” vs “Seen” Positions in Breadth-First Search

I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid. In ...
0
votes
0answers
9 views

Strange behaviour genetic algorythm

I created a function, in octave, that calc the acceleration time of a vehicle. I use that function inside a genetic algorythm, to optimize gear ratio. This is the behaviour (mean and standard ...
2
votes
1answer
27 views

Programming in Propositional Logic article notation question

I was reading this article about propositional logic and transforming problems to SAT. The author often uses the following notation (taken from Dominating set section): I don't understand what $[v,i]$...
3
votes
3answers
128 views

What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

This is a real-world application, not a student assignment. Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into ...
2
votes
0answers
16 views

Why do Karnaugh maps work?

The question is quite straightforward: Why do Karnaugh maps work? What was the reasoning that led Maurice Karnaugh to come up with these maps? At first glance, it doesn't seem a natural approach, ...
0
votes
0answers
17 views

Minecraft Computing

Basic computers have been created and optimized several times before in Minecraft. These were based on logic gates constructed from the 'redstone torch' block. I (who knows little of computers) was ...
2
votes
1answer
28 views

How should we interpret a transition rule $\epsilon,b\to c$ in a Pushdown Automata as Sipser defined in his book?

After defining pushdown automaton in Sipser's book at p. 113: at the bottom of p.114, he tries to describe a way to make a diagram for pushdown automaton as following: My question is about the part "...
1
vote
1answer
12 views

Proving undecidability of HALT_tm by reduction

Sipser in his book introduction to the theory of computation provided a proof of undecidability of $HALT_{TM}$. He uses a contradiction, he assumed that $HALT_{TM}$ ...
1
vote
0answers
14 views

How is it possible that an equational theory be terminating?

I'm a bit tripped up by this fundamental notion of an equational theory with respect to how we can possibly get termination if we have that we can always orient a set of equations either right to left ...
2
votes
1answer
80 views

Why the Call instruction in the x86 architecture saves the return address as EIP+5 instead of 4?

In 'The Computer Organization and design book' it illustrates the call instruction as Decrementing the stack pointer by 4. saving the EIP+5 into the stack. Jumps to the new address specified. What ...
0
votes
0answers
11 views

What is the dimensionality of the cost function given this specific ANN structure? [closed]

I have the following ANN architecture, the neuron is a sigmoid neuron: Where the weight and parameter matricies are given by: $$ \begin{vmatrix} & x1& & x2& & x3& \end{...
0
votes
0answers
18 views

Hashfunction for unique character distributions

The original problem is given a large input file, with n input lines of random string, find the number of pairs-> meaning same number and type of characters, in the file. Constraint on type of ...
1
vote
2answers
29 views

Why does MergeSort have O(n) space complexity if it splits the array log(n) times?

I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R". ...
2
votes
1answer
15 views

Allocation of many students to many schools based on capacity

Say I have a set of schools coordinates (S). I also have a set of neighborhoods centroid coordinates (N). I know how many kids are in each neighborhood, and they are categorized as either primary, ...
1
vote
1answer
17 views

Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?

Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current ...
1
vote
1answer
22 views

Reductions to and from PRIME

I think PRIME (is the given number a prime number?) is a good example a decision problem. Therefore, when I'm trying to explain reduction, I'd like to give an example of a problem that is related to ...
0
votes
1answer
16 views

Urgent Flag of TCP, Computer Networks

The Urgent Flag(URG) is set whenever the sender's Application Layer wants to send some urgent data to the receiver. In this case, the Transport Layer does not wait for enough data to achieve maximum ...
0
votes
0answers
13 views

Connecting islands to the mainland via flood fill

Say I have a large area filled using floodfill: Where the area in white has been flooded, and all other ares are not connected. I would like to "bridge" these islands to the main area in white, but ...
-2
votes
0answers
28 views

I need C++ help, please! [closed]

I have a simple problem in my textbook that I just couldn't understand. Since classes were cancelled, we didn't really get a chance to discuss it and I don't see any examples similar to it in the ...
0
votes
0answers
17 views

Need mentor: What kind of database should i use? [closed]

I need a little bit of guidance. I currently want to create a relational database with tables to later set it up with a website. I currently have mySQL on my Mac and have created a database with ...
1
vote
0answers
14 views

Combining TWO Monte Carlo algorithms to get a Las Vegas algorithm that solves the same problem

I came across a problem that I have no clue how to solve. Consider two Monte Carlo algorithms, called A and B that both solve the same problem. A is true-biased and t-correct, while B is false-...
3
votes
1answer
39 views

Is there a complexity class QPP?

The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach ...
0
votes
0answers
15 views

proof that SimpLe is fully expresive

Refering to this paper "SimplE Embedding for Link Prediction in Knowledge Graphs" by Seyed Mehran Kazemi and David Poole in 2018 : In page 4, about the proof of SimpLE being fully expressive, I ...
0
votes
1answer
22 views

In a NPDA if the stack is empty, where the start/end state are the same can you go again

Thoughts I am wondering if you get a string that goes through the NPDA and arrives back at q0 can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I ...
0
votes
1answer
16 views

Piecewise linear approximation for set of points

If we have a set of points $A$ and a known algorithm $Bestfit(A)$ to find the best-fit straight line-segment through $A$, what would be a good algorithm to construct piece-wise linear segments (with ...
2
votes
1answer
19 views

Is a DTM with k-tapes not the same thing as a NDTM with k-branches?

In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use. If a language L is ...
1
vote
1answer
36 views

Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
-1
votes
0answers
37 views

Number of gifts received problem

Assume we have N kids who all like dogs. One day they go to the shelter and there are M dogs of unique breeds. Each kid has a favorite dog breed and a second favorite dog breed. They are also lined up ...
0
votes
1answer
9 views

Intersection of two generative neural networks

I have an input x (a word), and I have a neural network Y such that Y(x), which is an image always satisfies F(x), and another neural network Z such that Z(x), which is also an image, always satisfies ...
1
vote
0answers
18 views

Determining Range of Current Node in Segment Tree

I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-...
2
votes
0answers
14 views

How to rank functions in increasing order [duplicate]

I mean I could just start putting values in each function and arrange them according to their corresponding values. But is there a better way of doing this.
1
vote
1answer
12 views

an algorithm for detecting if noisy univariate data is constant or is sum of step functions

In an explicit algorithm I'm writing, there is a certain stage where I need to determine whether or not a certain noisy univariate data is constant or is sum of step functions. For example, defining ...
0
votes
0answers
18 views

Is this a computable function? Is the reduction correct?

Let $A$ be a set, $K=\{x:\phi_x(x)\downarrow\}$. Let c to be a total computable function such that $\phi_{c(x,y,n)}(z)=\begin{cases}\phi_n(z) & \text{if }\phi_x(y)\downarrow\\\uparrow &\text{...
2
votes
1answer
39 views

Usual distances on DFAs (Deterministic Finite Automata)?

I've been searching in the literature for examples of distances defined on the set of the DFAs (or on the set of minimal DFAs) that are defined on a given alphabet sigma. Since the languages they ...
-1
votes
0answers
8 views

Time Complexity of this Question [closed]

Complexity of primeNumber function. int sqrt(int N) { int d; for(d=0; d*d<=N; d++) { } return d-1; } bool primeNumber(int n) { bool isPrime = true; int lmt = (sqrt(n)); for (int d=2;...
0
votes
0answers
30 views

Prove that regular languages are closed under Kleene star

Given $L$ is a regular language, how can I prove that $L^*$ is a regular language too? I've constructed an NFA which contains a new initial state that has an $\epsilon$-transition to the original ...
-1
votes
0answers
14 views

Develop an algorithm

I participated in a programming competition at my University. I solved all the questions except this one. Now I am practicing this question to improve my skills. But I can't figure out the algorithm. ...
1
vote
1answer
18 views

How many times in this pseudocode is the function F called?

For this question, I thought function F called twice but it called three times. Are those three functions were called? F(N), F(K) and f(N-1)? How many times in this pseudocode is the function F ...
0
votes
0answers
10 views

Matlab Optimisation Fitness Function COCOMO [closed]

I'm trying to calculate the COCOMO Model Parameters using Genetic Algorithm. This is the first time i'm using Matlab and I have watched a lot of videos on the Optimisation Tool in Matlab. I am not ...
0
votes
0answers
14 views

Red-Black Tree Height Proof

I know that the height of a red-black tree is at most 2 lg(n + 1). However, what is the mathematical proof of this? I searched various sites, however I couldn't find a good proof. I already know the ...

15 30 50 per page
1
2 3 4 5
700