Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

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

Logarithmic Time — O(log n) in Python

Hi , I am new to Data Structure and trying to get some clarifications. Following shows an example Logarithmic Time — O(log n) in Python. ...
-1
votes
0answers
20 views

Multipilcation table

we have this program: n = int(input('give n: ')) for i in range(n): for j in range(n): print(f'{i*n + j + 1:2}', end=' ') print() and we are supposed to changed it so that it prints 3 tables next to ...
0
votes
0answers
6 views

Competitive algorithm to solve a scheduling problem to minimize truncated gaps

Time is discrete. There are $m$ time-slots. There are $n$ jobs and one machine of budget $B$. If job $i$ is scheduled at time-slot $t$, then it will consume $c_i(t)$ units of the budget $B$. If job $i$...
0
votes
1answer
15 views

How do you prove these string/number radix encoding/decoding algorithms work?

A while back I learned of these great algorithms: ...
0
votes
0answers
7 views

How do you prove that this tree path calculation function works, from first principles mathematically?

I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the ...
1
vote
0answers
12 views

DAG decomposition, similar for one for series-parallel graphs

Let's consider directed acyclic graphs (DAGs) with single source and single sink. Such graphs can be combined with two operations, used in Series-Parallel graphs - parallel composition $P$ and series ...
0
votes
1answer
21 views

Asymptotic runtime of recursive algorithm uisng subsitution method

I need to solve this question using the substitution method: $T(n) = 3T(n/2)+2n$ if $n>1$ otherwise, $T(n) = 1$ Note: $$\sum_{i=0}^k x^i = \frac{x^{k+1}-1}{x-1}$$ $$a^{\log_b n} = n^{\log_b a}$$ ...
0
votes
0answers
12 views

Various implementations of adjacency list representation of a Graph

Just started learning about graph and it's various representations (matrix and adjacency list). Now I found that the adjacency list representation can be implemented in various ways: Array of arrays (...
1
vote
0answers
36 views

Oriented undirected edges in directed graph

I have a graph with $n$ vertices and $m$ edges. Some edges are already oriented, some are not. How do I determine how to orient all undirected edges so that each vertex has the same outgoing and ...
2
votes
2answers
39 views

Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?

When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced “big-oh of $g$ of $n$” or sometimes just “oh of $g$ of $n$”) the set ...
3
votes
2answers
51 views

How can I compute logarithm when comparison is undecidable?

In Haskell, I have the following datatypes that encodes arbitrary real numbers and arbitrary complex numbers, respectively: ...
1
vote
0answers
18 views

Non-Interactive Zero Knowledge Proofs: zk-snarks and zk-stark

I read up on an abstract example of ZKPs (the cave and the door), but I'm trying to understand NIZKs (specifically zk-snarks and zk-stark). All the examples I can find online seem to have some ...
1
vote
0answers
18 views

Algorithm to mapping given probabilities to empirical probabilities

Consider following problem statement: You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. The challenge is to perform given finite number of ...
3
votes
1answer
427 views

Why does the time hierarchy theorem use a rather intricate diagonal argument?

Isn't it possible to prove it by defining some problem that can be solved in $f(n)^2$ in the worst case due to its output always being $f(n)^2$ characters so that it won't be solvable in $f(n)$? Where ...
-2
votes
0answers
25 views

Сyclic routes in the table

In a $n × m$ table, some cells are locked. How to determinate time whether it is possible to split the remaining cells into cyclic routes of length at least $3$? All unremoved cells must participate ...
1
vote
0answers
15 views

Can Johnson's algorithm for simple cycles be modified in order to find only cycles up to length L (but all of them)?

I have a question regarding Johnson’s algorithm for finding all simple cycles in a graph. I was wondering it is possible to modify the algorithm in order to find only cycles up to a given length. ...
4
votes
1answer
178 views

The same outgoing and incoming degree in graph

I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same ...
0
votes
1answer
44 views

Bipartite maximum matching with added constraints

Suppose you have two lists as follows List $A$ = $(a_1, a_2, ..., a_m)$ List $B$ = $(b_1, b_2, ..., b_n)$ Each element in list $A$ can be paired with many or no elements in list $B$. I have a function ...
1
vote
1answer
43 views

Converting Decimal Numbers between 0 and 1 to Binary

