All Questions

Filter by
Sorted by
Tagged with
-1
votes
0answers
10 views

Data Preprocessing pipeline and saving as a pickle file [closed]

I have been working on a data science model building. I want to understand that, how can I create a working data preprocessing pipeline in python for a single pickle file to save transformer data. The ...
0
votes
0answers
12 views

Reusability of neural network architecture

I have created a neural network architecture by considering the data for one study area. Have performed grid-search to tune almost all the hyperparameters of the model. I want to use the same network ...
2
votes
1answer
37 views

Meaning of "approximation within $n^{1−\epsilon}$"

I am not sure I understand correctly the following assertion (source): For all $\epsilon > 0$, approximating the chromatic number within $n^{1−\epsilon}$ is NP-hard. Does this mean that, for any ...
10
votes
2answers
1k views

Find shortest path between two vertices that uses at most one negative edge

Given a directed graph $G = \langle V,E \rangle$ with $n$ vertices and $m$ edges and a weight function $w:E \rightarrow \mathbb{R}$, together with two vertices $s$ and $t$ in $V$: Describe an ...
1
vote
1answer
18 views

Shamos algorithm , cannot understand the Area part

I wanted to find shortest time algorithm for finding the diameter of a convex hull, so I found Shamos algorithm on wikipedia: ...
0
votes
1answer
28 views

modify dfs to find longest path

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$. For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
1
vote
1answer
15 views

Linear having two different connotations?

When we discuss data structures, linear typically means that we can iterate through the data sequentially. For example, a linked list or array can fall into this category while a binary search tree is ...
0
votes
0answers
8 views

Haskell family tree questions [closed]

it is a Haskell question down in the picture and I have no idea on how to solve this
0
votes
0answers
18 views

Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}

I'm trying to design a Turing machine that accepts all strings in the language $$\{x^{n}y^{2n}z^{n}|\ n\in N\}$$ but I'm having trouble getting it to accepts when n> 1, for some reason it rejects ...
0
votes
0answers
12 views

Constraint Satisfaction Constraints Transformation

In constraint Satisfaction, there are implicit constraints which is a single variable and explicit constraints which are multiple variables. I have found a way to transform an explicit constraint into ...
-3
votes
0answers
29 views

Time complexity of assignment problem arbitrarily vs with repetition

what is the difference between the worst case time complexity of assignment problem using Hungarian method arbitrarily: choose only one optimal solution (is polynomial time)and with repetition: choose ...
0
votes
1answer
16 views

Can Operating system allocate a page of process to any free frame in memory?

Consider I have a user program of 6 pages and 4 byte page size. Now my memory has 300 frames out of which 10 frames are free for allocation. Can the OS allocate page 1 of the given process to any of ...
1
vote
1answer
17 views

Solve recurrence where the base case's time complexity is a function of the original input size

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...
0
votes
0answers
21 views

What are some good strategies to test a floating point arithmetic implementation for double numbers?

For IEEE, the single representation is 1-bit sign, 8-bit exponent and 23-bit mantissa. This means that at each exponent value, you can test all 2^23-1 (roughly 9mil cases) possible combination of ...
2
votes
1answer
28 views

Why proofs of Cook's Theorem assume k is given (n^k for NTM)?

A typical proof of Cook-Levin's Theorem proceeds like this: Suppose problem X is in NP. Then there is an NTM M deciding X in time n^k, for some k. Given a word w, NTM M, and k, we construct a Boolean ...
0
votes
2answers
20 views

Searching for sorting algorithm taking into account all possible solution of similar numbers

I need a reference for sorting algorithm where all possible orders are considered. example: if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ...
0
votes
0answers
21 views

Closest pairs of points with conquer without divide approach

In an algorithm where I have to search for the pair of points in a plain, with the smallest distance: suppose that we want to use a "Divide and Conquer" approach. Is it possible to make it ...
0
votes
0answers
24 views

FO-Logic: Two theories in the same complexity class can always be reduced to each other in polynomial space and time

I am currently studying CS and came across a question in my lecture. Question: Two theories in the same complexity class can always be reduced to each other in polynomial space and time. This is part ...
0
votes
0answers
16 views

Triangular matrices in Prolog [closed]

I am trying to write a program that identifies lower triangular matrices. I am quite new to Prolog and i would like your assistance on this. Considering a matrix as a list of lists, where each list is ...
0
votes
1answer
61 views

How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is: Give a linear-time algorithm that ...
0
votes
0answers
20 views

Handwritten sources of first inventors

When I was undergrad student, wondering how the inventor of the algorithm thinks like that. What was he/she writing out/drafting on papers/boards? I still cannot throw the thougt out the window, even ...
0
votes
1answer
17 views

Maximal edge weight clique of given size

Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. ...
1
vote
0answers
15 views

Proving set of register machines that halt before k steps for some input is non-recursive

