algos-and-data-structs

[haughty mountain]

but some textbooks would complain

[fossil tapir]

ah okay okay

[haughty mountain]

T(1) = 1

[edgy gazelle]

depending on the base cases, T could be different things imo

[edgy gazelle]

whats T(3), T(7), etc.?

[fossil tapir]

the thing is, we were following some author called Cormen. But since the book was too thick, our prof just made her own notes and is teaching us from that

[edgy gazelle]

T could literally be linear (but wouldnt be practical cz its slope would be negative)

[fossil tapir]

we're just asked to apply substitution method on this eqn 💀

[edgy gazelle]

yea but im saying we should have more info than just that?

[fossil tapir]

yea it is also given that T(1) = 1

[haughty mountain]

we could consider 4T(ceil(n/2)) + n instead and avoid the issues I think you're trying to point out

[fossil tapir]

not given but we are supposed to assume that in all the sums

[edgy gazelle]

hmm ok

[haughty mountain]

but it's more sensible to assume that n is a power of 2

it won't matter for the analysis

[edgy gazelle]

if n is a power of 2, (or ceil assumption), we could let n = 2^k?

[fossil tapir]

i think i made a big mistake by choosing this subject 💀

[edgy gazelle]

T(2^k) = 4 T(2^(k-1)) + 2^k
Let P(k) = T(2^k) so we get
P(k) = 4P(k-1) + 2^k

[haughty mountain]

you could, idk if it's that helpful though

[fossil tapir]

@haughty mountain is this log n to the base 2?

[haughty mountain]

that's what I meant, yeah

I think the guess T(n) = cn² - n works

even without ignoring lower order terms

T(n)
 = 4 T(n/2) + n
<= 4 (c (n/2)² - n/2) + n
 = c n² - 2n + n
 = c n² - n

