All Questions

Filter by
Sorted by
Tagged with
2
votes
4answers
114 views

how to calculate $2^{5000}$ mod 10 without calculator in fast way?

How is it possible to calculate $2^{5000}$ mod 10 without using a calculator in a fast way? The result with calculator was 6.
1
vote
0answers
21 views

Does a decision variable that's just an upper bound on other decision variables make an integer program harder to solve?

I have several decision variables $max_s \in \mathbb{N}, s \in \mathcal{S}$ that are just upper bounds on other decision variables: $$x_{i,s} \leq max_s \forall s \in \mathcal{S}, \forall i \in \...
2
votes
1answer
23 views

In what sense if any does java have multiple dispatch?

I'm trying to get my head around the difference between message passing (with which we are all familiar as by far the most common form of object orientation today) vs generic functions as implemented ...
2
votes
0answers
8 views

Region-based memory management for recursive type

In the chapter 4 of Pierce's TAPL which discusses the implementation of untyped arithmetic expressions, the author said The most important [for the implementation requirements] are automatic ...
1
vote
0answers
10 views

Minimum Weight Binary Spanning Tree

Let $G=(V,E)$ be a simple graph with weights $w_{ij}$ (can be assumed to be positive). Is it possible to find the minimum (or maximum) weight, rooted spanning tree that is binary? That means every ...
0
votes
1answer
21 views

Proving whether an input sequence is in a given RE language

I've learned this a few years ago that this is impossible unless one simply 'executes' (in a modern computing sense) the input with the language rules, but I have some problems in just using this ...
0
votes
0answers
13 views

Can the value model for variables only be used together with static typing, not with dynamic typing?

There are two models of variables: the value model (e.g. variables in C) and the reference model (e.g. variables in Python). There is also a distinction between static typing and dynamic typing. Can ...
1
vote
1answer
10 views

Hardness of approximation statement clarification?

In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved ...
0
votes
0answers
16 views

Learning the weights in a directed acyclic graph

