Skip to main content

Questions tagged [python]

Programming questions are off-topic here. Do not ask questions about how to write code in Python. However, conceptual questions about computer science are more appropriate. See our help center for the scope of this site.

Filter by
Sorted by
Tagged with
13 votes
3 answers
4k views

Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks? [closed]

Python quite famously uses indentation to syntactically define blocks of code. (See Compound statements in the Python Language Reference). After years of using Python I'm still intrigued by and very ...
halloleo's user avatar
  • 257
11 votes
5 answers
3k views

Does an algorithm's space complexity include input?

Consider the Kadane's algorithm for finding maximum subarray within an array: ...
Eugene Yarmash's user avatar
9 votes
7 answers
6k views

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$. def is_equal(a: int, b: int) -> bool: return a == b <...
jtschoonhoven's user avatar
9 votes
12 answers
38k views

Time complexity of min() and max() on a list of constant size?

If you use min() or max() on a constant sized list, even in a loop, is the time complexity O(1)?
anshur's user avatar
  • 145
8 votes
3 answers
11k views

What is the expected time complexity of checking equality of two arbitrary strings?

The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters. So far so good. I think we can all agree that ...
jtschoonhoven's user avatar
7 votes
3 answers
2k views

Space complexity for storing integers in Python

So I was watching this mock interview by an Airbnb engineer on interviewing.io (https://youtu.be/cdCeU8DJvPM?t=1224) and around ~20:11 seconds he raises an interesting point. The question that the ...
Sidharth Samant's user avatar
4 votes
1 answer
753 views

What are the fundamentals of calculating space complexity in loops?

Imagine you loop n times, and every iteration you create a string of space n with scope only within that iteration (thus it is no longer accessible in the next iteration). I would look and say that I ...
Steven Zeng's user avatar
4 votes
1 answer
202 views

Warnsdorff's rule: more errors with odd sized boards

I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
Tortar's user avatar
  • 167
4 votes
1 answer
162 views

Why does parallelising slow down this simple problem against looping through all the data?

I've been using multiprocessing and parallelisation for the first time this week on a very large data set using 32 CPUs. I decided to explore it for a smaller task just to see if I could learn ...
quanty's user avatar
  • 205
3 votes
2 answers
1k views

Find 1s in almost all 0 array using comparisons only

So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python): ...
user555076's user avatar
3 votes
2 answers
810 views

Number of Inversions found in Selection sort vs Exchange sort

Exchange sort is similar to selection sort, just swaps "overly eagerly" instead of finding the minimum and doing only one swap. And the swaps affect how often the ...
Kelly Bundy's user avatar
3 votes
1 answer
188 views

Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order. I believe that I understood the three terms pretty well, and ...
Rodrigo's user avatar
  • 189
3 votes
2 answers
191 views

Python versus Matlab on the quantity 1/0

Python and Matlab seem to disagree on the division by 0. Python: ...
pluton's user avatar
  • 133
3 votes
1 answer
68 views

How does numpy.linalg.inv calculate the inverse of a matrix?

What is the algorithm behind this routine and is there documentation available for it?
oogabooga's user avatar
3 votes
1 answer
112 views

What's the runtime complexity of this algorithm for breaking up string into words?

I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to ...
AndresArpi's user avatar
3 votes
1 answer
527 views

Understanding Applicative Evaluation Order with the Z-Combinator

I am trying to understand how the Z-combinator (Y-combinator for applicative order languages) definition came about. As Python is applicative I am using Python for this. So I know Python's evaluation ...
lo tolmencre's user avatar
3 votes
2 answers
348 views

Are there any benefits of implementing the Fisher–Yates shuffle algorithm from tail to head instead of head to tail?

I was looking at the Fisher–Yates shuffle algorithm and followed the Python implementation for it. Python starts from the end of the array to the start. Looking at the algorithm I didn't see any ...
user1984's user avatar
  • 131
3 votes
1 answer
976 views

How to use Latin hypercube sampling with fixed points?

I use Latin hypercube sampling to select what point to evaluate my function. As evaluations take a lot of time, I want to limit the time by adding already evaluated points. I thought about taking the ...
HennyKo's user avatar
  • 131