(actually, I think it's kinda even the exact formula)

[edgy gazelle]

Solve: T(n) = 4 T(n/2) + n
Let P(n) = T(2^n). Then P(n) = 4 P(n-1) + 2^n
By substitution, P(n) = 2^(2n+1) - 2^n is a solution.
T(n) = P(log_2 n) = 2^(2 log_2 n + 1) - n = 2n^2 - n

And also P(0)=T(1)=1

algmyr u were right :p quadratic was dead on

[haughty mountain]

fwiw 2n² - n is what my recursive expansion arrives at

I kinda solved the task by expanding the recursion to get my guess...

so you have roughly n + 2n + 4n + ... + 2^log2(n) n

[edgy gazelle]

how'd u know that was quadratic?

just from exp?

[haughty mountain]

I said that's < 2 2^log2(n) n = 2n²

[edgy gazelle]

thats like n * (2^(log2(n)+1)-1) by geometric series ahh

which is exactly 2n^2-n

omg

[haughty mountain]

yeah

[edgy gazelle]

i gotta do this in fall 💀

[fossil tapir]

Yo regarding this, what is <2 in the start?

I understood the rest and how you got n^2

But kinda confused about what <2 is

[fiery cosmos]

im curious how these expansions work

[haughty mountain]

in context

n + 2n + 4n + ... + 2^log2(n) n < 2 2^log2(n) n = 2 n²

[fossil tapir]

He kept diving the eqn by 2

[haughty mountain]

I just use the definition of T(n) to evaluate T(n/2), and then T(n/4), ...

[haughty mountain]

ok, this is where working with n = 2^k would have been nice

  n + 2n + 4n + ... + 2^log2(n) n
= n + 2n + 4n + ... + n n
= 2^k + 2 2^k + 4 2^k + ... + 2^k 2^k
= 2^k (1 + 2 + 4 + ... + 2^k)
```this is kinda what went through my head working on the expression

this latter expression is a geometric sequence

I used that

1 + 2 + 4 + ... + 2^k < 2^(k+1)
```but it's even true that

1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1

oh, I replied wrong earlier...

[haughty mountain]

in context

n + 2n + 4n + ... + 2^log2(n) n < 2 2^log2(n) n = 2 n²

I just mean the < as less than

[fossil tapir]

oh

so thats just something which you assumed right?

[haughty mountain]

no

[fossil tapir]

so how did you get this?

to be precise, the 2 in that

[haughty mountain]

let's get rid of the silly log

n + 2n + 4n + ... + n n

factor out n

[fossil tapir]

i understood that 2^log2(n) n = n^2

[haughty mountain]

= n (1 + 2 + 4 + ... + n)

I claim the thing in () is less than 2n

[fossil tapir]

oh

[fiery cosmos]

@haughty mountain you are a saint for helping all of us tirelessly.. i don't know how you do it

[fossil tapir]

im sorry i still dont get it how you claimed it lesser than 2n

[fossil tapir]

frfr way better than my prof istg

[haughty mountain]

(this mostly makes sense because we assumed n is a power of 2)

[fossil tapir]

oh

[haughty mountain]

are you familiar with geometric series?

[fiery cosmos]

we were going through my prof's remedial material that apparently was just rife with mistakes, making my learning totally torpedoed from the get-go

[fossil tapir]

ah ive studied it but i dont remember it

[haughty mountain]

e.g. 1 + 1/2 + 1/4 + 1/8 + ...

[fiery cosmos]

idk why we get a bunch of academic mathematicians teaching algorithms to begin with, should be software engineers imo

[agile sundial]

algorithms are basically math

[fiery cosmos]

but academia doesn't pay 😂

[fossil tapir]

damn, our database prof is teaching us algorithms and she always complains about how the uni pushed the job onto her 😭

[fossil tapir]

oh yea

this i remember it

[fiery cosmos]

doesn't sound like someone who wants to be teaching

[fossil tapir]

she just plays some ppts and goes home

[fiery cosmos]

eh its academia what do you expect

[fossil tapir]

OH I REMEMBERED ITS GEOMETRIC PROGRESSION

[fossil tapir]

😭 atleast a bit of doubt clearing sessions

[haughty mountain]

I basically used that 1 + 1/2 + 1/4 + ... = 2

[fossil tapir]

ohh

[haughty mountain]

we have a truncated series

[fossil tapir]

damn im dumb asf

[haughty mountain]

to be fair it's a bit hidden as my expression was written

[fossil tapir]

ohh

damn you're pretty quick at these algos

i feel so slow as compared to you

also id like to say, thank you so much for helping me out, and im so sorry for all the trouble!

[fiery cosmos]

we all owe algmyr a debt of gratitude, as well as the other regular contributors here

[fossil tapir]

fr fr never thought ill get my doubts cleared as even my prof gave up on us

[haughty mountain]

I've seen this kind of geometric sequence before a lot, so I just immediately made the jumps here, lol

n + 2n + 4n + ... + 2^log2(n) n < 2 2^log2(n) n = 2 n²

but basically, this is just a geometric sum

[fossil tapir]

ah and the 2 in 2n^2 becomes c right?

for the assumption thing

i think i also need to start remembering these

[haughty mountain]

right, I kinda did stuff roughly, it seemed to be quadratic, so I assumed O(n²)

the c comes from the definition of O

[fossil tapir]

ohh

[haughty mountain]

I missed that the "rough" calculation I did can actually give the exact formula for T(n) though

glad someone else picked up on that

T(n) = 2n² - n

[fossil tapir]

damn tbh im still new to this so its taking some time for me to understand what yall were talking about, btw since how long have you been doing this algorithms thingy?

[haughty mountain]

err, this might be slightly off

[fossil tapir]

yea because 1+2+4+.... gives [(2^n)-1]

nvm idk why it looks wrong

[haughty mountain]

I think what you might do in practice is evaluate T(n) for some values of n to get some numbers to look at, e.g.
T(1) = 1
T(2) = 4T(1) + 2 = 6
T(4) = 4T(2) + 4 = 28
T(8) = 4T(4) + 8 = 120

and kinda guess

[fossil tapir]

ahh

[haughty mountain]

wait, I'm dumb

the formula is correct

I can't do simple arithmetic

that's kinda funny, you learn to do advanced stuff but forget the simplest stuff

[fossil tapir]

true true

[haughty mountain]

I've had it as a hobby for a long time

many years

[fossil tapir]

also uhmm i tried doing it by assuming c n^2 and you're right, that + n is not proving that T(n) <= c n^2

[fossil tapir]

damn thats great man

[fossil tapir]

infact, assuming that T(n) <= c n^3 worked fine 💀

[haughty mountain]

well, it does

but then you show it's O(n³)

[fiery cosmos]

you can upper bound anything with the highest ceiling guess, getting a tight bound is the difficult part

[haughty mountain]

which is true, but not a good bound

[fiery cosmos]

for example obviously some linear search is n which you can show is bounded from above by O(n!), but that's not helpful information, now is it

[haughty mountain]

O(n²) is a much tighter bound

the bound is Θ(n²) actually

i.e. it's the "correct" asymptotic

[edgy gazelle]

both Θ(n²), O(n²) yeaa

[fiery cosmos]

i'm going through my prof's slides again and the amount of in between steps she skips is insane

a lot of hidden algebra going on

which is.. unhelpful

[haughty mountain]

both O and Ω

which means Θ

[edgy gazelle]

yea i was just searching it up L

my bad

[fiery cosmos]

thanks knuth

its bc of him we have to do this crap 😂

[haughty mountain]

a good mental model is that in the world of asymptotics O is ≤, Ω is ≥, and Θ is =

[edgy gazelle]

When handwriting O, you usually finish at the top, and draw a squiggle. Therefore O(n) is the upper bound of the function. To be fair, this one doesn't work with most fonts, but it is the original justification of the names.

n then Ω has line at bottom, Θ has line in middle

[haughty mountain]

I mean, you tend to skip more and more steps as you get used to things

[haughty mountain]

e.g.

[fiery cosmos]

yeah thats fair but not helpful for learners

[haughty mountain]

it's a hard balance to strike

[fiery cosmos]

i'm sure

[edgy gazelle]

i think helps keep the "advanced/new stuff" dense

[haughty mountain]

you have prereqs so you kinda know what steps are trivial and can be skipped

[edgy gazelle]

bc u can always go back to other sources for fundamentals

[fiery cosmos]

its unhelpful for those who did not follow the traditional path from HS->college->grad school

which is, probably most students

[haughty mountain]

what is trivial is very subjective

[fossil tapir]

yea but when i try doing it with O(n^2), theres a + n left behind. Now our prof didnt gloss over it that much and said that + n will get removed at higher input values, but technically i still didnt prove that T(n) <= c n^2

[edgy gazelle]

but if u included pre-req materials inbetween new stuff, the material gets lengthy to a nontrivially large amount

[fiery cosmos]

i last had college algebra in 2008

[edgy gazelle]

ie a prealgebra textbook that showed every single addition/subtraction steps for every problem vs going "3x+4=7" has solution "x=1" immediately

[haughty mountain]

right, I mentioned that earlier

[fossil tapir]

💀 damn i was in 3rd grade or sumn in 2008

[fossil tapir]

yea

i still dont know if it is correct output or not

[edgy gazelle]

i think skimming over is fine. a technical proof uses limits/calculus imo

[haughty mountain]

you could try cn² - bn

(or cn² - n and see magic happen)

[fossil tapir]

oh

[edgy gazelle]

the idea is limit of (n^2-n)/(n^2) = 1

[fossil tapir]

oh okay let me try this 💀

[edgy gazelle]

so they are "basically the same" for infinitely large n

[fossil tapir]

yea she told us the same

ig ill try cn^2-n as algmyr said first, if nothing happened then ill just give up 💀

[haughty mountain]

yeah, when doing this stuff you can be a bit sloppy, you just need to know when you can't be sloppy

[edgy gazelle]

i think learning that its a geometric series is good

chances r ull see it again anyways

[fossil tapir]

yea i think i need to go through my old notebooks

[fossil tapir]

oh damn

[fiery cosmos]

i don't think giving up is a helpful concept to have around. as long as you never give up (in life) you can never truly be a failure

[haughty mountain]

oh yeah, arithmetic and geometric series show up a lot

[fossil tapir]

if nothing works for me, i just mug up the problem

its a bad habit of mine

[fossil tapir]

today i realised that it still has a significance, i thought we learnt that for fun

[fiery cosmos]

i'm not saying its a bad habit, just maybe think of it as tabling it for the moment and coming back later

[fossil tapir]

yea i usually do that

but currently, i dont have much time

my exam starts in a week

[fiery cosmos]

oof

[fossil tapir]

and i havent even started my revision yet 😭

plus all of sudden our previous algo prof went on a maternity leave

so we were without a prof for around 3 weeks

[fiery cosmos]

i'm all online so i'm basically learning everything myself, thank god for algmyr

but lets keep on topic to algos

[fossil tapir]

yea ngl, algmyr is an allrounder, ive seen him help in ai-ml and other field too

also yea, lets stick to algos

XD

[haughty mountain]

||jack of all trades, master of none||

[fiery cosmos]

i think they mean that for people who are like, shitty at the violin and at blacksmithing and disc golf, not someone who is a well rounded software engineer

could just be me though

great to be humble tho

finally solved a recurrence relation using substitution and the associated algebra. now i'm working on understanding what my prof was meaning when saying things like the exact form

first off, T(n) = 2T(n/2) + n gets rewritten to T(n) = 2T(n/2) + θ(n)

assume T(n) = O(1) for sufficiently small n

guess T(n) = θ(nlg(n))

[haughty mountain]

||T(n) = 2T(n/2) + n is merge sort, so it's θ(n log(n))||

[fiery cosmos]

yeah sorry i misinterpreted, what she is claiming is that, if there were asymptotic notation in the recurrence.. here is instead how we'd do it

@haughty mountain may i ask what is the purpose behind expanding a recurrence

[haughty mountain]

fwiw, this was mostly a joke, though it's the kind of thing I typically do if I recognize a recurrence

[haughty mountain]

sometimes you can spot patterns that way

e.g.

T(n) =  2T(n/ 2) + n
     =  4T(n/ 4) + n + n
     =  8T(n/ 8) + n + n + n
     = 16T(n/16) + n + n + n + n

the depth of the recurrence is O(log n), every step adds a term n

so O(n log n)

(actually, I should probably use Θ here, but whatever)

[fiery cosmos]

i see, thank you for this

this is the extra work you have to do to show for the constants

and this is the upper bound case

[haughty mountain]

seems like pretty routine simplifications/rewritings to me

[fiery cosmos]

right, i just haven't seen this and so i didn't know previously how one might accomplish it

last had algebra in '08

oh boy

now we're getting into constants d and d prime

[haughty mountain]

I've done some fun algebra over the years, quantum mechanics has so much greek

[fiery cosmos]

hm looks like you've got some psi and c'' in there (c double prime)

quantum mechanics is pretty hardcore physics

[haughty mountain]

here c''(x) is the second derivative of c(x)

[fiery cosmos]

i guess your education was physics/math/compsci sort of jammed together

ohh

didn't know that

[haughty mountain]

not so much compsci

though in your case d' will just be another constant

[fiery cosmos]

you just intuited my thought and answered before i could type it. once again, wizard

[haughty mountain]

guess who was glad they had software that could compute most of that matrix product so I didn't have to painstakingly write it out?

fun Taylor series

[fiery cosmos]

so you can go through matrix multiplications and find compositions such that x is R related to y and y is S related to z, so that x is RoS related to z yea

maybe that's not necessarily matrix multiplication what i'm thinking of, rather just set relation given two functions

[fringe blaze]

please

i need help

am new to python and all that

[fiery cosmos]

i was just able to plug in a guess of dn³ - d'n² to solve the recurrence T(n) = 8T(n/2) + θ(n²) and actually follow wth was happening, i'm a long way off from doing it on my own but making progress it finally feels like

[fringe blaze]

@fiery cosmos please help me

[fiery cosmos]

i am new myself, if i think i can help i will but there is a strong chance i'll be unable to or give you the wrong answer.. what's up?

[fringe blaze]

in python ther this requests feature you know it?

[fiery cosmos]

no

[fringe blaze]

the one that lets use your code as a browser

import requests?

[fiery cosmos]

just put your entire code/question/etc here someone who knows will see it and help at some point

[fringe blaze]

ok

import requests
import sys

if len (sys.argv) != 2:
sys.exit()

response = requests.get("https://itunes.apple.com/search?entity=song&limit=1&term="+ sys.argv[1])
print(response.json())

[agile sundial]

I don't think it relates to data structures and algorithms

[late jacinth]

Hey, I was wondering if somebody could help me.
I'm trying to calculate the shortest distance between a given point and a given line represented by a start point and a directional vector in 3D. Currently I'm using the scikit-spatial package to do it like that:

lineCurrentCurve = Line(point=[(x, y, z), direction_vector)
distance = lineCurrentCurve.distance_point([x2, y2, z2])

But I would like to be able to do it without that package.

[fringe blaze]

it not working what didi do wrong

[haughty mountain]

ask in #python-discussion

[fiery cosmos]

as @agile sundial said it may not relate to algs

[haughty mountain]

this is not the right channel

[fringe blaze]

if you know help me plz

[fiery cosmos]

#python-discussion

[haughty mountain]

if your line is L and your point if P, you are looking for a point X on L such that L and X-P are perpendicular

which boils down to some linear algebra

[late jacinth]

Yeah that would be the case, but I don't know how to compute it

Online I was able to find some implementations but those are based on a given line segment and I can't really define a line segment because I only have the start of the line and the direction of that line

def min_distance(r: np.ndarray, a: np.ndarray):
    """ Compute the minimal distance between a point and a segment.
    Given a segment of points xa and xb and a point p
    Parameters
    ----------
    r
        xb - xa
    a
        xa - p
    Returns
    -------
    d
        The minimal distance spanning from p to the segment
    """
    min_t = np.clip(-a.dot(r) / (r.dot(r)), 0, 1)
    d = a + min_t * r
    return np.sqrt(d.dot(d))

That would be one of those

[fiery cosmos]

more mistakes:

[jolly mortar]

distance between a+tb and c is |(c-a) x b|

[haughty mountain]

it's basically the same thing for a line but without the clip

[jolly mortar]

assuming b is a unit vector along the directiob

[late jacinth]

So I could use that with

  min_t = (-a.dot(r) / (r.dot(r)), 0, 1)

?

[haughty mountain]

min_t = -a.dot(r) / r.dot(r)

[late jacinth]

r would be the direction vector of my line and a would be the point or vise versa ?

[haughty mountain]

what that says is basically use dot product to project a onto the line, and then normalize

if you normalize r so that it's a unit vector it's just

min_t = -a.dot(r)

[late jacinth]

Seems like it worked, thanks for the help

[haughty mountain]

the clip is just there to make sure that t is between 0 and 1, i.e. on the segment

[late jacinth]

Yeah I was just confused with the whole segment stuff

[fiery cosmos]

why is there so much emphasis placed on function definitions, eg, one to one, onto, correspondence, isomorphic

[opal oriole]

If I don't know how to solve a problem A, but I know how to solve problem B and have found a correspondence between A and B, then I can just solve B instead of A, which solves A via the correspondence.

[fiery cosmos]

hm ok

[opal oriole]

Perhaps an example? You know the log rule log(xy) = log(x) + log(y)?

[fiery cosmos]

i'm more familiar with log(n/2) = log(n)-log(2) but sure lets work with your example

looks like its just the inverse rule anyhow

[opal oriole]

You should know these first 5: https://www.rapidtables.com/math/algebra/Logarithm.html#log-rules

[fiery cosmos]

ok i can review these and rewrite them to get them in my brain but what was your example

so im guessing or assuming that various functions can be evaluated for their one to one or onto characteristics and that some will be one to one, others onto, and others both and thus are known as one to one correspondence

am i thinking about this properly

[opal oriole]

The example I gave counts as a (group) "homomorphism". And it's a very useful one that is used all the time in algebraic manipulations.

Finding such homomorphisms is useful in solving problems (making use of log(xy) = log(x) + log(y) for example to maybe show some big O).

[fiery cosmos]

so one can say that the expressions log(xy) and log(x) + log(y) are homomorphic?

[opal oriole]

Well we are saying that log is a (group) homomorphism, because it matches the pattern (satisfies) of f(x * y) = f(x) . f(y), where * and . can be whatever (operations) (without going into that detail).

I'm going to show where this is going real quick, so we also have exp, and exp(x + y) = exp(x)exp(y), so it's also a homomorphism. And log and exp are inverses of each other, so log has an inverse that is also a homomorphism making log an isomorphism. Now all this is just math jargon and won't make sense until far later. But it suffices to know that knowing of such isomorphisms is very useful. I can make use of these rules described to solve all kinds of algebraic problems.

So finding isomorphisms is often one of the main goals in mathematics. And so math books will place a lot of emphasis on them.

(Some are much more complicated, and some are trivial to find, and finding the hard ones often leads to huge advances in mathematics (and anything that is applying that math, e.g. physics, CS, bio, chem))

[haughty mountain]

*exp(x) * exp(y)

[opal oriole]

Oops, fixed.

[haughty mountain]

but yeah, all the log and exp identities are all two sides of the same coin

[opal oriole]

Right now you are just given a bunch of rules such as the log rules and memorize them, but if you can imagine yourself in a situation in which you did not have rules such as those needed to solve some problem you were trying to solve and had to discover them yourself, you would benefit greatly from the general knowledge of things such as isomorphisms being a thing and that finding them will probably help you.

It would give you something to look for.

[fiery cosmos]

at some point i'm gonna ask y'all to help me implement the graph traversal prints

thanks for that writeup

[tight patio]

how do i find the time complexity of this algorithm

[edgy gazelle]

@tight patio we can first notice that we can ignore the inner if condition (doesnt rly affect time complexity)

[tight patio]

yes we can assume its o(1)

[edgy gazelle]

let T(hours, fee) represent the time (roughly, asymptotically, etc. whatever technical terms) to run hireAI(hours, fee)

note T(h, fee) = T(1, fee) + T(2, fee) + ... + T(h-1, fee)

[tight patio]

so work done outside the recursive function is constant right?

[tight patio]

yep

[edgy gazelle]

so then id just start by trial-and-error looking for a pattern

T(1, fee) is time complexity of O(f) where f is the length of fee

[tight patio]

i have a call tree for this

[edgy gazelle]

ooh

[tight patio]

its kind of a mess

[edgy gazelle]

its ok 👍 i can read it

[tight patio]

looks like it uses backtracking design pattern

[edgy gazelle]

im thinking its related to fibonacci hmm

[tight patio]

if it was divide & conquer, could've use master theorem

[tight patio]

oh yea kinda

[edgy gazelle]

wait so if T(1, fee) = t, then T(2, fee) = 2t?

T(1, fee) goes thru for loop once

T(2, fee) goes thru for loop twice: T(1, fee) and T(0, fee) which both take the same time?

[tight patio]

i guess

btw are you using this method to find the recursive function

or something else

[edgy gazelle]

then T(2, fee) = 2t; T(3, fee) = T(2, fee) + T(1, fee) + T(0, fee) = 4t?

i think it might be T(h, fee) = 2^(h-1) t then?

yea oh sorry it was confusing ahh

so like if u run AI(hours, fee)

[haughty mountain]

this recursion feels exponential, at least this recurrence should rule out any polynomial T

T(n) = T(n-1) + ... + T(0)

[edgy gazelle]

u end up calling AI(hours-1, fee), AI(hours-2, fee), ..., AI(0, fee)

[tight patio]

oh yep
dont think its a efficient algotithm

[edgy gazelle]

so AI(hours, fee) takes time equal to the sum of all these

[haughty mountain]

you can make it O(n) with memoization

[tight patio]

dp?
how

[edgy gazelle]

these tree stuff r rly inefficient fs

[haughty mountain]

because so many overlapping subproblems

[tight patio]

ooh yep

[haughty mountain]

so yeah, dp I guess

[edgy gazelle]

thats also kinda why this reminded me of naive fibonacci (except this one is worse 💀 )

[haughty mountain]

T(n) <= 2^n works

I think

[edgy gazelle]

yup, i used this!
Base case: T(0, fee) = t
Recursion: T(hours, fee) = T(hours-1, fee) + T(hours-2, fee) + ... + T(0, fee)
(some induction/guess gives T(hours, fee) = 2^(h-1) t

[haughty mountain]

the sum on the rhs is 2^n - 1 with that assumption, which is < 2^n

[tight patio]

cool
thats prob right

so is this a brute force

[haughty mountain]

oh right, my thing assumes T(0) = 1

[tight patio]

algorithm?

[haughty mountain]

idk what to call it really

[edgy gazelle]

basically they assumed t=1 if ur comparing it to my sol

[tight patio]

backtracking?

[edgy gazelle]

fuk im so sorry for pronoun assmption algmyr

[haughty mountain]

it screams overlapping dp subproblems that wasn't utilized

[haughty mountain]

meh, use whatever

[edgy gazelle]

good for learning abt algorithm complexity tho

lmao really shows u how much op dp is

[tight patio]

oh i have to design an efficiant verison

[edgy gazelle]

ooh

oh shoot! for a completely correct solution

[tight patio]

Write a more efficient algorithm using one of the advanced design patterns Divide and Conquer, 1D array Dynamic Programming or Backtracking

[edgy gazelle]

we have to take into account that hours <= length of array fee

[tight patio]

i guess dp is easy

[edgy gazelle]

so its actually

O(2^(max(hours, length(fee))))

wait no its not max

[tight patio]

wait
what do you mean by max

[haughty mountain]

is it? the if statement makes it weird

[edgy gazelle]

i got this

its O(2^hours) BUT

[edgy gazelle]

notice how the big if says hours <= length(fee)

[haughty mountain]

if hours > len the thing doesn't run at all 😛

[edgy gazelle]

so if hours > length(fee)

oh ur right function doesnt even run my bad haha

O(2^hours)

[tight patio]

yeah the conditional statement

thats why i thought its backtracking

[haughty mountain]

let's just assume it's in range

[tight patio]

what about the for loop

[edgy gazelle]

if its out of range like algmyr said

the program runs in O(1)

cz it just returns 0

[tight patio]

yep

cool
thanks so much @haughty mountain @edgy gazelle

[haughty mountain]

I'm trying to think what this program even accomplishes

oh fee[i] is the fee if you "offload" i hours of work, I guess?

so the formulation is

dp(h) = max(fee[1]+dp(h-1), ..., fee[h]+ dp(0))

I guess it might be O(n²) with dp actually

but a lot better than 2^n

[tight patio]

oh wait i have the context to the problem

maybe that help??

The AusSmart Farming company hires out an Artificial Intelligence system (AI) for spotting and treating infected tomatoes at maximum cost to various clients with tomato patches. The company charges the following prices for their equipment and expertise which can only be hired for the hours specified in the table below.

Doug from the AusSmart Farming IT department has come up with the following recursive algorithm to determine the maximum money they can earn for their AI agricultural system expertise based on the hourly hire fees per day according to the table.

[haughty mountain]

basically compute dp(0), then compute dp(1) using that, then compute dp(2) using those, ...

dp[0] = 0
dp[1] = max(fee[1]+dp[0])
dp[2] = max(fee[2]+dp[0], fee[1]+dp[1])
... in general ...
dp[n] = max(fee[n-i]+dp[i] for i in range(n))

[tight patio]

wait im confused what do you mean by max again

[haughty mountain]

the largest of the arguments (or largest in sequence)

[edgy gazelle]

just drop max hehe 😉

[tight patio]

ooh
btw is this similar to coin change problem?

[haughty mountain]

idk what typical problem it's closer to tbh

it just feels like a typical dp problem

[edgy gazelle]

if u recall the OG recursice function, u had an inner if condition that made it so u returned the maximum value

it feels more like fibonacci to me, where instead of just adding the last two, i add everything before it

[tight patio]

oh yep

[haughty mountain]

I think this is correct, though maybe it can be sped up, I'm not sure

dp = [0]*(hours + 1)
for h in range(1, hours+1):
  dp[h] = max(fee[h-i]+dp[i] for i in range(h))

# answer: dp[hours]

O(n²)

[tight patio]

this is what i was refering to ^

[tight patio]

this is kinda hard for me to visualise

[edgy gazelle]

yeaaa ok sorry im just seeing the conn

[haughty mountain]

the for loop in your function is that max expression, only it calls the function recursively rather than using previously computed values

[edgy gazelle]

coin change: u wanna minimize the number of coins to add up to a number (change)
the other problem: u wanna consider all the differnt possible "coins" u can have to minimize the amount u pay

[edgy gazelle]

wouldnt ur sol have to assume fee[] is sorted in increasing order tho?

[tight patio]

ooh so your storing maximum money for each hour

[edgy gazelle]

but ig thats O(n log n)

[haughty mountain]

why?

sorting doesn't matter

fee[i] is the cost to reduce h by i

[edgy gazelle]

wait nvm 👍 nvm

[agile sky]

Hi, Im unsure of the following question:

Comment on the suitability of the following hash functions for a dictionary key s
where s is a ASCII character string.
• A random number generator
• The sum of the ASCII values of the characters in the string.
• The sum of the ASCII values of the characters in the string mod 128

Not sure what or how Im suppose to be answering really

[fiery cosmos]

depth first search huh

[fiery cosmos]

i'm going to answer with my trivial understanding, and let the pros critique my answer.
random number gen: not good because you'll need a lot of storage array space to store all the random keys you might end up with, wasting memory
the sum of the ASCII characters in the string: better but would result in many collisions given the same inputs
mod 128: best? but by my previous logic it'd still result in the same collisions, someone wanna weigh in here?

[fervent saddle]

Wouldn't mod 128 limit the size to 128 keys?

I think maybe that's what that option is getting at

Random numbers wouldn't make sense because the hash function can't be random, something that only produces 128 values wouldn't work because then the array would be limited to 128

[agile sundial]

yeah you'd want your hash function to produce a big range, then users would mod if necessary

these are all pretty bad tbh

[fiery cosmos]

is this true

what is the ackermann function used for

[agile sundial]

no, since you could use chaining to get more. it limits you to 128 hash values though

[fervent saddle]

Unless you don't use closed hashing

You're right, what do you call the positions in the array?

"Hash positions"?

[agile sundial]

indexes?

[fervent saddle]

Alright

I wonder if the question is talking about a hash table with 128 possible indexes

[agile sundial]

yeah without knowing the assumptions the question is making it's hard to answer

[haughty mountain]

err, in order:
invalid
valid but terrible
valid but terrible

a decent fun hash for string

h = 0
base = (something larger than 255 because ascii values)
mod = (something large and preferably prime)
for c in string:
    h = (base*h + ord(c))%mod

# hash is h

it's a "polynomial rolling hash" meaning you can actually compute the hash of substrings quickly with some math

[fiery cosmos]

im reading my discrete math book and seeing that there are adjacency matrices and path matrices, might it be better to implement one of these for my graph traversal / path / search algorithms?

[haughty mountain]

e.g. h * pow(base, -k, mod) % mod is the hash of the string without the last k characters

[fiery cosmos]

also does my breadth first search algo seem valid:

#BFS
from collections import deque
import math

vertices = [0,1,2,3,4,5,6,7]
neighbors = [[1,4],[0,5],[3,5,6],[2,6,7],[0],[1,2,6],[2,3,5,7],[3,6]]
predecessors = []
distances = []
colors = []

def BFS(vertices_list,neighbors_list,predecessors_list,distances_list,colors_list,sourcenode):
    for vertex in vertices_list:
        colors.append('white')
        distances.append(math.inf)
        predecessors.append(None)

    colors[sourcenode] = 'grey'
    distances[sourcenode] = 0
    predecessors[sourcenode] = None

    q = deque()
    q.append(sourcenode)

    while q:
        u = q.pop()
        for v in neighbors[u]:
            if colors[v] == 'white':
                colors[v] = 'grey'
                distances[v] = distances[u]+1
                predecessors[v] = u
                q.append(v)
        colors[u] = 'black'

    def traversedAll(colors):
        return all([color != "white" for color in colors])
    

    return (predecessors_list,distances_list,colors_list)
    
i = BFS(vertices,neighbors,predecessors,distances,colors,0)
print(i)

def traversedAll(colors):
    return all([color != "white" for color in colors])

print(traversedAll(colors))

[haughty mountain]

fwiw I wouldn't pass the three empty lists to the function, define them inside and return them to the caller

[fiery cosmos]

ok noted

[haughty mountain]

is the coloring stuff for checking if the graph is bipartite?

oh nvm, it's not

[fiery cosmos]

no its supposed to track discovered / visited / processed nodes

[haughty mountain]

this is a dfs

because you use the deque as a stack

pop and append

for using deque as a queue use either pop_left and append, or pop and append_left

otherwise it looks like I would expect

[fiery cosmos]

ok ty for input

[haughty mountain]

I tend to use a "visited" list or set to make sure I don't backtrack, but the color stuff works as well although a bit overkill

[fiery cosmos]

and critiques

eh thats CLRS i guess

[haughty mountain]

it might be helpful for learning though, seeing the "active" nodes

[fiery cosmos]

what i'd love to do is write in a way to visualize it working or work with paths, i guess i'll get there. alternatively i can simply paste it into that website that shows how it is executing and see each step and variable value

https://pythontutor.com/visualize.html#mode=edit

woah

pretty cool

[haughty mountain]

I use graphviz a bunch for generating images of graphs, though idk how easy it is to have some animation or whatever

[fiery cosmos]

is that a package / library

its actually really freaking cool to see it working on this site, and im going to go and check the distances list to see if its accurate based on the original graph

its totally computing the distances accurately.. amazing

i hate to admit this but i've become interested in math since beginning this course, last night i was watching calculus videos on khan academy

i guess thats a good thing considering the career field im trying to enter

anyway, tysm, back to my discrete math book

[haughty mountain]

a program for visualizing graphs, e.g.

graph {
  a -- b
  b -- c
  c -- a
  c -- d
}

and you can add edge labels, colors and whatnot

I frequently hack together some code that generates such files so I can visualize stuff

[fiery cosmos]

is it its own executable or does it run off of python or some other language?

oh i see its its own exe

[haughty mountain]

graphviz is both a library and a command line program

though I usually just use the command line things

[fiery cosmos]

are you on linux

[haughty mountain]

yes

[fiery cosmos]

i figured

[haughty mountain]

lol

[fiery cosmos]

i mean, i think i do have ubuntu or something, but best to keep things simple for now

actually i was going to partition a drive and make a for real linux subshell but i guess thats not necessary today

[haughty mountain]

e.g. this is the kind of thing I've written a lot

python program.py | dot -Tpng > out.png

program.py outputs a graphviz file, then I pipe that to the program that renders it, and put the output in a file

[fiery cosmos]

i recognize the pipe command.. is that.. bash?

yea googled

But back to my original ?.. should I try to implement an adjacency matrix for any reason.. is it easy enough to add certain path and traversal features to what I already have?

[haughty mountain]

adjacency matrix isn't really useful most of the time, adjacency lists are just nicer to work with

[fiery cosmos]

The distance it is computing.. there are no inherent properties of that correct just like a distance, eg could there be a shorter distance between the source node and the node at index i

I guess path traversal algos are a whole different thing

[haughty mountain]

if you do a bfs and you have an unweighted graph the distances will be the shortest ones

[fiery cosmos]

Ok

[haughty mountain]

traversal stuff is pretty separate from the description of the graph

like, given a graph and a start node you can make whatever traversal

my goto structure for dfs/bfs and even Dijkstra-like traversal is

visited = set()
while not container:
  cur = container.pop()
  if cur in visited:
    continue
  visited.add(cur)
  for neigh in adj[cur]:
    container.push(neigh)

the only thing that changes between the three versions is what container is

if it works as a
stack -> dfs
queue -> bfs
priority queue -> "Dijkstra"

then you can of course add a bunch of extra stuff as needed, keeping track of distances or whatever you like

[fiery cosmos]

so the code representing the graph is largely unchanged and you simply modify your traversal code

[haughty mountain]

right

if you have to introduce weights or similar you might need to slightly change the graph representation somewhat

but otherwise it tends to be pretty unchanged

[fiery cosmos]

unless i am mistaken, you could simply add another array weight = [0_weight,1_weight,2_weight...n_weight]

ah no you'd need edges for weights

hmm i have an edge generator but it was based on my previous structure using a dictionary. i'll have to figure out how to generate edges using the array based approach

[haughty mountain]

you can have a dict mapping from pairs of nodes to weights

or store the weight in the adjacency list

alongside the index of the neighbor

[fiery cosmos]

ok no i have an edge generator in my notes:

vertices = [0,1,2,3,4]
neighbors = [[1,4],[0,2,3,4],[1,3],[1,2,4],[0,1,3]]
edges = []

for node, neighs in enumerate(neighbors):
    for neigh in neighs:
        if node<neigh:
            edges.append((node,neigh))

print(edges)

[haughty mountain]

I wrote something similar a bit back

not that you really need an edge list most of the time

[fiery cosmos]

is this stuff that gets worked out in data structures

[haughty mountain]

what stuff exactly?

I guess adjacency lists and similar are data structures for representing a graph yes

[fiery cosmos]

like, representing weighted / directed graphs in memory

[haughty mountain]

how you choose to represent your data is what data structures is all about

[fiery cosmos]

i like the approach for storing the weight of an edge with a node's neighbor in a tuple, so like nodes = [0] and neighbors = [(1,3)] would read that node 0 is neighbors with node 1 with an edge weight of 3

what about direction

[haughty mountain]

adjacency lists can do directions already

in fact they kinda always do directions

you model an undirected edge as two directed ones

[fiery cosmos]

right so like (1,3),(3,1)

or in my case nodes = [0,1] neighbors = [1,0]

[haughty mountain]

a directed graph with weights
[[(1, 10), (2, 20)], [(2, 30)], []]

1 --10-> 2 --30-> 3
|                 ^
+------20---------+

making ascii art graphs is terribe

[fiery cosmos]

yeah im seeing it here, the adjacency list represents node: neighbor, neighbors where node --> neighbor

[fiery cosmos]

i tried getting graphvis .exe running on my PC, didn't work, i'll tinker some more

[fiery cosmos]

yeah i gotta get that running

[haughty mountain]

didn't work in what sense?

[fiery cosmos]

in that i tried installing the .exe and it totally just, doesn't appear in my progs and when i find the folder there are a bunch of different apps that just run the cmd prompt and don't do anything. i will install for ubuntu

[haughty mountain]

did you try running them from a terminal with flags?

I'm assuming you have a dot.exe or something

[fiery cosmos]

ok i could do that where will it output to

[haughty mountain]

so put this in a file e.g. graph.dot and then you should be able to run dot -Tpng graph.dot > graph.png

I think windows has the same redirection syntax

dot -Tpng graph.dot -O should also generate graph.png

combining the input file name and the chosen type

[fiery cosmos]

i think you're greatly overestimating how user friendly windows can be

[haughty mountain]

oh, I don't find it in docs, but "-o output_file" also works

[fiery cosmos]

i cannot save where i want as i don't have 'administrator privileges' (i built the machine and installed windows myself and im the only user)

the scope in windows is always messed up like it never knows where you want to point at

maybe if i put the full file path where graph.dot is

[haughty mountain]

that or use the full path to the program

(or edit the PATH variable)

[fiery cosmos]

i couldnt save graph.dot into the graphviz folder 😠

[haughty mountain]

wait, does graph.dot exist there or not?

(regardless you probably want to put the files elsewhere)

[opal oriole]

If the graphviz folder is in your programs directory on WIndows you can't edit stuff in it without admin permissions.

[fiery cosmos]

it exists in my MyDocuments folder, wherever that is..

[opal oriole]

Save the file to somewhere in your home directory.

[fiery cosmos]

wdym home

tried saving on the root of the hard drive, not allowed

[opal oriole]

Every user on the PC has a home directory, which contains directories such as My Documents, Videos, etc.

[haughty mountain]

C:\Users\username\My Documents or something

[opal oriole]

And Desktop.

[haughty mountain]

it's been a good while since I used windows

(close to a decade 👴 )

[opal oriole]

I have not touched Windows in years either, but I doubt this has changed in Windows 11.

[fiery cosmos]

yeah its already there in C:\Users\me\mydocs

wait there it went

[haughty mountain]

[fiery cosmos]

very cool

[haughty mountain]

woo

[fiery cosmos]

now my profs will be pleased at my stellar visuals

[haughty mountain]

(now as practice write a program that takes a graph description and generates a graphwiz file)

[fiery cosmos]

thats a good idea

[haughty mountain]

it's not too hard

and it's pretty useful code to have

[fiery cosmos]

i'd love to do that, and it'd be much more fun than what i'm doing now, but i have to get through this discrete math book

i've just turned my attn to this bc im on the chapter about directed graphs

eh i feel like i should work on that while you're around

im gonna get back to my reading i will work on that code this evening

thanks again

which graph command would i use to represent one that looks like this:

for example, to make the graphs above we used the digraph command

i mean, this is also a digraph so i suppose that cmd is the proper one

just won't have weights

[haughty mountain]

yeah, digraph and you can just leave out the attributes

i.e. don't give the [...] at all

!e

adj = {
  'A': ['B', 'E', 'F'],
  'B': ['E', 'L'],
  'C': ['D', 'E', 'J'],
  'D': ['E'],
  'E': ['F'],
  'F': ['D'],
  'J': ['D', 'K'],
  'K': ['C', 'L'],
  'L': ['C', 'E'],
}

print('digraph {')
for node in adj:
  for neigh in adj[node]:
    print(f'  {node}->{neigh}')
print('}')

[halcyon plank]

@haughty mountain :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | digraph {
002 |   A->B
003 |   A->E
004 |   A->F
005 |   B->E
006 |   B->L
007 |   C->D
008 |   C->E
009 |   C->J
010 |   D->E
011 |   E->F
... (truncated - too many lines)

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

[haughty mountain]

finally

[rough lynx]

So I've been given a heads up for an interview that I'm going to tomorrow, and the question will be along the lines of parsing a log file for a specific phrase
Normally I'd be fine with looping over each line of a log and possibly using regex to look for specific phrases, but I'm going in under the assumption that the interviewer will throw me a curve ball like "the log file is incredibly big and will take a long time to parse line by line", so I want to think of a solution for that ahead of time

My first guess would be to use some async / multithreading solution, where each line is read and sent to a different thread to read / parse the requisite phrases as needed. This would certainly help, but now I'm wondering if they'll say that async / multithreading is also of limits - what else can I do to more optimally look through a file for a specific phrase?

[haughty mountain]

||grep||

[rough lynx]

Aside from external apps like grep

I assume it'd be doing it in python natively, and they could also say stuff like "no external apps"

[haughty mountain]

try neato layout instead

instead of dot

it should be a bit neater

[fiery cosmos]

graph.neato?

[haughty mountain]

no there should be a neato.exe

[fiery cosmos]

whats the calling argument then

[haughty mountain]

same

you're just switching the layout is tries to use

[haughty mountain]

you can also play with node shapes and whatnot

[fiery cosmos]

yeah i'll have to hit up the readme

[haughty mountain]

e.g.

[fiery cosmos]

i'm guessing you specified that within the graph.dot file

[haughty mountain]

digraph {
  node [shape=circle]
  ...
}

[fiery cosmos]

dang i really want to write that program you recommended 😂

[haughty mountain]

so this basically 😛

[fiery cosmos]

i'm going to modify it to handle saving that output as the text file.. don't give it away 😂

[haughty mountain]

hint: ||print can take a file argument||

[fiery cosmos]

🤔

will i need the open argument

[haughty mountain]

with open('some_file_name') as f:
  print('hi', file=f)

[fiery cosmos]

what is the close file command.. f.close? close(f)?

so weird its not working

[haughty mountain]

with open('graph.dot.txt','w') as f:
    print('digraph {',file=f)
    for node in adj:
        for neigh in adj[node]:
            print(f'  {node}->{neigh}', file=f)
    print('}', file=f)

[fiery cosmos]

its working!! very cool

alright, now im for real going back to discrete

ttyl

[lost gulch]

Where I can learn bout algos any recommendation

?

[lost gulch]

thnk u 😅

that was kinda hillarious tbh

felt like stupid xD

[fiery cosmos]

im wondering if i should try to implement these simpler graph traversals in my discrete book, for example, they show that they can solve a flights between cities with shortest numbers of stops problem

np, wasn't my intention, its just not helpful to say pins if you're not familiar with discord

happy learning

also one thing i haven't even begun to breach yet in my learning is boundary cases and try/except blocks

[halcyon plank]

:incoming_envelope: :ok_hand: applied mute to @trail viper until <t:1660767440:f> (9 minutes and 59 seconds) (reason: duplicates rule: sent 4 duplicated messages in 10s).

[fiery cosmos]

how would i unpack this type of weight code wise

i think before we used enumerate to unpack tuples

[haughty mountain]

enumerate is not to unpack

enumerate creates tuples with (index, element)

for neigh, weight in adj[node]:
  ...

is probably what you're after

[fiery cosmos]

perfect ty

just wanted a stickynote of that before i start on the binary trees chapter. i feel like i should linger and really understand directed graphs but i have a lot of ground to cover

plus it'd be cool to solve a real world example e.g. the plane exchanges and cities shortest route

and im sure i'll be asked some sort of problem like that during my course

there are a lot of cool directed weighted graphs to test say the pruning algorithm with

still don't know what the ackermann function* is for

[haughty mountain]

I don't think you need to care about the ackermann function

[fiery cosmos]

oh i don't, just curiousity

[haughty mountain]

it's mostly just a curiosity, a very expensive thing to compute

though it kinda shows up in some time complexity analysis

[fiery cosmos]

afaik it was about demonstrating computability by reproducing the basic arithmetic operations

[haughty mountain]

disjoint set union has an amortised time complexity per operation of O(inverse_ackermann(n))

[fiery cosmos]

dang glad you reminded me.. gotta learn amortization

[haughty mountain]

which is basically a constant, since the ackermann function gets ridiculously large very quickly

it's not weird as a concept

it's just the average cost

[fiery cosmos]

i understand memoization but haven't implemented anything yet

[fiery cosmos]

makes sense. i know in finance they talk about x$ or % return amortized over y time

[haughty mountain]

amortization is useful when you have occasional expensive operations, e.g. appending to a list

you intentionally make the memory reserved for the list larger than you need to so you don't have to resize so often

e.g. 2x the size you really need at that moment

then on average (amortized) append is O(1)

but worst case O(n)

[fiery cosmos]

hmm yes this is vaguely familiar from some CLRS readings..

what are these like random or permutation searches where you pass an array and a search term and select a random element from the array and return the search term's location if it exists otherwise call the algo again recursively

[haughty mountain]

not sure what you're referring to

it sounds like a somewhat off explanation of quickselect

[fiery cosmos]

is that really faster on avg than a linear search

[haughty mountain]

quickselect isn't really a search algo though

you can use it to find stuff like the kth smallest element

[fiery cosmos]

ok ok

[haughty mountain]

is it even that you were talking about?

[fiery cosmos]

i'll have to find it again. it was like a permutation select out of this really old discrete text

alright i want to try to modify my existing BFS into a DFS and solve this graph (i'm going to generate) for the shortest path between two points (s,t)

[agile sundial]

wouldn't you use bfs for that

[haughty mountain]

DFS is not what you want for shortest path

[fiery cosmos]

hmm

[haughty mountain]

remember that in an undirected graph a bfs explores stuff in distance order from the start

dfs will just go all out in some direction (hence depth first)

[fiery cosmos]

here's my graph, going to write an adjacency list

[haughty mountain]

if you have a list of edges you can generate the adjacency list

[fiery cosmos]

ugh the mapping btwn letters and indices is annoying

[agile sundial]

easiest way to do it in this case is just ord(the_letter) - 65

[haughty mountain]

in this case, sure

[opal oriole]

If it's just ASCII values.

[haughty mountain]

well, ord

but close

[agile sundial]

ah, always get those mixed up 😔

[haughty mountain]

ord as in ordinal

[fiery cosmos]

lowercase? does it matter?

[haughty mountain]

97 for lowercase

[agile sundial]

it does matter since it would change the second number, because "a" and "A" have separate ascii values

[haughty mountain]

or just subtract ord('a') to not have to think

[opal oriole]

https://www.asciitable.com/

You can see lowercase starts at 97.

[haughty mountain]

I think most people here have seen me write about how neat the ascii layout is

basically A is 1, B is 2 and so on, but we set some high bits

[agile sundial]

and lowercase is just setting another bit

[haughty mountain]

e.g.

A = 0b01000000
a = 0b01100000

[fiery cosmos]

omg i made this so confusing by using non contiguous integers and alphanumeric characterts

characters

eg 0=a but 9=s

[haughty mountain]

and 0-9 is 0-9 with some high bits set

0 = 0b00110000

I mean, you could go with using strings as labels as well

and use dicts all over the place

if you map stuff to indices you can also map them back to labels when printing

[fiery cosmos]

let me rewrite using ints as node labels

[opal oriole]

If you have used A-Z or a-z, you already have that.

Just subtract 65 or 97.

If you are using whatever other symbols or strings for the labels then use a dict.

[haughty mountain]

(or generate a mapping)

[hoary stratus]

hello

mind if i show you some of my work?

[fiery cosmos]

https://tenor.com/view/relief-phew-gif-22113399

[haughty mountain]

I sense you're not as allergic to manual labor as I am 😛

automate all the things

[fiery cosmos]

oh i am i just don't know how to overcome it yet. right now i'm writing in the neighbors with weights as tuples list

i'll need to learn to automate this in the future bc this is highly error prone

especially when node 7 has zero neighbors and so needs its own empty list

whew ok i have neighbors with weights adjacency list

i'm already keeping track of predecessors

hm but y'all said this won't be a BFS or DFS

[haughty mountain]

ah, this is a weighted graph

[fiery cosmos]

and directed

[haughty mountain]

directed doesn't really matter much for these traversal algos

[fiery cosmos]

fair enough. right now i need to modify my traversal to unpack the weights

[haughty mountain]

so, you will want a priority queue as your container

[fiery cosmos]

so i need a heap

heapq

[haughty mountain]

but other than that the difference from a dfs or a bfs is minimal

right

[fiery cosmos]

hm, vscode automatically writes your import call if you write in heapq. thats neat

[haughty mountain]

neat until is imports some random thing you didn't actually want to import 😛

[fiery cosmos]

true true

should i make another array for weights?

oh no i already have distances

[haughty mountain]

by weights you mean the edge weights?

didn't you add those to your adjacency list?

[fiery cosmos]

yes. i just need to modify this line:

distances[v] = distances[u]+1

to instead add the weight of the edge instead of that 1 there

interpreting this rn:

[haughty mountain]

so adj[node] is a list like [(node, weight), (node, weight), ...]

[fiery cosmos]

neighbors_n_weights = [[(1,3),(5,5),(4,1)],[(2,4),(5,1)],[(7,4),(6,1)],[(0,4),(4,6),(8,2)],[(5,4),(9,2),(8,3)],[(2,2),(6,4),(10,3)],[(7,2),(10,2)],[],[(9,6)],[(5,1),(10,4)],[(7,3)]]```

[haughty mountain]

e.g. if you look at your first element it's [(1,3),(5,5),(4,1)]

which should be a bunch of (node, weight) pairs

[fiery cosmos]

right

[haughty mountain]

when you iterate over them you can unpack the tuple

[fiery cosmos]

i changed q to heapq

oh i have no destination node

i want to know the shortest path from 3 --> 7

[haughty mountain]

heapq is not a container, it's operations you can do to a list

e.g. u = heapq.heappop(q)

[fiery cosmos]

hmm

[haughty mountain]

heapq.heappush(q, v)

you could easily wrap it into a class

e.g.

class PrioQueue:
  def __init__(self):
    self.data = []
  def push(self, value):
    heapq.heappush(self.data, value)
  def pop(self):
    return heapq.heappop(self.data)
  def __len__(self):
    return len(self.data)
  def __bool__(self):
    return len(self.data) > 0

oh, and you need to put the distance into the priority queue

[fiery cosmos]

do you mean put this class inside of the function call

sry

inside of the body of the function

[haughty mountain]

huh? no

just put it somewhere in the beginning of the code

what I meant is that you need to push (distance, node) tuples into the priority queue

because it will order by the values of the tuple, and you want it to be ordered by distance

[fiery cosmos]

hey i have to help my dad a sec, brb

tysm for your help thus far

[haughty mountain]

discord doesn't allow to spoiler code, does it...

[halcyon plank]

Hey @haughty mountain!

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

[haughty mountain]

oh ffs

https://paste.pythondiscord.com/kefezevado

[fiery cosmos]

lol

well as usual i will go and study what you have written to understand how it works. sadly my first graph traversal algorithm that was previously printing the correct distance between any inputted start node is no longer, i shouldn't have modified that algo

hey can use graphviz for undirected graphs and what would the graph.dot file look like

i got it

[haughty mountain]

^

[idle pier]

Hello folks currently doing 450. Delete Node in a BST on Leetcode.
I was having trouble solving it so I looked up the solution

def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
            
        if root.val > key:
            # Target node is smaller than currnet node, search left subtree
            
            root.left = self.deleteNode( root.left, key )

        elif root.val < key:
            # Target node is larger than currnet node, search right subtree
            
            root.right = self.deleteNode( root.right, key )

        else:
            # Current node is target node
            
            if (not root.left) or (not root.right):
                # At least one child is empty
                # Target node is replaced by either non-empty child or None
                root = root.left if root.left else root.right

            else:
                # Both two childs exist
                # Target node is replaced by smallest element of right subtree
                cur = root.right

                while cur.left:
                    cur = cur.left

                root.val = cur.val
                root.right = self.deleteNode( root.right, cur.val )
                    
        return root```
I'm having trouble understanding the last `else` statement, when 2 childs exist

[gaunt harbor]

hello, can i get some help? everytime i run my code i get a memory error

[summer fossil]

https://www.codechef.com/submit/KLIP

how to solve this

which topic is used?

[tight patio]

hi sorry
im still confuse about this part

fee[h-i]+dp[i] for i in range(h)
what is the second loop doing?

i've only done theory for dp
first time implementing
so bit confuse

[haughty mountain]

you know the loop you had in the image you posted? basically

max_fee = 0
for i in range(h):
  thisfee = fee[i] + dp[h-i]
  if thisfee > max_fee:
    max_fee = thisfee
```(but with a recursive call instead of the dp array access). The max with the generator expression does the same thing as the loop

i.e.

max_fee = max(fee[i] + dp[h-i] for i in range(h))

[tight patio]

oh its replace the recursive call

and you can get the answer by indexing the dp right?

[tight patio]

so if i "expand" this
would look something like thus?

maxfee ← 0
        for i in 1 to h:
            thisfee = fee[j]+dp[h-i]
            if thisfee > maxfee:
                 maxfee ← this fee
         dp[h] = maxfee

assume index start at 1

[haughty mountain]

something like that yeah

ah, I might have a bug

[haughty mountain]

it should be this

max(fee[i] + dp[h-i] for i in range(1, h+1)) 

my range wasn't quite right

[summer fossil]

plz reply me

[haughty mountain]

very greedy, make as many ones as you can, the only detail is optimizing so that you don't actually flip bits, which would be O(N K)

and there should be an editorial out

[narrow yarrow]

hello i need some support to help me configure python 3.8.2 with selenium and chrome drive i can give nitro lifetime for help!

[fiery cosmos]

is this an error?

[jolly mortar]

log(a/b) = log a - log b

[fiery cosmos]

i'd think it would become nlg(n)-nlg(2)

[jolly mortar]

thats what it is

[fiery cosmos]

ok

[opal oriole]

nlg(n)-nlg(2) = n(lg(n)-lg(2))

You can add parenthesis around stuff, so you can think of what they did as: nlg(n/2) = n(lg(n/2)) = n(lg(n)-lg(2)).

[fiery cosmos]

right i just thought it was going to simplify incorrectly but it worked

[shadow plume]

anyone have a recommended geopandas tutorial? Also is there a better channel to post this in ?

[real blade]

Can someone tell me how can I make infinite loop in python

[glossy breach]

while True

[cunning ocean]

Data has been encoded using an odd-parity SECDED code. The hexadecimal
value was then retrieved as 883. If there was an error, either correct it and report the
corrected ASCII character or explain why it could not be corrected.
Showing your Hamming/SECDED table steps including the bits covered by each parity
bit in your answer.
To obtain the original data binary string, you need to remove the parity bits.

can anyone help

[burnt trellis]

anyone have any idea how to get the ID of a file? i took sometime to search it up and the only i found is to use os.popen but that doesnt work either so :/

nvm it worked

[fiery cosmos]

is this mistake? one would think the equality would only hold if that -dn(lg(3)-2/3)+cn term were positive, eg, dnlgn could only be greater if you have dnlgn - something on the previous line

hmm maybe it could make sense if one included the negative sign out front

nvm i think im getting caught on semantics

[haughty mountain]

they have d n lg n + something

where something <= 0

[haughty mountain]

(i.e. something = -dn(lg3 - 2/3) + cn)

basically "take all that is not the term we want, is that <= 0?"

[fiery cosmos]

Yeah it checks out if you make the entire thing less than zero (including minus sign) or if you make the thing positive (not including minus sign) so you’re subtracting something positive. Either way works

[haughty mountain]

you could rewrite things like

  dn lg n -  dn(lg3 - 2/3) + cn
= dn lg n - (dn(lg3 - 2/3) - cn)

note that you need to change sign of cn if you put it inside the () being subtracted

[fiery cosmos]

one thing that was not explained in the video was why a recursion tree terminates at a certain depth

[haughty mountain]

because base cases

I think a reasonable assumption is that T(constant) = constant

[fiery cosmos]

do you mean like T(n) = O(n)?

[haughty mountain]

not if you think n is allowed to be not a constant

in sloppy words I mean T(O(1)) = O(1)

[fiery cosmos]

the time complexity of a constant is a constant

[haughty mountain]

like, in fibonacci you might have base cases like f(0) = 0, f(1) = 1

boring base cases

doesn't really matter for the complexity

you just can't have something that scales weirdly for small values

actually, it might only matter that they aren't ∞

regardless, you come down to cheap base cases

that's why the recursion terminates

e.g. something like merge sort T(n) = 2T(n/2) + n has a base case something like T(1) = 1

"if array is 1 long don't really do any work, it's already sorted"

[fiery cosmos]

ah yes the old trivially sorted n of 1

can you help me see how this works

[haughty mountain]

what is f here?

[fiery cosmos]

its not really clear, its f(n/b) from the master theorem

the part that is typically written aT(n/b)

the expression capturing the recurrence bit

[haughty mountain]

feels like there some context missing

could you share a bigger screenshot with stuff before it?

[fiery cosmos]

we have wound up in case 3 of master theorem and case 3 means we have an additional conditional; check whether af(n/b) < cf(n) for c<1

sure

[haughty mountain]

I'm confused by

err, without the c, didn't mean to circle that

[fiery cosmos]

they're claiming it works when c is greater than 0.5

[haughty mountain]

there is some serious lacking whitespace there

[fiery cosmos]

true but i have the audio so its np

[haughty mountain]

(I don't, so it was confusing without context)

[fiery cosmos]

yes my bad

[haughty mountain]

I read it as ^.5

which was...weird

[fiery cosmos]

yeah sry bout that

the next thing im confused by is the claim that n^(log_2(5)) is polynomially larger than n^2

[haughty mountain]

what they write sure isn't true for all functions f

oh, f(n) = n^2

2(n/2)^2 = n^2/2 < c n^2

if c > 1/2

[haughty mountain]

why is it surprising?

without using a calculator or similar, can you say anything about the value of log_2(5)?

[fiery cosmos]

btwn 2-3

[haughty mountain]

right, it's for sure > 2

[fiery cosmos]

yes

alright i need to learn what is meant by polynomially larger then

[haughty mountain]

well, that's it

check the highest exponent in the polynomial

x^a is polynomially larger than x^b if a > b

not that weird

[fiery cosmos]

no its not, i would have understood had they just said larger

that extra term makes it sound like there is some special condition that must hold or some

[outer aspen]

msg = 'Welcome my friend'
print(f'{len(msg):<10}' + msg)
```can someone tell me what that means

esp this

[runic tinsel]

it means add spaces on the right side

[haughty mountain]

it's not necessarily larger though, unless you look at large values

e.g. x^2 < x for small x

but x^2 is polynomially larger

asymptotically larger

[fiery cosmos]

right right i just looked at 0.5^2 and 0.5^2.5

[haughty mountain]

what they basically mean is asymptotics

[fiery cosmos]

could you explain in english

i'm still not really grasping this

[haughty mountain]

e.g. if you have two polynomials p(x) and q(x), if |p(x)|/|q(x)| tends to 0 as x gets large q(x) is "larger"

if it tends to ∞ p(x) is "larger"

[haughty mountain]

you get the first equality, right?

I guess to do things step by step, this is the criterion to check

a f(n/b) < c f(n)

in your example a = 2, b = 2, f(n) = n^2

so we are checking

2(n/2)^2 < c n^2

we can rewrite the left hand side to get

n^2/2 < c n^2

now it should be easy to see that this is true if c > 1/2

[fiery cosmos]

yes i see it now for sure

ty

[fiery cosmos]

what is this lg^2 doing in the final expression

[haughty mountain]

log^2(n) = (log(n))^2

[fiery cosmos]

the only log^exponent expression in case 2 of master theorem was already fulfilled with the n^3 factor. there is no n^(log_b(a)) * lg^(somepower)) or similar

dude.. this must be +3, i need a sanity check

[opal oriole]

Is this not from that work that algmyr already pointed out a ton of errors in?

[fiery cosmos]

i mean, a lot of it is correct, there are hours of this stuff

and its the only examples i have to learn from, so i'd rather just work through and find and understand the errors

[haughty mountain]

the log^2 is correct I think

wiki version of the master theorem case 2

[fiery cosmos]

🤦‍♂️

thanks

i had heard that "online school" was an afterthought for most unis, this confirms it

[haughty mountain]

oh lol, that's for sure an error

[fiery cosmos]

feel like im taking crazy pills

[opal oriole]

I guess it gives you more practice with algebra.

[haughty mountain]

keeps you on your toes 👀

[fiery cosmos]

thats true but i have bigger fish to fry and idk how much of my grade will actually come down to substitution proofs / master theorem. i did get really good at working the substitution proofs involving recurrences and asymptotic expressions

[opal oriole]

As for this, the extra lg comes from the f(n), see case 2.

[haughty mountain]

tbh I don't have the master theorem memorized at all

if I need it I look it up

it's good to know how to use it if you need to though

[opal oriole]

It's not exactly the kind of thing mathematicians like to memorize, too many cases.

[haughty mountain]

I also don't recall how to derive it, but at least I know how to use it as a tool if forced to 😛

[fiery cosmos]

we literally skip the proof of it, we're not mathematicians

[haughty mountain]

I've seen the proof in one algo course I took I think

[fiery cosmos]

its in CLRS

[haughty mountain]

but from what I recall it's a bit messy because of all the cases

[opal oriole]

(Not a fun kind of thing to prove)

(Computer assistance helps a lot with this)

[fiery cosmos]

i don't think i have any sort of heapsort working yet, i do have a binary tree working, class based

my graph representation is really sloppy 😂

a bunch of parallel arrays

[opal oriole]

Are you using a generic graph representation for trees? Because trees can be done in a much more simple way.

[fiery cosmos]

those were separate points

[haughty mountain]

iirc you expand the recursion and then analyze this expression for various forms of f

[fiery cosmos]

my binary tree is Class based, my graphs are essentially just a bunch of parallel arrays. i'm going over heapsort now which made me wonder what my version of a tree looks like

[haughty mountain]

actually...the sum is not to ∞, is it?

[opal oriole]

You could just only do the cases you care about. Don't need to list them all to make the full master theorem.

[haughty mountain]

it's to some log

something like log_b(n)

I think this

you can do this sum directly to solve stuff I guess

if you want

[opal oriole]

Seems correct, but i'm only wondering about floor or ceil.

I'm too lazy to write up examples right now to play with.

[fiery cosmos]

did y'all know deque supports the copy() method

[haughty mountain]

e.g. f(n) = n, a = 2, b = 2

[fiery cosmos]

how does deque indexing work given that you can append to either side? does it shift?

[haughty mountain]

it does

and indexing is O(n)

because it's basically a linked list

[fiery cosmos]

um, is it re-indexed every time something is appended or popped?

and if so wouldn't popping or appending take n time since you have to re-index

[haughty mountain]

you don't re-index

but the indices change

you can't really index into a deque just like you would a list

with a list you can just jump to the ith element

[fiery cosmos]

ohh you mean the method index() takes O(n) times

time*

i gotcha

well that makes sense

[haughty mountain]

with a deque you have to walk something like i steps to get to the element

[haughty mountain]

right

my_deque[i] takes O(i) time

[fiery cosmos]

sort of neat that one can rotate the deque

[haughty mountain]

(method __getitem__, but details)

[haughty mountain]

i.e. a push and a pop 😛

[fiery cosmos]

right thats essentially rotating the deque one way or the other

hm im not seeing push in the documentation

you mean analogous to append?

[haughty mountain]

pop/appendleft or popleft/append, yeah

[fiery cosmos]

ok. its all new to me im just trying to get my bearings

[haughty mountain]

when you talk about queue as an abstract data structure you tend to talk about pop and push

[fiery cosmos]

i need to spend more time in the python documentation before asking questions, i've found

[haughty mountain]

so it's just me not speaking snake right know

[opal oriole]

Some libraries/languages like to use push, and others like to use append. Just word choice.

[haughty mountain]

appendleft is kinda silly though

[opal oriole]

Yeah.

[fiery cosmos]

speaking snake

[haughty mountain]

rather than prepend

or whatever

[opal oriole]

I mean people understand it though so it's kind of whatever.

[haughty mountain]

C++ uses push_back and push_front which is at least less silly

[opal oriole]

Yeah but on the other hand, C++ thinks dynamic arrays are "vector"s.

[haughty mountain]

and thinks list is a linked list

[fiery cosmos]

so deque seems to make sense in my head, and stack is analogous to like plates on a spring stack at a cafeteria, and queue is like people waiting at a bus stop.. any way i should be thinking about the three of these in relation to one another?

[haughty mountain]

a deque can act both as a stack or a queue depending on how you use it

but yeah, stack and queue are quite good names, they describe pretty well how they behave

[opal oriole]

Python has pretty decent naming (mostly), it's not C++. Deque can be used for multiple things, it's a bit generic in that way.

[fiery cosmos]

a stack or a queue?

[haughty mountain]

ah, typo

[fiery cosmos]

i'm so excited to get further into the world of software engineering, i hope this course doesn't prevent me from walking that path ☠️ ☠️ ☠️

too much theory, not enough actual coding

i think i need to take some time and play around w heapq

[jolly crypt]

why is time complexity of computing the maximum of the depth of each leaf in a tree proportional to n^2? What would be a configuration of a tree with n nodes that results in this? Like i know the depth() of a leaf is computed in the worst case in O(n) (in the case the tree is a single branch), but generally the depth of a node is computed in O(d_p + 1) where d_p is the depth of p

[haughty mountain]

why is time complexity of computing the maximum of the depth of each leaf in a tree proportional to n^2?
you can do that in O(n)

if you compute the depth for every leaf individually it could be O(n^2) yeah

but you don't need to do that

[jolly crypt]

yh, but how? Like worst case for depth(leaf) is O(n), for worst case O(n^2) i would need n leaves to get O(n*n) but then how do i get a configuration with just n nodes that results in O(n^2). Maybe i am just getting confused lol

[frank vault]

https://leetcode.com/problems/jump-game/

def canJump(self, nums: List[int]) -> bool:
    """
    time O(k**n)?

    space O(n), recursive calls
    """
    n = len(nums)

    def jump(i):
        if i == n - 1:
            return True

        k = nums[i]
        # O(k)
        return any(
            jump(i + j)
            for j in range(k, 0, -1)
            if i + j < n
        )

    return jump(0)

is the time complexity of this solution O(k**n)? I think it is because if you draw a tree of possibilities, you can see that for every element there could be up to k branches, where k is the maximum number of jumps, and there are n elements in total.
But I'm not sure

[haughty mountain]

this is an example of something that can be O(n^2)

[jolly crypt]

could you explain why this is O(n^2)?

ahh