All Questions

0
votes
0answers
46 views

Lomuto Quicksort with Middle Pivot [closed]

Would it be possible? It seems to be very hard and inefficient to implement as we would have to track the location of the pivot and swap the pivot when the left and right pointers meet \ cross. There ...
0
votes
0answers
22 views

how to transform problem into P or NP problem that can be solved by DFS? [closed]

i search that P or NP just yes or no problem , NP just with verify in polynomial time. but how to apply in real situation how to transform every problem into P or NP problem that can be solved by ...
0
votes
0answers
35 views

Mapping reduction for the useless state problem to prove that its undecidable

I want to give a mapping reduction (many-to-one) using the Empty_TM which accepts nothing, so the accept state is a useless state. This is to show that useless_TM is undecidable. A state q in a TM M ...
1
vote
1answer
43 views

How much does C# gain from its value types

C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to ...
0
votes
0answers
14 views

What is the difference between parallel virtual machine and message passing interface. And how both works [duplicate]

I m learning beowulf system architecture and I encounter these terms many time. I know these are the library file and we use these to write parallel programing. But I do not know how these work and ...
2
votes
1answer
28 views

Finding an unambiguous grammar of a language provided by a CFG

I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman. In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ...
-1
votes
0answers
28 views

Range queries in Trie

The question specifically aims to ask about range queries in a trie data structure. I have a binary trie which represents a set of numbers in the binary form. The numbers are initially given as an ...
0
votes
1answer
20 views

Boolean expression for sum bit of full adder

The Boolean expression I find on the internet for the sum bit of a full adder is A xor B xor Cin. Does't this expression exclude the A=1,B=1,Cin=1 situation? When that happens, the sum bit is also 1, ...
0
votes
0answers
11 views

Propagation delay vs max frequency

Do you agree with the following computation - and if no, can you explain why ?, if we make the assumption the the size of a CPU chip is 1 [cm] (which I am not sure, but I guess is not much bigger?): ...
3
votes
1answer
37 views

Proof for Unusual QuickSort Partition Scheme

TL:DR I wrote code for a QuickSort variant. It seems a bit off from original QuickSort. Can anyone tell me why and how this works? Is it a quicksort? The following is code I wrote for a middle pivot ...
0
votes
0answers
24 views

Computational Complexity of a Matrix Multiplication

I am computing a matrix multiplication with inverse operation $AB^{-1}C$ $A \in \mathbb{R}^{m \times n}, B \in \mathbb{R}^{n \times n}, C \in \mathbb{R}^{n \times o}$. So the inverse operation takes $...
5
votes
1answer
49 views

Optimal prefix-free binary code with several codewords already assigned

The classic Huffman algorithm, as Wikipedia states, finds an optimal prefix-free binary code with minimum expected codewords length, given a set of symbols and their weights. Now, suppose codewords ...
0
votes
0answers
9 views

Stuck in proof for $AM[2] = BP \cdot NP$