I have a directed acyclic graph $G=(V,E)$ where each vertex $v$ is associated with a weight $w_v$ such that $$w_v=1+\sum\limits_{(v,v')\in E} w_{v'}$$ and $w_v=1$ in case $v$ is a leaf. I am trying ...
1
vote
1answer
43 views

Does the Bellman-Ford algorithm find all the negative cycles?

The Bellman-Ford algorithm "can detect and report the negative cycle", but does it guarantee to find them or it may find some? The algorithm really focuses on the shortest paths, so I'm unclear if it ...
0
votes
1answer
18 views

Calculation of speed up of a program executed in multi-threaded system

Speed up of execution of a program is to be calculated within a multi-threading rather than a single thread system. The program's 30% instruction can be executed serially & rest can be executed ...
0
votes
1answer
21 views

Finite Language Closure Properties

Let L={F| F is a finite language over Σ} which of the following operation is not closed for L? a. intersection b. union c. complement d. none of the above I thought the ans as d as all finite ...
0
votes
0answers
8 views

Linux editing C files [migrated]

I want to edit a C file in linux, but I want to convert it to machine instructions and then edit the code instruction by instruction. Similar to the way gdb dumps the machine code but I want the ...
2
votes
0answers
39 views

How strong is an oracle that avoid don't-halt

Consider such an oracle: Given a turing machine[1], return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt. How strong is a TM with the oracle? Can the ...
1
vote
0answers
39 views

Algorithm to save state of array as it changes

There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be ...
0
votes
0answers
13 views

What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages?

I understand the basic operation of the algorithms however i'm unclear as to when to use one over the other and what advantages/disadvantages they offer over each other. Also as an aside, if anyone ...
0
votes
1answer
22 views

Condition in Arden's rule

According to Arden's rule, the language equation $X= AX\cup B$, with unknown $X$, has the solution $X=A^*B$, provided $A$ does not contain the empty string. My question: what is the problem with the ...
0
votes
0answers
31 views

For a processor running at 50 MIPS, what is the average execution time per instruction?

I have a practice test question. I am given only the MIPS with 4 choices of the average execution time. How is this calculated? Don't I need other data? I know that MIPS = (number of instructions / ...
0
votes
1answer
23 views

Looking for the name of this job scheduling algorithm

You have a list of jobs. Each job has a deadline and an associated profit if completed before the deadline. Also, each job takes 1 unit of time to complete, and only one job can be completed at any ...
0
votes
1answer
14 views

Comparison of constructive and local-search heuristics for TSP

In my high school class, we are currently looking at evaluating heuristic methods for intractable problems - especially TSP. My question is what is the advantages or disadvantages of using a ...
2
votes
1answer
47 views

Definition of extensional and propositional equality in Martin-Lof extensional type theory

Martin Hofmann states in Extensional Concepts in Intensional Type Theory (§1.1 p.[4-5]) that: A similar situation occurs in extensional Martin-Lof type theory where propositional and definitional ...
0
votes
0answers
8 views

Adding height to a minimum quantity of steps

I have a set of concrete steps. Each step has a height. I record the height of each stair, from first to last, bottom to top, as a list of heights: [1.3, 2, 3.5, 4.2]. There is an implicit first ...
-1
votes
0answers
21 views

smallest subset with given sum

How to find the smallest subset with a given sum? All elements are integers. I have an array of integers and I want to find a given sum with the least number of element possible with both the ...
0
votes
0answers
27 views

Algorithm and Time Complexity for k-Sum problems

In fact, there are three different k-Sum problems: Problem1: Given unsorted integer array $\{a_1, a_2, ..., a_n\}$ and a target number $T$, determine whether there exist at least one solution $\{a_{...
1
vote
0answers
25 views

How realistic of a concern is data corruption?

Similar to this question, but I wanted to be more specific to my real-world situation. I am a college software engineer currently working on a project that involves a large number of read cycles. ...
0
votes
0answers
6 views

Count compound words with an ambiguous decomposition

I have a set of words $D$, and I make compound words by concatenating a fixed number $n$ of words from $D$ (repetitions are allowed). Let's call such words $n$-compounds. I want to know how many ...
1
vote
1answer
32 views

I am looking for an algorithm that can find the best possible combination of inputs, in order to determine the optimum output

So as the title poorly implies, I'm looking for an algorithm that can accomplish the following task (as an example): Given the inputs A(1:100), B(1:100), C(1:100), that can take on any value between ...
9
votes
1answer
695 views

Why say that breadth-first search runs in time $O(|V|+|E|)$?

It's often stated (e.g., in Wikipedia) that the running time of breadth-first search (BFS) on a graph $G=(V,E)$ is $O(|V|+|E|)$. However, any connected graph has $|V|\leq |E|+1$ and, even in a non-...
1
vote
1answer
24 views

How to detect infinite loop exist in linear bounded automata (LBA)?

The following theorem from Michael Sipser's book "Introduction to the Theory of Computation" states: $A_{\textrm{LBA}}= \{ \langle M, w \rangle \mid \text{$M$ is an LBA that accepts string $w$} \}$....
0
votes
1answer
23 views

Do there exist any problems with optimal algorithms beyond $O(n)$?

Blum's Speedup Theorem famously shows that there are problems which admit no fastest algorithm. This raises an obvious question: are there any problems that do admit a fastest algorithm? In other ...
4
votes
1answer
566 views

What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
1
vote
2answers
56 views

Is there a formal definition for iteration?

I wanted know if there is a formal definition of iteration. In the sense that, this definition will say that after the 4th iteration is termination or the 5th iteration and not the 2nd iteration. ...
-1
votes
0answers
13 views

How to select M max Sum from N stack

We are given N stacks of variable length. We need to choose M element such that sum is maximum. example 3 3 stack a) 1 2 200 stack b) 5 10 7 stack c) 4 6 the answer will be 1+2+200 = 203 .
0
votes
0answers
11 views

Configuration space for multi robot system