3 votes
0 answers
39 views

Subtype Check with Type DAG

Trying to understand how compiler/static-type-checker checks for subtyping, I run into 2 problems. 1. Reachability in DAG Since both Python/C++ support multiple inheriatnce, the types can be ...
mq7's user avatar
  • 131
2 votes
2 answers
648 views

Doubt about computing running time / time complexity of a function in Python

I am learning about time complexity now, and I am working with BST (Binary Search Trees). This question needs some context and this is a follow up post to this post. Basically, I would like to compute ...
Rodrigo's user avatar
  • 189
2 votes
2 answers
623 views

“Converting” networkx / osmnx graph to a planar graph

I am currently working on some analyses of the Berlin road network, and I am using OSMNX to get a relevant graph representation. I noticed that - if with drawbacks - many authors use planar ...
Ben's user avatar
  • 123
2 votes
2 answers
72 views

Complexity of iterative exponentiation

I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it: The following function calculates $x^n$ ...
user109396's user avatar
2 votes
1 answer
279 views

Why is this n^2 growth?

I am attempting to understand the growth of the following algorithm, which is described as $n^2$ growth in the book I am reading: "... performs of the order of $n^2$ steps on a sequence of length $n$....
Elliot Rodriguez's user avatar
2 votes
1 answer
175 views

Repeated addition and comparisons of floating point numbers

