#algos-and-data-structs

1 messages · Page 153 of 1

midnight dew
#

So you think if I don't flip the y, I just need to alter my rolls to go the other direction?

#

I didn't write any of this, so I'm just trying to figure out why each line is important. It would make sense if the roll()s are written specifically for a flipped kernal

#

I still don't know how I would go about deriving those values for the translation myself, but it would at least provide an answer as to why they're there.

vocal gorge
#

actually, hmm

#

no, they aren't quite the same with and without the flip

vocal gorge
# midnight dew So you think if I don't flip the y, I just need to alter my rolls to go the othe...

!e I think the rools are different, yeah. Because I'm able to achieve the same results by adding some additional rolls:

import numpy as np


def convolve(myarray, flip: bool = True):
    m, n = myarray.shape
    y = np.zeros((m, n))
    y[int(m/2-1): int(m/2+2), int(n/2-1): int(n/2+2)] = np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]])
    fr = np.fft.fft2(myarray)
    if flip:
        fr2 = np.fft.fft2(np.flipud(np.fliplr(y)))
    else:
        fr2 = np.fft.fft2(y)
    #print(f"fr2=\n{fr2}")
    m, n = fr.shape
    cc = np.real(np.fft.ifft2(fr*fr2))
    if flip:
        cc = np.roll(cc,1,axis=0)
        cc = np.roll(cc,1,axis=1)
    #print(f"cc=\n{cc}")
    cc = np.roll(cc, - int(m / 2) + 1, axis=0)
    cc = np.roll(cc, - int(n / 2) + 1, axis=1)
    cc = cc.round()
    return cc

myarray = np.random.randint(2, size=(4, 4))
print(convolve(myarray,True))
print(convolve(myarray,False))
halcyon plankBOT
#

@vocal gorge :white_check_mark: Your eval job has completed with return code 0.

001 | [[4. 6. 6. 5.]
002 |  [5. 4. 6. 6.]
003 |  [4. 5. 6. 4.]
004 |  [4. 4. 5. 6.]]
005 | [[4. 6. 6. 5.]
006 |  [5. 4. 6. 6.]
007 |  [4. 5. 6. 4.]
008 |  [4. 4. 5. 6.]]
vocal gorge
#

The ones I wrote will only work for an array of this size obviously (probably)

#

I made them up, by staring at the results of the cc prints for the two calls.

midnight dew
#

lol

#

Well okay that at least gets me started towards understanding this bit

vocal gorge
#

actually, you know what? it might always be 1

#

because what makes them needed is the fact the kernel isn't centered

#

when it's centered (so, when the array has odd size along each dimension), then whether you flip y doesn't matter; it's symmetric after all

#

Only even dimensions produce problems.

#

And there, I think it might just need a roll of 1 or something like that

midnight dew
#

Ok that makes a lot more sense

#

I still don't understand the intuition behind how the kernal gets applied to all the values at once, but I'm just gonna leave that for now as gospel

vocal gorge
#

fourier transforms are nonlocal by their nature - the value of a single frequency depends on the entire array, and when doing inverse transform, the value of every cell depends on every single frequency

#

as for how to derive this algorithm, uhhhh

midnight dew
#

It's okay. I'll probably end up taking a linear algebra class at some point to fill in the holes

vocal gorge
#

I'd say it's calculus and not linear algebra

#

maybe discrete mathematics

#

didn't hear anything about fourier on linear algebra, personally

midnight dew
#

Hmmmm okay good to know.

#

Maybe EE 201

#

I guess the jump from hermitian matrices to signal processing is a bit of a departmental jump

vocal gorge
#

except, oh dear, there's stuff about what order the frequencies go in the output too

haughty mountain
mossy osprey
#

What is a sweep line algorithm?

haughty mountain
# haughty mountain I guess I should post the obvious nit that "fft" is a particular family of algor...

and if you want to see a good video deriving the fourier transform, there is https://www.youtube.com/watch?v=spUNpyF58BY it gives some very good intuitions and interpretations about the transform, though this video does not cover the convolution theorem

YouTube
3Blue1Brown
But what is the Fourier Transform? A visual introduction.

An animated introduction to the Fourier Transform.
Help fund future projects: https://www.patreon.com/3blue1brown
An equally valuable form of support is to simply share some of the videos.
Special thanks to these supporters: http://3b1b.co/fourier-thanks
Learn more about Janestreet: https://janestreet.com/3b1b

Follow-on video about the uncertai...

▶ Play video
haughty mountain
#

that convolution is deeply connected to the fourier transform isn't entirely obvious, but it's a very deep connection that falls out easily from the math, if you are comfortable with the calculus involved

#

Fun thing, fourier transform is also applicable to polynomials. Multiplying polynomials knowing the coefficients is a convolution, multiplying polynomials given the values of the polynomial is just multiplying the corresponding values

#

And roughly speaking, the transform of polynomial coefficients are the values

haughty mountain
mossy osprey
#

Ook

#

Nice explanation lol

open moth
# 
#include <stdio.h>  
#include <vector>  
#include <algorithm>  
#include <cstring>
using std::vector;  
#include <iostream>
#include <iterator>
using std::ostream_iterator;
using namespace std;
void calc_constrain_prob(unsigned int end,vector< vector<long double> >& probs)  
{  
static const unsigned int highcount = 20;  
unsigned int highsum = highcount*end;  
probs.resize(highcount+1,vector<long double>(highsum+1,0));  
probs[0][0] = 1;  
for(unsigned int i = 1;i <= highcount;++i)                // 20  
{  
for(unsigned int k = 1;k <= end;++k)  
{  
for(unsigned int j = 0;j + k <= highsum;++j)  
{  
probs[i][j+k] += probs[i-1][j]/end;  
//printf("(%Lf,%Lf)",probs[i][j+k],probs[i-1][j]); 
}  
//printf("___"); 
}  

for(unsigned int t = 0;t < sizeof(probs[i]);++t)  
{
printf("%Lf",probs[i][t]); 
printf("\n");
}

printf("\n_%u_\n",i);
} 

}
# 
int main()  
{  
vector< vector<long double> > probs[21];  
calc_constrain_prob(4,probs[4]);  
calc_constrain_prob(6,probs[6]);  
calc_constrain_prob(8,probs[8]);  
calc_constrain_prob(10,probs[10]);  
calc_constrain_prob(12,probs[12]);  
calc_constrain_prob(20,probs[20]);  


static const size_t buff_size = 1000;  
static const size_t maxsize = 10*20*20;        // 4000  
char buff[buff_size] = { 0 };  
unsigned int nCases = 0;scanf("%d",&nCases);  
  
for(unsigned int iCases = 1;iCases <= nCases;++iCases)  
{  
unsigned int h = 0,s = 0,x = 0,y = 0;  
scanf("%d%d",&h,&s);  
  
long double ans = 0;  
for(unsigned int i = 0;i < s;++i)                    // 10  
{  
scanf("%s",buff);  
int delta = 0,z = 0;  
if(NULL != strchr(buff,'+'))  
{  
sscanf(buff,"%dd%d+%d",&x,&y,&z);  
delta += z;  
}  
else if(NULL != strchr(buff,'-'))  
{  
sscanf(buff,"%dd%d-%d",&x,&y,&z);  
delta -= z;  
}  
else  
{  
sscanf(buff,"%dd%d",&x,&y);  
}  
  
long double prob = 0;  
if(delta > (int)h) delta = (int)(h - 1);  

for(unsigned int i = h - delta;i <= x*y;++i) 
{prob += probs[y][x][i];
printf("<><><>");
printf("%Lf",probs[y][x][i]); 
}
if(prob > ans) ans = prob;  
}  
  
printf("Case #%u: %.9f\n",iCases,(double)(ans));  
}  
return 0;  
}
#

why the probs variable became 3d array

glossy breach
#

its an array of vectors of vectors

#

so its used like a 3d array

#

also this is python server

fathom delta
#

what's an efficient way to select the largest number in a very lengthy number list, in each iteration that largest number is halved and reinserted into the list
i could just use max(number_list) in each iteration but it's too inefficient. I've also considered sort the list, pick the last element, and then bisect.insort

haughty mountain
open moth
glossy breach
#

vector< vector<long double> > probs[21];

open moth
#

that's shown values inside the 2d array

#

after some lines when print probs
for(unsigned int i = h - delta;i <= x*y;++i)
{prob += probs[y][x][i];
printf("<><><>");
printf("%Lf",probs[y][x][i]);
}

became 3d

#

where the change happen and which part that push the value into 3d array

haughty mountain
stable hawk
#

Anybody with algos for trading experience?

fiery cosmos
#