I have a problem that I think can be casted in the following way. Suppose I have a simple closed polygon $\mathcal{P}$ and $n$ squares (bounding boxes) $\mathcal{B}_1, \ldots, \mathcal{B}_n$, you can ...
0
votes
0answers
27 views

Using Hoare logic to show an invariant holds or using induction?

I want to know if given a while loop: x = 0 while(x < 5){ x = x + 1 } I want to show that x (at the a ith iteration of the loop), the value of i is ...
0
votes
0answers
16 views

Is it interesting to make an FPT algorithm for a P-Space completer problems?

I have done a course on paramertized algorithms. For NP-Hard problem, Most of the researchers try to design an Fixed parameter Tractable algorithm. Let $P$ be a some P-Space complete problem. ...
0
votes
0answers
23 views

Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
1
vote
0answers
34 views

Bit stuffing in ethernet

I am naive to computer networks. I studied bit stuffing protocol which helps in identifying the end of the frame. If we assume a two systems which use ethernet protocol at data link layer. How the end ...
0
votes
0answers
35 views

Need help understanding set-associative cache

The problem I'm trying to solve is: A set-associative cache consists of 64 lines, or slots, divided into four-line sets. Main memory contains 4K blocks of 128 words each. Show the format of main ...
1
vote
1answer
193 views

Hamilton Circuit

The Dirac's theorem states that: "For a Graph G with N vertices, if the degree of each vertex is atleast N/2 then, the Graph has a Hamilton Circuit." Can the same be said if a graph has a Hamilton ...
1
vote
1answer
17 views

Differences between ALLTM and INF

The definitions of ALLTM and INF are as follows: $$\mathrm{ALLTM} = \{ \langle M \rangle \mid \text{ TM $M$ such that $L(M) = \Sigma^*$} \}. $$ $$\mathrm{INF} = \{ \langle M \rangle \mid \text{...
0
votes
0answers
8 views

Un-compute an operator given its oracle access

In general, is it easy to un-compute an operator given its oracle access? I want to ask in terms of computational complexity, that is, if there's any computationally feasible way to do this, or if not,...
0
votes
0answers
26 views

Program synthesis based on function properties

I am fairly new at program synthesis and the use of SMT solvers for this purpose. Given a function g, I want to generate all the functions f and h such that the following holds: f . g = h . f Are ...
1
vote
1answer
45 views

Analyzing time complexity of solution in tutorial

Could someone explain time complexity of solution of in this tutorial? I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$. What I figured so far is, for ...
1
vote
1answer
57 views

How to remove objects from an array most efficiently?

I am wondering if I can rearrange an array faster when I would like to delete more than one object. You are given a List: 1 2 2 3 4 5 7 And now you want to delete every "2" in the list. So what I ...
1
vote
0answers
7 views

Descriptors in key-features during mapping

This question is related to this question. In SLAM-type applications the feature detectors like SIFT are used for finding keypoints in the images to be matched. The candidate keypoints are matched by ...
6
votes
1answer
43 views

What publication first introduced the concept of a non-deterministic Turing machine?

What publication first introduced the concept of a non-deterministic Turing machine? Turing did not define the concept in his 1936 paper.
0
votes
1answer
16 views

What is the difference between a collection of Turing Machines and a family of Circuits?

Given a Collection of Turing Machines $T_1, T_2, T_3,...T_n$ where $T_1$ denotes that the Turing machine can only take in an input of size 1. Is there any difference in computational power to a family ...
4
votes
1answer
64 views

Definitional equality of two propositions about propositional equality

Martin Hofmann states in Extensional Concepts in Intensional Type Theory (§1.1 p.3) that: It is important that definition equality is pervasive so if M and N are definitionally equal then P(M) is ...
0
votes
1answer
14 views

Difference Between PTAS and FPTAS [duplicate]

According to this link: Polynomial Time Approximation Scheme (PTAS) is a type of approximate algorithms that provide user to control over accuracy which is a desirable feature. These algorithms ...

15 30 50 per page