algos-and-data-structs

[fiery cosmos]

idk like as an exemple si (a != b) alors etc. finsi

[half lotus]

Sure, != is a more common syntax for "not equal"

[idle pier]

hello folks I have a question
lets say we have an inter array nums = [1,2,3]
whats the difference between nums and nums[:]?

[half lotus]

The latter creates a copy of the list

[idle pier]

huh I did not know that
thanks

[zinc oriole]

Hi everyone, i want to learn data structure but, it's hard for me, there has an course for people like me?

[fiery cosmos]

The pins have some resources (though they may be intermediate )

[agile sundial]

data structures is intrinsically not a beginner topic though. intermediate is kinda the easiest you'll get

[fiery cosmos]

Can someone help verify my math here? Problem is: ```
Given some positive real number L find positive integers a and b
such that a/b is as close to L as possible, and b <= B where B is a given positive integer

I'm thinking ```py
a1 = round(L*B)
b1 = B
g = gcd(a1,b1)

a = a1//g
b = b1//g

Kinda using the idea that (I think) in general x rounded the nearest y is y*round(x/y) where here x is L and y is 1/B

Basically rounding L to 1/Bs

[vocal gorge]

i've heard of this, hold on

https://wikipedia.org/wiki/Diophantine_approximation?lang=en

I remember finding these via continued fractions

yeah, e.g. here:
https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations

One can choose to define a best rational approximation to a real number x as a rational number n/d, d > 0, that is closer to x than any approximation with a smaller or equal denominator.
This seems to be what you want.

[fiery cosmos]

But I don't have a continued fraction this feels too complicated for what I'm going for

[vocal gorge]

you can calculate the continued fraction from the real
https://en.wikipedia.org/wiki/Continued_fraction#Calculating_continued_fraction_representations

[fiery cosmos]

Why can't this work? Round L to the nearest 1/Bth and then get the fraction round(L*B)/B in lowest terms

When L = .6 and B = 3 it gives a/b = 2/3, but B = 10 gives a/b = 3/5 (.6 exact). I feel like it already works how I want

I guess lowest terms doesn't really matter in the question. Can consider that separately

[vocal gorge]

The issue here is that I don't think the best fraction necessarily has a denominator of B.

[fiery cosmos]

Oh yeah

hmm, well I think I'm ok with the approximation

interesting

[vocal gorge]

!e

def to_continued_fraction(x):
    while True:
        div, mod = divmod(x, 1)
        yield round(div)
        if mod == 0:
            break
        x = 1/mod
def to_fraction(lst):
    from fractions import Fraction as F
    res = F(lst[-1])
    for el in lst[-2::-1]:
        res = el+1/res
    return res
def to_best_fractions(x):
    lst = []
    for c in to_continued_fraction(x):
        lst.append(c)
        cur = to_fraction(lst)
        yield cur
from math import pi
for i,x in enumerate(to_best_fractions(pi)):
    print(x)
    if i==20: break

[halcyon plank]

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

001 | 3
002 | 22/7
003 | 333/106
004 | 355/113
005 | 103993/33102
006 | 104348/33215
007 | 208341/66317
008 | 312689/99532
009 | 833719/265381
010 | 1146408/364913
011 | 4272943/1360120
... (truncated - too many lines)

Full output: https://paste.pythondiscord.com/wuritemise.txt?noredirect

[vocal gorge]

check this out

this one isn't quite right though, because for truly optimal results you need to search a handful of nearby ones and determine whether they're the best by some annoying rule that compares to last one (https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations)

[fiery cosmos]

Yeah, I see how like with L = .9 and B = 11 my way would choose 10/11 = 0.909090... when it could simply be 9/10 or even 8/9 is closer

[vocal gorge]

yup

[fiery cosmos]

though yours get scary quick 👀 8/9 9/10 2533274790395912/2814749767106569 I assume that's float quirkiness

[vocal gorge]

you could actually solve it the dumb way in O(B) - consider all F(round(L*n),n), n=1 to B and take the closest one

[fiery cosmos]

yeah

[vocal gorge]

hmm, yeah, need to replace ==0 with something like abs<1e-9 or whatever

oh right, there's math.isclose

[jolly mortar]

this is nice

[vocal gorge]

!e

def to_continued_fraction(x):
    while True:
        div, mod = divmod(x, 1)
        yield round(div)
        if abs(mod)<1e-6:
            break
        x = 1/mod


def to_fraction(lst):
    from fractions import Fraction as F
    res = F(lst[-1])
    for el in lst[-2::-1]:
        res = el+1/res
    return res


def to_best_fractions(x):
    lst = []
    for c in to_continued_fraction(x):
        lst.append(c)
        cur = to_fraction(lst)
        yield cur
t = 0.9
for i,x in enumerate(to_best_fractions(t)):
    delta = float(x)/t-1
    print(f"{x}, {delta:.3e}")
    if i==20: break

[halcyon plank]

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

001 | 0, -1.000e+00
002 | 1, 1.111e-01
003 | 8/9, -1.235e-02
004 | 9/10, 0.000e+00

[vocal gorge]

there

[fiery cosmos]

Well I'll try various ways and see what works best in the end. Thank you for the excellent help ConfusedReptile you are a star 🌟

[haughty mountain]

@fiery cosmos @vocal gorge the (truncated) continued fractions gives you "convergents" which are indeed the best approximations up to some denominator, but as you've seen they are not the only ones

for a complete picture you also want to look at "semi-convergents"

https://en.wikipedia.org/wiki/Continued_fraction#Semiconvergents

for context, I had to do a deep dive into this a few years back in a programming contest https://www.hackerrank.com/challenges/minimal-distance-to-pi/problem

tl;dr: find the closest fraction to pi with a denominator in the range [l, r]

[haughty mountain]

in your case you have an easier task than the one I had in the contest problem

you need to find the largest convergent (truncated continued fraction) and then search in continued fractions until you hit the limit (rather, just find the largest one in O(1), it's just linear interpolation)

if you just want to do it, and don't care about doing it yourself there is stuff in fractions.Fraction for exactly your task

!d fractions.Fraction.limit_denominator

[halcyon plank]

fractions.Fraction.limit\_denominator

limit_denominator(max_denominator=1000000)```
Finds and returns the closest [`Fraction`](https://docs.python.org/3/library/fractions.html#fractions.Fraction "fractions.Fraction") to `self` that has denominator at most max\_denominator. This method is useful for finding rational approximations to a given floating-point number:

```py
>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)
```  or for recovering a rational number that’s represented as a float...

[haughty mountain]

maybe the source code is interesting, the bulk of the work is to find the closest continued fractions
https://github.com/python/cpython/blob/420f0df862cf2290ad6a5e25286925ad197c9ef5/Lib/fractions.py#L202

[halcyon plank]

Lib/fractions.py line 202

def limit_denominator(self, max_denominator=1000000):```

[fiery cosmos]

Oh dang, I would use that but actually this is to be implemented in JS xD

[haughty mountain]

if so look at the python source and port that

[haughty mountain]

the details are what is on the wiki page I linked, you have two adjacent convergents and you find the biggest allowed semiconvergent

and as said, the main complicated logic is to generate the continued fraction above and below (at the same time)

Oh yeah, the problem I shared has weird special cases, e.g. you can be asked about large intervals that don't contain and convergent or semiconvergents

that was painful, I remember reading various research papers about it when doing the task

this was the contest https://www.hackerrank.com/contests/w29/challenges

guess which task ended up hardest

[runic tinsel]

megaprime?

i mean it shows that pi was the hardest for everyone, but i assume you mean for you

[cobalt lotus]

hey y'all so im trying to follow a blockchain tutorial but i came across this problem
the video is in python 2 but im using python 3 and anyone has an idea how i can replicate this? (the code line is supposed to get the previous list element?)

[cobalt lotus]

Forgot to say, its saying KeyError: -1

[agile sundial]

is self.chain supposed to be a list

[cobalt lotus]

i just checked and i set it to a dict

ah, stupid me

thanks for the help

[raven kraken]

Hey everyone, I am trying to understand this recursive solution for below question and am unable to understand how recursion is working over this python code. Can anyone help me understand it ?

  def numTilePossibilities(self, tiles: str) -> int:
        letter_count = collections.Counter(tiles)

        def dfs():
            count = 0
            for tile in letter_count:
                if letter_count[tile] == 0:
                    continue
                letter_count[tile] -= 1
                count += dfs() + 1 
                letter_count[tile] += 1
            return count   
        return dfs()