Hi folks, I have a question for u.
imagine that I want to calculate the ceil of the division of 2 numbers. I can either do -(-X // Y) or do math.ceil(X / Y). So my q is, for instances like these that I want to calculate/do small tasks, is it better to use specifics libs or I should do things in the "vanilla" way?

agile sundial
#

i'd much prefer the latter. there's no thinking required to figure out what you mean by math.ceil

glossy breach
#

-(-X // Y) is more accurate, i always try to avoid floating number

haughty mountain
#

the ceil version is clearer, but less accurate in general

#

I would personally do a third option

(X + Y - 1) // Y
#

assuming X and Y are positive, I think the ones with negatives does the right thing in the more general case in python

fiery cosmos
#

hi all,
trying to learn algorithms from my CLRS text. i don't understand the loop invariant.

#

well i don't understand their pseudocode either, but thats a different story

fiery cosmos
#

in addition, is anyone good with runtime analysis? the way it is presented in the book is beyond confusing

agile sundial
#

i can probably help explain some details

fiery cosmos
#

ok that would be excellent. for example, in looking at insertion sort i am struggling to understand their nomenclature surrounding the times cost. i can post a photo

agile sundial
#

sure

fiery cosmos
agile sundial
#

wow is that a physical copy? 👀

fiery cosmos
#

yes

agile sundial
#

ok, which part is confusing?

fiery cosmos
#

so on the previous page, they state, "we let t_j denote the number of times the while loop test in line 5 is executed for that particular value of j"

agile sundial
#

right

fiery cosmos
#

it seems redundant. isn't that what they are saying in the previous expression, the summation of the number of times the while loop runs for given n when j=2

#

maybe i'm reading that incorrectly

#

also, not understanding the next sections where they prove best and worst case runtime, because they end up getting different terms an^2 +bn + c for a single input array A

#

also why is it t_j-1 on line 6

agile sundial
#

they assume the loop body is executed 1 less time than the loop test

#

it's the same reason why line 2 is n - 1 times

fiery cosmos
#

why would that be

#

just the nature of loops themselves?

agile sundial
#

yeah, if you think about what happens in a loop. first the test is checked, then the loop body is run if the test is true

#

if the test is false, then the body isn't run, so the test is run 1 more time than the body when it ends

fiery cosmos
#

ok

agile sundial
fiery cosmos
#

here is the computation of the running time given the above photo

#

sorry i just don't understand any of it. for me to go online and find a python implementation of insertion sort and see how it runs line by line is trivial. but for me to come up with a mathematical model of pseudocode is impossible.. any advice?

#

for example many of the exercises in the book are either "write the pseudocode for" or conduct a runtime analysis of some algorithm and im totally in the dark trying to learn it in this manner

agile sundial
#

you don't actually have to use pseudocode, and it's probably better to write it in an actual language, that way you can test it

fiery cosmos
#

if i understand my upcoming course correctly, many of the assignments are going to be write pseudocode in english and implement these runtime summations where appropriate

#

so i need to be able to convert back and forth between pseudocode and python and conduct runtime analysis on pseudocode

#

😵‍💫

#

maybe i need to just read on and not get hung up in the weeds, but then the book isn't really doing anything for me

#

conducting runtime analysis on real code seems difficult enough, for example i don't know when to declare something as log_2(n)

#

something to do with binary i know but then why isn't it instead O(0.5) or O(2)? so confused

agile sundial
#

the book is a bit difficult. you should be able to ask your prof for help

fiery cosmos
#

i'm not taking this until the fall, trying to understand it now before the course starts as i will have other graduate courses

agile sundial
fiery cosmos
#

i am well aware of that and have been unable to find those to help me including discord, online tutors, in person tutors with math PhDs, etc

#

it seems the people that truly understand this stuff are too busy to help others

agile sundial
#

do you know about binary search?

fiery cosmos
#

no

tacit nova
#

can anyone explain this code

#

s = [i for i in s.lower() if i.isalnum()]

#

it's basically regex

agile sundial
#

it's not regex pithink. it just takes the alphanumeric characters from a string, and lowercases the alpha ones

agile sundial
# fiery cosmos no

hm, ok. basically, the idea is you can halve the search space on each iteration, so it takes log n time, because it takes log n iterations to reduce the space to 1 or 0 elements

fiery cosmos
#

i thought logarithm was the inverse of exponentiation

agile sundial
#

it is

fiery cosmos
#

so why is halving equated with logn and not n/2

agile sundial
#

in binary search, because we halve on each iteration, log measures how many times we need to halve before we get to 1

fiery cosmos
#

log should be equated with n/n if anything

agile sundial
#

i'm not sure what you mean by that

fiery cosmos
#

dividing something in half is mathematically equal to multiplying by 0.5 or dividing by 2

#

so where does this log even come from

fiery cosmos
agile sundial
#

we're not just dividing by 2, we divide by 2 until we reach 1

#

if we have 2^n = x, then log_2(x) = n

fiery cosmos
#

ok i think the caveat here is that in runtime analysis theyre talking log_2 of some input n, not log_10

#

but then is it typically log_2 because of the nature of memory itself or because what the algorithm is doing

agile sundial
#

it's log_2 because we divide in half each time

#

log answers the question "how many times do we need to divide in half to reach 1"

#

hence, the running time is log n

fiery cosmos
#

ok so you used the example of binary search, which perhaps i will come across. i think the example of nlog_n in my books runtime analysis was that of mergesort?

agile sundial
#

mergesort is O(n log n), yes

fiery cosmos
#

do you know why the book uses theta for worst runtime analysis and not O?

#

i mean, to symbolize worst case runtime?

#

i think theta is an upper and lower bound and big O is only upper bound?

#

but if theta were upper and lower bound then it couldnt be worst-case, which is upper bound

agile sundial
#

theta is simply an asymptotically tight bound for a function. it doesn't say whether that function describes the best, average, or worst cases

fiery cosmos
#

thanks for your help btw something about log just clicked i realized that you cannot have an inverse of exponentiation in division, because you'd just reach 1 after the first step

#

ok they use theta as worst case runtime notation in the book, i'll have to see the formal def later

burnt trellis
#

if i have a list full of numbers

#

can i sort the numbers from highest to lowest ?

#

for example we have ```py
numbers_list = [3, 3, 4, 5, 7, 1]

#

like is there something like a module or something that can do that?

burnt trellis
agile sundial
#

numbers_list.sort(reverse=True)

burnt trellis
#

that works only for the lenght of strings tho

#

.sort doesnt work for integers

agile sundial
#

huh?

burnt trellis
#

;-;

#

try it

# 
numbers = input()
numbers_list = list(numbers)

print(numbers_list.sort(reverse=True))
agile sundial
#

!e

numbers_list = [3, 3, 4, 5, 7, 1]
numbers_list.sort(reverse=True)
print(numbers_list)
halcyon plankBOT
#

@agile sundial :white_check_mark: Your eval job has completed with return code 0.

[7, 5, 4, 3, 3, 1]
burnt trellis
#

wait what

#

huh??

agile sundial
#

it returns None and modifies the list in-place

burnt trellis
#

oh

agile sundial
#

you probably want to convert your input to ints too

burnt trellis
#

list..

#

jeez, thanks a lot btw

burnt trellis
#

appreciate it

fiery cosmos
#

can someone help me to understand mergesort? I don't understand their inputs p,q,r

#

the text reads "A is an array and p,q,r are indices into the array such that p<=q<r

#

also i'm still not understanding the math behind the analysis of insertionsort

burnt trellis
#

what exactly are u studying btw? i can barely understand anything from the image u sent , just curious what exactly ur studying

#

algos?

#

or its smth more complex

fiery cosmos
#

algorithms. the text is the famous introduction to algorithms text aka CLRS

#

their pseudocode is needlessly confusing and the runtime analysis is very mathy for no reason. for example

#

this is their analysis of the worst case runtime for insertionsort...

agile sundial
#

that's CLRS for you, it's very rigorous on purpose

fiery cosmos
#

its very unhelpful for those that are new to algos

grizzled schooner
#

they use p, q, and r to determine where in the large array are the sub-arrays that you're trying to merge

fiery cosmos
#

so they aren't required arguments

#

thats what the pseudocode makes it look like

grizzled schooner
#

huh? they are required

opal oriole
fiery cosmos
#

but when you call mergesort its on some input array A, not that plus subarrays

fiery cosmos
opal oriole
# fiery cosmos

Also this is mathematician bad variable naming, there is a reason why in every programming course they teach you to use long descriptive variable names.

grizzled schooner
agile sundial
#

what are you gonna call them lol. "left", "right", "center"?

fiery cosmos
#

ohhh

opal oriole
fiery cosmos
#

well not q although it is used later in a merge argument

agile sundial
#

so it can call itself recursively with smaller bounds

haughty mountain
fiery cosmos
#

soo the way its written above makes it seem as if i've gone through the array myself beforehand and identified the indices which will split the array..

burnt trellis
#

all of this needlessly complicated logic ur trying to understand is whats pushing ur logical thinking to the next level

#

its like punching a wall lmao, each time ur fist gets harder and harder

#

so tryna study all this complex logic is rlly good tbh

agile sundial
#

unless you only want to sort a subset ig

haughty mountain
#

input output example

[1, 4, 6, 2, 3, 7] and p = 0, q = 3, r = 6
 -------  -------
  sub1     sub2

[1, 2, 3, 4, 6, 7]
 ----------------
     result
fiery cosmos
burnt trellis
#

for how long have yall been studying such complex code btw? im curious

haughty mountain
#

oh wow, I actually aligned stuff properly on my phone

burnt trellis
#

such complex logic*

burnt trellis
haughty mountain
#

the algo isn't complex

fiery cosmos
agile sundial
#

are you not majoring in CS or something?

burnt trellis
haughty mountain
#

the analysisnis more complivated than what I would want to do though, that's for sure

burnt trellis
fiery cosmos
burnt trellis
#

maybe of one of yall explained it fully i can prob understand smth idk

fiery cosmos
burnt trellis
#

but not making anyone do that

#

too much lmao

opal oriole
# burnt trellis its like punching a wall lmao, each time ur fist gets harder and harder

I'm more for having multiple passes, I feel that it's needed anyhow to actually remember it after you finish and having that first pass that is not rigorous makes the second pass that more efficient to get through. But if you have already done a lot of this kind of thinking before, then you may be able to skip that first pass and go straight to the more rigorous part (e.g. you have done a lot of math and can just pick up some new book for some other branch and be fine with all the notation and abstract ideas).

fiery cosmos
#

so q and r are just like A[q] and A[r]?

burnt trellis
burnt trellis
agile sundial
burnt trellis
#

oh

fiery cosmos
#

so like 0 - len(A)?

agile sundial
#

something like that, yeah

fiery cosmos
#

ok

burnt trellis
#

hm

#

interesting tbh

fiery cosmos
agile sundial
#

no, because you only need to pass the first and last to the mergesort routine

haughty mountain
# fiery cosmos

the equivalent python would probably be clearer

inf = <some large value>
def merge(A, p, q, r):
  L = A[p:q] + [inf]
  R = A[q:r] + [inf]
  i = 0
  j = 0
  for k in range(p, r):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
fiery cosmos
#

yes, it is clearer

#

then what is up with their n_1 = q-p+1?

#

your example makes much more sense

haughty mountain
agile sundial
#

their arrays are 1-indexed iirc

opal oriole
#

The Python version can avoid some loops.

haughty mountain
fiery cosmos
#

but again, this is getting back to the heart of my issue, where understanding a real implementation line by line is straightforward but the pseudocode doesn't make sense. perhaps i need to go through with their pseudocode and a real implementation line by line, and discover for myself that "by this pseudocode they mean (real python line)"

agile sundial
fiery cosmos
haughty mountain
fiery cosmos
haughty mountain
#

I personally don't like this detailed pseudocode

fiery cosmos
#

i didn't like their more simplistic example either

opal oriole
#

Theirs is more like what C might look like (no fancy built-in slicing (slicing is amazing and pretty much every lang should have it these days IMO (and the new ones do))).

haughty mountain
fiery cosmos
#

hmm

haughty mountain
#

in particular, what happens if we have picked all the elements from one of the lists? we still need to move the rest of the elements in the other array over, but we have no element to compare with from the first array

#

there are other typical implementations as well that don't add inf at the end

#

e.g.

def merge(A, p, q, r):
  L = A[p:q] + [inf]
  R = A[q:r] + [inf]
  i = 0
  j = 0
  k = p
  while i < len(L) and j < len(R):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1 
    k += 1
  while i < len(L):
    A[k] = L[i]
    k += 1
    i += 1
  while j < len(R):
    A[k] = R[j]
    k += 1
    j += 1
#

now the main loop just runs until we run out of elements in one of the lists, and then it adds the remaining elements afterwards

#

adding the inf means we don't really have to do this handling, we can just keep picking the smallest element

#

I've never actually seen the version where you append an inf, it's pretty neat pithink

#

this kind of technique is kinda common for things like string algorithms, you sometimes can add an extra character at the end to remove a bunch of complicated bounds checking and whatnot

fiery cosmos
#

what is [inf]? A[p:q] is a subarray of the elements from index p through index q yeah?

haughty mountain
#

then list ends up as

[A[p], A[p+1], ..., A[q-2], A[q-1], inf]
#

and as I mentioned, tacking the inf at the end is there to make the rest of the logic cleaner

fiery cosmos
#

i'm thinking of inf as an input array of numbers

#

(a pythonic list)

haughty mountain
#

inf is just some large number

#

conceptually, infinity

fiery cosmos
#

wat

#

mergesort is supposed to take as input some unsorted array of integers and return them in sorted array

haughty mountain
#

the input array to merge is A pithink

fiery cosmos
#

where is the infinity coming from

#

or why is it in the example rather

#

are you just using that so say for arbitrarily large A?

#

oh my gosh im seeing the array index minus the other again in this python implementation of mergesort online.. what gives???

#

def merge(arr, l, m, r): n1 = m - l + 1 n2 = r - m

#

same as in book

haughty mountain
#

say I'm merging lists

L = [1, 3] R = [2, 4]
     ^          ^
     i          j
```1 < 2, add 1 to output

L = [1, 3] R = [2, 4]
^ ^
i j

L = [1, 3] R = [2, 4]
^ ^
i j
```3 < 4, add 1 to output, but what now? i will be incremented outside the list

#

if I add an extra element that will never be the minimum I don't have to worry about this case

#

and of course, any number in my input will be < inf, so I can put that at the end

haughty mountain
#

I kinda get most of that for free in python with slicing

opal oriole
#

If L[i] is inf (it reached the end), R[j] will always be lesser, so the else branch is always run from then onward, which is equivalent to the third while loop above, which copies the remaining elements.

#

So you no longer need the extra separate loops for the remaining.

haughty mountain
#

in reality the code underlying the slicing will have to compute sizes and copy over elements, much like in the pseudocode

fiery cosmos
#

how do we do markdown mode

#

for code

opal oriole
#

*Depending on the language and what you are slicing in it, it may not actually create a copy, and it's important to know when it copies and when it does not, or it will break things.

haughty mountain
halcyon plankBOT
#

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

fiery cosmos
#

ok

haughty mountain
fiery cosmos
#

i need to test my next question but i don't understand the p, q, r being inputs into the algorithm

opal oriole
#

Two examples of when it copies and not in Python, numpy does not copy unless it has to (or you tell it to) (some algos require that you copy): ```py

A = [0, 1, 2, 3, 4, 5, 6, 7, 8]
l = A[1:3]
l
[1, 2]
l[0] = 10
l
[10, 2]
A
[0, 1, 2, 3, 4, 5, 6, 7, 8]
import numpy as np
A = np.arange(9)
A
array([0, 1, 2, 3, 4, 5, 6, 7, 8])
l = A[1:3]
l
array([1, 2])
l[0] = 10
l
array([10, 2])
A
array([ 0, 10, 2, 3, 4, 5, 6, 7, 8])

fiery cosmos
#

it seems to me like they wouldn't exist until you slice through the input array and declare variables

haughty mountain
#

and it would make A into [1, 2, 2, 3, 4]

fiery cosmos
# 
def some_function(A,p,q,r):
        for item in range(1,len(A)):
                return item

A = [9,5,2,6,3]
some_function(A)
#

if i run this made up code with an input array, its going to tell me im missing 3 required positional arguments

#

how then can you define a mergesort function with required positional arguments of indices that need to be predefined

haughty mountain
#

mergesort doesn't really need those arguments

#

the merge function does

opal oriole
#

merge and mergesort are not the same thing. mergesort uses merge.

haughty mountain
#

right, mergesort makes use of merge for merging sorted ranges

opal oriole
#

You would call mergesort on an array, which internally uses merge.

fiery cosmos
#

how does merge get its required arguments

#

lets take for example this code from google

haughty mountain
#

do you know conceptually how merge sort works?

fiery cosmos
# 
# Python program for implementation of MergeSort
 
# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
 
 
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
 
    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)
 
    # Copy data to temp arrays L[] and R[]
    for i in range(0, n1):
        L[i] = arr[l + i]
 
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]
 
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
 
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
 
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
 
