All Questions

42,733 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
8 views

it is a Haskell question down in the picture and I have no idea on how to solve this
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
20 views

Is arithmetic/constants code optimization a function of the Language/Compiler/CPU/ALU/OS and what languages implement such features in itself?

Take the following case ...
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 ...
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 ...
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 ...
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. ...
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 ...
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$ ...
19 views

...
55 views

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