# All Questions

33,511 questions
Filter by
Sorted by
Tagged with
4 views

### Prove the Droid Trader Problem is NP-complete

This question is from Algorithms Design. A player in the game controls a spaceship and is trying to make money buying and selling droids on different planets. There are $n$ different types of droids ...
15 views

### Can a Non-Deterministic Pushdown Automata recognize $\# a^nb^{2^n} \#$ which a TM can?

$\# a^nb^{2^n} \#$ such that • The alphabet of the machine is {, a, b, x}. • The symbol x will never appear on the input a. • The contents of the tape at completion may be anything. • The head ...
7 views

### Algorithm to separate single contour of glyph into several strokes?

A glyph contour contains points set {p}, a point contains tuple (x,y,on_curve). Now, think about this need, converting contour of glyph X, for example, into to two contour parts or two strokes, point ...
11 views

### Finding a node in a binary tree by looking at the path between it and the root

There is a directed binary tree as shown in the picture (all edges are diercted from higher- to lower-level nodes). In that tree there is some specific unknown node $s$. All nodes in the $(s, root)$ ...
11 views

### Does quantum computing convert any O(2^n) algorithm into a polynomial running time and how?

For example, if it is a $O(2^n)$ algorithm that loops through 0 to $2^n - 1$ and check whether the number of 1 bits is divisible by 3, 5, 7, 9, 11, does quantum computing reduce it to non-...
9 views

8 views

### Confusion about analysis of lenght of lists in Hash Table with chaining under SUHA

I am working on to prove that the maximum length of any chain in a hash table of length n which gets n elements added to it is $O(\frac{\log n}{\log \log n})$ (Assuming uniform hashing). Let $X$ be ...
10 views

### How to make single cycle processor pipelined?

I was asked that how can one make a single cycle processor pipelined on a CS course without any specifications regarding the design. I suppose, that I should answer that what should be changed on ...
14 views

### Given a set of sets, what is the largest common intersection between them?

Given a set of sets: $S = \{~\{1, 2, 3\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$, I would like to find the largest common subset of $S$. If $S$ does not have a subset across all elements of $S$, I would like to ...
7 views

### Question on Cache Size

I'm having trouble understanding this particular problem. So given that: Cache size in bytes = 4096 The number of cache lines = 64 The cache block size in bites = 64 The number of main memory ...
26 views

### What's the problem of Learning Algorithms used for Automated Theorem Provers?

I've googled a lot but I haven't found an automated theorem prover/problem solver able to solve problems like a human. I am interested in a specific type of prover: the learning ones, like Support ...
8 views

### Path with least max-weight, in an undirected connected graph

The problem we were given, states that we have graph, where vertices are cities, and edges are roads. Each edge has a weight equal to the kilometers of the corresponding road. We want to get from city ...
13 views

### Getting rid of negative-cost edges in min-cost max-flow algorithmically

I have a min-cost max-flow problem. The designed network (without cycles) gives correct results using cycle cancelling, but it is way too slow. I would like to get rid of negative edges so that I can ...
31 views

### Max nodes whose value exceeds all neighbors

A node is valid if its value is greater than all of its incident edges. Task is to maximize the number of valid nodes. Given $n$ values for nodes and $n-1$ values for edges, how do I assign these ...
15 views

### CTL formula for “for every computation it is always possible to return to the initial state”

In the book 'Principles of Model Checking' by Christel Baier and Joost-Pieter Katoen they state that the CTL formula for " for every computation it is always possible to return to the initial state" ...
21 views

### Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar: E->E+E*E | E-E*E E->E+E | E-E | E+E | E*E | E/E E->(E) | x I must convert it to an unambiguous one ...
35 views

### How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

Consider the recurrence $$T(n)= 4T(\sqrt n) + \log^2n.$$ I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
48 views

### Converting connected graph to disconnected graph by removing minimum vertices

How to find the minimum number of vertices that need to be removed from a graph so it makes a disconnected graph?
15 views

### Finding maximal cardinal independent set given oracle

The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the ...
10 views

### Is checking if the length of a C program that can generate a string is less than a given number decidable?

I was given this question: Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable? With respect to ...
31 views

### Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
26 views

### Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?

I am having difficulties in understanding why the recurrence $$T(n)=3T(n/4) + n\log n$$ is solvable with Master Method but $$T(n)=2T(n/2) + n\log n$$ isn't? Despite they both look very similar ...
77 views

### How to prove LastToken problem is NP-complete

Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding ...
11 views

### Git Merge Lowest common ancestor problem

How does Git find the 'merge base' of two branches in a commit graph? From what I understand, this reduces to finding the lowest common ancestor of a directed acyclic graph. After reading up on ...
23 views

### doubt in pipelining

I am not from cse but trying to learn computer architecture on my own. Please clarify the following. In case of pipelining, each stage or subcomponent or subtask is assumed to be done in 1 CPU ...
18 views

### File Systems (Operating Systems)

The figure below depicts the structure of a simple inode-based file system. Each rectangle represents a disk block of some fixed block size. In respect to this diagram, I am asked: (a): Does this ...
12 views

### Adding two 4 bit binary numbers into 2 7 Segment LED up to 30 [closed]

I am trying to build a 2 bit binary adder into 2 7 segment LED's up to 30 and I'm having trouble getting passed nine as I believe there need to be an overflow but I am not sure. Was hoping to get some ...
23 views

### Knapsack with a fixed number of weights

Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There ...
15 views

### Associative mapped cache, word addressable

I have an associative mapped cache with 10 tag bits and an offset of 7bits. What is the size of each main memory block in words(word addressable) and main memory size in words? i worked it out as: ...
14 views

### Creating a Deterministic Push-Down Automaton for the Union of two languages

Suppose, we have $L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$. Now we want to create a Deterministic Push-Down Automaton for ...
23 views

### Decidability Turing Machine [closed]

If I have the code of a TM as $\omega$ with $\Sigma=\{0,1\}$, is it decidable that $\omega$ is the code of an TM? I would say yes because there is a finite number of codes of all TMs and i can create ...
99 views

### Regular expression for strings not starting with 10

How can I construct a regular expression for the language over $\{0,1\}$ which is the complement of the language represented by the regular expression $10(0+1)^*$?
22 views

### Another Subset sum problem

Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
34 views

### “Character placeholders” in a text field

The following question is asked to understand if this question can even be answered. Say we have a data field to which a stream of one or more characters could be inputted (say as a string or as a ...
22 views

### Dynamic length of union of segments (1d Klee's measure problem)

Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of ...
31 views

### How to find an solution set of subset sum when given an oracle to subset sum problem [closed]

The Subset Sum Problem: Input: a finite subset S of integers, and an integer t. Question: does there exist a subset A ⊆ S such that the members of A sum to t? Suppose you have access to an oracle that ...
41 views

### Proving NP-Complete problem by reduction of subset-sum

My assignment question as "given a multiset of symbols (letters) L from an alphabet Σ (thus, the same letter may appear in L multiple times), and a set of words W ⊆ Σ' , UseAllLetters asks if it is ...