# l is for left index and r is right index of the
# sub-array of arr to be sorted
 
 
def mergeSort(arr, l, r):
    if l < r:
 
        # Same as (l+r)//2, but avoids overflow for
        # large l and h
        m = l+(r-l)//2
 
        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)
 
 
# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("Given array is")
for i in range(n):
    print("%d" % arr[i],end=" ")
 
mergeSort(arr, 0, n-1)
print("\n\nSorted array is")
for i in range(n):
    print("%d" % arr[i],end=" ")
 
# This code is contributed by Mohit Kumra
#

well thats sort of what im trying to understand but given their pseudocode

opal oriole
#

Mergesort sorts the left and the right, and then merges those two parts, recursively. It's that straight forward and elegant, merge contains all the actual work in terms of programming.

haughty mountain
#

and for the "sorts each half" part, it uses mergesort, but now with fewer elements

fiery cosmos
haughty mountain
#

that's mostly irrelevant to the question here

fiery cosmos
#

m is defined on the line m = l+(r-l)//2 and l and r are args to mergeSort so they are defined

haughty mountain
#

err, ok, you do need the indices for mergesort if it wants to call itself, my bad

fiery cosmos
#

how can one function have access to a variable defined within another function, isn't that "out of scope"?

fiery cosmos
haughty mountain
# 
# sort range [l, r)
def mergesort(A, l, r):
  mid = (l + r)//2
  mergesort(A, l, mid)
  mergesort(A, mid, r)
  merge(A, l, mid, r)
#

this is basically merge sort

#

you just need to handle the base case where you have 1 element

#

a list with 1 element is of course sorted

#

i.e.

# sort range [l, r)
def mergesort(A, l, r):
  if r - l <= 1:
    return
  mid = (l + r)//2
  mergesort(A, l, mid)
  mergesort(A, mid, r)
  merge(A, l, mid, r) 
fiery cosmos
halcyon plankBOT
#

@fiery cosmos :white_check_mark: Your eval job has completed with return code 0.

001 | calling called with 3 4
002 | called with  3 4
tacit nova
#

for Graph problem, I think they have 2 forms : the table and the graph (attached images). Are there any differences in term of solving the algorithm ?

Screen_Shot_2022-05-27_at_5.02.16_PM.png Screen_Shot_2022-05-27_at_5.02.22_PM.png
agile sundial
#

the top is what you might call an "implicit graph", where the graph is sorta implicit in the data structure

#

there isn't really a difference in the algorithm

tacit nova
#

thank you for helping me

keen hearth
#

Although if the graph is constrained to a lattice in that way, you may be able to use that fact to your advantage, depending on what kind of problem you're trying to solve.

trim prawn
#

how can I generate a random 4 digit number which doesn't have the number 8 or 9

fiery cosmos
agile sundial
#

or choices

lost apex
#

Anyone know of a good way to learn more about parsing text specifically? I'm trying to parse something like this:

Name: Skin Care Product

Ingredients: ingredient 1, ingredient 2, ingredient 3

Out of plain text files. The Name: part was easy for me, I just do a f.readlines(), iterate through the lines removing Name: from the line and what's left is the product name. However, with ingredients, it is trickier because there can be any number of lines of ingredients... I guess the only way to tell if it's the end is if there are two newline chars. Anyway, I'm a bit rusty with this hence my question about these type of string/text parsing algorithms.

#

I also thought about just using YAML for example, but thought if nothing else doing my original plan there would be a good learning exercise. 🙂

#

I guess the real question is, is there any way to use some pythonic stuff for this or will I likely need to get nitty gritty with the indexing of the strings? I can think of ways to do this but it's going to involve while loops with i,j etc...

opal oriole
# 
>>> s = "Name: Foo"
>>> s.split(": ")
['Name', 'Foo']
>>>
lost apex
#

Hmm ok I'll take a look at those docs thanks

vocal gorge
fiery cosmos
half lotus
#

You can reduce the space complexity to constant by using a "two pointer" approach

#

Basically, there is a slow pointer and a fast pointer. The slow moves one node at a time while the fast moves two nodes at a time. If the pointers equal each other then you know there's a collision.

#

Because in order for the fast pointer to equal the slow one, it means it must have gone backwards (i.e. a cycle)

fiery cosmos
glossy breach
#

you could do something like this to avoid using set ¯_(ツ)_/¯

# 
def has_cycle(head):
    if head == None: return 0
    pointer = head
    while pointer != None:
        if hasattr(pointer, "v"): return 1
        pointer.v = 1
        pointer = pointer.next
    return 0
fiery cosmos
glossy breach
#

just something to mark if the node has been visited

fiery cosmos
#

but pointer class has no such field? In this case node class

glossy breach
#

python actually lets you set one outside

fiery cosmos
#

oh. that's cool

fiery cosmos
#

This code below to validate whether a string of brackets is balanced

def isBalanced(s):
  brackets = {']':'[','}':'{',')':'('}
  open_bracket = []
  for bracket in s:
    if bracket in brackets.values():
      open_bracket.append(bracket)
    elif len(open_bracket)>0 and open_bracket[-1]==brackets[bracket]:
      open_bracket.pop()
    else:
      return 'NO'
   return 'YES'

This is failing the online judge. what do you think is wrong with it? I can't seem to identify the issue here
https://www.hackerrank.com/challenges/balanced-brackets/problem?isFullScreen=true

half lotus
fiery cosmos
half lotus
fiery cosmos
#

What is the best practice when it comes to null checking in python?
I usually use if len(mylist)==0: or if mylist==None

#

if mylist is really a list then it can't be None, but if not mylist: works to check if a list is empty

#

I see. That makes sense. Although, I find if not.. notation not as readable in this context. What other alternatives are there?

#

if not mylist: is probably the "Pythonic" way, though I agree it feels less readable. Otherwise if len(mylist) == 0: is fine (if not len(mylist): also works but is a weird in-between)

#

though if not mylist: also checks that mylist is None (which you may or may not want)

#

I agree. Thank you for the insight on this.

ionic locust
#

When should I use a linked list over a regular list?

So far ive only found it better in performance when inserting/deleting an element at or near the head of the list, since with a regular list youd have to shift over all those elements after the insertion/deletion point.

With regular lists you can also append at O(1) compared to O(n) for linked lists, and accessing an element at a given index is also only O(1) compared to O(n) for linked lists/

fiery cosmos
#

You can append but can't add in between at linear speed.

ionic locust
#

Also another question, when you're inserting a new element into a list of full capacity, is it correct that the program finds another random area of memory with 2x the allocated memory space of the original list to copy the new inserted list over to, then it performs the insert operation of shifting elements after the insert index one index down?
If so, what happens to the original list, is it deleted?

unknown.png
#

Also, how do you make a list reach full capacity? Do all lists have a default capacity, or is this capacity just the number of elements you initialise a list with e.g. with, ['a','b','c','d'], the program allocates a memory capacity of 4

fiery cosmos
fiery cosmos
ionic locust
#

Thanks!

ionic locust
fiery cosmos
#

Hmm, yeah your scenario of inserting at the head of the list is the main reason to use one. This comes up maybe most commonly with a queue (see collections.deque again), thought a queue can also be made with a normal array and a circular buffer https://en.wikipedia.org/wiki/Circular_buffer so the LL is not crucial

#