Given an enumeration of register machines $R_n$ that take a single natural number as input, and a constant $k$, the function $f$ is defined as: $$ f(n) = \begin{cases} 1 & \exists m \text{ such ...
0
votes
0answers
26 views

Compute intersection points of n circles

Let $S$ be a set of $n$ circles in the plane. I need to describe a algorithm which computes all the intersection points of the circles. The algorithm should run in $O((n + k)\log n)$ time, where $k$ ...
0
votes
1answer
55 views

Shortest walk from $u$ to $v$ through $w$

We have an undirected, weighted graph $G=(V, E)$ with two weight functions $W_1 : E \rightarrow \mathbb{R}^{+}$ and $W_2 : E \rightarrow \mathbb{R}^{+}$ such that for every $e \in E$ we have $W_1(e) &...
0
votes
0answers
16 views

Implementing map for trees in agda - termination checking problem

I'm trying to implement Trees in agda as follows: ...
-2
votes
0answers
29 views

Try to solve a question from ProjectEuler [closed]

consider the following question from this link. How it possible to slove this question with finding largest path in Dircted Acyclic graph?
0
votes
0answers
22 views

Parameterized complexity of 3-SAT

Is the 3-SAT problem with $s$ variables and $t$ clauses FPT, parameterized by $s+t$, or W[1]-hard, or para-NP-hard?
1
vote
0answers
19 views

Deciding whether a set of relations can be composed to the empty relation

Is there an efficient algorithm to solve the following decision problem? Given a finite set $S$ and a set of relations $\mathcal R$ from $S$ to $S$, determine whether there is any sequence of ...
0
votes
3answers
200 views

How it's possible decide CNF by having a turing machine that decide SAT?

Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
0
votes
1answer
16 views

Understanding P, NP with an example decision problem

I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you ...
1
vote
1answer
32 views

How to think about heuristics

I have a game about drone delivery company. The game consists of a rectangular map, which contains tiles that cannot be passed. I can control a certain amount of drones, each one of them starts at a ...
6
votes
2answers
1k views

Proof that for 2n nodes of +1 and -1 position doesn't count

I'm having a hard time understanding how to solve this problem for my Computer Science 101 class. On a circle there are $2n$ nodes. $n$ out of these hold -1 power and $n$ hold +1 power. Say we play a ...
-2
votes
1answer
26 views

Need the time complexity of this conditional statement method

My idea of the program is : Input = n sets objective function ObjFn equals to O(n^3) Output = the order of n sets Steps: Applying ObjFn to all n sets Choose the n of the Minimum ObjFn to be ordered ...
0
votes
0answers
20 views

Showing that for all positive integers m and n there are sorted lists with m elements and n elements such that m+n-1 comparisons are needed

I was trying to solve a discrete math question regarding the comparison needed by a merge-sort algorithm. I wanted to ask if there were a more formal way to put organize my reasoning for this problem ...
0
votes
1answer
30 views

Expected value of the remainder when a random variable is divided by a number

Let $a,b,c,d,e,f$ be integers selected from the set $\{1,2,\cdots, 100\}$ uniformly and at random with replacement. Let $M=a+2b+4c+8d+16e+32f$. What is the expected value of the remainder when $M$ is ...
0
votes
0answers
20 views

Calculate complexity of game of life(cellular automata) [duplicate]

I want to calculate the kolmogorov complexity of n evolution of a game of game of life(game of life is a kind of cellular automata). I’m not searching for the complexity of a certain pattern of cells ...
0
votes
0answers
20 views

what is the running time of this while loop? [duplicate]

Hello i have a piece of code like this: ...
0
votes
0answers
28 views

Reduction techniques in complexity

I am learning computational complexity and parameter complexity. In order to proof that a problem is np-hard, we should reduction one which is np-hard to the problem. However, I don't have any idea ...
0
votes
0answers
16 views

Looking for a reference for "structured programming for data structures"

In a talk by Tony Hoare, he said something interesting and I'm looking for more reading on the topic minute 57: "Languages don't recognize the different structuring principles that are being ...
0
votes
0answers
23 views

Intuition behind : recursive algorithm takes exponential time [duplicate]

So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
0
votes
0answers
28 views

Is there a difference between Heapify and Bottom-Up/Top-Down heap construction, when using array representation of binary tree?

Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap? ...
0
votes
0answers
11 views

Queuing delay in packet switched network

So I was going through the exercises in the 'Kurose and Ross' book. Suppose users share a 2 Mbps link. Also, suppose each user transmits continuously at 1 Mbps when transmitting, but each user ...
2
votes
1answer
60 views

Counting number of times we visit vertices of given tree

Suppose we are given a tree $T=(V,E)$ where $|V|=10$. Now, one of the vertices is goal and we want to find it. The structure of the tree is given as input, but which vertex is the goal is unknown. In ...
-1
votes
0answers
11 views

Convert nested Schemas of SQL Columns to Hierarchical naming representation [closed]

Information: In SQL (e.g. Presto/Hive), there exists columns of "Complex" type {ARRAY, STRUCT, MAP} which are higher level structures on top of the basic INTEGER, BOOLEAN, DOUBLE, STRING, ...
-3
votes
0answers
13 views

recurrence equation 2T(n-4) + n^2 solution?

need help solving this equation. the general equation I end up with: 2^k * 2T(n-4k) + [ 2^k-1(n-4(k-1))^2 + 2^k-2(n-4(k-2))^2 + 2^k-3(n-4(k-3))^2....2^k-k(n-4(k-k))^2 ]
-4
votes
1answer
23 views

Proving correctness of Polynomial reduction

Given a problem A is NP-Hard and A ≤𝑝 B, is there a way to prove that B is also NP-Hard?
-1
votes
0answers
30 views

Can a machine that, given infinite space, functions as a non deterministic turing machine actually exist in the real world?

I am a novice when it comes to computer science. But I know that traditional quantum computers are not non deterministic Turing machines. But it seems to me that the principles of quantum mechanics ...

15 30 50 per page