# All Questions

30,177 questions
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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?): ...
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 ...
24 views

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 ...
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 ...
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 ...
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: ...
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. ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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/...
10 views

### Lexicographic permutation list

Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order? Thanks.
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!
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"}) ...
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 ...
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, ...
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?
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
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 ...
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 ...
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
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 : ...
19 views

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 ...
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 ...
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 ...
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 ...