tbh linked lists almost never seem necessary in practice, in my experience at least lemon_sweat, arrays, dicts, sets and graphs come up way more (though LLs are really just a special case of a directed graph). I view linked lists as more of a quirky DSA learning tool than a super practical data structure lirikTHINK

ionic locust
#

Sounds good haha, thanks

opal oriole
#

Another key thing is that when it does come up, the nodes are not small, not like 1 integer per node. Like maybe an entire big chunk of memory per node (array or whatever in there).

mossy osprey
#

what's an Active Edge Table

glad vale
#

Hello!
I need better solution or an improvement for my code for this problem. I think I'm doing it right ( i've got all test passed but it's taking 17seconds and i know it can be a lot lot faster)

It's graph algorithm. Some modification of MST
We have an array A with towns. each town is represent by (x,y).
The weight of the streets is the lenght among each town given by formula :
len =sqrt((x1-x2)^2 + (y1 - y2)^2)

The time need to build the street is
ceil(len)
We need to create streets among all towns that the all towns are connected and the time to build all street is the lowest possible.
We assume that we are creating each street simultaneously.

So we have to minimize the building time of all streets.

My approach

  1. Sort edges by time ASC
  2. take first edge (the lowest time ) and for all edges
  3. Create edges_copy which will contain all edges with cost reduced by the current_lowest_one
    If the reduced time is < 0 then it's INF
  4. MST by Kruskal

Example:
A =[(10,10),(15,25),(20,20),(30,40)]

Result: 7

Because the streets is
0 -1, 0 - 2, 1-3

#

That's my code

from math import ceil

class Node:
    def __init__(self, vale):  # makeSet
        self.value = vale
        self.parent = self
        self.rank = 0


def find(x):
    if x.parent != x:
        x.parent = find(x.parent)
    return x.parent


def union(a, b):
    repA = find(a)
    repB = find(b)

    if repA == repB:
        return

    if repA.rank > repB.rank:
        repB.parent = repA
    else:
        repA.parent = repB

        if repA.rank == repB.rank:
            repB.rank += 1


def mst_kruskal(G, index, edges):
    A = []
    findUnion = [Node(i) for i in range(len(G))]
    min_edge = float('inf')
    max_edge = 0

    i = index  # index of curr el in findUnion
    e = 0  # number of edges that are in our MST ( should be lower than len(G) - 2 )
    while i < len(edges) and e < len(G) - 1:
        u, v, cost = edges[i]
        u, v = findUnion[u], findUnion[v]

        if find(u) != find(v):
            e += 1
            # A.append(edges[i])
            min_edge = min(min_edge, cost)
            max_edge = max(max_edge, cost)
            union(u, v)
        i += 1
    if e == len(G) - 1:
        return max_edge - min_edge
    return float('inf')

def highway( A ):
    # estimate the cost
    ans = float('inf')
    V = len(A)
    edges = []
    for i in range(V):
        for j in range(i + 1, V):
            cost = ceil(((A[i][0]-A[j][0])**2 + (A[i][1]-A[j][1])**2)**(1/2))
            edges.append((i, j, cost))

    edges.sort(key=lambda x: x[2])
    E = len(edges)
    for i in range(E):
        fixed_edge_cost = edges[i][2]
        edges_copy = []
        for e in range(i, E):
            if fixed_edge_cost <= edges[e][2]:
                edges_copy.append((edges[e][0], edges[e][1], edges[e][2] - fixed_edge_cost))
            else:
                edges_copy.append((edges[e][0], edges[e][1], float('inf')))

        edges_copy.sort(key=lambda x: x[2])
        ans = min(mst_kruskal(A, 0, edges_copy), ans)
    return ans
#
  • we never execute this line
            else:
                edges_copy.append((edges[e][0], edges[e][1], float('inf')))
shut breach
#

if you're building the roads simultaneously, and all you care about is the build time, all you care about is minimizing the maximum road

#

I'd sort your roads, then add the next longest to the graph until the graph is connected

glad vale
#

Hmm next longest?

shut breach
#

*next shortest

#

every road except the longest one is free

glad vale
#

So it's basically mst

shut breach
#

how so?

glad vale
#

But the only mst is not working here because if all roads are built for example in 5 days. and we have to add one that build in 30 days
the result will be 30 - 5 so 25.

#

Look example that i gave

shut breach
#

are you talking about in the problem or in your algorithm

glad vale
#

About the proble

#

m

shut breach
#

are you not trying to minimize the build time

glad vale
#

We have array of towns
A = [(23, 56), (12, 120), (45, 98), (73, 37), (1, 101)]

When i create (u,v,cost) array we have
edges = [(1, 2, 8), (0, 2, 15), (0, 1, 16), (1, 3, 22), (2, 3, 23), (0, 3, 37)]

and only the mst algorithm will give us
[(1, 2, 8), (0, 2, 15), (1, 3, 22)]
This is the solution by your idea if i understand correctly
so we have
22 - 8 = 14 days to build all roads

#

But the correct answer is 7 days

shut breach
#

explain why you're subtracting those

#

that's the time between when the first road finishes and last road finishes

#