In the following program where I repeatedly half an integer, it takes until i = 1074 for my integer to be equal to zero (I know that ideally the while loop shouldn'...
Rakhal Chandran.B's user avatar
2 votes
1 answer
322 views

Compute hash value according to multiplication method

In "Introduction to Algorithms" by C. E. Leiserson, R. L. Rivest and C. Stein (ISBN: 978-0262033848), p. 264 they state this: I get everything but the last part stating $h(k) = 67$ ...
ted's user avatar
  • 123
2 votes
1 answer
450 views

How can I optimize 3 variables in order to maximize the end product?

I am in the process of making a cryptocurrency trading bot. Currently, I am doing backtesting over a period of 7 months in which I provide a portion of historical data as if it were in real-life. By ...
CryptoTrader's user avatar
2 votes
1 answer
86 views

Repeated Substring Pattern

I've been working on the following challenge on LeetCode: Problem: Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together....
Ariana's user avatar
  • 123
2 votes
1 answer
64 views

Which approach of mine for an algorithm upper bound is correct?

Say we have this algorithm in Python. ...
CSch of x's user avatar
2 votes
2 answers
604 views

Why does python's threading library use OS level threads when it can't achieve parallelism?

I was surprised to hear that the threading module from python uses OS level threads. From what I know, OS level threads are more expensive (but can achieve parallelism) meanwhile green threads are ...
OneRaynyDay's user avatar
2 votes
1 answer
150 views

Why is KMP preprocessing O(N)?

My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from ...
Ewin Zuo's user avatar
2 votes
2 answers
364 views

Lambda Calculus Conversion

How can I take a Haskell data type or function (eg fold, list, String, zip) and convert or translate it to a lambda calculus abstraction? Example: If sum computes a sum of all elements in a list, and :...
Zuckerbrenner's user avatar
2 votes
1 answer
3k views

Min-coin change problem with limited coins

I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
Rikus Honey's user avatar
2 votes
1 answer
581 views

(Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?

The following question is taken from Leetcode entitled 'Combination Sum' Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique ...
Idonknow's user avatar
  • 169
2 votes
1 answer
846 views

Minimum cost node cut

I am interested in solving the following problem: Given an undirected graph whose vertices are weighted, find a subset of vertices of minimal weight whose removal disconnects the graph. Is there ...
SaRa's user avatar
  • 23
2 votes
2 answers
102 views

What is the practical use of list.clear() method in Python?

I was wondering if there is a reason behind clearing all the values in a list and reusing it, as opposed to deleting the list and creating a new one. Are there any practical advantages of using ...
Akshay Katiha's user avatar
2 votes
4 answers
123 views

Algorithm that finds 4 "O"s or 4 "X"s on a diagonal, horizontal, or vertical

My algorithm homework revolves around matching 4 "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical. ...
bbartling's user avatar
  • 123
2 votes
1 answer
3k views

Finding the area of a rectangle in python [closed]

Q: Standard input consists of exactly four integers, first x1 and y1, the coordinates of the bottom-left corner of a rectangle, then x2 and y2, the coordinates of the top-right corner. Write a Python ...
Lostsoulaside's user avatar
2 votes
1 answer
174 views

"Visited" vs "Seen" Positions in Breadth-First Search

I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid. In ...
Robin Andrews's user avatar
2 votes
1 answer
754 views

Conditional Shortest Path Through Weighted Cyclic Directed Graph

Vertices in my graph are composed of {name, category} where category is one of {red, grn, blu, ylw}. Edges in my graph are weighted and directed. In the visualization, the thick end of the edge ...
nickos556's user avatar
  • 121
2 votes
0 answers
32 views

Fast calculations using fast-Fourier convolution

Consider an array $X$ with shape $H \times W$. Let $Y$ be the other array of the same shape and $Z$ is an array of shape $h \times w$. We want to construct an array $R$ of shape $(H-h + 1, W-w+ 1)$ by ...
openspace's user avatar
  • 151
2 votes
2 answers
41 views

What is an algorithm to do this binary image segmantation task?

What I need to do is go from a binary image like this: to a segmented structure like this: because I have a program that operates on those separated line contours after. As you see, those contours ...
Konstantin H.'s user avatar
2 votes
0 answers
130 views

How to calculate delta Q (modularity increase matrix) in graphs?

I've been trying to implement the Three-stage Algorithm to compare its results with our new proposed algorithm with different datasets than those mentioned in the article. I've succeeded in ...
Imen Z Imanou's user avatar
2 votes
0 answers
139 views

How do you write a python\pseudo code that generates all pair permutations?

What would be a good pseudo code or Python 3 code for the following permutations problem? Let us define a n-permutation as a bijective function $\pi: \{0,...,n-1\}\rightarrow \{0,...,n-1\} $ and ...
Yoav's user avatar
  • 21
2 votes
0 answers
65 views

Reducing Kleene's predecessor for Church numerals

I am trying to "reinvent" Kleene's predecessor myself. The following code snippet should be self-explanatory. The idea is to make a 2-tuple and count up from zero, i.e. ...
nalzok's user avatar
  • 1,101
2 votes
0 answers
79 views

Consider vectorization and for loop, do both approaches have the same time complexity?

I am learning this post Fast computation of nearest neighbors is an active area of research in machine learning. The most naive neighbor search implementation involves the brute-force computation ...
singularli's user avatar
2 votes
0 answers
392 views

On teaching Kolmogorov complexity with Python and the complexity of composed strings

The setting of this question is a bit long-winded, but please bear with me. This fall I will be lecturing a course on mathematical information theory, and on a few lectures we will be discussing ...
Rami Luisto's user avatar
2 votes
0 answers
1k views

Knapsack problem in real life

My task is to develop an algorithm for the optimal arrangement of cylindrical objects in cartons. The algorithm is to have the task of placing as many products as possible into cartons, at the same ...
Kamor04's user avatar
  • 121
1 vote
2 answers
211 views

Why does Python allow stand-alone expressions?

In Python, this is a valid program def PrintWorld(): print('World') print('Hello') 0 'beautiful' True None 0 < 0 3, 3 lambda c:3 PrintWorld() All it does ...
Jann Poppinga's user avatar
1 vote
2 answers
478 views

Is the complexity of this two-sum binary search algorithm $O(\lg n)$ or $O((\lg n)^2)$?

This algorithm solves the Two-Sum problem$^1$ assuming that the input array/list is sorted. ...
joseville's user avatar
  • 115
1 vote
1 answer
1k views

How to wiggle sort an array in linear time complexity?

The wiggle sort is nums[0] < nums[1] > nums[2] < nums[3] > nums[4] ... For an input: nums = [1, 5, 1, 1, 6, 4], the expected output is ...
Aviral Srivastava's user avatar

1
2 3 4 5