To be exact I didn't understood this part -

  letter_count[tile] -= 1
  count += dfs() + 1 
  letter_count[tile] += 1

[haughty mountain]

nah, pi was by far the hardest one

[icy geode]

Anyone know how to get a point between 2 points on a 2D plane but with a minimal distance of point 2.

Im not pretty good at math, got the equation for the rect line, but Idk where I should go now...

[gaunt current]

Do you have a more elegant/better/smarter way of doing this or any feed back?

""" 
Quesitons:

Permutation: Given two strings, write a method to decide if one is a permutation of the other. 


Source: Cracking the coding interview
 """


def is_permutation(str1, str2):
    if len(str1) != len(str2):
        return False

    dict1 = map_dict(str1)
    dict2 = map_dict(str2)

    return dict1 == dict2


def map_dict(str):
    char_dict = {}
    for char in str:
        if char in char_dict:
            char_dict[char] = char_dict[char] + 1
        else:
            char_dict[char] = 1
    return char_dict


print(is_permutation('hi', 'ih'))

[icy geode]

distance is not a constant

[haughty mountain]

map_dict can be replaced by Counter from the standard collections module

def is_permutation(x, y):
  return Counter(x) == Counter(y)

[halcyon plank]

Hey @umbral gulch!

It looks like you tried to attach a Python file - please use a code-pasting service such as https://paste.pythondiscord.com

[nimble lance]

myText = "hello"
print(myText)

...
>> myText = "hi"
>> run script1 with changing myText var
...

how can i run the second script in the first script with changing the value of myText variable ?

[jolly mortar]

what about something like this instead:

# script1.py
def my_function(my_text):
    print(my_text)

# script2.py
from script1 import my_function
my_function("hi")

[fiery cosmos]

hey y'all,
for the master's theorum in CLRS, does the recurrence you are solving have to be in the exact form as in the formula?

in other words, the master theorem is:
T(n) = aT(n/b) + f(n)

so if i have something in the form T(n) = aT(n/b+1)+n, i'll need to manipulate the +1 expression to be in the proper form first before drawing conclusions, is that correct?

[haughty mountain]

for large n your added 1 won't matter

[fiery cosmos]

also, what happens if i get my eq in the form of something like T((n/1)+2)+n+3