I've been playing around with a program I wrote that converts decimal numbers to binary numbers and i've noticed that eventually, after applying the algorithm (multiply by 2, subtract 1 if greater ...
-2
votes
1answer
26 views

“what does the 1 to 10 mean?” FOR number ← 1 TO 10

"what does the to 10 mean?" FOR number ← 1 TO 10
0
votes
0answers
50 views

Are some algorithms inherently recursive?

Are some algorithms inherently recursive? As in, rewriting it in tail-recursive/iterative form with a stack is still needed, and there is no way to do it otherwise. I am asking because I struggled to ...
-2
votes
0answers
22 views

Probability of false positive for lookup in hashtable

I am going over Mikkel Thorups notes on hashing, as revision, and I came to the following exercise that i cannot see how to tackle (even initially - I know this is not ideal for a question.) $$ \...
0
votes
1answer
41 views

3SAT and directed graph

Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each ...
3
votes
1answer
25 views

Minimize range of distances between two sets of points

I have two sets of n points each in 2D Cartesian coordinates. I want to find a one-to-one pairing between the points in sets A ...
0
votes
1answer
51 views

Knapsack Problem with Constraints on Item Values

Given $n$ items with weights $w_1,...,w_n$ and values $v_1,...,v_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight ...
3
votes
1answer
111 views
+100

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never ...
0
votes
1answer
21 views

algorithms and the sequencing of numbers given a value

The numbers in the table below are the result of executing an algorithm that has one parameter $n$, a non-negative integer, and produces sequences of integers as outputs. For values of $n$ from 0 to 5,...
0
votes
0answers
18 views

How to write a method that takes two int parameters and return a string? [closed]

How do I write a method that takes two int parameters, a and b, and returns a String in the form a=q*b+r where q is the quotient from division and r is the remainder? Also how do I write a method that ...
2
votes
2answers
29 views

Why does case 3 regularity condition of master theorem always hold when f(n)=$n^k$ and f(n)=$\Omega(n^{\lg_b^{a+\epsilon}})$

I know that the regularity condition for master theorem Case#3 stating that [$af(\frac{n}{b}) ≤ cf(n)$ for some constant $c < 1$ and all sufficiently large n] always holds when the $f(n)=n^k$,$f(n)=...
2
votes
0answers
19 views

Comparing Directed Unweighted Graphs with Different “Densities” [closed]

I'm looking to compare 2 unweighted directed graphs and get an (ideally differentiable) similarity score. Both graphs describe a trajectory in a 2d space. The reference graph is a step by step guide ...
0
votes
0answers
23 views

(Searching + Splaying) in a Splay Tree

Given a tree To search for value 1, I do the following splay operations: i) Zag on 7 ii) Zag on 1 And hence obtain 1 in the root. But why would this be incorrect? i) Zag on 1 ii) Zag on 1 The ...
-1
votes
0answers
10 views

Flowchart Problem Sets in Computer Science

Instructions : Give an algorithm for each of the following problems using flowchart. Apply the necessary concepts and state your assumptions before drawing the flowchart that represents the algorithm. ...
0
votes
1answer
25 views

Making an algorithm that picks a unique random number in fixed set more efficient

I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have ...
0
votes
1answer
62 views

3Sum Why this O(nlogn) solution doesn't work?

I have been doing LeetCode and tackled the problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is $O(n^2)$ or $O(n^2 \times \...
0
votes
1answer
21 views

proof non-empty AVL tree

The vertex of a binary tree is called an single child if it has a father's vertex but does not have a neighbor. The root is not considered an single child. let mark in numOnly a number of vertices ...
0
votes
1answer
57 views

Find list of tickets with best price sum

I have an optimization problem, where i need to find set of tickets for certain period, such that sum of prices for these tickets is minimal. Algo should accepts list of trips and list of tickets as ...
0
votes
0answers
18 views

Are there any dynamic programming algorithms that combine solutions to sub-problems in a more 'dynamic' way?

First of all, I now know that 'dynamic' has nothing to do with the dynamism of a dynamic programming algorithm. But I didn't before I studied them, and I was kind of disappointed that they all seem to ...
2
votes
1answer
103 views

How to detect “tree-able” set-families?

A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
3
votes
1answer
52 views

Finding certain elements when only able to ask in chunks

I have a set of $n$ elements. Of these elements $b\ll n$ are blue and $r=n-b$ are red. I want to find all blue elements. My only way to discriminate between red and blue objects is by asking a ...
1
vote
1answer
22 views

Lowest complexity - Number closest to 0

I'm currently trying to improve my algorithm skills and I was trying a simple algorithm : Given a list of integers. We want to find the one that is the closest to 0. If we have a number and his ...
4
votes
1answer
179 views

Game on the graph with matchings

The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move ...
0
votes
1answer
67 views

Longest common sub-sequences with a condition

A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length....
2
votes
2answers
28 views

Finding the most frequent element assuming $\Theta(n)$ frequency

We know [Ben-Or 1983] that deciding whether all elements in an array are distinct requires $\Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $\Theta(...
0
votes
0answers
28 views

Problem with the algorithm

I am trying to execute the following algorithm shown in the image from my course slide. I am trying to get the table shown in the image: 1st Iteration L2: 1:CS=A, SL = A, NSL = A L3: while NSL!=[]: ...
0
votes
2answers
53 views

What is an algorithm for minimizing the standard deviation of m sums summed from n summands? [with attempt]

I have m bins (sums) and n summands. Each summand goes into a bin. In order to minimize the standard deviation, I have a greedy algorithm that appears to accomplish this. I am not sure of the name, ...
-1
votes
1answer
11 views

Maximal vs maximum matchings

Let $M_1$ be an inclusion-maximal matching in $G$ (that is, there is no matching which strictly contains it), and $M_2$ a maximum-size matching in $G$. How to prove that $|M_2| \le 2|M_1|$?
0
votes
1answer
35 views

Data structure that allows accessing elements by index and delete them in O(logn)

I need to take an kth index element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would ...
1
vote
1answer
38 views

Independent sets into which all the vertices of the graph can be split

How to prove that if $G$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $G$?
0
votes
0answers
27 views

How to handle distribution of values with same attributes into different classes

I'm a student studying a data mining course and have come across a problem. I need to explain the problem with the help of an example scenario as I do not know how to explain the problem in any other ...

1
2 3 4 5
177