(also that wouldn't be my solution)

#

my solution builds every road shorter than the longest road included in the solution

glad vale
#

Okey we need that because we want to know how many time we will need to build all roads ( we are building them simultaneously) So if the road with lowest cost is 7 ( so we will build the road in 7 days) and the highest road is for example 25 ( we are building these roads in the same time so)
that gives us 25 - 7 days in total to build all roads

shut breach
#

I'd argue that gives you 25 days to build all roads

glad vale
#

Yes that's right

#

But the answer we need is "the number of days separating the opening of the first and last highway."

#

Sorry i wasn't precise

#

so first highway we open after 7 days and the last one in 25 days so
25 - 7 = 18 is our answer here if there would be such an case

#

Hmm i can't get your idea 😅 Can you do it in pseudocode or on example that i gave?

shut breach
#

I don't think it'll help with this problem

glad vale
#

Okey

#

My idea is that some edge weight has to be the minimum edge weight among the edges in an optimal spanning tree; so fix a minimum edge weight and find an MST that only contains edges heavier than that. Since all MSTs are also minimum bottleneck spanning trees, this will work.

shut breach
#

yeah it should, but it's like O(E^2 log E)

glad vale
#

Yep that's right i know it's possible in O(E log V ) but i don't have idea how

#

I found something similiar on stack overflow but i don't know how to do update(connected) here

unknown.png
shut breach
#

that just means check if the current edges form a connected graph

glad vale
#

Okey sure but how to implement it efficient

#

I'm using in my code Union-Find structure

shut breach
#

worst case is O(E) by doing flood every time

#

it's easy to amortize the adding an edge part... not sure about removing edges though

#

maybe you could maintain a list of cut-edges as you build up the graph, then you'd know whether removing one disconnects the graph

#

idk how to maintain that list efficiently though

glad vale
#

me too

#

I'm struggling with this for 3 days

#

If i use cProfiler in pyton to see what takes the most time i see the MST takes a lot

#

If only there will be option to pick the appropriate edge first and then do the MST to check rather than just picking the lowest one and then increase

#

Because now it's O (E * MST) so O(E^2 * log E )

fiery cosmos
#

I was trying to print hello in python but it doesn't work

arctic shard
#

hello. is this channel appropriate for speeding up math based functions / algorithms?

lost apex
fiery cosmos
#

I am working on the hackerrank "define a queue using two stacks" question. Please se my code below:

class Que:
  def __init__(self):
    self.enqstack = []
    self.deqstack = []
  def enque(self, val):
    self.enqstack.append(val)
  def deque(self):
    if self.deqstack:
      self.deqstack.pop()
    elif self.enqstack:
      self.deqstack[:]=self.enqstack[::-1]
      self.deqstack.pop()
  def write(self):
    if self.deqstack:
      print(self.deqstack[-1])

How could have avoided using so many self statements? What else do you think can be improved?

keen hearth
#

Other suggestions:
You could simplify the logic of deque slightly (such that you don't repeat the line self.deqstack.pop()).

#

Also, are you remembering to clear self.enqstack after moving its items over to self.deqstack?

#

And also, you need to remember to return a value from the deque method.

glacial sail
# 
def binary_search(list_of_numbers, item_searched):
    the_lowest_element_in_the_list = 0
    the_highest_element_in_the_list = len(list_of_numbers)-1
    while the_lowest_element_in_the_list <= the_highest_element_in_the_list:
        the_middle_of_the_list = (the_lowest_element_in_the_list + the_highest_element_in_the_list) // 2
        guessed_number = list_of_numbers[the_middle_of_the_list]
        print(guessed_number)
        if guessed_number == item_searched:
            return guessed_number
        elif guessed_number > list_of_numbers[the_middle_of_the_list]:
            the_lowest_element_in_the_list = the_middle_of_the_list + 1
        else:
            the_highest_element_in_the_list = the_middle_of_the_list - 1
binary_search([1,6,7,9,11,14,18,19,21,25,27,29,33,36,40], 40)
#

why this binary search doesn't work?

fiery cosmos
# keen hearth Other suggestions: You could simplify the logic of `deque` slightly (such that y...

I still can't see how I could simplify it. I added a line for reseting the enqstack and that part seems to be working.
Another question: why the write function below is not working? It is supposed to print the last element of the que once triggered.

class Que:  def __init__(self):
  self.enqstack = []
  self.deqstack = []
  def enque(self, val:int):
    self.enqstack.append(val)
  def deque(self):
    if self.deqstack:
      self.deqstack.pop()
    elif self.enqstack:
      self.deqstack[:]=self.enqstack[::-1]
      self.enqstack=[]
      self.deqstack.pop()
  def write(self):
    if self.deqstack:
      print(self.deqstack[-1])
      
query_count = int(input())
q = Que()
for i in range(query_count):
  query = [int(n) for n in input().split(' ')]
  if query[0]==1:
    q.enque(query[1])
  elif query[0]==2:
    q.deque()
  elif query[0]==3:
    q.write() 
compact condor
#

Write a small list and run the logic on your notebook

#

before writing the code

#

see the logic first

#

when your loop should stop

glossy breach
#

It'd work better in this case

keen hearth
#

What if not self.deqstack (in the write method)?

#

Sorry, that was meant to be a reply to @fiery cosmos

keen hearth
fiery cosmos
keen hearth
rare garden
# 
def kth_largest(self, k: int) -> AVLTreeNode:
        """
        Returns the kth largest element in the tree.
        k=1 would return the largest.
        WC TC: O(logN)
        """
        if(self.root is None):
            return -1
        
        self.kth_largest_aux(self.root,k)
        self.count = 0#reset count
        return self.result
    def kth_largest_aux(self,current: AVLTreeNode,k):
        """auxilary function for kth_largest"""
        if current is None or self.count >= k:
            return
        self.kth_largest_aux(current.right,k)
        self.count += 1
        if self.count is k:
            self.result = current
            return current
        self.kth_largest_aux(current.left,k)```
#

Hi, can someone tell me if this method's time complexity will be O(logN) in an balanced AVL tree or would it be O(k)

#

bc if it isnt O(logN) i need to refactor

#

ping if needed

rare garden
#

Solved

#

it is infact not O(logN)

glad vale
glossy breach
#

idk

#

you could use prim with k-d tree

#

Then it'd be E log E or E log^2 E

#

i have never implemented it tho

#

also boruvka would make it E^2, which is still better than E^2 log E nevertheless

glad vale
#

The only MST algo is not the answer here

glossy breach
#

What do you mean?

glad vale
#

We need to minimize the number of building days separating the shortest road and the longest road.

#

So we have to do the MST through all edges

#

So E * MST_complexity

glossy breach
#

We assume that we are creating each street simultaneously.

glad vale
#

Yes

glossy breach
#

What does that mean though

#

You add edge one by one ?

glad vale
#

It means that each street start builds in the same time

glossy breach
#

Ohh

#

so the time is maximum of all build time?

glad vale
#

The time is max number of days that is need to build the longest one road

#

But our answer is

glossy breach
#

Yeah I see now

#

You can do it in log2(E) * MST

#

by using binary search

#

Wait you don't even need MST

#

Or am I still understanding it incorrectly

glad vale
#

I don't think so the binary search should help here because how it helps. I start searching the answer from the smallest cost one already

#

What's the approach without MST?

glossy breach
#

Why doesn't it help though

#

Let's say you fix a certain value to be the minimum build time possible to connect all the edges

#

Then it is obvious that any value greater than it is also valid

#

hence you can binary search for that value

#

log2(E) is much faster than E

glossy breach
#

You just have to find any spanning tree

#

So a simple dfs is enough I guess

glad vale
#

Yes, but that doesn't assure us that taking the edge with a smaller cost than we set will give us a larger value of the difference between the end of building the longest road and the end of building the shortest one

glossy breach
#

I don't get it

#

how does the shortest one affect the answer

#

isn't it only about the longest one

glad vale
#

It is further possible that taking the edge with the smaller cost will result in a smaller difference

#

It's about
the_longest_one_time - the_shortest_one_time

glossy breach
#

I see

glad vale
#

to "open" roads as close together as possible after being built

glossy breach
#

We need to create streets among all towns that the all towns are connected and the time to build all street is the lowest possible.
you should have interpreted it more clearly 🙂

glad vale
#

Yes i see 😅 Everyone has a problem with this

#

Even i when i first read this i though oh its just mst and done

glossy breach
#

i see now why you used kruskal and not another mst algorithm

#

only kruskal works in this case

glad vale
#

Prim's MST works as well but it's slower and not convenient

#

I currently has 1.56s to complete all test in my code because I add If -> break condition to prevent doing algorithm for no reason

glossy breach
#

There's a way to use 2 pointer with link cut tree to get E log E

#

but idk if someone would bother implementing link cut tree in python

glad vale
#

You know that i was trying to to that? But it overwhelmed me and nothing was working

glossy breach
#

i wouldn't do that either

#

it's going to be the most painful thing to code

glossy breach
#

isn't that fast enough

glad vale
#

Noo my classmates has like 0,04s xD

#

But we can't talk about the code and ideas because we have a serious palagit system here

glossy breach
#

is it alright that you are asking it on this server :)

glad vale
#

Yes i think so. If something would go wrong no one before me asked about that so i would justify myself

glossy breach
#

okay

#

can you try implementing that in c++ or sth because i'm sure it's gonna be much faster

#

python is quite slow in competitive programming

glad vale
#

I know that but we are doing all stuff in python currently

glossy breach
#

oh

glossy breach
#

but lets move this to DMs ig

glad vale
#

Okey that's interesting

haughty mountain
#

I didn't read the problem closely, but shouldn't O(E log E) be fairly easy? Sort edges by weight, use a DSU data structure to add edges one by one until everything is connected.

#

The worst part of the complexity is just from sorting the edges, the DSU part is cheap

shut breach
#

they're trying to minimize the difference between the longest edge and shortest edge

#

(which you should really mention up front because it's a very different problem)

haughty mountain
#

so not minimize max edge cost?

shut breach
#

right

haughty mountain
simple pier
#

Find the sum of integers between 1 and N (inclusive) that are not multiples of A or B.
You are given N, A and B.

the naive way is to iterate from 1 to N and check if it's divisible by A or B

or we can use the AP formula
then do sum of all - sum of multiples of A - sum of multiples of B - sum of multiples of B + sum of multiples of both A and B

#

are there other ways?

vocal gorge
#

the second way seems like it'd be the best one

tacit nova
#

this is a simple depth first search here, anyone know why we use * in the last line /

def depth_first_values(root):
  if not root:
    return []
  left_values = depth_first_values(root.left)
  right_values = depth_first_values(root.right)
  
  return [ root.val, *left_values, *right_values ]
tired wadi
sour ether
#

Hey Guys
I want to take input from user in binary tree but it is showing the error (ValueError: invalid literal for int() with base 10: '').

This is the code:
`class treenode:
def init(self,data):
self.data=data
self.left=None
self.right=None
def printtree(root):
if root==None:
return
print(root.data, end=":")
if root.left!=None:
print("L",root.left.data,end=",")
if root.right!=None:
print("R",root.right.data,end="")
print()
printtree(root.left)
printtree(root.right)
def treeinput():
rootdata= int(input())
if rootdata == -1:
return None
root=treenode(rootdata)
lefttree=treeinput()
righttree=treeinput()
root.left= lefttree
root.right= righttree
return root

root= treeinput()
printtree(root)`

#

Pls correct why it's not working

rocky iris
#

What is the purpose of an activation function?
A. To decide whether a neuron will fire or not
B. To increase the depth of a neural network
C. To create connectivity among hidden layers
D. To normalize the inputs

scenic schooner
#

not allowed

#

to send homework/exam problems

scenic schooner
# 
def treeinput():
    try: rootdata= int(input("enter number"))
    except: return None
    root=treenode(rootdata)
    lefttree=treeinput()
    righttree=treeinput()
    root.left= lefttree
    root.right= righttree
    return root
sour ether
#

Yeah I got it.

fiery cosmos
#

What would be the most appropriate data structure for the following use:
lookup (preferably O(1)) whether an element exist in the dataset?

fiery cosmos
#

How can I prepopulate a dictionary using enumerate but keys and values will be flipped?
word = ['p','y','t','h','o','n']
dictionary = dict(enumerate(word))
leads to {0:'p', 1:'y', 2:'t', 3:'h', 4:'o', 5:'n'}
but I want {'p':0, 'y':1, 't':2, 'h':3, 'o':4, 'n':5} instead

dark aurora
#

How to use binary search tree but without classes and objects just with lists and stuff like that?

austere sparrow
austere sparrow
tacit halo
#

Hi

#

I mean

#

sup

tacit nova
#

for binary tree,
i feel like DFS recursion has faster runtime than BFS queue, even though both speed are O(n), right ?
also we need O(n) space for queue and DFS is O(1), right ?

agile sundial
#

no, since the call stack takes space too

ancient ermine
halcyon plankBOT
#

@ancient ermine :white_check_mark: Your eval job has completed with return code 0.

{'p': 0, 'y': 1, 't': 2, 'h': 3, 'o': 4, 'n': 5}
woven jolt
#

Hi

fiery cosmos
#

Hi

young kiln
#

str1="hi this is your chap"
vowels=["a","e","i","o","u"]
reslt=""
def func1(str1,vowels,reslt):
for i in str1:
if i not in vowels:
reslt.join(i)
return reslt

func1(str1,vowels,reslt)

Could anyone assist me with the above function as to why itss not returning the complete sentence without vowels using joins

fiery cosmos
#

Below is my attempted solution to the 98. Validate Binary Search Tree leetcode question. It is failing the online judge. What is it that I am missing? I see nothing wrong with it.

class Solution:
  def isValidBST(self, root: Optional[TreeNode]) -> bool:
    return self.validator(root, None, None)
  
  def validator(self, node, minimum, maximum) -> bool:
    if not node:
      return True
    minbounds:bool=minimum and node.val<=minimum
    maxbounds:bool=maximum and node.val>=maximum
    if minbounds or maxbounds:
      return False
    return self.validator(node.left, minimum, node.val) and self.validator(node.right, node.val, maximum)
silk canyon
young kiln
#

thanks @silk canyon for the info.

torn nacelle
#

Can I ask my doubt here?

#

I am unable to clear 2 test cases I think I tried all the cases but still don't know the error

gritty monolith
#

Are there any disadvantages to implement __hash__ like this, when I need my class to be hashable?

    def __hash__(self) -> int:
        return id(self)```
#

I don't care about two objects having equal attributes and not having an equal hash, I just wan't single objects to be hashable

lean walrus
#

add this to your class```py
def eq(self, other: object) -> bool:
return self is other

gritty monolith
ivory yacht
#

That is the default hash behaviour anyway. It might also be clearer to just do __hash__ = object.__hash__ and the same with __eq__.

fleet adder
#

Hey guys, I was wondering if there was any way to produce this sort of behaviour :)

class Foo:
    def __init__(self) -> None:
        self.a = 0

    def set(self, var, val) -> None:
        # If it exists, set this object's
        # var = val
        pass

thing = Foo()
thing.set("a", 3)
gritty monolith
gritty monolith
#

e.g. setattr(thing, "a", 3)

#

but this will set regardless of if it already exists

#

@fleet adder I am curious for what you need this, I only remember using this for some little hackery

fiery cosmos
#

Is it possible to pass/receive comparison operators as parameters?
without using conditional statements and treating them as strings but instead processing them directly

def comparison(num1, operator, num2)->bool:
  return num1 operator num2

comparison(5, <, 3) will return false
on the other hand
comparison(1, >, 0) will return true

gritty monolith
#

You could pass these functions

gritty monolith
ivory yacht
#

Integers return themselves as the hash value.

lean walrus
#

!e

print(hash(2**64))
halcyon plankBOT
#

@lean walrus :white_check_mark: Your eval job has completed with return code 0.

8
lean walrus
#

🧐

agile sundial
#

up to a certain limit

gritty monolith
fiery cosmos
#

hello,

#

i do not understand this definition of mathematical induction

#

Specifically what I do not understand is "assuming P(k) is true" (they say what the kth element is, but not how it would be true or false) and also I do not understand their math following "to both sides of P(k), obtaining..."
They show that something equals (k+1)^2 and then "which is P(k+1) and I don't follow that simplification.

austere sparrow
#

@fiery cosmos The core idea behind induction is:

  1. You prove that if a statement is true for some number n, then it also true for the next number (n + 1)
  2. You prove that the statement is true for some initial number (like 1)
  3. Then if follows that it's true for 1, therefore it holds for 2, therefore it holds for 3 etc.
lament totem
#

P(k) is an equation that says that the sum of odd numbers (*2) is equal to that number squared

#

So that is why P(k) can be true or false

#

It's a claim

austere sparrow
#

yep, it's like a function returning a bool

#

it's not the function returning the sum from 1 to k

lament totem
#

What they say in text is different from the equation they show though which is weird

#

they say sum of odd numbers up to n, but then they go to 2n-1

#

Oh wait nvm

#

the first n odd numbers

austere sparrow
austere sparrow
fiery cosmos
#

right why then do they just drop the exponent

#

they finish by saying =(k+1)^2 which is P(k+1)

#

what gives?

#

another thing, what does the right arrow mean in set theory

opal oriole
fiery cosmos
#

i can see that P(n) = n^2 and that must have something to do with the answer to what youre pointing out but at this point i dont understand at all

opal oriole
fiery cosmos
#

i don't know. i'm trying to bridge the gap from these all being random symbols. to me it looks like logical gobbledegook

#

anyone understand this definition?

dark aurora
opal oriole
fiery cosmos
#

what does the arrow mean

#

i'm very familiar with functions both programming and math wise. not so much relations on sets

#

for example

opal oriole
#

"Goes to" / "maps to".

fiery cosmos
#

what is this about? is the relation R on the set A not A*A?

#

if it is A*A, why is 1,1 not in the set of ordered output pairs?

lament totem
#

A*A ?

#

relation on a set is literally just the arrows of each node to other node

#

so (1, 2) means there is an arrow from node 1 to node 2

#

and you can see (2, 2) as the arrow from 2 pointing to itself

#

@fiery cosmos

opal oriole
#

From the link provided:

lament totem
#

That is what the right arrow means for set theory yes, note that that is different from these relation arrows @fiery cosmos

#

every node can have any arrow to 0, 1 or multiple other nodes

fiery cosmos
#

can you make sense of this:
"if R is a relation from set A to itself, that is, if R is a subset of A^2 = A*A, then we say R is a relation on A"

lament totem
#

A*A probably means an arrow from each node to all other nodes

#

?

#

not sure on this

opal oriole
#

Do you mean the Cartesian product (usually "x" as the operator)? https://en.wikipedia.org/wiki/Cartesian_product

Cartesian product

In mathematics, specifically set theory, the Cartesian product of two sets A and B, denoted A × B, is the set of all ordered pairs (a, b) where a is in A and b is in B. In terms of set-builder notation, that is

    A
    ×
    B
    =
    {
    (
    a
    ,
    b
    )
    ∣
    a

...

fiery cosmos
#

no so A*A, if A = {1,2}, is = {(1,1),(1,2),(2,2),(2,1)}

lament totem
#

alright

#

so it makes sense that R is a subset of that then right?

fiery cosmos
lament totem
#

They say that they would explain it in chapter 8

#

so maybe it is best to wait for that

opal oriole
#

Perhaps using sets without numbers in them might make it make more sense for you?

fiery cosmos
#

"if R is a relation from set A to itself, that is, if R is a subset of A^2 = A*A, then we say R is a relation on A"

#

any ideas???

#

literally none of this makes sense to me. like i don't understand how this is going to be helpful in proving what they set out to prove or even what they're trying to say to begin with

#

especially with that function definition

opal oriole
#

A relation is generalization of a function.

#

And a function is the kind of function normally found in high school math, they might give a more advanced definition of it, but it's the same thing.

#

If you have something like ```py
def foo(x):
return x * x

#

You can give it whatever input you want, and it gives one output for that input.

#

If you list all the input output pairs, for example: ```
(1, 1)
(2, 4)
(3, 9)
...

#

Maybe you can see how it relates the inputs to the outputs.

#

In this case my input was the set {1, 2, 3}.

#

It relates two sets.

#

If we want to represent all possible input output pairs we could simply write it as AxB.

fiery cosmos
#

can we pick this statement apart:
"a function f: A -> B is a relation from A to B(e.g. a subset of A x B) such that each a in the set of A belongs to a unique ordered pair (a,b) in f"

opal oriole
#

"f is some function / relation that maps from A to B"

fiery cosmos
#

like that maps an element a in A to an element b in B?

opal oriole
fiery cosmos
#

ok so where does the (a,b) come in

opal oriole
#

From what I showed above for foo.

fiery cosmos
#

(a,b) "in" f

opal oriole
#

Yes, let me put it this way

#

Let's say foo only takes inputs 1, 2 and 3, and nothing else.

#

I can replace foo with a lookup table now.

#

First column is the input {1, 2, 3} and second is the output {1, 4, 9}.

fiery cosmos
#

ah this is why they are specifying that relations are only binary unless otherwise specified

opal oriole
#

So I can define foo as that table / set of ordered pairs.

fiery cosmos
#

bc we input a set of discrete elements (a) in set A and via the function map them to b elements of set B

opal oriole
#

Yes, but the cool thing is that it does not need to be finite, either of the sets.

#

For example, set of all real numbers to all real numbers.

fiery cosmos
#

n-ary relations involve ordered n-tuples

opal oriole
#

foo from above does not need only take 1, 2, 3.

#

I can give it any number.

fiery cosmos
#

text states "the term relation shall then mean binary relation unless otherwise stated or implied"

opal oriole
#

The table version would only take 1, 2, 3, unless I had an infinite table which I don't, so I would not use a table for that.

#

But the order pairs are still there implicitly.

#

The pop up as I compute them.

#

Like if I give 100 to foo it spits out whatever.

fiery cosmos
#

@opal oriole the explanation for how the function relates elements in one set to elements in another has helped. so relating a set to itself is simply A x A, = cartesian product = A^2

opal oriole
#

One important thing to note that makes it less general than any relationship, is that functions needs to map to exactly one thing. While for example R has 2 go to two different things.

fiery cosmos
#

but one thing could be an ordered pair

#

?]

#

e.g. 1 pair (1,2)

opal oriole
#

Like if I have (2, 3), and (2, 2). Then I can't draw a single arrow from 2 to the output for 2.

#

There are two arrows.

fiery cosmos
#

woah lost me now

opal oriole
fiery cosmos
# opal oriole Like if I give 100 to foo it spits out whatever.

since we're talking about relation, instead of using spitting out whatever, I'd suggest an example of

def does_relate(a, b):
  return a%b==0

like this stating that relation ship exists between a and b given that a belongs to A(domain) and b belongs to B(co-domain)

#

domain and codomain definitely are coming up in my book so i'll reread that section

fiery cosmos
#

aren't you mixing things up?

opal oriole
fiery cosmos
#

assuming relation is >= on N=>N (5,2) and (5,3) are both valid.

opal oriole
fiery cosmos
#

yeah so you mentioned function, saying that for same input, you can't expect 2 different outputs, but that is not always a case with relation.

opal oriole
#

Yes.

#

Relation is more general.

fiery cosmos
#

relation is just a subset of cartesian product of domain and codomain.

#

sounds like for functions domain = input and codomain = output

fiery cosmos
fiery cosmos
opal oriole
#

Function is relation, but may not be the other way around.

fiery cosmos
#

for relation?

fiery cosmos
#

function spits out in your terminology, while relation just exists or doesn't exist

opal oriole
opal oriole
#

Spits out is not exactly a mathematical term here. It's the analogy of a function being some machine you put something into and it gives out a value.

fiery cosmos
opal oriole
fiery cosmos
#

i understand probably 2% of what I read in the book, trying to change that

fiery cosmos
#

i'm typically very in tune with what they're saying and then abruptly have no idea

#

the question is how can I learn enough discrete math to learn enough algorithms to get a necessary B in grad school algos in the engineering school. currently the probability of that is 0%. trying to change that

#

so i got this book, Schaum's outlines Discrete Mathematics 3rd edition

#

I also have Discrete Mathematics and its applications 6th edition, but havent really used it

fiery cosmos
#

so are you stuck on relation?

fiery cosmos
#

and its okay to be confused.

#

none of it makes sense to me. just seems like a bunch of letters and symbols. i've been focusing on the first three chapters, set theory, relations, and functions and algorithms

fiery cosmos
#

and the operations on them? intersection, union and stuff!!!

lament totem
fiery cosmos
#

definitely not to any helpful extent. but in their essence yes. the set union is "or" and the set intersection is "and"

#

symbols can be confusing intially, but you get a hang of it.

#

which have logical equivalents

#

that is to a helpful extent, means given 2 sets you can do both operations of them right?

#

yeah seems easy

#

nice! so thats more than 0%.

#

well i haven't even gotten into the algos book yet 😅

#

i have 2 discrete math books to understand first

opal oriole
#

I am going to leave this book title here, you can skip to relevant parts in it (it covers a whole bunch of different mathematics in a very non-rigorous way): Concepts of Modern Mathematics by Ian Stewart. It may help you if you are lost, as a first pass to some topic (it's not in-depth / a "real" math text book).

fiery cosmos
#

ok thanks @opal oriole

fiery cosmos
#

i want to be ready for the fall semester.. so awhile

#

few months

#

THATS TIME!!

#

it'll be here before i know it

opal oriole
#

*Chapter 5 is "What is a Function?", so you have a whole chapter for that.

fiery cosmos
#

see if you're afraid of symbols thats understandable. I'd say make a note of every weirdo symbol, make a note of them, like

for all is reverse of A thingy.
belongs to is line on C thingy.
make a note of them with small example of sets, and you'll find them helpful.

#

i'm not concerned with the symbols so much as when i read a logical statement i don't even understand what is it they're trying to say, much less how it'll be helpful for proving something or computing something

#

like the relation A on A is like wtf??????

#

like my initial notes would be

union of 2 sets => members of both sets(non repeatitive):
symbol: A U B
(and may be a venn diagram)

intersection of 2 sets => members common in both sets:
symbol: A ^ B (reverse of U to be precise)
(and may be a venn diagram)
opal oriole
#

*Here the beginning of chapter 4 "The Language of Sets": ```
"Almost any book on 'modern mathematics' talks about sets, and is liberally bespattered with strange symbols ..."

fiery cosmos
#

dang i need to get that book. i'll check amazon

fiery cosmos
opal oriole
#

It also tells you purpose, why you care about sets.

fiery cosmos
#

@opal oriole

opal oriole
#

It also has a programming section, but it's very old. Still can be useful though.

fiery cosmos
#

So say for

A = {1,2,3}

we have relation

R:A=>A (you can read like relation from A to A)
R = ((1,1), (1,2), (2,3))

first, this is relation because this IS subset of cartesian product of AxA

#

is that understandable?

#

what about (2,2),(3,2),(3,3)?

#

(1,3)?

fiery cosmos
fiery cosmos
#

oh ok ok

#

you can invent any supposed R and check if it exists

opal oriole
fiery cosmos
#

wait but @fiery cosmos

#

the cartesian product of A = {1,2,3}, let me see if i can compute it

fiery cosmos
#

= {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}?

fiery cosmos
fiery cosmos
#

ok

#

glad i at least understand that. but in the cartesian product A x B the output is the same (set of ordered pairs) and so A x B =/= B x A

fiery cosmos
#

so no, they are not same.

#

so in computing the output, the matrix you set up to solve, how does one know to put A as the rows or columns?

#

i think in the book it states to put A as the rows..

fiery cosmos
#

i would not think of it as a table.

#

ok fair enough, but so to compute the output above i used a series of rows and columns and computed accordingly

#

AxB = {(a,b) \forall a in A \forall b in B}

fiery cosmos
#

.latex

$AxB = \{(a,b) \forall a \in A \forall b \in B\}$
#

eh

#

@fiery cosmos I need to go eat dinner but I look forward to speaking with you more in the future thank you

fiery cosmos
#

thank you!!

#

but yeah, I may not be able to answer now soon since its 3 39 AM.

#

woah.. where are you? get some sleep!!

#

India. yeah. I was coding some stuff.

#

thats cool i'm going to go eat some sambar rice

#

have fun!

#

no j/k but i do have some friends from south india 😉

#

haha alr, have fun and take it easy, math is fun!

quasi sapphire
#

Can anybody spot what's wrong with my merge sort? I'm new to recursion. The code runs but the array is ordered incorrectly ```py
def mergesort(array):
if len(array) > 1:
mid = len(array) // 2
l = array[:mid]
r = array[mid:]
print(l)
print(r)
mergesort(l)
mergesort(r)

    merged_array = []
    i = j = k = 0

    while len(l) > i and len(r) > j:
        if l[i] < r[j]:
            merged_array.append(l[i])
            i += 1

        else:
            merged_array.append(r[j])
            j += 1

    while len(l) > i:
        merged_array.append(l[i])
        i += 1

    while len(r) > j:
        merged_array.append(r[j])
        j += 1

    return merged_array

mylist = [1, 8, 7, 4, 10, 2]
t = mergesort(mylist)
print(f"{t}.")```

#

Thanks

fleet wind
#

hi. I'm not sure where I should ask this, but I'm trying to figure out how to shift an item n spaces in an array by its current index. I was challenged with taking a string

alphabet = "abcdefghijklmnopqrstuvwxyz"
``` and shifting each letter by it's current index. A = 1, B = 2, C = 3 and so on where A is the letter of current iteration, and 1 is the number to shift by. I have been trying to figure this out for the past hour trying everything I can think of, plus everything I could find on stack overflow/google with trying to solve this. Help please. Thanks in advance!
stark stone
#

off the top of my head, wouldn't making a list of empty strings twice as long and making every other entry a letter do it?

#

['', 'a', '', 'b', '', 'c' ... ]

fiery cosmos
#

When I do

for i in range(n):
  if i in hashmap:
    print('python')

will my in lookup be O(1) or O(n)?

grizzled schooner
#

it can be O(n) worst case because of hash collisions, but generally O(1)

agile sundial
#

O(n) can be assumed to never happen

fiery cosmos
#

According to the documentation the worst case is O(n)

agile sundial
#

the average and best case is O(1)

#

the only time O(n) comes up in python is if your input is malicious

#

it's possible with ints, but again, your input needs to be malicious

haughty mountain
#

so if your user can control the input to your hash table, be vary

dapper sapphire
umbral wagon
#

hey i'm doing a backtracking question and i'm kind of confused on how state is passed between recursive calls
the question is asking to print all the paths of a ternary tree

#

why is this code wrong?

    def dfs(node, cur_path, paths):
        cur_path.append(str(node.val))
        if all(c is None for c in node.children):
            paths.append('->'.join(cur_path))
            return
        for child in node.children:
            if child is not None:
                dfs(child, cur_path, paths)
   
    paths = []
    if root:
        dfs(root, [], paths)
    return paths```
#

this is the correct code:

    def dfs(node, cur_path, paths):
        if all(c is None for c in node.children):
            paths.append('->'.join(cur_path) + '->' + str(node.val))
            return
        for child in node.children:
            if child is not None:
                dfs(child, cur_path + [str(node.val)], paths)
   
    paths = []
    if root:
        dfs(root, [], paths)
    return paths```
#

cur_path is the path from root to the current node

#

why can't i append the value of the current node at the beginning, and must instead do it while i call the next recursive call?

scenic schooner
#

your function returns ['node.val'] while the solution wants ['->node.val']

fiery cosmos
#

anyone know good resources to learn asymptotic analysis

violet eagle
#

why is the behaviour of [dict()]*9 different from [dict() for i in range(9)]

ps. the behaviour seems to be same if dict() is replaced by a non container like an integer 0

agile sundial
#

doing list * int copies the references of the things inside the list, it doesn't make new things or copy what the references are referencing

#

you don't see a difference with ints because ints are immutable, so it doesn't really matter if they're all the same reference

violet eagle
violet eagle
violet eagle
agile sundial
#

no, since with the list comp, you're putting a new dict in on each iteration

#

!e
you can check with id,

A = [dict()] * 9
print(" ".join(map(str, map(id, A))))

B = [dict() for i in range(9)]
print(" ".join(map(str, map(id, B))))
halcyon plankBOT
#

@agile sundial :white_check_mark: Your eval job has completed with return code 0.

001 | 140338032649856 140338032649856 140338032649856 140338032649856 140338032649856 140338032649856 140338032649856 140338032649856 140338032649856
002 | 140338032650944 140338032651008 140338032651072 140338032651264 140338032651328 140338032651456 140338032651520 140338032651584 140338032650368
agile sundial
#

they're all the same in the first one, so they're the same object

violet eagle
#

wow thanks that clears stuff out

#

ok also in the case of non containers, like lets say an int 0, the reference remains the same in list comp or mult, but since ints are immutable they are updated separately?

#

i cant seem to get my head around how immutability changes the behaviour of updates for ints

vocal gorge
agile sundial
#

it doesn't change the behavior, it's just the result of that behavior that changes

#

if it's immutable, then it doesn't matter if you have 2 different 4s, or the same 4

vocal gorge
#

I guess one way to think of it is that x += b is a fancy operation that, depending on whether the object x is pointing to is mutable, either changes the object itself, or is equivalent to x = x + b (which replaces x with a new object).

(This applies even when x is a fancy name like a[5] (an element of a list/value of a dict))

violet eagle
#

Thanks, it makes a lot of sense now 😄

fiery cosmos
violet eagle
fiery cosmos
#

DSA?

violet eagle
#

Data Structures and Algorithms

fiery cosmos
#

ok thanks

tardy helm
#

for some reason this code isn't working for 10 and above

unknown.png
#

but it is sorting for values below 10

agile sundial
#

can you copy and paste the code

#

!code

halcyon plankBOT
#

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

tardy helm
# 
def insertionSort(arr):
    # for i in range(1, len(arr)):
    #     val = arr[i]
    #     index = i - 1
    #     while index >= 0 and val > arr[index]:
    #         arr[index + 1] = arr[index]
    #         index -= 1
        
    #     arr[index + 1] = val
    for i in range(1, len(arr)):
 
        key = arr[i]
 
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while (j >= 0 and key < arr[j]) :
                arr[j + 1] = arr[j]
                j -= 1
        arr[j + 1] = key
    return arr


size = (int(input("Enter size og the array: ")))
arr = []
for i in range(size):
    arr.append(input("Enter the value: "))
print(arr)
#print(bubbleSort(arr, size))

print(insertionSort(arr))
agile sundial
#

hm

tardy helm
#

i debugged it as well and it goes only once in the while loop and then never if greater than 10 values

tardy helm
agile sundial
#

ah

agile sundial
tardy helm
agile sundial
#

but your algorithm is also deleting some elements

tardy helm
#

is it?

tardy helm
agile sundial
fiery cosmos
#

when referring to decision tree learning, are those different trees than the binary tree data structure?

#

nvm, seems like they are

#

(are different)

glad vale
#

Hello! I have another not funny problem but now I don't have any idea that isn't just stupid brute force.

In a country, there are cities connected by a network of one-way pipelines, each with a specific capacity. The oil fields have been depleted, but an inexhaustible source of a new type of fuel has been discovered in one of the cities. It was decided to **build two factories** in different cities to purify the new fuel. **For some reason, these factories cannot be located in a city
where the new fuel was discovered** and the new fuel will be transported through the existing pipeline network. Indicate the two cities where the factories should be built to maximize the production of refined fuel.
Please implement the function maxflow(G,s) that for an existing pipeline network G and a city in which deposit s was discovered, returns the maximum total throughput to the two cities in which factories should be built. The cities are numbered consecutively with the numbers 0, 1, 2, ... The pipeline network is described by a list of triples: **(the city where the pipeline starts, the city where the pipeline ends, pipeline capacity)**

Example:
G = [(0,1,7),(0,3,3),(1,3,4),(1,4,6),(2,0,9),(2,3,7),(2,5,9),(3,4,9),(3,6,2),(5,3,3),(5,6,4),(6,4,8)]
s = 2

The result is: 25 (city 4 and 5)

#

Another example but did in online graph maker

unknown.png
lucid oyster
#

whats Digital Signature Algorithm ?

dark aurora
#

What is map() time complexity?

half lotus
#

Depends on which function is being mapped

#

But map on its own is just O(n) I believe

dark aurora
half lotus
#

I suppose int's time complexity is linear based on the length of the string

#

So if you have a list of n strings of length k, map(int, lst) is O(n * k) but I am taking a guess on int's time complexity I haven't seen its actual implementation.

dark aurora
half lotus
#

That would have to be something that maps in parallel

#

Actually not even

#

The problem is that you give it a list and it has to apply the function to each element, so if you have a list of length n it needs to call the function n times

dark aurora
half lotus
#

Parallelism doesn't change the complexity anyway, but if you're looking for some sort of performance increase, look into that.

dark aurora
fiery cosmos
#

hi i wanna make a program in python that calculated the approximation of (for example ln2) using the trapezoidal method

#

🙏

fiery cosmos
#

does breath first search on trees has pre-order, post-order, in-order versions like depth first search does?

torpid cedar
#

anyone knowledgeable in support, lift, and confidence for comparisons? Need to make a function to compare movies given user reviews:

movies = {'User_1': {'Movie_55': 5,
  'Movie_203': 4,
  'Movie_183': 5,
  'Movie_150': 5,
  'Movie_68': 4,
  'Movie_201': 3}, User_2: {'Movie_55': 1,
  'Movie_203': 2,
  'Movie_183': 3,
  'Movie_150': 5,
  'Movie_68': 4,
  'Movie_201': 3}}```
spare olive
#

Trying to solve minimum span tree on a graph of nodes. What's making it tricky-different in this case, the edges can only travel strait horizontal or vertically. IE if 0,0 and 1,1 are the closest points that should be connected, the edge that connect them have to first go to 0,1 or 1,0 on its way.

First idea was to create all the needed virtual points where things can intersect (like 0,1 and 1,0), But not sure how to setup MST algorithm to allow the use of those points without it routing to all of those as if they were required targets.

Other idea is to compute the weighs as if it was taking the long way without the points. IE 0,0 to 1,1 = distance of 2, without actually keeping track that it goes 0,0 to 0,1 -> then 0,1 to 1,1. Problem here is then these partial edges cannot be reused - But they should be. IE if we have edge from 0,0 to 0,1 already - then we should be able to get from 0,0 to 0,3 by only having to add 2 to the overall MST, not 3. By not keeping track of the 'half' edges the overall solution won't work.

quasi oracle
halcyon plankBOT
#

Hey @spare olive!

It looks like you tried to attach file type(s) that we do not allow (). We currently allow the following file types: .gif, .jpg, .jpeg, .mov, .mp4, .mpg, .png, .mp3, .wav, .ogg, .webm, .webp, .flac, .m4a, .csv, .json.

Feel free to ask in #community-meta if you think this is a mistake.

quasi oracle
#

!paste maybe you can post it here

halcyon plankBOT
#

Pasting large amounts of code

If your code is too long to fit in a codeblock in discord, you can paste your code here:
https://paste.pythondiscord.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

spare olive
quasi oracle
#

How are the edges defined? is it some sort of a clique?

spare olive
#

There are no edges. I am generating a potential edge list using a list of X and Y from the targets. If targets = [
(50, 30),
(40, 30),
(30, 20),
(00, 50),
(20, 10)
]
Then I sort and loop X's = [0, 20, 30, 40, 50]
Then Y's = [10, 20, 30, 50]

Then I made a nested loop that uses those to build edges. IE to build all the Horizontal edges, start with first Y of 10 and make edge from (0,10 to 20,10) (20,10 to 30,10) (40,10 to 50,10) etc
Then I do another loop to build all Vertical edges - Start with first X, and loop Y's (0, 10 to 0,20) (0,20 to 0,30) etc.

In the end MST incorrectly connects everything, making some optional is what i don't understand

fiery cosmos
#

hey all,
trying to understand the concept of inorder successor of a binary search tree. so far I have:
-if node has right subtree, its inorder successor is the left most node of the right subtree
-if node has no right subtree, the inorder successor is the parent node for which the given node would be in the parents left subtree

#

am i missing anything?

spare olive
fiery cosmos
#

anyone here familiar with asymptotic analysis?

#

(of algos)

quasi oracle
# spare olive Top one would be 5 'target' points. Bottom image - a MST solution that involved ...

Thinking out loud here. If we take Prim's algorithm as a basis, we can treat this as a clique, and generate each time the next edge with the smallest weight (if you do it smartly there might be a way to avoid having to actually generate all edges, focusing on a subset of candidates). Whenever you create a virtual point, you'll have to update the weights of the existing edges to account for the existence of this new vertex. The challenge will be figuring out which virtual vertex needs to be created (since if you're going from point A to point B you have two ways of going parallel to the axes). If you don't pick the right virtual point you won't get an optimal solution, but it should at least be better than the solution you have below.

quasi oracle
spare olive
fiery cosmos
#

i'm just asking generally bc this is my syllabus:

#

looks like it is mostly asymptotics

quasi oracle
#

I'm guessing you'll be learning those algorithms and comparing between them with asymptotic analysis

fiery cosmos
#

yeah for sure. right now i'm learning the data structures i'm not yet familiar with (binary search trees, red black trees, others) but I'd like to start with the "basics of asymptotic notation and analysis" bullet as well

quasi oracle
#

yeah you should start with that actually

#

It will give you context on when it's best to use one data structure over another, and why one even exists

fiery cosmos
#

i bounce around a lot. i have 3 different books i've been learning data structures, big O, the algos themselves from. i just learned that big O was introduced in 1892 🤯

#

the implementation of a binary tree is analogous to that of a linked list (at least the way it is structured in memory). i don't think in one million years i'd sit around and figure out that such a data structure is that much more efficient than implementing some simpler structure on a PC, but at least i know what they're talking about now (eg why it exists) 😅

quasi oracle
#

What do you think is a simpler structure? 😄
To answer that question you first need a problem you need to solve

fiery cosmos
#

my lack of mathematical intuition is such that i'd think operations on a binary tree are more steps and thus having greater runtime complexity than say, searching through an array for some element. clearly that is not the case

quasi oracle
#

yeah, a BST, if balanced, allows you to search for values in time comparable to binary search in a flat array

spare olive
# quasi oracle Thinking out loud here. If we take Prim's algorithm as a basis, we can treat thi...

Apparently what I have is the node-weighted Steiner tree problem. https://stackoverflow.com/questions/10056212/minimum-spanning-tree-between-a-start-location-and-a-set-of-required-nodes

Stack Overflow
Minimum spanning tree between a start location and a set of require...

I'm trying to determine the optimal search case to compare to a search algorithm I have written.

I have a set of nodes marked "required" and a node marked "start", the rest are marked "optional"...

quasi oracle
fiery cosmos
#

694 problems to practice in algorithms with implementations in python

signal knot
#

Is there any advantage of implementing a stack using a linked list vs an array/list?

agile sundial
#

no, unless you're in a super memory constrained environment where you can't amortize properly

lean dome
#

I'd expect that on such memory constrained environments, the overhead of the linked list would be higher than the overhead of the array. A doubly linked list's memory overhead is 2 pointers per element, after all

agile sundial
#

hmm, you can lower that with the trick python's deque uses, though 🤔. that reduces the overhead to 2 pointers per some constant number of elements

lean dome
#

sure, but then you're back to using an array/list

#

but yeah, deques are way better for implementing queues or stacks than linked lists are.

agile sundial
#

an array, you mean?

lean dome
#

no, I meant deques

#

I was saying that your point is correct, and a doubly linked list of arrays (a deque) is a much better data structure for implementing a queue or a stack than a doubly linked list of elements is

agile sundial
#

i see. i was confused because i'm used to deque as an adt, like queues or stacks.

#

since you can also make a deque with a circular buffer

lean dome
#

right, Rust does it that way. C++, Python, and Java all implement their deque with the doubly linked list of chunks, so that's what comes to mind first for me

haughty mountain
# spare olive Apparently what I have is the node-weighted Steiner tree problem. https://sta...

in paricular you have this problem https://en.wikipedia.org/wiki/Rectilinear_Steiner_tree

Rectilinear Steiner tree

The rectilinear Steiner tree problem, minimum rectilinear Steiner tree problem (MRST), or rectilinear Steiner minimum tree problem (RSMT) is a variant of the geometric Steiner tree problem in the plane, in which the Euclidean distance is replaced with the rectilinear distance. The problem may be formally stated as follows: given n points in the ...

tacit drift
#

is this the correct way to find the complexity? written in purple
Image

haughty mountain
#

I think the complexity should be O(n log n)

#

it does work on a range of size d - s, and then proceeds to call recursively twice for ranges of size (d - s)/2

#

in short the recurrence is

T(n) = n + 2 T(n / 2)
#

I could look up the more general formula for getting what that boils down to, but this is the same thing as what quicksort would do for perfect choice of pivot

#

so O(n log n)

tacit drift
haughty mountain
#

I have no clue what is happening after the 3rd line on the right

#

simple derivation of the correct complexity, starting from T(n) = 2 T(n / 2) + n

unknown.png
tacit drift
#

i think you're right

#

seems more logical than my solution

#

thanks

vestal forum
#

Hello peeps, I need help with implementing a tree traversal that deletes odd valued nodes from a binary search tree, how would i go about that?

haughty mountain
agile sundial
#

as long as you have a working delete function ig

haughty mountain
#

what delete function? just don't include the odd values in the new tree

agile sundial
#

ah, that is a better way

vestal forum
haughty mountain
#

you can easily do O(1) work per node in the traversal

toxic ivy
#

Hi guys what Certifications are needed for IT industry

#

I am B. E PASSOUT 2021

haughty mountain
#

so yes, I guess the delete operation is the important part

spare olive
# haughty mountain in paricular you have this problem https://en.wikipedia.org/wiki/Rectilinear_Ste...

Thank you didn't find that on my own!

Was writing a general steiner tree solver last night that added one target point at a time as an end point and solve with dijkstra's, starting from everything else I already have in my path. (was someone's shared pseudocode) Pretty sure this still only gives a 'close enough' answer and not actual minimum but hopefully good enough for what I actually need it for.

After looking at that Rectilinear Steiner tree wiki article, maybe I could improve results by starting with some single trunk trees between subsets. I'm using this for pipe/plumbing/wire routing inside buildings - mainly for estimating pricing.

fiery cosmos
#

sharing a small victory here, i implemented a working insertion sort in python using no outside resources, only reading the CLRS book 🙂

fiery cosmos
#

hello, i am currently working using the CLRS text and writing from the various algorithmic pseudocodes. i do not understand which expression to use for their "sentinel card" in their mergesort algo, that is, when they set expressions equal to infinity in their pseudocode.

#

i'm thinking it can be any special value like none or null but perhaps it must be infinity so that the expressions are always set to a value larger than an arbitrarily large number passed into the algorithm

agile sundial
#

do you understand why they use infinity?

fiery cosmos
#

so that whenever that "card" (in their analogy) is exposed, it cannot be the smaller of the two card values being compared

agile sundial
#

exactly

fiery cosmos
#

thats fair i just can't think how i'd model infinity in a real implementation

#

i mean trivially one could always say somevalue = somevalue+=1

#

in aiming for the same effect

agile sundial
#

the float spec defines how to represent infinity in a float

fiery cosmos
#

val = float('inf') ducky_ninja

agile sundial
#

it's special cased to be greater than all numbers

fiery cosmos
#

also float('-inf') is a thing though same as -float('inf')

#

so i know float is a reserved keyword, its just a special version of the keyword float?

#

float is the builtin to convert things to float (technically a class, and you can reassign it, just bad practice), that is a special input though, yeah

#

hm ok. in the pseudocode they are setting array[someslicing] = ∞

#

so i can effectively just set that = float(inf)?

#

sure

#

ok!

#

great to know, thanks

#

or maybe = [float(inf)] * slicelength if they mean assigning a whole slice

#

(though that might be weird in practice pithink could also loop and assign and whatnot)

#

yeah its a bit esoteric

opal oriole
# 
import math
x = math.inf
``` Is another option.
fiery cosmos
#

thank you, one of my questions was going to be about if i would need to import anything

#

what is the terminology, one is importing, a library?

#

a module?

#

nvm googled, it is a module.

opal oriole
#

I think both are understood, but module is more precise.

fiery cosmos
#

yeah, module/package/library all kinda interchangeable (if imprecise)

#

good to know

fiery cosmos
#

as much as i disliked it several months back, asymptotics are actually quite interesting

dark aurora
#

What is the time complexity of list(i)

shut breach
#

O(n)

hoary kayak
#

Hi guys

dark aurora
haughty mountain
#

they have the exact same time complexity

#

write whatever is more readable

#

if you care about that level of performance you're using the wrong language

fiery cosmos
#

What would be the overall time complexity for the equation below:
O((2^n - 1)^2)

haughty mountain
#

that simplified should be O(2^(2n))

vocal gorge
# 
(2^n - 1)^2 = (2^(2n) - 2^(n+1) + 1), and O(2^(2n)) consumes the other two as clearly smaller
bold pelican
fiery cosmos
#

What does the line below do?

string = (str)(A)
jolly mortar
jolly mortar
fiery cosmos
jolly mortar
fiery cosmos
agile sundial
#

no, 2^2n is 2^n times larger than 2^n, which is more than a constant facttor