I am trying to solve this problem from Arora, Barak Exe 8.3 . For showing $BP \cdot NP \subset AM[2]$ , I have the following Since $BP.NP = \{L | L \leq_R 3SAT\},\ \exists \text{ PTM M st. } \Pr [...
3
votes
1answer
37 views

Lower bound on $1^k+2^k+\dots+n^k$

I calculated the worst case scenario of a time complexity of an algorithm problem using recurrence tree. (The problem cannot be solved by master theorem.) Now I want to find a lower bound on the ...
0
votes
0answers
10 views

Similarity of images with tree shape drawn objects

I'm trying to find the best algorithm for my task. I have images looking like this one: I want to find the most similar ones from a set of such images. I tried several algorithms to compute the ...
1
vote
0answers
22 views

Small step vs big step semantics for static analysis?

To be an honest question poster I do not yet fully grasp the difference between small step and big step semantics. There was a good discussion here My question is if I were to do static analysis on ...
2
votes
1answer
18 views

Modelling regex replacement via a DFA

I wish to model the following common construction in code via a finite state automaton for the purposes of static analysis: ...
1
vote
2answers
69 views

How do I model line comments in a CFG?

Assume we want to define a context free grammar of say a programming language, where on each line everything after the character # until the end of line is considered a comment and should be ignored. ...
0
votes
0answers
49 views

How to find all subarrays whose bitwise and lies in a given range? [closed]

Given an array A of integers,we are required to find subarrays ,the bitwise & of whose elements lie in a given range low to ...
0
votes
0answers
10 views

Doubt on the definition of Partial funtional dependency

I have some doubt regarding the definition of partial functional dependency. According to the book Fundamentals of Database Systems by Elmasri and Navathe the definition of partial functional ...
1
vote
0answers
70 views

Accounting for spaces in grammars

Sometimes in a context free language we'd like to require spaces between productions, and sometimes not. For example take the following part from a grammar describing grammars: ...
1
vote
1answer
16 views

How to cluster images based on meta-information in tags

Context and Motivation I have researched online for an algorithm (independent of a programming language AND in the context of Machine Learning) that accepts images as inputs with the expectation that ...
0
votes
0answers
12 views

Recognizing hardware on a system [closed]

Ok I recently asked this question https://raspberrypi.stackexchange.com/questions/96439/ensure-lock-a-program-to-run-on-raspberry-pi-only on Raspi section. I guess people are misunderstanding my ...
0
votes
0answers
14 views

Message Passing Algorithm and Implementation

I have a tree T with N nodes (Min-Span-Tree of a graph), and what I am gonna do is to calculate for each node Vi, the number of ...
0
votes
1answer
13 views

Importance of Frequency vs CAS Latency in memory performance

I was looking at the Wikipedia page for CAS Latency: https://en.wikipedia.org/wiki/CAS_latency And I noticed the obvious trend - at higher frequency, despite CAS latency degrading (growing), the ...
4
votes
1answer
56 views

Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
2
votes
0answers
21 views

LTL and alternation

Apparently, model checking LTL on Kripke structures is PSPACE-complete (see this question). Usually, when something in finite model theory is PSPACE-hard, there is a simple proof using the APTIME ...
1
vote
0answers
108 views

Can someone give me the resolution procedure for 2 SAT, which is O (nˆ2)

According to Wikipedia, Even, S .; Itai, A .; Shamir, A. cited it in "On the complexity of time table and multi-commodity flow problems". The paper can be found here: http://www.cs.technion.ac.il/...
0
votes
2answers
10 views

Lexicographic permutation list

Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order? Thanks.
-2
votes
0answers
34 views

Give a regular expression for language L [closed]

guys! I am studying formal language now. There is a question: Give a regular expression for language L={a,bb,aa,abb,ba,bbb...}. Can anyone give me some advice? Thanks in advance!
1
vote
1answer
38 views

Is this problem in NP?

I am new in complexity theory and have a doubt. If you have a language (alphabet) L (for example {"a";"b";"Y","0","1","◄"}) and a Dictionary D (for example {"abY";"Ú■";"ba";"000001◄";"FFG","342"}) ...
0
votes
1answer
53 views

Finding $t$, $r$ and $w$ in Cache - Direct Mapping

I had a question in my past System Architecture exam and I am not sure how to solve it. Question was this: Consider a 16-bit addressable memory and a direct-mapped cache sized 64 bytes. MAR is 10 ...
0
votes
0answers
12 views

Implementation of multiple sink shortest pair of disjoint paths problem for multigraphs

I would like to implement the shortest pairs of edge-disjoint paths of Suurballe and Tarjan for multigraphs in the interpretation of Banerjee et al. (http://web.cs.iastate.edu/~pavan/papers/short.pdf, ...
2
votes
2answers
38 views

Is intersection used in regular expression?

As union is part of regular expression in form of positive closure, similarly intersection is also a part of regular expression? in which form it can be used?
0
votes
0answers
18 views

How to measure the length of time-slices on os such as windows or linux? [on hold]

Is there any way to get the length of the time slide? How to design an experiment to figure it out in some ways such as a piece of C code
1
vote
1answer
20 views

Analyzing the railways network [closed]

I am studying complex networks and I have a question. Is it possible to use the tools and methods of the theory of complex network to study the properties of railways network? Are there any articles ...
0
votes
0answers
23 views

How to print the perimeter of a square using asterisks on Python? [closed]

I want to write a program that asks the user to enter the length of the side of a square then display a square composed of asterisks along its perimeter, such as shown below: My coding attempt is as ...
0
votes
0answers
15 views

How to ask neighbours to a bitcoin full node? There are some API to do that? [closed]

My goal is to write a program that analizes all the bitcoin network
0
votes
0answers
28 views

How can an unstable kernel write a memory dump?

I always wondered how a kernel that became unstable, e.g. due to a BSOD or a kernel panic, is able to do specific tasks. For example, if a Windows driver corrupts the stack of the kernel. It leads to ...
0
votes
0answers
19 views

How to prove this language is not context-free language by pumping lemma? [duplicate]

Could I get help to prove that the language $\{a^i b^j c^k \mid i>j>k\ge 0\}$ is not context free language by using pumping lemma?
1
vote
1answer
28 views

Can the complement of a context-free language be regular?

I know that the context-free language is not closed under the complement , and the result could be context-free language or non-context free language but my question is : is it possible of the ...
2
votes
0answers
10 views

area of the projection of a mesh

Given: a quadrilateral mesh that forms the surface of a sphere a linear projection from 3D to 2D (a 2x3 matrix) The mesh is not convex in general, but it is regular enough that we know that the ...
0
votes
1answer
42 views

How can I develop a pseudo-polynomial time algorithm for a non-integer problem?

I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$. Since the problem ...
1
vote
0answers
8 views

How to build an execution graph of concurrency accesses

Sorry If I don't use the right vocabulary, maybe part of my question is due to the fact that I don't know the name of what I'm searching. I have a bounded set of operations that need to access a ...
0
votes
0answers
55 views

Calculate makespan of job shop solution?

I have a job shop problem with n jobs and m machines, a job shop means that not all jobs have to go through every machine. A job shop problem can be written as such : ...
0
votes
0answers
19 views

Represent 4th root of 8 on line number exactly [closed]

Please help me how to represent 4th root of 8 on line number exactly? Please provide the step by step solution. Thanks in advance
0
votes
0answers
4 views

distribution of the system time and the number of customers in the system

I am trying to understand about two distributions: The system is customers are coming in and they are being serviced. There is a single server, and therefore, when a customer comes in, if server is ...
0
votes
0answers
8 views

MissForest package in CRAN R and it’s computational complexity or time complexity? [closed]

Can anyone give me the notation for the time complexity of missforest in R with ‘n’ as the number of instances and ‘m’ as the number of attributes? Is computational complexity as the same as time ...
2
votes
1answer
23 views

Equivalent unambiguous grammar

Given the grammar: $S \to AS\mid \varepsilon$ $A \to A1\mid 0A1 \mid \varepsilon$ Generate a new unambiguous grammar that generates the same language as the grammar above. I have no idea how to ...
2
votes
1answer
60 views

Determine number of values less than mean in one pass through list

The problem statement is as follows: Can we determine precisely the number of elements less than the mean in a list $A$ of $n$ numbers in only one pass through the array (starting at $A_1$ and ...

15 30 50 per page