can f(n) (of master's theorem) be = n+3?

[haughty mountain]

again, the +3 won't matter for large n

only the asymptotics of f(n) matters

[fiery cosmos]

so when plugging into the master's theorem cases, how would i eval when my f(n) = n+3

[haughty mountain]

for the recursive part, I think additive constants don't matter, but multip;icative ones do

[fiery cosmos]

i just mean i cannot see how to plug it into the formula for evaluation. here are the 3 cases:

[haughty mountain]

the conditions only consider the asymptotics of f(n)

[fiery cosmos]

so would it be like case 1 looks like:
n+3 = O(n+3^log_b(a) )?

[haughty mountain]

f(n) = n+3 is O(n)

[fiery cosmos]

it would depend on the a and b though?

and apparently epsilon..

[haughty mountain]

well Θ(n) even

[haughty mountain]

no?

the asymptotics of f(n) is one thing

[fiery cosmos]

yeah thats what the master's theorum is all about, comparing the asymptotics of the recursion to that of the f(n) term

[haughty mountain]

you are comparing it with other stuff

this is kinda why I'm a bit iffy about writing = when it comes to O notation

it's a bit misleading

[fiery cosmos]

whichever grows larger it doesn't really mean =

it is taken to mean a given function is in the set of functions which bound that term or expression

the book it pretty good about making that distinction

[haughty mountain]

right

[fiery cosmos]

anyway, i'm struggling to know how to plug the numbers in or how far along i need to manipulate a given equation to get it to look exactly like the form of the master theorem

[haughty mountain]

as said, only the asymptotics of f(n) matters

you would ask which of the three buckets f(n) = n+3 falls into

which bucket depends on the a and b constants

but the +3 will never matter

because what is in the conditions are all asymptotic bounds

O, Θ and Ω

[fiery cosmos]

so it would only matter if say, it's 2n,3n, etc?

it has to matter in some sense otherwise all the eqs would end up the same

[haughty mountain]

it doesn't matter for f(n)

it would matter if it was something like n²

or a constant

the multiplicative constant matters for the recursive call

[fiery cosmos]

ok so in this case i've worked it to be like 3T((n/1)+2)+n+3

so using the masters theorem i get something like a=3 b=1, f(n) = n+3 and n =1?

[haughty mountain]

it will behave the same as 3T(n/1) + n

[fiery cosmos]

but then on the left must i input n+3?

like im still trying to plug the numbers into the eqs

[haughty mountain]

though that particular recursion won't give anything useful, it diverges

[haughty mountain]

it's not an equation on the left in the master theorem

as you said it's really a set membership

[fiery cosmos]

maybe case 1 would look like n+3 = O(n^log1(3-E)?

oh you're just looking at how the f(n) term is bounded

ohhh

[haughty mountain]

yes

[fiery cosmos]

ok so lms

so in my hw i had T(n) = 3T((n/3)+1)+n

and apparently it's a no-no to use in the form as is

so the hint was "use a substitution to handle the +1 term"

so the hint i was given was let m = n+3, substitute in for n and solve

so i think that evaluates to 3T((n/1+2)+n+3

which doesn't get me any closer to the form of the eq i want it in..

why can't we use the form as is???

as you said, that +1 would never change the asymptotics of it all

i have wasted so much time this summer on these petty details because i have zero access to the instructor, its super lame. i don't even learn i end up moving on to something else and then coming back and still not knowing what im doing

[haughty mountain]

n = m - 3
T(n) = 3T((n/3)+1)+n
T(m - 3) = 3T((m - 3)/3 + 1) + m - 3
         = 3T(m/3) + m - 3

[fiery cosmos]

wat

she said let m = n+3

[haughty mountain]

same thing as n = m - 3

just rearranged

[fiery cosmos]

well i need an n at the end to work with

[haughty mountain]

I guess the general substitution would be

n = m - bc
T(n) = aT(n/b + c) + f(n)
T(m - bc) = aT((m - bc)/b + c) + f(m - bc)
          = aT(m/b) + f(m - bc)

though idk why the latter form is a lot more useful

[fiery cosmos]

how can it be that m-3/3 = m/3????

[haughty mountain]

you eliminate the constant in one place but add a new one in another

[fiery cosmos]

from here:

[haughty mountain]

(m-3)/3 + 1 = m/3 - 3/3 + 1 = m/3 - 1 + 1 = m/3

[fiery cosmos]

oh yeah its bc of the +1

ok

alright so lets assume that i can use these values of m for the master theorum, where m = n, or do i have to convert m back to n using the m=n+3 thing

[haughty mountain]

I'm curious what CLRS would say on this

I don't feel it's a strong argument that you can make a substitution

because it just moves constants elsewhere

[fiery cosmos]

well my assignment was just use the master theorem to find the asymptotic bounds of this. so i don't have an answer. i do have another practice problem we could work though if you're interested

[haughty mountain]

I'm guessing tha answer is just n log n?

[fiery cosmos]

the answer to which

the practice problem? lms

[haughty mountain]

nvm additive constants matter, I'm dumb

[fiery cosmos]

uh oh

i already emailed my prof about it lol

[haughty mountain]

e.g. T(n) = T(n-1) + 1

you can't just ditch the -1

[fiery cosmos]

ok so for this next one i get something like "is it true that nlogn can be upper bounded by O of (n^0.792-epsilon)?

so like, wth to do w that

it would seem to be true and so T(n) = theta(n)

lms if thats right

nope

i've never gotten one of these correct

[haughty mountain]

are you missing a parenthesis?

[fiery cosmos]

i guess if you wanted to show n to the that term

but anyway here is their reasoning:

[haughty mountain]

I think n log n is upper bounded by n^(1+ε)

for any ε>0

but your exponent is <= 1

[fiery cosmos]

omega is lower bounded though?

[haughty mountain]

yes, you're not in the case when it's upper bounded

[fiery cosmos]

can we stop for 1 sec

when i evaluate these, i first look at case 1, and then case 2, and so-on. and it wasn't immediately clear to me that case 1 did not apply

how does one know that nlogn cannot be upper bounded by n to some exponent minus some constant?

[haughty mountain]

I think this is true:

n log n = Ω(n^(1 - ε))
n log n = O(n^(1 + ε))

what you are asking which of n log n or n^a grows larger

or equivalently log n vs n^(a-1)

<@&831776746206265384>

[fiery cosmos]

anyway..

[haughty mountain]

it's a pretty fundamental result that n^ε grows faster than log n

[fiery cosmos]

right, which is why i thought case 1 applied

i thought it must be true that nlogn could be upper bounded by n^somepower

[haughty mountain]

if somepower > 1

[fiery cosmos]

wait well in this case nlogn = n

[haughty mountain]

n^ε grows faster than log n
n^(1+ε) grows faster than n log n

[haughty mountain]

huh?

[fiery cosmos]

in this specific example, f(n) = n = nlogn

if you look at the equation, T(n) = 3T(n/4) + nlogn

[haughty mountain]

wdym n = n log n?

f(n) = n log n

not n

[fiery cosmos]

but thats what you plug into the formula for n when you solve, no?

what do you plug in on the RHS for n

[haughty mountain]

idk what you're talking about here

[fiery cosmos]

what goes in for n?

[haughty mountain]

where exactly?

[fiery cosmos]

nothing?

[haughty mountain]

it's just n?

[fiery cosmos]

so you don't plug anything in there.

[haughty mountain]

you are asing which of the three buckets your function f(n) = n log n falls into

"smaller than" n^log_b(a)
"equal to" n^log_b(a)
"greater than" n^log_b(a)

log_b(a) in the case you mentioned was ~0.793 which is <= 1

n log n is "greater than" that

if log_b(a) had been > 1 you would have been in case 1

[fiery cosmos]

but it matters what n is

if n is 1, then any power doesn't matter

if n is 2, then 2^0.792 = 1.727

furthermore how do you know nlogn is greater than (someunknown_n)^some arbitary power

or is it simply 2^log_2(2) = 2, which is larger than 2^0.792 power

[haughty mountain]

I put stuff in quotes for a reason

I mean asymptotically greater than

i.e. for large n, what dominates

[fiery cosmos]

but i need real numbers to plug in rather than "knowing" something is asymptotically greater or less than by glancing at it

which is why in the example were n = 2 it works or leads you to the conclusion that is case 3 you need

[haughty mountain]

it's not about just knowing

it's a limit you compute

what happens when n gets large

[fiery cosmos]

but can you see how i dont know the answer unless i plug something in?

[haughty mountain]

I mean, you do. n/n² tends to 0 as n grows, so n = O(n²)

wait...let me double check if what I wrote makes sense...

right, it does

n² is just miles larger than n

when looking at n log n you end up looking at

n log n / n^(1 + t) =
log n / n^t

as n grows large

so you do need some knowledge of typical limits

like, if that t>0 then log n/n^t tends to 0

i.e. log n is dominated by any polynomial with positive exponent

you don't need to plug in specific numbers to derive these, you study the limits

[fiery cosmos]

well, now i need to go learn probability, discrete random variables, the geometric and binomial distributions, indicator random variables, and randomized algorithms, so that i "understand" the analysis of quicksort (i won't)

then i'll be back here in a few weeks trying to learn the master theorem and substitution and inductive proofs again

[haughty mountain]

CLRS kinda assumes a bunch of math knowledge already, or at least that you have the fundamentals down. Re-learning the fundamentals (algebra, calculus, ...) at the same time feels like it will be kinda painful

[fiery cosmos]

i don't see what other option i have

well, im actually not even able to do that. i cannot self study enough of that stuff all summer to truly know what im doing. i cannot be self-sufficient when learning math. i need someone there to show me where im going wrong and what to do properly the next time

which was the idea behind this discord. but as it turns out typing everything out takes more time than a normal conversation

[haughty mountain]

at some point it comes down to fundamental results that someone who don't know about them feels like they are some magic "you just know"

e.g. the growth of log n compared to n^ε (where ε>0)

or the growth of e^x compared to any polynomial in x

the stuff in the definition of O Θ Ω boils down to limits as n grows large

for which some stuff is just "standard results" that you proved at some point and now you just know and use them

#data-science-and-ml might be more pandas savvy

[plucky dagger]

Perfect, ty

[fiery cosmos]

what does this mean

why does it strip away the base and make it log_unknown(1000)/log_unknown(2)?

[vocal gorge]

1. in math, log usually means natural logarithm.
2. This is correct because it's the base-change formula - log_b(a) = log_c(a)/log_c(b), where c is an arbitrary other base.

[haughty mountain]

that's how logs work in general, yeah

you can change base like that

[fiery cosmos]

how can you mathematically evaluate another arbitrary number

[vocal gorge]

wdym?

[half lotus]

You can use a known one like the natural logarithm

[vocal gorge]

it doesn't use an arbitrary number here. log means base-e. I'm saying the result would still be correct if you used any other base for the two logarithms here.

[haughty mountain]

yeah, it's true for any valid log base

[fiery cosmos]

so when you tell wolfram alpha "i want log base 2 of 1000" it converts it to log_e(1000)/log_e(2) and computes?

[haughty mountain]

that's one way of computing it

[fiery cosmos]

isn't that more complicated computationally?

[vocal gorge]

The "exact result" it shows doesn't need to have anything to do with what form it converts it into internally. It shows it in this form because it considers base-e logarithms simpler than base-2 ones for humans to see. I wouldn't jump from that to thinking it's the internal representation.

[fiery cosmos]

how could using some super long irrational number be simpler than 2

[haughty mountain]

log base e is the natural logarithm for a reason

it's much nicer to do analysis on

much like we write exponentials in base e

because analysis on that is easier

(because derivatives)

[fiery cosmos]

ok

[fiery cosmos]

how did they get this recurrence and what is meant by

[vocal gorge]

take the max over some expression, as q goes from 0 to n-1 inclusive.

same principle as

.latex $\sum_{0\leq q \leq n-1}$

[vocal gorge]

just with max instead of sum

[fiery cosmos]

ok

i need to learn to evaluate recurrences with a theta in them

i know there was a section on that in CLRS if anyone can remember where

i dont have the digital version so i cannot ctrl F

anyone can help me with worst case analysis of quicksort?

once again i do not understand why they are plugging in what they are where they are

[fiery cosmos]

i don't understand why they replace certain qs where they do and why they treat the entire second term as if the guess is written c(n)^2

[half lotus]

Because that is how it's written

First you do the exponentiation, then multiply

[vocal gorge]

You can make whatever assumption you want on T(n) and see if that helps you solve the recurrence. Here they assume T(n) <= cn^2, and determine that this fits the recurrence. So they got an upper bound this way.
At least, if I understand correctly what you're asking.

[fiery cosmos]

i'm just not comfortable plugging in cn^2 into 7.1 and being able to get the next inequality

i think i see what they did now.. sort of

[opal oriole]

T(n) <= cn^2
T(q) <= ???

[fiery cosmos]

cq^2

[opal oriole]

T(n) <= cn^2
T(n - q - 1) <= ???

[fiery cosmos]

c(n-q-1)^2

[opal oriole]

What factor do both T(q) and T(n - q - 1) have in common?

[fiery cosmos]

uhh.. in the problem? or how you've written it

in the problem yeah they factor out the c

[opal oriole]

So the questions have been answered?

You just did what they did.

[fiery cosmos]

i think i see it now yes. what is meant by "the second derivative of the expression with respect to q is positive?"

[opal oriole]

That is calculus. Are you familiar?

[fiery cosmos]

i am afraid i am not

which expression

[opal oriole]

I can explain it visually maybe.

[fiery cosmos]

that's ok, i can get help in the mathematics server. which expression are they referring to

oh: q^2 + (n-q-1)^2

i just don't follow their explanation, it continues here:

[opal oriole]

https://www.desmos.com/calculator/yj0sqdgmut

You can try different values of N. Notice that the maximum is at the end points.

[fiery cosmos]

how or why does that then mean that the bound max(expression) <= (n-1)^2?

[opal oriole]

Try plugging in 0 and n-1 for q.

(The end points, which we know give the max)

[fiery cosmos]

i get (n-1)^2 and (n-1)^2 + 4

[opal oriole]

Try n-1 again.

[fiery cosmos]

how do they get the expression followed by "continuing our bounding of T(n)"

[fiery cosmos]

working

[opal oriole]

Show steps.

[opal oriole]

When you plug anything in, surround it with parens.

e.g. q -> (n-1)

[fiery cosmos]

ok, but then i wouldnt know how to evaluate that lol

[opal oriole]

What is -(n-1) = ?

[fiery cosmos]

-n+1

[opal oriole]

Yeah.

Notice that that is not the same as - n - 1.

[fiery cosmos]

ahh ok. they both equal to (n-1)^2

thank you for showing me the basics

[opal oriole]

Yes, so both end points, which we know gives us the maximum possible value are both (n-1)^2.

And all values in between are less.

So all values are less than or equal to (n-1)^2.

[fiery cosmos]

ok so they then expand that to n^2 - 2n + 1 it looks like

[opal oriole]

Yes.

[fiery cosmos]

so how do they arrive at the penultimate inequality

that is, T(n) <= cn^2 - c(2n-1) + theta(n)

[opal oriole]

We know that max q^2 + (n - q - 1)^2 <= n^2 - 2n + 1. So we can substitute that whole expression. Imagine that whole "max ..." is one variable that you can replace.

[fiery cosmos]

so because the second term is minus c, we must change the sign on the +1 to minus one, as it is implied that out front of that expression there is a negative 1 factor

[opal oriole]

If it makes it easier let's actually make the "max ..." a new variable.

Let's call it "a". Then from before we had c * a + theta(n).

[fiery cosmos]

im with you

[opal oriole]

Now we also know that "a" is less than or equal to n^2 - 2n + 1.

So we can replace "a" with that.

Again, when replacing anything surround with parens.

What do you get?

[fiery cosmos]

c*((n^2)-2n+1) + theta(n)

[opal oriole]

Ok, now distribute the c.

[fiery cosmos]

ahh ok

so there seems to have been that crucial moment when they say "note that the second derivative..."

is that critical to being able to do this work?

[opal oriole]

*The key is to realize that you can replace entire chunks with some other chunk of stuff because you can always give any chunk a name (a variable letter) turning that entire chunk into a single character.

(And you know that you can replace a single character with a chunk of stuff)

[fiery cosmos]

that makes sense

[opal oriole]

You could also have graphed it in this case as shown above. But to prove it is something else.

Calculus is a very powerful tool for finding when things are max or min (among the many other things it can be used for).

[fiery cosmos]

did we just do calculus

[opal oriole]

The "second derivative" part.

It did not show work for it.

It just said "hey if you take the second derivative you will notice that the max happens at the end points."

Left to the reader to do.

[fiery cosmos]

so when would one stop during these proofs and think "boy i oughta look at the second derivative of this"

[opal oriole]

Well you know that you want to know what the max points are.

Because that can give you an upper bound.

[fiery cosmos]

max points?

[opal oriole]

And calculus instantly comes to mind from experience.

When q is 0 and n-1.

Two points, (0, n-1), (n-1, n-1). When looking at the graph.

[fiery cosmos]

wat

so q in quicksort is the partition?

[opal oriole]

max q^2 + (n - q - 1)^2 is asking for the max of that expression (which you can graph).

[opal oriole]

.

[fiery cosmos]

i'll have to go back and reread that section but i don't understand how from the behavior of an algorithm which typically takes as input n we can start getting stuff we can graph. i guess we could look at like when input is x, output is y (i guess) but then that would be one point for a single input and output. how can we get multiple points i just dont follow the logic or the buildup of it all

[opal oriole]

Regardless of what the algorithm is doing at some point we got to that point in our math where we got max q^2 + (n - q - 1)^2.

[fiery cosmos]

i dont understand why we wanted to replace it with something that is greater than or equal to that expression. especially when its on one side of an inequality

[opal oriole]

The goal is to simplify so that we end up with the end goal (cn^2).

To do this, we def. need to replace max q^2 + (n - q - 1)^2 with something.

[fiery cosmos]

makes sense

[opal oriole]

And so we can try to replace it with an upper bound.

[fiery cosmos]

wait hang on

wasn't that the reason for setting out in the first place? and now we're adding an upper bound into our upper bound expression??

[opal oriole]

We guessed cn^2, what we did not guess and where given (from prior) is (7.1).

[fiery cosmos]

oh btw

why is that the recurrence for this particular algo. how do they come up w that

[opal oriole]

If we can massage (7.1) to become our guess, then we were able to go from start to end goal.

[opal oriole]

That would derail, for now this is more important.

It's more general about how to solve things.

[fiery cosmos]

ok

[opal oriole]

This entire process we have been doing is to massage our start (7.1) into our end goal (our guess).

[fiery cosmos]

right

[opal oriole]

We want to connect the dots, which is what a proof is all about.

This informs all our in-between decisions like to try to get an upper bound to replace max q^2 + (n - q - 1)^2.

Because it seems like it would move it towards our end goal.

(n-1)^2 seems a lot closer to the guess than max q^2 + (n - q - 1)^2.

[fiery cosmos]

and an upper bound makes sense because if we instead inserted a lower bound, we'd be violating the inequality that T(n) <= new expression

[opal oriole]

Now sometimes you will make the wrong step forward. Maybe doing (n-1)^2 was not the right step, you ended up further away. In that case you rewind and try something else.

[opal oriole]

Yes.

The steps must not break any of the rules.

All steps must be valid in a proof.

[fiery cosmos]

how do you know which steps are valid?

[opal oriole]

You know what the rules are.

For example: ``

x + 1 = 0
x = -1

Did I break the equality?

Was it a valid step?

[fiery cosmos]

no, yes

[opal oriole]

In algebra class they try to blast you with a bunch of valid steps.

Options you can do.

[agile sundial]

as long as each individual step is valid, the entire chain of steps is valid

[fiery cosmos]

well i don't remember algebra so.. 😂 😭

[opal oriole]

There is some small steps which are considered valid, and when you chain those steps together you can think of having done one macro/large valid step.

This entire proof could be seen as one step depending on the context.

Maybe showing this runtime was just part of a larger proof you were doing.

[fiery cosmos]

its really mostly the algebra i struggle with, less the logic (though i occasionally dont know wth they're on about)

[opal oriole]

Now how small your valid steps need to be / how precise, depends on context.

It's whatever convinces the reader. And a professional logician's job is to be very hard to convince.

[fiery cosmos]

i just don't understand how we don't learn about it in the book (or coursework) and out of nowhere they'll be like "prove that x is a relation on y", that is, that something <P something else <P finalterm

and i have no idea what they're talking about

i think graph theory is going to be impossible for me

[opal oriole]

You lack mathematical foundation for any of this.

[fiery cosmos]

so whats the fastest way to get it

[opal oriole]

It's like being asked to solve a chess puzzle without knowing how all the pieces can move yet.

(Funnily enough, doing a checkmate in chess is a kind of proof)

[fiery cosmos]

i mean, i don't have time to learn algebra and calculus and discrete math so whats the next best thing to do going into this

[agile sundial]

it's kinda like running before walking

[opal oriole]

Make time. I would drop out and just work on that. But that is up to you to decide.

And this is not a career advice channel.

[agile sundial]

i don't think he's a cs major, right? this is some course you need for some requirement?

[fiery cosmos]

that's essentially what i've done. i left my career and i'm only studying this stuff. i don't work

[agile sundial]

oh

[fiery cosmos]

correct

non CS major, but have to take algos as part of grad school

in the engineering school

[agile sundial]

you're an engineer?

[fiery cosmos]

no

i think you can gather im not an engineer at this point

lol

[opal oriole]

If you want to be way ahead of most, you can just be good at math. A lot of people try to force their way through like you are now, to get a job. But I will always hire someone that knows some math over those that do not.

[fiery cosmos]

i mean, if i fail algos im going to just continue to study computer science and get a programming job. i'll do anything to leave my old work (which was deadend)

and when I say fail i mean get a B-

i know i'm making it sound easier than it is but the reality is that people who know how to code can get programmer jobs (not software engineering) that are much better paying and better career trajectory than my old line of work

[opal oriole]

#career-advice

[fiery cosmos]

i mean, you sort of forced me to respond by saying "you don't know enough for this" but my class starts next month

[opal oriole]

I'm just saying that we can continue the discussion there.

[fiery cosmos]

oh

[high musk]

has anyone used a range tree before? seems like a relatively obscure ds and I can't really find python implementations

[golden kraken]

using python turtle. how should I go about constructing waypoint navigation for multiple turtles where each go to different waypoints?

having each go straight to a waypoint and then make a half turn

[haughty mountain]

I would say it's quite obscure yes

it has some uses, of course

though I've never implemented them or used them

[high musk]

i was thinking of using it to optimise a particle simulation

might just use an octree, that seems like the more common way

[haughty mountain]

probably, depends on what you need to do in your simulation

if you need to find nearby points and you need a structure you can update dynamically an octree is reasonable

[high musk]

mm

i could actually do away with real trees now that i think about it

i just need to consider a small neighbourhood of particles around a given particle, so a fixed size grid with that radius should be ok

i could use trees to traverse the neighbouring cells, but the trees wouldnt be the primary container for the particles

[haughty mountain]

if you have a smallish radius a fixed size grid is fine, yeah

if you pick >= 2 rad grid size you only need to check 4 cells

[high musk]

mm true

[haughty mountain]

or you could go smaller and have to check 9 in the worst case

grid size >= rad*2/3 I think

[high musk]

mm

ill bump it up a little in case

thanks!

[opal oriole]

Octrees are just easier to implement / work with (so they show up a lot).

[opal oriole]

It also depends how dense you expect your stuff to be when working with fixed grid size.

Octree just adding more splitting to deal with when things are too dense.

(A fixed grid is still better than no grid usually in any case)

(Unless everything is in one cell at some point in time)

[high musk]

in my case i can ignore particles that are too far away, as opposed to a barnes hut, which would consider the center of mass

for this reason i think the octree isnt actually needed

[opal oriole]

With a very large fixed grid (large cell size) it can easily ignore far away particles by ignoring anything that is not in the same cell or a neighboring one.

If those cells can end up being dense you can still build a tree in those fixed cells.

(e.g. an octree)

[high musk]

mm

[opal oriole]

(fixed - dynamic hybrid)

[high musk]

what would the point of the internal octree be?

I'd assumed the octree was partially for the COM, and partially to quickly reject particles that are too far away

[opal oriole]

If your cell size is chosen to be big, and you can have many particles in any given cell, the runtime would still be really bad.

Imagine all your particles are in one cell.

It's the same as having no grid.

[high musk]

mhm

would there be a benefit to choosing a large cell then?

[opal oriole]

So if any cell gets too many, you can still do the dynamic thing of further splitting that cell (e.g. octree).

Well, ignoring far away particles with large fixed cells is easy.

If the particles are far away then they are probably not in the same cell, nor a neighboring cell.

So in general you can just straight up not check all the cells except for the neighbors (ignore the far away particles).

You have some "window" in which particles can interact, and outside they are considered too far away to matter.

Their influence too weak.

[haughty mountain]

if you still need to find everything in a radius an octree likely won't help much

[opal oriole]

It depends which searches you are doing. But in general you can pretty much always combine some fixed grid with whatever.

The fixed grid acting as a "too far away, don't care".

You may have particles in clusters / local groups that interact. In that case your fixed grid storage will look sparse. A common thing in particle simulations.

(Most cells completely empty)

[haughty mountain]

in which case you should probably use some proper adaptive grid, though that's a bunch more work

[opal oriole]

So, it all really depends on how the particles are interacting / with what / at what distances.

At what level of approximation.

[haughty mountain]

yeah, the details matter a lot

[opal oriole]

Oh and very important, are all the particles the same, or are there many different types that have different interaction distances, etc (then it becomes a nightmare to code).

In general though, start "dumb" and keep adding more crazy-ness as needed. So no grid -> fixed grid -> etc.

And you need to really look at how the simulation plays out (do you get sparse clusters, etc).

(Under different starting conditions)

[long cove]

guys i'm confused

ok look at this

Raphael is visiting his friend Steinunn,
in Iceland, He's staying with her and her family in the capital Reykjavik.

He's staying with her and her family

who the hell is her

[haughty mountain]

this is not #english-grammar

Steinunn is her

though that comma after Iceland should be a period

[spring hollow]

bro help PLSS

[pseudo walrus]

Take a look at these examples, you'll have your answers.
However, if this is your assignment or homework, we can give you hints, but not the direct solution [Rule 8 in #rules].

#HAPPYCODING

[finite sandal]

you'll also want sleep() from the time library with the right amount of sub seconds
https://docs.python.org/3/library/time.html#time.sleep

[golden kraken]

using python turtle. how should I go about constructing waypoint navigation for multiple turtles where each go to different waypoints?

having each go straight to a waypoint and then make a half turn?

I plan on adjusting waypoints mid simulation

[tacit nova]

why this work ?
list.append(listB[:])

and this doesn't work
list.append(listB)

[haughty mountain]

both "work", but they do different things

first one appends a reference to a new list (the slice makes a copy)

second one appends a reference to the existing list, so it will change if the underlying list changes, which is probably what's confusing you

[tacit nova]

oh i understand now, ty for yr explanation

[dapper sapphire]

// L A M B R
// [1, 2, 3, 4, 5, 6, 7]

L = Left
M = Middle
R = Right
what can I name A and B that are to the left and right of M?

[civic tulip]

hello! I am self-studying python right now. Can someone recommend me some great books to learn data structures and algorithms in python as a beginner, please? Almost all the books I found are coded in C or Java. Thank you.!

[stoic stream]

Hi,

I have a service that stores connections between user profiles on various sites. My solution works, but it feels like reinventing a wheel.

Although it seems like a rather generic problem, I wasn't able to find any open-source projects that I can take inspiration from.

I tried to open this question in a help channel, but perhaps this channel could be more fitting. Please let me know if not and I'll delete my comment.

#help-cake message

Does anyone know any open-source projects or articles that would address a similar problem?

[vocal gorge]

It seems to me like what you've reinvented is a graph database:
https://wikipedia.org/wiki/Graph_database?lang=en

Switching to a specialized graph database might therefore reduce the boilerplate. I don't know if that's the best way to implement it, though. Probably?

[stoic stream]

I'm kind of aware that specialized databases for storing graphs exist, but that would be out of the scope of this project.

Storing relations between the profiles is just one of the features. My implementation works, but I'm not entirely happy that it's an original solution for something that feels like a standard problem.

You are probably right, that using a graph database for this kind of problem is the proper standard way. I just hoped that the problem is so common that there are even some implementations with relational databases.

[finite sandal]

have you checked out the pins for the channel?

[median spire]

Hi!
I need to create probability distributions.
How can I generate random numbers in a list that are in sum 1 (100%)?

e.g. [1/6, 1/6, 1/6, 1/6, 1/6, 1/6] but random

[half lotus]

Interesting question. I haven't heard of this distribution before https://stackoverflow.com/a/18662466

[halcyon plank]

Hey @wintry osprey!

It looks like you tried to attach file type(s) that we do not allow (.heic). 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.

[wintry osprey]

Hey all! So I recently came across a TON of stamps, and I am trying to create a dB of them. Because there are literally thousands, I am hoping to be able to take a photo of multiple stamps and have my app split them into individuals. Are there any API's or SDK's or algorithms that anybody knows of that could help me do this?

[fiery cosmos]

Sound more like a question for #data-science-and-ml

[tacit nova]

hey can anyone explain this line from https://leetcode.com/problems/subsets/solution/

Note that for space complexity analysis, we do not count space that is only used for the purpose of returning output, so the output array is ignored.

nvm found it https://cs.stackexchange.com/questions/83574/does-space-complexity-analysis-usually-include-output-space

[quick owl]

# number to find the factorial of
number = 6   

# start with our product equal to one
product = 1

# track the current number being multiplied
current = 1
 
# write your while loop here
while product < 720:
    product=product*number
    number-=1
    
    # multiply the product so far by the current number
    
    
    # increment current with each iteration until it reaches number



# print the factorial of number
print(product)

pls help

[clear pier]

import math

number = 6

number_list = []

for i in range(1, n+1):
    number_list.append(i)

print(math.prod(number_list))

@quick owl try this code

[quick owl]

ok

[quick owl]

n is not defnied

[plain violet]

Good point but this loop is useless, you can pass an iterable such as range to prod, so you can simplify your code to get more efficiency:

from math import prod


print(prod(range(1, n + 1)))

[quick owl]

idk

how

to do it

:(

[plain violet]

Define it like number

[quick owl]

# number to find the factorial of
number = 6   

# start with our product equal to one
product = 1

# track the current number being multiplied
current = 1
 
# write your while loop here
while product < 720:
    product=product*number
    number-=1
    
    # multiply the product so far by the current number
    
    
    # increment current with each iteration until it reaches number



# print the factorial of number
print(product)

thats the qs

[plain violet]

n is short name for number in this case

[quick owl]

im very new to coding

so...

[clear pier]

import math

number = 6

number_list = []

for i in range(1, number +1):
    number_list.append(i)

print(math.prod(number_list))

[clear pier]

bro he is new to coding better if we keep the code brief and easy to understand

[quick owl]

thx

can I add you?

[plain violet]

I got you, but what is hard in short version? It is readable like plain English "Product the exclusive range of numbers from 1 to n + 1"

[quick owl]

the question is

Practice: Factorials with For Loops
Now use a for loop to find the factorial!

It will now be great practice for you to try to revise the code you wrote above to find the factorial of a number, but this time, using a for loop. Try it in the code editor below!

# number to find the factorial of
number = 6   

# start with our product equal to one
product = 1

# write your for loop here



# print the factorial of number
print(product)

[plain violet]

Your solution was almost correct, just change the condition in loop to number > 0

[clear pier]

ok.. you won i lose

[quick owl]

# number to find the factorial of
number = 6   

# start with our product equal to one
product = 1

# track the current number being multiplied
current = 1
 
# write your while loop here
while product < 720:
    product=product*number
    number-=1
    
    # multiply the product so far by the current number
    
    
    # increment current with each iteration until it reaches number



# print the factorial of number
print(product)

I did this for the other part

this

Find the factorial of a number using a while loop.

A factorial of a whole number is that number multiplied by every whole number between itself and 1. For example, 6 factorial (written "6!") equals 6 x 5 x 4 x 3 x 2 x 1 = 720. So 6! = 720.

We can write a while loop to take any given number and figure out what its factorial is.

Example: If number is 6, your code should compute and print the product, 720.

I hardly did this one

[clear pier]

where you're getting these questions ? @quick owl

[quick owl]

Course

[clear pier]

ohh I thought this was from hackerrank coz I did this question this week

[quick owl]

oh lol

see

idk how to do this one tho

[plain violet]

Use range

[quick owl]

🥲 how

[plain violet]

You can iterate over range() using for loop

[quick owl]

how can I put it in a code

[plain violet]

Range is a sequence of numbers

[quick owl]

yea

for product in products:

[plain violet]

You are right

Just assign range() with required bounds to products

[quick owl]

for product in products:
  product*number
product-=1

im very dumb im sorry

lol

[quick owl]

how to I bound it

[plain violet]

range(start, end)

But keep in your mind that range() is exclusive

[quick owl]

yea

[quick owl]

how do I put that in this

range(start, end)

[plain violet]

Create a products variable

[quick owl]

product = 1

[plain violet]

To avoid names conflict you need to do for i in products

[quick owl]

but i is not in products

bc there is no list

which has

"i"

[plain violet]

products = range(...)

[quick owl]

range is

1,721

bc i need answer 720

[plain violet]

for i in products:
    ...  # do factorial logic there

[quick owl]

# number to find the factorial of
number = 6   

# start with our product equal to one
product = 1
products = range(1,721)
# write your for loop here

for product in products:
  product*number
product-=1

# print the factorial of number
print(product)

okok

# number to find the factorial of
number = 6   

# start with our product equal to one
product = 1
products = range(1,721)
# write your for loop here

for i in products:
  product*number
product-=1

# print the factorial of number
print(product)

the output is 0

:|

oh 1-1 is 0

but why did it not multiply?

i said product*number

[plain violet]

Because you haven't save result of multiplication

[quick owl]

how do i make it to 720

like

<720

this

[plain violet]

You would like to assign multiplication result to product variable

[quick owl]

so hardddd

[plain violet]

Yes programming at beginning is hard

[quick owl]

i started like 4 days ago

[plain violet]

Have you done this?

[quick owl]

nope

idk how

multiplcation = product*number

like this?

[plain violet]

My bad, i have said my idea incorrectly a little bit

[quick owl]

oh

see

# number to find the factorial of
number = 6   

# start with our product equal to one
product = 1
products = range(1,721)
# write your for loop here

for i in products:
  product = product*number
product+=1

# print the factorial of number
print(product)

[plain violet]

Assign it to product variable

[quick owl]

but it makes like

a

99999999999999252392396782390572398705238905723578923

number

ir sn

or sm*

how do I stop at 720

[plain violet]

Yes, because range of numbers is very big

[quick owl]

but

I typed

products = range(1,721)

[fiery cosmos]

1*2*3*4*5*...*720 is a big number

[plain violet]

range(1, 721) is like [1, 2, 3, 4, 5, 6, 7, 8...720]

[quick owl]

my asnwer has to be 720

[fiery cosmos]

try range(1,7) if you are trying to do 6! which is 720

[quick owl]

yeaaaa

[plain violet]

You are product all these numbers

And getting a very big number

[quick owl]

it makes 48231 somethings

see

# number to find the factorial of
number = 6   

# start with our product equal to one
product = 1
products = range(1,7)
# write your for loop here

for i in products:
  product = product*number
product+=1

# print the factorial of number
print(product)

[plain violet]

Remove the product += 1 line

[fiery cosmos]

oh, why are you multiplying by number?

[quick owl]

46656

new output

[fiery cosmos]

number+1 is the thing you want to loop up to, i is the thing to multiply by

factorial mean like 1*2*3*4*5*6 but you have product = product*number meaning you do a *6 in there each time

[quick owl]

🥲

?

sorry I started codign like 4 days ago

[fiery cosmos]

products = range(1,number + 1)
# write your for loop here

for i in products:
  product = product*i

[quick owl]

but the asnwer has to be 720

[fiery cosmos]

!e ```py
number = 6

start with our product equal to one

product = 1
products = range(1,number + 1)

write your for loop here

for i in products:
product = product*i

print the factorial of number

print(product)```

[halcyon plank]

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

720

[fiery cosmos]

looks good to me

[quick owl]

is it a for loop?

[fiery cosmos]

yeah, I only slightly modified your code

[quick owl]

why does it look so hard now

lol

[fiery cosmos]

you can see the for i in products:

[quick owl]

this is the solution

when I solve it shows

# number we'll find the factorial of
number = 6
# start with our product equal to one
product = 1

# calculate factorial of number with a for loop
for num in range(2, number + 1):
    product *= num

# print the factorial of number
print(product)

this*

can u explain 1 thing?

[quick owl]

what is this range? range(1,number + 1)

like ranges are

(1,7)

[plain violet]

This is a range of numbers from 1 to number + 1

[quick owl]

n+1

oh

sequence from my math book

lmfao

[haughty mountain]

ranges are sequences of numbers, when you loop over range(a, b) you loop over
a, a+1, a+2, ..., b-2, b-1

[quick owl]

😵‍💫

0 idea what these means

https://cdn.discordapp.com/attachments/650401909852864553/994492989219033138/unknown.png

[quick owl]

this is the first part

[haughty mountain]

they are asking you to loop over

start_num
start_num + count_by
start_num + 2*count_by
...
end_num

[quick owl]

?

[haughty mountain]

like, if start_num = 3, count_by = 2 it's the sequence of odd integers starting at 3:
3, 5, 7, 9, ...

and then you stop before you go larger than end_num

so if end_num=7 you would have
3, 5, 7

it's an arithmetic sequence, if you know that term from math

[quick owl]

yes

[plain violet]

count_by is the denominator of sequence

[quick owl]

start_num=0
end_num=100
count_by=2
break_num=100
while start_num<break_num:
    start_num+=count_by
    end_number=start_num+count_by
    
    
print(break_num)

did it

[tacit nova]

https://leetcode.com/problems/combination-sum-ii/solution/
can anyone explain this line right here ? I mean we for candidates [1,2,2,6] and target [5]. We have to use [1,2,2] with 2 as duplicate to solve it

if next_curr > curr \
                  and candidates[next_curr] == candidates[next_curr-1]:
                    continue

[final thunder]

In a hash table which uses buckets as a method of handling collisions, should the load factor be determined based on the total number of key-value pairs in the hash table or the total number of buckets which contain at least one elements (which is a count of total hash keys which have collision potential)?

I am leaning towards the latter but interested in people's thoughts

Also feel free to @ me if you respond 🙂

[agile sundial]

average number of elements in a chain

[final thunder]

@agile sundial Why?

[agile sundial]

because it makes analysis easier lol. the expected time to search for an item is then just your load factor

[final thunder]

Haha that's a good reason

Thanks!

[ivory light]

is there a particular search algorithm that usually works for everything

im trying to learn some search algorithms but i dont wanna know how to do like every single one of them D:

[agile sundial]

brute force

[ivory light]

0-0 isnt that like super slow usually

[agile sundial]

well yeah, but it works for everything

[agile sundial]

if you want it to be fast, you need a more specific algorithm

[tacit nova]

binary search

it's not a fancy search algo
but there are a lot of Leetcode questions on binary search so it's better to be good at them

[remote raven]

best way to learn data satuctures and algorithms?

[remote raven]

how to learn topics i know python

[plain violet]

look pinned messages

[sick lodge]

What is the code behind python .sort()?

[jolly mortar]

it's an algorithm called timsort, based on merge sort

the cpython repo has a detailed explanation about it

https://github.com/python/cpython/blob/main/Objects/listsort.txt

[dark aurora]

why is my code so much slower when accesing elements

so I have code like this

....

for i in range(10)

g = l[2]+l[3]

and this is much slower then

for i in range(10)

g = 2+3

Isn't accesing elements O(1) complexity

[jolly mortar]

O(1) just means it takes a constant amount of time regardless of the size of the list, it doesnt tell you whether that's fast or slow

also g = 2 + 3 probably gets constant folded at the compilation step itself

[haughty mountain]

it makes it so that you can't ever skip the beginning of a group of the same value

[tacit nova]

can you explain some more ? i have been stuck on that for awhile tbh.
For example if we have [1,2,2,2,5,6] with target is 6
[2,2,2] is one of the answer

[haughty mountain]

when you get to the first 2 the condition allows you to pick it and recurse, it does not allow you to not pick the first 2 and then pick a later 2

[tacit nova]

ohhhhhhhhhhhhh

[haughty mountain]

when you recurse you can again pick the first 2 in the group starting at curr

so it allows you pick consecutive 2s

but only from the front of the group

[tacit nova]

i understand it now lol (honestly i looked up 5 Discussion posts, they also use that line but dont explain it that much)

[haughty mountain]

tbh, I would just extract the counts and work with that, it makes the code a lot more obvious

you have one 1, three 2s, one 5, one 6

[tacit nova]

i think thats Approach 1 in official solution

[haughty mountain]

yeah

[tacit nova]

Approach 1 Backtracking with Counter
Approach 2 Backtracking with Index

okay i will work on them later

thanks for the help, i alsmot give up on it

[woven heart]

anyone please link me nice course on dsa using python

[lament totem]

I've learned most of dsa using sites like hackerrank/codewars etc. @woven heart

You could probably just look through some video going over the basics by Corey Schafer on youtube, and try some simple challenges for yourself

and build up the difficulty

[haughty mountain]

I remember when hackerrank had contests back in the day, they were pretty good

sadly that's long gone

I guess my 99.91th percentile there is set in stone now

[lament totem]

I was actually 1st percentile

[ivory light]

ive been stuck on the same challenge from hackerrank for like a month because i dont know how to access a list 😭

[woven heart]

well i'm new to the thing so i need some nice explanation before doing any leetcide

[lament totem]

Well this is a bit of a general intro to lists, sets and tuples
https://www.youtube.com/watch?v=W8KRzm-HUcc&t=8s&ab_channel=CoreySchafer

The next video in the series is about dicts

@woven heart

It's a bit of an old video, but I think pretty much all of it is still relevant

And I'm pretty sure hackerrank also has some very basic beginner challenges that even introduce the topics again

[tepid bramble]

Even i need it too

[tepid bramble]

How can I learn dsa to prepare for interview is there any YouTube channel or videos that can help me to learn different solutions of a particular problem! Any idea

[tepid bramble]

Oh thanks

Can you send a sample video

I can't find it

Link please so that I can make use of ut

*it

[icy badger]

python is crashing again n again

[hearty tapir]

Below functions flatten the nested list of integers (List[List[int]]) into a single list and remove duplicates by leaving only the first occurrences. When the total number of elements is N, choose the one that correctly compares the time complexity with respect to N of each function.

Help!!! 😭

[agile sundial]

are we missing some info, like answer choices or something?

[hearty tapir]

Oh, yeah.

[agile sundial]

so, find the time complexities of each function

[hearty tapir]

Hm.

[hearty tapir]

Is my answer correct?

[agile sundial]

no

[hearty tapir]

Does a set make f3 more complex?

[agile sundial]

no, do you know what a set is/does?

[hearty tapir]

Yeah. Acts like a list? ☹️

C'mon. Please help me with it, then tell me how the answer was gotten.

[agile sundial]

no

a set is an unordered collection, that has O(1) time membership testing

can you see how that changes the result from f1 to f3?

[hearty tapir]

I really wish I knew. 😔

[agile sundial]

do you understand the O(1) membership testing?

[hearty tapir]

I only know that's the least complex.

..and a for loop constitutes O(n)

Two for loops O(n^2)

[agile sundial]

well, that's not quite right

[hearty tapir]

But, I really do not know how to apply these in specific real-world scenarios.

[agile sundial]

i'm assuming you're learning this in class?

[hearty tapir]

Not really.

This is self-learning...and I'm trying to understand time complexity.

This is an exercise.

All of them have two for loops. Looks like they're equal.🤔

[agile sundial]

yes, that's where your "2 for loops = O(n^2)" rule breaks down

you can't simply rely on the "structure", you need to read what the code is actually doing

[hearty tapir]

So, answer is E?🤔

[agile sundial]

no?

the only difference between f1 and f3 is the introduction of a set, right?

[hearty tapir]

Yes.

[agile sundial]

ok wait, what's the time complexity of f1?

[hearty tapir]

O(n^2)

[agile sundial]

why?

[hearty tapir]

First loop: O(n) * Second loop: O(n)?😕

[agile sundial]

no

N is defined as the total number of elements

[hearty tapir]

Okay?

[agile sundial]

each loop doesn't loop over all the elements, so it can't be O(n) for each loop

[hearty tapir]

For real, I'd understand better if I know which one is more complex.

[agile sundial]

not really

[hearty tapir]

All right. Looks like we're going nowhere with this.

[agile sundial]

i mean, i gave you this

[hearty tapir]

I'll just go with anything that's not A or E. Thanks.

[agile sundial]

sure

[rare musk]

How long did it take you guys to consistently complete LC easy questions? I've been learning programming (majority in C++ and a bit of python) for about a month seriously. Have been really really learning data structures (up until binary trees). I've been able to complete about 40 easy questions (with focus on finding optimal time+space complexity every single time) but the majority of new questions is still not doable to me. How much longer will it go until its possible to consistently complete the easy (or even medium) questions?

I would be very happy if anyone is down to chat about this as these problems are super demanding at times

[runic tinsel]

it's impressive to be able to do that, they are "easy" because it's assumed you've read how to do it, essentially spoiled yourself

[clear pier]

i was doing lc easy problem but i gave up it was very hard though

[runic tinsel]

so like if it takes you 12 more months, that would be average, 4 would be speedrunning

just made up numbers idk

[clear pier]

any tips / help for me @runic tinsel

[runic tinsel]

uh, read the solutions

[slender light]

Hey can anyone help me with my python code I need help

The matrix r in which rij=(pi1q1j+pi2q2j+...+pinqnj) is called the product of P and Q and denoted as P.Q or simply PQ.cij is the dot product of the i th row in P and the j-th column in Q. Write and test a Python function, called matrixProduct, that takes two matrices and returns their product, if exists. Hint: don’t forget to create the resulting matrix before you put values into it.
we can't use library

This is the question from my university I am having trouble getting the solution

[fiery cosmos]

i dont get this rij=(pi1q1j+pi2q2j+...+pinqnj) but what i get is that you need a function that will take two matrices as input and return their matrix product

they asked not to use library because this is literally a two line code in numpy including importing library 🤣

[haughty mountain]

it's just three nested for loops to write a matrix multiplication, the wiki on matrix multiplication ought to have it stated

[rare musk]

the completed questions i have actually figured out myself (i've looked at many more questions and surely picked up some patterns and strategies)

no looking-up the answer

[slender light]

can you help me I have to complete this assignment

[rare musk]

me?

i have no idea how matrixes work in detail but will look into it now

can you post the whole question or was that it?

[runic tinsel]

that's exactly what i assumed yes

[slender light]

P=⎛⎝⎜⎜⎜a11a21...an1a12a22an2.........a1na2nann⎞⎠⎟⎟⎟ and Q=⎛⎝⎜⎜⎜b11b21...bn1b12b22bn2.........b1nb2nbnn⎞⎠⎟⎟⎟

[rare musk]

i mean learning the pattern is the whole point of leetcoding. you repeat it so often that you have a chance at these brutal tech interviews

[slender light]

It has this

including the question above

[rare musk]

At what point are you in your journey in learning DSA if I might ask?

[slender light]

Only the merge sort and sorting algorithms

[rare musk]

yeah thats beyond the scope of my knowledge mate

[slender light]

do you know anyone who can help??

[runic tinsel]

i don't know, i'm not learning deliberately, it's like a hobby

[slender light]

i have searched it on the internet

its from the leetcode

[rare musk]

send the LC problem i wanna check it out

[rare musk]

gotcha

[slender light]

let me check it out mate I don't remember if it this ques or the other

let me send you a ss

[rare musk]

ye

[slender light]

I am having toruble with these questions

[rare musk]

oh isee

[slender light]

*trouble

[rare musk]

you just iterate over the matrix and simultaneously multiply the element by the same index in the vector

[rare musk]

@slender light

hey

this should explain it

you iterate over the matrix and multiply the element in place with the element of the vector

code is inefficient and stuff but i wanted to show how it fully works

or how i think it works 😄

[haughty mountain]

the definitions are quite literally telling you what to do, to compute y[i], compute the sum a[i][1]*x[1] + a[i][2]*x[2] + ...

the math is one indexed, python is zero indexed, so change where appropriate

[round glacier]

How do you get better at comprehension of algorithm questions on leetcode/hackerrank? I feel like a lot of the time it's hard to even understand what I'm asked to do

Like all of the code you see is very unclean, using variable names like "i" and "k" and "j" which further confuses my undertstanding of the problem.

[half lotus]

If the variable names are confusing then restate the problem using variable names more clear to you

[round glacier]

I cannot do that if I don't understand the initial intent of the problem and what someone else is doing. I am referring to looking at other people's code.

It seems very common that people who write and do well with algorithms, are VERY bad at writing clean code.

[half lotus]

Oh your question mentioned the question, not the solutions

[round glacier]

It's kind of both. haha

I don't know how to solve many of these algorithms because they are not easy to understand.

Using "k" and "j" and "i" does not help anyone to understand the problem.

Why don't they use english?

[half lotus]

Yeah, some solutions suck at writing clean code. Ultimately you just gotta browse the forums until you find something good. Sometimes comments will rewrite the code better too.

[round glacier]

Any idea where to go search?

[half lotus]

Well on leetcode there is a discussion board which is mostly used for sharing solutions

[round glacier]

I want to see solutions which are written with English verbiage

[half lotus]

I don't really use their official solutions cause most are paywalled anyway

[round glacier]

So like, if you are calculating max value for example, I wouldn't want to see something with a non-descriptive variable name

I want all variable names to be in english

Not in math.

This is a very big pet peeve of mine, because I don't think I should have to sit there and try to figure out what's going on because the author of the code didn't write proper variable names, or comments

You know what I mean?

[half lotus]

Yes I agree. It's just general good coding practice to use meaningful variable names

Some exceptions can be made for commonly understood names like "i" for index

I think the bigger problem with solutions posted is that many lack an adequate explanation. What's most useful is to understand the intuition behind the solution.

But even comments in the code go a long way.

[round glacier]

I agree. This is a similar problem honestly with regards to people learning mathematical concepts. In my opinion, all code should be smooth like butter. If your grandma read it, she should be able to have a "decent" understanding of what you're trying to do.

Having to dig, read and understand someone else's poorly written code, is not a great use of anyone's time.

[half lotus]

Though in my experience I can usually find a decent solution within the first page of the discussions.

[round glacier]

I also think that variable names like "left" and "right" are not useful

LeftPtr, RightPtr

[half lotus]

What would you name them then?

I think they're fine if there's a comment that explains that they converge towards the middle

[round glacier]

That's kind of the problem, two-pointer solutions are just not intuitive at all lol

To the common person

Like you cannot write names that make logical sense outside of the problem itself

And the problem itself is so specific

[rare musk]

I believe left and right are quite descriptive, if you know what a two-pointer approach is

[half lotus]

Names can only take you so far. That's why other documentation is important too.

Like what i said about comments and discussion intuition

[rare musk]

@round glacier have you learned about all important data structures and can you implement them?

[round glacier]

Yeah

Although, some are not committed to long term memory

But yes lol

Being able to implement data structures does not help you with algorithms though

In all honesty

It might increase your ability by 10-20%

But that's about it

[rare musk]

so you'd know i.e. how to insert a node after a given node in a linked list, traverse a binary tree or use hashtables?

[round glacier]

yep

I'm an engineer at a major video game company and I still struggle with algorithms

which goes to show how hard algorithms truly are to master

I know people who work at google who still struggle

[rare musk]

agree with you there

i've just started about a month ago and really learned the data structures and basic algorithms... can do easy questions but not consistently

[round glacier]

Yeah

[rare musk]

from what i've heard its really just about repetition. you try a question for 30 mins and then look at the optimal solution. after x amount of problems you'll see the patterns

[round glacier]

They are some of the hardest things you will ever have to learn in your life

Honestly, the fact I got into the company I work at, I feel is a blessing by god.

I don't even feel like I deserve it, so I work overtime constantly, and on weekends.

[rare musk]

congrats man!

[round glacier]

lo

But like i want to get to a point where i can learn these algorithms

and be able to go to other companies

[rare musk]

the fact that you're still there shows you're good enough. surely they'll dump you if you don't perform well.

[rare musk]

yeah thats my primary goal too

How many questions have you done?

[round glacier]

On and off, about a hundred I think

over the last 2 years lol

[round glacier]

ive only been here about a year in 2 months, so we will see during perf reviews lol

but my boss has given me multiple opportunities to prove myself, and get publicity by writing code that will be seen by others

so i hope ill be fine lol

holy shit, someone is smoking weed outside, 1 second

[rare musk]

sounds solid man

[round glacier]

its coming up the windows

Welcome to los angeles

weed smoking everywhere

[rare musk]

lol

[round glacier]

# Problem statement
# https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
import sys


def max_profit(prices: list[int]) -> int:
    max_profit = 0
    min_price = sys.maxsize
    for price in prices:
        if min_price > price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit


# tests
test_data = [7,1,5,3,6,4]
assert max_profit(test_data) == 5, 'Incorrect result'

Like here's an algorithm I just did

This is what I mean by writing "clean" code

Isn't that far easier to understand, than seeing "for i in prices"

[rare musk]

let me solve it one sec

ok maybe couple minutes i'll brb

[half lotus]

You don't need to use sys.maxsize. The constraints tell you the upper limit is 10^4

[round glacier]

oh true

i didnt read that

i think leetcode automatically imports the sys module though on its own

[half lotus]

Worth paying attention to constraints. Sometimes you can end up doing clever tricks.

[round glacier]

so i dont think it makes much of a difference in runtime lol

[half lotus]

Sorry that isn't a clever trick

I mean, there are clever tricks like using an array instead of a dictionary cause you know the upper limit of items

[round glacier]

Like in all honesty, if I ever get to be a senior engineer. I will interview people, and I don't think I will want to hire people who cannot write clean algorithms during tests lol.

[half lotus]

Or sometimes knowing whether an input can be negative or not

[lean hatch]

Hi. I have a statistics question.

[round glacier]

Not trying to be a dick, but I just cannot stand bad variable naming

[lean hatch]

If I have some z-scores and combine them into one z-score, is this a good approach? I have 1 sample so I can't use Stouffer's method.

[round glacier]

@half lotus the only way I would be able to consistently get myself to do these leetcode algorithms is if I joined some bootcamp I think lol

They are just so infuriatingly boring

Lol

And stressful

I would want 1 on 1 support

for this

[half lotus]

I did them consistently for several months with a study buddy. But on my own I have less motivation.

[round glacier]

yeah

I feel you

but even with a study buddy, what if neither of u can solve it lol

[half lotus]

Just look up the solution and discuss

[round glacier]

Also, these things are almost never used in real jobs

like idk

i feel like some of it is

recursion is extremely useful for parsing custom file types for example

if u have a special filetype that has a lot of unique things, recursion is useful