#algos-and-data-structs | Python | Page 101

agile sundial Mar 2, 2021, 5:00 PM

#

yeah, that's not ideal

old rover Mar 2, 2021, 5:01 PM

#

but I think I'm actually getting better at it

#

slow improvement

inland iron Mar 2, 2021, 5:01 PM

#

k, and what about the indentation error at "else:"? how would i fix that?

old rover Mar 2, 2021, 5:01 PM

#

function twoDivides(x){
    var count = 0;
    while (parseInt(x) > 1) {
        x = x / 2;
        count = count + 1;
    }
    return count;
}

#

how do you do this in python?

#

what is parseInt?

agile sundial Mar 2, 2021, 5:01 PM

#

parses a string in to an int? idk

old rover Mar 2, 2021, 5:02 PM

#

i looked at the doc too

#

yeah i think you're right

inland iron Mar 2, 2021, 5:02 PM

#

im new to python tbh

old rover Mar 2, 2021, 5:02 PM

#

agile sundial parses a string in to an int? idk

can't you do that w casting?

#

cast a string to an int?

agile sundial Mar 2, 2021, 5:02 PM

#

depends on the language

old rover Mar 2, 2021, 5:02 PM

#

you can't do it in java?

#

oh wait

#

that's #ot0-psvm’s-eternal-disapproval nvm

agile sundial Mar 2, 2021, 5:03 PM

#

that's not java

old rover Mar 2, 2021, 5:03 PM

#

whatttttt

#

what is that????

jolly mortar Mar 2, 2021, 5:03 PM

#

js

old rover Mar 2, 2021, 5:03 PM

#

oh i forgot i learned that

#

~~just never used it again~~

jolly mortar Mar 2, 2021, 5:03 PM

#

inland iron k, and what about the indentation error at "else:"? how would i fix that?

I'm not entirely sure why you're getting that error

agile sundial Mar 2, 2021, 5:04 PM

#

replace your indentation with spcaes

inland iron Mar 2, 2021, 5:05 PM

#

agile sundial replace your indentation with spcaes

It worked, mk then?

#

thx...?

old rover Mar 2, 2021, 5:06 PM

#

function twoDivides(x){
    var count = 0;
    while (parseInt(x) > 1) {
        x = x / 2;
        count = count + 1;
    }
    return count;
}

#

so how does putting in 2 return 1 here?

#

while 2 >1

inland iron Mar 2, 2021, 5:06 PM

#

jolly mortar I'm not entirely sure why you're getting that error

also, thx. i tried the smallest = biggest = input() and it worked

old rover Mar 2, 2021, 5:06 PM

#

so it goes inside the while loop

#

then 2 is divided by 2 and it becomes 1

#

~~confusion~~

agile sundial Mar 2, 2021, 5:09 PM

#

yeah

#

the loop iterates one time

old rover Mar 2, 2021, 5:09 PM

#

oh

#

am dumb

#

sorry

#

seems like i may have burnt out

#

so is it O(log(n) bc it's getting the input gets halved?

agile sundial Mar 2, 2021, 5:10 PM

#

it is log n, yeah

#

because the loop runs log n times

old rover Mar 2, 2021, 5:10 PM

#

~~idk what that means~~

#

bc when you put in 2 it runs once

#

and 2 is the n

agile sundial Mar 2, 2021, 5:11 PM

#

you're unsure what log n means?

old rover Mar 2, 2021, 5:11 PM

#

i kinda forgot from high school math

#

guess i'll watch some videos

#

https://youtu.be/4UNkQcBrLaQ

YouTube

Don't Memorise

Logarithms - Basics | What are Logs? | Don't Memorise

What are Logarithms or logs? How are they related to Exponents? Watch this video to know the answers.

To learn more about Logarithms, enrol in our full course now: https://bit.ly/logarithms_DM

In this video, we will learn:
0:00 Exponents
0:26 What are Logs?
1:13 Logarithms (Example)

To watch more videos related to Logarithm, click here: htt...

▶ Play video

#

ok so i watched this and now i kinda remember them

#

hang on i'm watching O(log(n) videos rn

gusty grove Mar 2, 2021, 5:24 PM

#

if you get -inf that means 1-sig was 0

buoyant garden Mar 2, 2021, 5:24 PM

#

yes

gusty grove Mar 2, 2021, 5:24 PM

#

sig has to be smaller than 1 and larger than 0

#

it can be 0 though

#

but it can never be 1

#

whats your sigmoid function

buoyant garden Mar 2, 2021, 5:27 PM

#

def sigmoid(z):
    result = 1 / (1 + np.exp(-z))
    return result

old rover Mar 2, 2021, 5:30 PM

#

I have a question

#

why do we always use log base 2 in CS?

#

why is it implicit?

agile sundial Mar 2, 2021, 5:31 PM

#

binary is base 2

old rover Mar 2, 2021, 5:31 PM

#

oh ok

agile sundial Mar 2, 2021, 5:31 PM

#

it's just easier for computers to work with than base10

old rover Mar 2, 2021, 5:32 PM

#

ok that makes sense

#

you know

#

I may be ready for data structures and algos now

#

but using ~~someone's github notes bc they already exist and are nice and short~~

buoyant garden Mar 2, 2021, 5:36 PM

#

^^^

old rover Mar 2, 2021, 5:40 PM

#

buoyant garden ^^^

I can't believe I didn't think of that sooner

buoyant garden Mar 2, 2021, 5:40 PM

#

?

old rover Mar 2, 2021, 5:41 PM

#

buoyant garden ?

looking at someone's notes on github

buoyant garden Mar 2, 2021, 5:41 PM

#

ah

old rover Mar 2, 2021, 5:42 PM

#

yeah these people who just casually read 1k page long textbooks amaze me

spring jasper Mar 2, 2021, 5:43 PM

#

I dont think anybody does that

buoyant garden Mar 2, 2021, 5:43 PM

#

uh

old rover Mar 2, 2021, 5:43 PM

#

uh

#

public static void main enters the chat

spring jasper Mar 2, 2021, 5:43 PM

#

Doubt he would agree tbh

old rover Mar 2, 2021, 5:44 PM

#

i was kidding

#

some people learn differently

#

like I saw this 200 page long book called algorithms unlocked

#

and even that was just too much

#

i don't like fluff in books

buoyant garden Mar 2, 2021, 5:46 PM

#

^

spring jasper Mar 2, 2021, 5:46 PM

#

Reading is fine but are you applying what youre reading

old rover Mar 2, 2021, 5:47 PM

#

well i don't see how I would be explaining the math behind big O to an interviewer any time soon

buoyant garden Mar 2, 2021, 5:47 PM

#

personally, i understand the math alot more when its in code, like equations confuse the hell out of me, but seeing like the python implementation im like "ooooooooooooooooooo"

old rover Mar 2, 2021, 5:47 PM

#

they're more interested in seeing you say the time complexity of an algorithm by looking at it

buoyant garden Mar 2, 2021, 5:47 PM

#

but thats just my convoluted brain

#

oop
'

old rover Mar 2, 2021, 5:47 PM

#

guys I actually got another interview

#

but now i have to do two leetcode questions in the span of 45 minutes

#

F in the chat for me ig

buoyant garden Mar 2, 2021, 5:58 PM

#

buoyant garden ```python def sigmoid(z): result = 1 / (1 + np.exp(-z)) return result ``...

@gusty grove this good

old rover Mar 2, 2021, 8:59 PM

#

function twoDivides(x){
    var count = 0;
    while (parseInt(x) > 1) {
        x = x / 2;
        count = count + 1;
    }
    return count;
}

#

I know I've sent this code before

#

but can someone please explain why this is O(log(n)?

#

I watched videos on log and I watched videos on O(log(n)

#

https://youtu.be/M4ubFru2O80

YouTube

Back To Back SWE

Deeply Understanding Logarithms In Time Complexities & Their Role I...

Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching

Lo...

▶ Play video

#

this one specifically

#

but I still don't get it

#

well if you put in 2

#

it returns 1

#

yeah part of it is dividing

#

while 2 is bigger than 1 so you enter the while loop

#

then you do 2/2 = 1

#

and count is 1

#

uhhhhhhh

#

no?

#

count is 0 which is an integer

#

and then it becomes 1

#

what does parseInt even do?

#

turn a string into an integer?

#

i looked at the doc

#

ok

#

so then how would you be returning a string here

#

my plan????

#

this isn't "my function"

#

https://github.com/pavankat/big-o-in-plain-english

GitHub

pavankat/big-o-in-plain-english

the only big o guide written in plain english :). Contribute to pavankat/big-o-in-plain-english development by creating an account on GitHub.

#

this is from this github repo trying to teach big O

#

I didn't ask that

#

I asked why is it O(log(n)

#

not for you to "fix" the function

#

idk why you're getting a headache

#

but why is it O(log(n) other than just saying it's bc there's a while loop?

#

this is #algos-and-data-structs

spring jasper Mar 2, 2021, 9:10 PM

#

What it does is divide the number by 2 every step

#

Its like binary search

#

Hence log(n)

old rover Mar 2, 2021, 9:13 PM

#

#

when he says "so _____ total" is he referring to operations?

#

and when you input 8 it returns 3

#

8 divided by 2 isn't 3

#

maybe it's bc 2^3 is. 8

#

ohhhhhh

#

maybe that's why

#

and 2^4 is 16

#

and so on and so forth

#

just think of the number 2 when you're doing your input v output

#

bc it's log base 2

#

~~pattern recognition~~

#

is that what you guys were trying to say???

spring jasper Mar 2, 2021, 9:17 PM

#

I was just thinking that the number of steps depends on the division operation and that binary search is literally just like that

#

So it should have the same O

old rover Mar 2, 2021, 9:18 PM

#

oh I don't really know binary search yet

spring jasper Mar 2, 2021, 9:18 PM

#

Ah ok fair then

old rover Mar 2, 2021, 9:18 PM

#

I was focusing on learning big O first

#

but I think I may have actually figured it out

#

#

oh look

#

a for loop inside a for loop that isn't O(n^2)

#

~~how interesting~~

#

I don't actually know how to put this into python

#

i get why there's an O(n) there

#

but why is O(log(n)?

#

is it bc it's getting halved?

mint jewel Mar 2, 2021, 9:32 PM

#

yes

old rover Mar 2, 2021, 9:33 PM

#

understood

#

this may be stupid but

#

nlogn(3)
[3, 1, 3, 1, 3, 1]

#

how does nlogn(3) return that? I see it's "pushed" to a list

#

but if 3/2 how is it still 3??

mint jewel Mar 2, 2021, 9:36 PM

#

big O only really makes sense for large inputs
3 * ⌈log_2(3) is indeed 6

#

don't use big O to predict how long something will take

#

it doesn't do that

#

at all

old rover Mar 2, 2021, 9:36 PM

#

what about a thousand?

#

not big enough?

mint jewel Mar 2, 2021, 9:37 PM

#

it is big enough I guess

#

but you are missing the point

old rover Mar 2, 2021, 9:37 PM

#

I know it's not for how long something takes

spring jasper Mar 2, 2021, 9:38 PM

#

nlogn(3)
Starts the inner loop with j = 3
It appends that
Then j = 3//2 which is 1 and then appends that too

#

And then the loop terminates and starts over again

old rover Mar 2, 2021, 9:38 PM

#

spring jasper nlogn(3) Starts the inner loop with j = 3 It appends that Then j = 3//2 which is...

but it's not j = 3//2 it's j =3/2

mint jewel Mar 2, 2021, 9:38 PM

#

consider an algo like

def weird(N):
    arr = []
    for k in range(N):
        arr.append(k)
    n = 0
    while n * n < N:
         arr.append(n)
         n += 1

#

this is O(n)

spring jasper Mar 2, 2021, 9:39 PM

#

Its parseInt(3/2) which is equivalent to 3//2

mint jewel Mar 2, 2021, 9:39 PM

#

but the actual output size will not be exactly linear to N

old rover Mar 2, 2021, 9:39 PM

#

spring jasper Its parseInt(3/2) which is equivalent to 3//2

oh my bad i'm not familiar w JS stuff

old rover Mar 2, 2021, 9:40 PM

#

mint jewel but the actual output size will not be exactly linear to N

what is N supposed to be here?

mint jewel Mar 2, 2021, 9:40 PM

#

some number

#

fixed the sample code

old rover Mar 2, 2021, 9:41 PM

#

oh I didn't realize thanks

#

does range start from zero?

mint jewel Mar 2, 2021, 9:42 PM

#

yes

old rover Mar 2, 2021, 9:42 PM

#

yes right?

#

ok

mint jewel Mar 2, 2021, 9:43 PM

#

big O tells you the growth, so I can guess that running weird with 1000 will about twice as fast as running it with 2000

#

but it just a guess

old rover Mar 2, 2021, 9:43 PM

#

"Big O is short for Big O Notiation.

Big O is how programmers talk about scalability of algorithms.

An algorithm's Big O Notation is determined by how long the algorithm takes to return output in the worst case scenario.

The math term for the worst case scenario is "upper bound"."

#

this is this github repo's definition of big O

#

it's wrong btw

#

but the sad thing is that this is the understanding of most people in the tech field

agile sundial Mar 2, 2021, 9:44 PM

#

it's about 7/8ths ok

old rover Mar 2, 2021, 9:44 PM

#

the worst case scenario is right

spring jasper Mar 2, 2021, 9:44 PM

#

He got the name right

old rover Mar 2, 2021, 9:45 PM

#

big O does indeed mean upper bound on time

mint jewel Mar 2, 2021, 9:45 PM

#

not necessarily on time, but yeah

#

and honestly, I wouldn't really agree with that

#

that algo above will always take longer than just a linear function would predict

old rover Mar 2, 2021, 9:46 PM

#

why is it

#

that every textbook I look at

#

has a different def of big O

mint jewel Mar 2, 2021, 9:46 PM

#

it means that the algo will grow linearily for large enough inputs

old rover Mar 2, 2021, 9:46 PM

#

can't y'all just standardize????

mint jewel Mar 2, 2021, 9:46 PM

#

because it is used in casual conversation and people try to simplify the horrible math version to be more comprehensible

old rover Mar 2, 2021, 9:47 PM

#

but then people who simplify it are completely wrong

mint jewel Mar 2, 2021, 9:47 PM

#

and inevitably end up introducing wrong things

old rover Mar 2, 2021, 9:47 PM

#

sigh

agile sundial Mar 2, 2021, 9:47 PM

#

i'm sure most textbooks will have close to the exact same definition when they are being rigorous.

#

the issue is when you try to simplify it

mint jewel Mar 2, 2021, 9:47 PM

#

since mathematicians aren't horrible because they want to be seen as smart, but because it needs to be precise and well defined

old rover Mar 2, 2021, 9:48 PM

#

well unfortunately my reading comprehension skills are not good enough to understand them being well defined and precise

#

it takes some balls to admit that at least

#

i'll work on it dw

mint jewel Mar 2, 2021, 9:48 PM

#

yeah, that is fine. Its just an indication of how things grow on very large inputs

old rover Mar 2, 2021, 9:48 PM

#

so what if my interviewer is like

#

oh yeah it's just how fast an algorithm runs

mint jewel Mar 2, 2021, 9:49 PM

#

well, then they are wrong

#

don't tell them that though

old rover Mar 2, 2021, 9:50 PM

#

also

#

if big O is used for the worst case scenario

#

what notation is used for the best case scenario?

mint jewel Mar 2, 2021, 9:50 PM

#

~~little o~~

agile sundial Mar 2, 2021, 9:50 PM

#

eh?

mint jewel Mar 2, 2021, 9:50 PM

#

actually, that may be something else, never mind me

old rover Mar 2, 2021, 9:50 PM

#

"An algorithm's Big O Notation is determined by how long the algorithm takes to return output in the worst case scenario."

spring jasper Mar 2, 2021, 9:51 PM

#

Its omega

old rover Mar 2, 2021, 9:51 PM

#

oh ok

#

so I need to learn that too ig

#

can I start algos and data structures w just big O?

spring jasper Mar 2, 2021, 9:51 PM

#

Ω(f(n))

mint jewel Mar 2, 2021, 9:51 PM

#

yes

agile sundial Mar 2, 2021, 9:51 PM

#

arguably big O is part of dsa

#

so you've already started

old rover Mar 2, 2021, 9:52 PM

#

good stuff

spring jasper Mar 2, 2021, 9:52 PM

#

Learning big o without any context of the data structures involved sounds boring tbh

old rover Mar 2, 2021, 9:52 PM

#

better start learning data structures then

#

at least I'm making progress

#

what is fibonacci

#

// assume number is an integer
function fib(number) {
 if (number <= 1) return number;
 return fib(number - 2) + fib(number - 1);
}

wise fiber Mar 2, 2021, 9:54 PM

#

does anyone have the explanation for USACO Feb?

old rover Mar 2, 2021, 9:54 PM

#

this is how this guide introduces fibonacci

wise fiber Mar 2, 2021, 9:55 PM

#

Fib numbers? here u go
https://cp-algorithms.com/algebra/fibonacci-numbers.html

old rover Mar 2, 2021, 9:55 PM

#

~~it sounds Italian~~

spring jasper Mar 2, 2021, 9:55 PM

#

It is

old rover Mar 2, 2021, 9:55 PM

#

oh it is cool

#

I didn't wanna be racist or trigger anyone so I crossed out the text

wise fiber Mar 2, 2021, 9:56 PM

#

crossing out italian is racist man

old rover Mar 2, 2021, 9:56 PM

#

oof ya got me

wise fiber Mar 2, 2021, 9:56 PM

#

🤔

spring jasper Mar 2, 2021, 9:56 PM

#

His name was Lenny from Pisa in italy somewhere

old rover Mar 2, 2021, 9:59 PM

#

leonardo of pisa

#

didn't they write a whole book on this shit or something

#

anyways I digress

#

why does it matter that I'm not learning data structures in conjunction w big O

#

is it just customary?

spring jasper Mar 2, 2021, 10:02 PM

#

Its easier i guess

#

~~Big O doesnt exist in a vacuum~~
Dang mathematicians

old rover Mar 2, 2021, 10:02 PM

#

What does existing in a vacuum mean?

#

Not used?

#

irrelevant?

spring jasper Mar 2, 2021, 10:03 PM

#

As in, they exist independent of other concepts or structures

old rover Mar 2, 2021, 10:04 PM

#

I mean

#

Big O is important for algorithms

spring jasper Mar 2, 2021, 10:05 PM

#

Its easier to understand something by doing, implementing the algorithm will help you more than just studying the theory

old rover Mar 2, 2021, 10:06 PM

#

Yep

keen hearth Mar 2, 2021, 11:53 PM

#

old rover if big O is used for the worst case scenario

Actually, big-oh could be used for best-case, average-case, or worst-case performance.

old rover Mar 2, 2021, 11:56 PM

#

oh boy

#

then what the hell is this github repo saying

#

~~guess that's why you don't just randomly read github repos and trust them~~

#

~~but I don't like reading gigantic textbooks too~~

#

~~what do I do w my life~~

keen hearth Mar 2, 2021, 11:58 PM

#

I can try my best to summarise it here with a sufficient level of rigour, if you like? 😄

old rover Mar 2, 2021, 11:58 PM

#

keen hearth I can try my best to summarise it here with a sufficient level of rigour, if you...

sure go ahead

#

just make sure to ping me bc i'm gonna take a shower

keen hearth Mar 2, 2021, 11:59 PM

#

Alright, I'll write it out here then ping you 😄

#

So, we want to characterise the performance of an algorithm. We could just time how long it takes to run for a specific problem, but there are a couple of problems with this:

An algorithm is designed to solve a set of problems not a single problem. (We don't just want an algorithm that sorts one particular list of numbers, we want it to be able to sort any list of numbers.)
The actual time it takes to complete will depend on the properties of the computer that it runs on.

#

So instead we characterise the performance by looking at the relationship between the size of the input and the run-time.

#

Imagine we have a mathematical function T(n) that tells us how many CPU instructions it takes to sort a list of n numbers (with our sorting algorithm).

#

But actually, to define T we need to decide if we are dealing with the worst-case, best-case, or average-case list of length n.

#

[1, 1, 1], [1, 2, 3], and [3, 2, 1] are all length-3 lists of numbers, but they are different and may take a different number of CPU instructions to sort. Some sorting algorithms are faster if the list is already sorted (bubble-sort), and some are slower in that case (quicksort).

brave oak Mar 3, 2021, 12:11 AM

#

(in particular, Timsort - which Python uses, and which was made for Python, is baaasically mergesort but better with data that's already partially sorted)

old rover Mar 3, 2021, 12:11 AM

#

i'm back

keen hearth Mar 3, 2021, 12:12 AM

#

So if T(n) is worst-case run-time, it's telling us what is the maximum number of CPU instructions it would take to sort a list of length n.

#

Note I haven't mentioned big-oh yet.

old rover Mar 3, 2021, 12:12 AM

#

noted

keen hearth Mar 3, 2021, 12:13 AM

#

But actually exactly figuring out a mathematical formula for T is kind-of difficult.

#

The actual number of instructions is going to depend on things like which programming language and CPU architecture the algorithm is implemented in.

#

Also, T might be complicated for small values of n.

#

So we simplify it by:

removing any constant factor in the formula, and
only looking at very large values of n.

#

That's where big-oh comes in.

#

A rigorous definition of big-oh would be something like this:

The function f is a member of the set O(g) (where g is also a function) if and only if there exist constants, n0 and k, such that, for all n > n0, f(x) < k g(x)

#

That's probably a little abstract unless you've done some mathematics before at university.

#

In everyday language it means that you can multiply the function g by a constant such that it eventually overtakes the function f, and f never catches up.

old rover Mar 3, 2021, 12:22 AM

#

uhhh only math I did was calculus for CS before I switched my major

#

on a side note

keen hearth Mar 3, 2021, 12:22 AM

#

If you imagine that f(t) and k * g(t) represent the positions of two cars along a race-track at time t.

old rover Mar 3, 2021, 12:23 AM

#

can you recommend a book that's not a thousand pages long?

keen hearth Mar 3, 2021, 12:24 AM

#

Erm, you might want to check out Khan Academy's algorithms course, not sure if I've already recommended it.

old rover Mar 3, 2021, 12:24 AM

#

KHAN ACADEMY HAS AN ALGORITHMS COURSE?

#

WHAT?

keen hearth Mar 3, 2021, 12:24 AM

#

Yes 😄

#

https://www.khanacademy.org/computing/computer-science/algorithms

Khan Academy

Algorithms | Computer science | Computing | Khan Academy

We've partnered with Dartmouth college professors Tom Cormen and Devin Balkcom to teach introductory computer science algorithms, including searching, sorting, recursion, and graph theory. Learn with a combination of articles, visualizations, quizzes, and coding challenges.

#

It's kind-of hidden on their website.

old rover Mar 3, 2021, 12:25 AM

#

~~holy shit~~

#

do they have a data structures course too?

keen hearth Mar 3, 2021, 12:25 AM

#

They're kind of the same subject tbh.

#

The course has input from one of the authors of the CLRS textbook I believe.

old rover Mar 3, 2021, 12:26 AM

#

yeah Cormen

#

Cormen wrote CLRS w some other buddies

keen hearth Mar 3, 2021, 12:27 AM

#

Btw, this kind of illustrates what I was saying:

#

From Wikipedia.

old rover Mar 3, 2021, 12:27 AM

#

got it

#

uhhh

#

it's all of the algorithms?

#

or just a few

keen hearth Mar 3, 2021, 12:28 AM

#

It's just core concepts.

#

The algorithms are just to use as examples.

#

In practice, it's not all that useful to know 10 different sorting algorithms, but they provide nice examples for teaching the ideas.

old rover Mar 3, 2021, 12:29 AM

#

i tried to read algorithms unlocked and CLRS

#

but they both made my head spin

#

and algorithms unlocked is just 200 something pages

agile sundial Mar 3, 2021, 12:32 AM

#

khan academy's course is in js

keen hearth Mar 3, 2021, 12:32 AM

#

That's true. The exercises are in JS, although they're optional.

agile sundial Mar 3, 2021, 12:32 AM

#

if you wanna learn the exercises are not optional

old rover Mar 3, 2021, 12:34 AM

#

but aren't algorithms language agnostic or something

#

so you should be able to learn them in anything

keen hearth Mar 3, 2021, 12:35 AM

#

You might also want to check out this course by Udacity. The instructor is a cool guy 😄 https://www.udacity.com/course/intro-to-algorithms--cs215

Intro to Algorithms

This class will give you an introduction to the design and analysis of algorithms, enabling you to analyze networks and discover how individuals are connected.

old rover Mar 3, 2021, 12:35 AM

#

hey as long as it's not Siraj Rival I'm ok

keen hearth Mar 3, 2021, 12:36 AM

#

They kind of frame the whole course around social networks. The course is a few years old now.

old rover Mar 3, 2021, 12:36 AM

#

I mean does it matter? Have algorithms changed much in the last couple years?

keen hearth Mar 3, 2021, 12:36 AM

#

Shouldn't matter, although it may use Python 2 😄

old rover Mar 3, 2021, 12:36 AM

#

~~UHHHHHHHHHH~~

#

yeah then I'll stick w Khan Academy

keen hearth Mar 3, 2021, 12:37 AM

#

It's also pretty heavy on graph algorithms.

old rover Mar 3, 2021, 12:37 AM

#

is that supposed to scare me or inform me

keen hearth Mar 3, 2021, 12:37 AM

#

(Which are very useful to know!)

old rover Mar 3, 2021, 12:37 AM

#

or both

#

lmao

#

ok good

agile sundial Mar 3, 2021, 12:37 AM

#

graph theory is awesome

keen hearth Mar 3, 2021, 12:37 AM

#

Inform 😄

old rover Mar 3, 2021, 12:37 AM

#

ofc one of the guys wrote CLRS wrote algorithms unlocked

agile sundial Mar 3, 2021, 12:38 AM

#

clrs was written by 4 guys lol

old rover Mar 3, 2021, 12:38 AM

#

"one of the guys"

agile sundial Mar 3, 2021, 12:38 AM

#

"(edited)"

#

the 4th edition of clrs is coming out soon, with color!

old rover Mar 3, 2021, 12:38 AM

#

yay more thousand page long book that I won't read

#

yayyyyy

agile sundial Mar 3, 2021, 12:38 AM

#

ok but imagine this

#

the red black trees, will be red and black

old rover Mar 3, 2021, 12:39 AM

#

sure pretty illustrations are pretty

#

maybe I can use it as a picture book

keen hearth Mar 3, 2021, 12:39 AM

#

agile sundial the red black trees, will be red and black

Wow 😄

#

Fancy

agile sundial Mar 3, 2021, 12:39 AM

#

ikr

#

before it's just "the lightly shaded are red, and the darkly shaded are black"

keen hearth Mar 3, 2021, 12:40 AM

#

Apparently they use MacDraw on an old macintosh to make the illustrations.

old rover Mar 3, 2021, 12:40 AM

#

I don't even know how to read CLRS

agile sundial Mar 3, 2021, 12:40 AM

#

i think it's in english

old rover Mar 3, 2021, 12:40 AM

#

there's barely any bolded text

agile sundial Mar 3, 2021, 12:40 AM

#

they use italics in some spots

keen hearth Mar 3, 2021, 12:41 AM

#

I'm not sure why I know that 😄

old rover Mar 3, 2021, 12:41 AM

#

I'm not reading page long paragphs

#

I mean look it up

#

there's reddit posts saying CLRS is hard to read

#

I'm not the only one

agile sundial Mar 3, 2021, 12:41 AM

#

well, i'm not denying that lol

keen hearth Mar 3, 2021, 12:41 AM

#

The style is fairly mathematical. There are a lot of proofs.

#

You have to kind of get used to it.

old rover Mar 3, 2021, 12:41 AM

#

~~I don't care about maths~~

agile sundial Mar 3, 2021, 12:42 AM

#

~~computer science is all about that~~

old rover Mar 3, 2021, 12:42 AM

#

I just don't like their writing style

agile sundial Mar 3, 2021, 12:42 AM

#

it's very rigorous

keen hearth Mar 3, 2021, 12:42 AM

#

But the explanations are very clear.

old rover Mar 3, 2021, 12:42 AM

#

even in their "simpler, antipasta" book or whatnot it's still gigantic paragraphs

#

Algorithms Unlocked

agile sundial Mar 3, 2021, 12:43 AM

#

it elucidates even the most minute details

old rover Mar 3, 2021, 12:43 AM

#

how wonderful

agile sundial Mar 3, 2021, 12:43 AM

#

quite

keen hearth Mar 3, 2021, 12:45 AM

#

I looked a bit closer at that Udacity course. It shouldn't really make much difference that it uses python 2, aside from the occasional print x.

#

And the coding is all done online, so you don't need to install python 2 on your machine 😄

old rover Mar 3, 2021, 12:49 AM

#

I'm actually trying something different

#

I'm going through the MIT OCW notes bc they're ~~short and concise~~ and then doing problems associated w the algorithms they're talking about

#

let's see if that works

agile sundial Mar 3, 2021, 12:50 AM

#

you mightt as well watch the lectures then

old rover Mar 3, 2021, 12:51 AM

#

no

agile sundial Mar 3, 2021, 12:51 AM

#

ok ¯_(ツ)_/¯

old rover Mar 3, 2021, 12:51 AM

#

~~perhaps~~

#

so I have a question

#

there is no such thing as a "peak-finding algorithm" right?

keen hearth Mar 3, 2021, 12:52 AM

#

That would probably be an "optimisation" algorithm.

old rover Mar 3, 2021, 12:54 AM

#

#

why are they saying to look at the left half?

#

they said the straightforward algorithm is to look left to right

#

I actually watched the entire lecture and it lost me here too

#

y'all ever heard of Grokking algorithms???

keen hearth Mar 3, 2021, 1:10 AM

#

Nope sorry. Looks interesting though.

old rover Mar 3, 2021, 1:13 AM

#

keen hearth Nope sorry. Looks interesting though.

Nope sorry in response to why they're asking to look at the left half or Grokking algorithms?

keen hearth Mar 3, 2021, 1:14 AM

#

old rover Nope sorry in response to why they're asking to look at the left half or Grokkin...

Sorry, Grokking algorithms.

old rover Mar 3, 2021, 1:14 AM

#

oh ok

#

yeah I've never seen a book w algorithms focus on visual stuff as much as this one

#

have I mentioned how it's only 200 pages?

keen hearth Mar 3, 2021, 1:18 AM

#

It has nice illustrations 😄

keen hearth Mar 3, 2021, 1:20 AM

#

old rover why are they saying to look at the left half?

So it looks like the idea of that "peak-finding" algorithm is to keep splitting the list in half, each time taking the half that appears to be uphill from the midpoint.

old rover Mar 3, 2021, 1:22 AM

#

keen hearth So it looks like the idea of that "peak-finding" algorithm is to keep splitting ...

damn couldn't they just say that

#

what is n/2 --- 1?

#

~~damn you'd think MIT would actually teach this well~~

agile sundial Mar 3, 2021, 1:27 AM

#

are you watching the lecture?

#

ah, you did

old rover Mar 3, 2021, 1:28 AM

#

yeah

#

maybe MIT OCW is just not for me

agile sundial Mar 3, 2021, 1:28 AM

#

n/2 - 1 is an index

old rover Mar 3, 2021, 1:28 AM

#

I mean

#

my understanding of binary search

#

is you look at the middle

#

and then you compare it to the left and the right

agile sundial Mar 3, 2021, 1:30 AM

#

usually you're looking for a specific key, but in this case you're just looking for a peak

old rover Mar 3, 2021, 1:30 AM

#

oh

#

does --- mean ...?

agile sundial Mar 3, 2021, 1:31 AM

#

that's probably just a typo

old rover Mar 3, 2021, 1:31 AM

#

oh

#

ok

#

I will look at Grokking for a while and then come back

agile sundial Mar 3, 2021, 1:32 AM

#

ok

keen hearth Mar 3, 2021, 1:38 AM

#

old rover and then you compare it to the left and the right

Yeah, basically you want to determine whether the index you are currently at (the midpoint) is a valley, peak, or slope. If it's a peak, you've found a peak. If it's a slope, you know there must be a peak somewhere in the uphill direction. If it's a valley, the same thing, but both directions are uphill so you can choose one arbitrarily. At each step you narrow down the range of indices to search in by cutting it in half.

old rover Mar 3, 2021, 1:38 AM

#

slope???? valley????

keen hearth Mar 3, 2021, 1:40 AM

#

                 v
peak:    ..., 1, 2, 1, ...
valley:  ..., 2, 1, 2, ...
slope:   ..., 0, 1, 2, ...
                 ^

#

These aren't technical terms, just the best words I could think of to describe the three possibilities.

old rover Mar 3, 2021, 1:42 AM

#

oh ok

#

thanks

oblique panther Mar 3, 2021, 1:52 AM

#

@old rover 👋🏻

old rover Mar 3, 2021, 1:52 AM

#

hey

oblique panther Mar 3, 2021, 1:53 AM

#

what do you think the big-O of that algo is?

#

the fibb one?

old rover Mar 3, 2021, 1:54 AM

#

oblique panther what do you think the big-O of that algo is?

O(2^n)

oblique panther Mar 3, 2021, 1:54 AM

#

why

old rover Mar 3, 2021, 1:54 AM

#

I'm actually not sure I just read somewhere that recursive sequences tend to be O(2^n)

#

not a good answer I know

vocal gorge Mar 3, 2021, 1:55 AM

#

// assume number is an integer
function fib(number) {
 if (number <= 1) return number;
 return fib(number - 2) + fib(number - 1);
}

the recurrent equation for T(n) here is T(n) = T(n-1) + T(n-2), and that happens to be precisely the recurrent equation for fibonacci numbers themselves. So you get the famous fact that the complexity of recursively calculating fib(n) is... fib(n) 😅

And fib(n) for big n is approximately exponential - it's something like phi^n where phi is the golden ratio.

#

so 2^n isn't that incorrect of an answer

old rover Mar 3, 2021, 1:56 AM

#

it also doesn't help that I have seen recursion used like twice

#

that's my own fault tho

oblique panther Mar 3, 2021, 1:56 AM

#

def fib(n):
    """You know I had to do it to them"""
    return n if n <= 1 else (fib(n - 2) + fib(n - 1))

old rover Mar 3, 2021, 1:57 AM

#

ok so let's say we put in 5

oblique panther Mar 3, 2021, 1:58 AM

#

do you know what T(n) means?

old rover Mar 3, 2021, 1:58 AM

#

not really

#

probably should have said something

#

is it another notation?

oblique panther Mar 3, 2021, 1:59 AM

#

it's a way of saying what the whole runtime is for a given algorithm

old rover Mar 3, 2021, 1:59 AM

#

ohhhhh

#

ok

oblique panther Mar 3, 2021, 1:59 AM

#

whereas O(g(n)) is a set of algorithms that scale according to g(n)

#

or something like that

vocal gorge Mar 3, 2021, 2:00 AM

#

Basically, you know how the O-notation is by itself about functions? Well, when we say the algorithm is O(something), that means the algorithm's T(n) is O(something).

#

so it's the precise-ish number of operations or something like that.

old rover Mar 3, 2021, 2:01 AM

#

so T(n) is actually what people are saying when they're like O(N) is the runtime of an algorithm

#

common misconception

oblique panther Mar 3, 2021, 2:02 AM

#

So when you have a recursive function, T(n) appears in T(n) = ...

#

If you have a T(n) = ... equation where there's no recursion, you can determine the big-O just by looking at it

#

do you know how to do that?

old rover Mar 3, 2021, 2:03 AM

#

yes

oblique panther Mar 3, 2021, 2:03 AM

#

explain

old rover Mar 3, 2021, 2:03 AM

#

Idk what it looks like without recursion

oblique panther Mar 3, 2021, 2:04 AM

#

it might be something like T(n) = 5 + n(n + 72) + sqrt(n)

#

do you know what the big-O of this would be?

old rover Mar 3, 2021, 2:04 AM

#

O(1) constant time

oblique panther Mar 3, 2021, 2:05 AM

#

no

old rover Mar 3, 2021, 2:05 AM

#

F

oblique panther Mar 3, 2021, 2:05 AM

#

T(n) can only belong to O(1) if n isn't actually used in the calculation of the runtime.

#

I see two fellow staffers furiously typing

#

what have I done wrong?

vocal gorge Mar 3, 2021, 2:06 AM

#

not strictly speaking true - for example, T(n) = log(n)/n is O(1), so is T(n) = 10000 - e^(-n)

oblique panther Mar 3, 2021, 2:06 AM

#

I can learn too lemon_hyperpleased

vocal gorge Mar 3, 2021, 2:06 AM

#

it's O(1) if it's bounded by a constant - it doesn't have to be constant.

oblique panther Mar 3, 2021, 2:07 AM

#

I knew the formal definition but I went out on a limb and figured there were no funny cases like this

vocal gorge Mar 3, 2021, 2:07 AM

#

that might be true

icy crane Mar 3, 2021, 2:08 AM

#

oblique panther I can learn too <:lemon_hyperpleased:754441879822663811>

Wat I thought you knew everything

#

Oh, this is not ot oops

oblique panther Mar 3, 2021, 2:08 AM

#

but also log(n) / n is (1/2)(n)(log(n)). so why isn't that O(n)?

#

wait

#

I am dumb sorry

old rover Mar 3, 2021, 2:09 AM

#

idk Stelercus I think you're pretty cool

vocal gorge Mar 3, 2021, 2:10 AM

#

log(n)/n is O(1) because it just goes to zero with increasing n, whereas 10000 - e^(-n) approaches 10000 from below.

keen hearth Mar 3, 2021, 2:11 AM

#

old rover so T(n) is actually what people are saying when they're like O(N) is the runtime...

T(n) is like the maximum number of CPU instructions it would take for the algorithm to complete for an input of size n

old rover Mar 3, 2021, 2:11 AM

#

oh

#

ok

#

nvm then

keen hearth Mar 3, 2021, 2:12 AM

#

You could also say the time in seconds of the algorithm, or the number of python bytecode instructions.

#

The reason we use big-oh notation is to avoid these details.

#

If T(n) was n or 2n or n + 100000 or even 1000000 n + 100000, it would still be O(n)

old rover Mar 3, 2021, 2:18 AM

#

brain goes brrrrr it's 9:30

#

brain has left the chat

#

I'll be back tomorrow

keen hearth Mar 3, 2021, 2:19 AM

#

Alright, see ya 😄

cerulean river Mar 3, 2021, 4:29 AM

#

Hey guys, are we allowed to ask Hackerrank/Leetcode questions here? By that I mean if I am confused as to how to why my code is not working (usually not compiling and I cannot seem to understand why) are we allowed to discuss that here?

old rover Mar 3, 2021, 4:30 AM

#

@cerulean river yeah sure as long as it has to do w algos/ds

cerulean river Mar 3, 2021, 4:30 AM

#

thank you for clarifying this for me.

old rover Mar 3, 2021, 4:33 AM

#

Any time

uneven jungle Mar 3, 2021, 7:19 AM

#

how do you stop an iterative quicksort? I get it to sort everything, then it just continues and messes up.

austere sparrow Mar 3, 2021, 9:54 AM

#

I have to advance several state machines concurrently, and sometimes an event can make a state machine go into 'high priority' state, and in that case it should be advanced instead of a low-priority state machine. State machines can also be added and removed. What would be an asymptotically good way of achieving this?

#

by 'concurrently' I mean arranging their updates in a round-robin fashion

mint jewel Mar 3, 2021, 9:58 AM

#

a priority queue from which every thread takes a state machine to advance

austere sparrow Mar 3, 2021, 9:58 AM

#

ah, hmm

#

but

#

I should be able to add and remove them

#

and how do you suppose this will work @mint jewel ? how will a state machine change its position in the priority queue when it's triggered to become high-priority?

mint jewel Mar 3, 2021, 10:01 AM

#

I think there is a priority queue implementation that allows modifying the element priority.

austere sparrow Mar 3, 2021, 10:02 AM

#

I found a 15-page C++ paper http://ceur-ws.org/Vol-1525/paper-13.pdf wish me luck...

#

although in my case I can probably get away with a dict or something like that

#

but I will have on the order of 1000 state machines

mint jewel Mar 3, 2021, 10:03 AM

#

I think heaps are good for this.

austere sparrow Mar 3, 2021, 10:04 AM

#

yeah, asyncio.PriorityQueue is implemented with heapq

#

which also makes it a misnomer because it doesn't care about insertion order

inland iron Mar 3, 2021, 2:17 PM

#

Im trying to make algorithms that act as substitutes for the min() and max() function, but this time they are defined functions. Yet again though, I can't get my loop to work and it only iterates through the next number (6) once and stops. This is the (albeit unfinished) max function btw.```py
Tnums = [1,6,200,-12,123,2,65]
def findMax(nums):
biggest = Tnums[0]
x = 0
while x < len(nums):
biggest = Tnums[0]
if biggest < Tnums[1]:
(placeholder)
x = x + 1
return biggest
Tnums = [1,6,200,-12,123,2,65]
print("The largest number is:", findMax(Tnums))

#

How do I fix the iteration loop here?

shadow flower Mar 3, 2021, 2:23 PM

#

you have to put x = x + 1 inside the while loop

#

i think

old rover Mar 3, 2021, 2:24 PM

#

what's the time complexity of that algorithm

inland iron Mar 3, 2021, 2:27 PM

#

is that what it should look like?

#

Tnums = [1,6,200,-12,123,2,65]
def findMax(nums):
    biggest = Tnums[0]
    x = 0
    while x < len(nums):
        biggest = Tnums[0]
        if biggest < Tnums[1]:
            biggest = Tnums[1]
        x = x + 1
    return biggest
Tnums = [1,6,200,-12,123,2,65]
print("The largest number is:", findMax(Tnums))

#

Okay, i tried it and it didnt work

inland iron Mar 3, 2021, 2:31 PM

#

old rover what's the time complexity of that algorithm

wym time complexity?

old rover Mar 3, 2021, 2:31 PM

#

you know

#

the big O

inland iron Mar 3, 2021, 2:31 PM

#

Im a relatively new python nerd, lul

old rover Mar 3, 2021, 2:32 PM

#

oh

#

nvm

#

I am too don't worry

#

just trying to improve

inland iron Mar 3, 2021, 2:33 PM

#

yeah, i mean im coming to this channel cause i went to a help channel and i wasted 2 hours and got nowhere

#

lmao

#

anyways, what is wrong with my algorithm now? it still doesnt work

#

no errors, just doesnt work as intended

old rover Mar 3, 2021, 2:39 PM

#

can I ask

#

why are you making substitutes for the min() and max() function?

#

are you trying to learn how they work?

inland iron Mar 3, 2021, 2:41 PM

#

its for an assignment, but i only really need help with the loop. I just dont understand why the loop isnt working. I can mostly figure everything else out on my own

old rover Mar 3, 2021, 2:41 PM

#

is it a ~~high school or college assignment?~~

inland iron Mar 3, 2021, 2:42 PM

#

Well yeah, why

#

i dont want the answer to the whole project

#

I just wanna know what the problem with my loop is, cause i cant think of why it isnt working

spring jasper Mar 3, 2021, 2:44 PM

#

It doesnt work because you hardcoded the index in the loop

shadow flower Mar 3, 2021, 2:44 PM

#

inland iron ```py Tnums = [1,6,200,-12,123,2,65] def findMax(nums): biggest = Tnums[0] ...

i think switching out Tnums for nums inside of the function would fix it

spring jasper Mar 3, 2021, 2:45 PM

#

Also you keep setting the biggest to the first element

shadow flower Mar 3, 2021, 2:45 PM

#

because you are using the test numbers inside of the function

#

instead of the actual nums that are being taken in for the function

spring jasper Mar 3, 2021, 2:45 PM

#

Also that yea, just noticed

#

Theres a simple way to find a max in a list, you just need a for loop, an if and a variable

inland iron Mar 3, 2021, 2:46 PM

#

So, like this? ```py
Tnums = [1,6,200,-12,123,2,65]
def findMax(nums):
biggest = nums
x = 0
biggest = nums
while x < len(nums):
if biggest < nums:
biggest = nums
x = x + 1
return biggest
Tnums = [1,6,200,-12,123,2,65]
print("The largest number is:", findMax(Tnums))

shadow flower Mar 3, 2021, 2:46 PM

#

yeah

#

wait no

#

keep the indexes the same

#

like where you have Tnums[0]

spring jasper Mar 3, 2021, 2:47 PM

#

That wont even run

shadow flower Mar 3, 2021, 2:47 PM

#

change it to nums[0]

inland iron Mar 3, 2021, 2:48 PM

#

Tnums = [1,6,200,-12,123,2,65]
def findMax(nums):
    biggest = nums
    x = 0
    biggest = nums[0]
    while x < len(nums):
        if biggest < nums:
            biggest = nums
        x = x + 1
    return biggest
Tnums = [1,6,200,-12,123,2,65]
print("The largest number is:", findMax(Tnums))

spring jasper Mar 3, 2021, 2:48 PM

#

Bruh

shadow flower Mar 3, 2021, 2:48 PM

#

not just a single index

hollow flame Mar 3, 2021, 2:48 PM

#

hi

shadow flower Mar 3, 2021, 2:48 PM

#

change everything to their respective indices

#

you are basically just switching out nums for Tnums

inland iron Mar 3, 2021, 2:49 PM

#

wait i just realized i have duplicate code

hollow flame Mar 3, 2021, 2:49 PM

#

any algo train or problem?

inland iron Mar 3, 2021, 2:49 PM

#

one sec

#

Tnums = [1,6,200,-12,123,2,65]
def findMax(nums):
    x = 0
    biggest = nums[0]
    while x < len(nums):
        if biggest < nums[1]:
            biggest = nums[1]
        x = x + 1
    return biggest
Tnums = [1,6,200,-12,123,2,65]
print("The largest number is:", findMax(Tnums))
``` fixed the duplicate code...?

shadow flower Mar 3, 2021, 2:51 PM

#

i think this should work

inland iron Mar 3, 2021, 2:51 PM

#

It doesnt

spring jasper Mar 3, 2021, 2:52 PM

#

It wont

#

My guy

agile sundial Mar 3, 2021, 2:52 PM

#

you're always accessing specific indices

hollow flame Mar 3, 2021, 2:52 PM

#

yes

spring jasper Mar 3, 2021, 2:52 PM

#

Youre hardcoding the indices

hollow flame Mar 3, 2021, 2:52 PM

#

u r wrong

#

why x < len()

#

why did u do this

spring jasper Mar 3, 2021, 2:52 PM

#

Thats not even the problem

agile sundial Mar 3, 2021, 2:52 PM

#

hollow flame why x < len()

it's a non-issue right now

inland iron Mar 3, 2021, 2:52 PM

#

Its what i was suggested to do

shadow flower Mar 3, 2021, 2:52 PM

#

oh i get what you guys are saying now

#

yeah you're hardcoding the indices

spring jasper Mar 3, 2021, 2:52 PM

#

Suggested by who

shadow flower Mar 3, 2021, 2:52 PM

#

it'll keep on looking at the second value

#

and repeating that 6 times

inland iron Mar 3, 2021, 2:53 PM

#

i originally had is as x < 8 cause the list has a static 8 indexes

spring jasper Mar 3, 2021, 2:53 PM

#

Thats not the problem....

inland iron Mar 3, 2021, 2:53 PM

#

or 7 or something

hollow flame Mar 3, 2021, 2:53 PM

#

inland iron Its what i was suggested to do

why?

spring jasper Mar 3, 2021, 2:53 PM

#

The problem is biggest < nums[1]

agile sundial Mar 3, 2021, 2:53 PM

#

the problem is not your bounds, the problem is that you're always comparing the same indices, because you've hardcoded them

hollow flame Mar 3, 2021, 2:53 PM

#

no guys

#

listen

spring jasper Mar 3, 2021, 2:53 PM

#

Bro stop

hollow flame Mar 3, 2021, 2:54 PM

#

spring jasper The problem is `biggest < nums[1]`

he's correct yeah

#

u should put counter in []

#

not 1

inland iron Mar 3, 2021, 2:54 PM

#

Like this? ```py
Tnums = [1,6,200,-12,123,2,65]
def findMax(nums):
x = 0
biggest = nums[0]
while x < len(nums):
if biggest < nums[]:
biggest = nums[1]
x = x + 1
return biggest
Tnums = [1,6,200,-12,123,2,65]
print("The largest number is:", findMax(Tnums))

hollow flame Mar 3, 2021, 2:55 PM

#

inland iron Like this? ```py Tnums = [1,6,200,-12,123,2,65] def findMax(nums): x = 0 ...

i don't think so

#

u should make a counter

#

then use it as index

inland iron Mar 3, 2021, 2:55 PM

#

ohhhh so put the x = x + 1 in the []?

spring jasper Mar 3, 2021, 2:55 PM

#

No, also i dont understand why youre not using a for loop

hollow flame Mar 3, 2021, 2:56 PM

#

this code works now

agile sundial Mar 3, 2021, 2:56 PM

#

please don't give out full solutions

hollow flame Mar 3, 2021, 2:56 PM

#

agile sundial please don't give out full solutions

ok

hollow flame Mar 3, 2021, 2:57 PM

#

inland iron ohhhh so put the x = x + 1 in the []?

why x+1

#

i said

#

a counter

#

like for loops

spring jasper Mar 3, 2021, 2:57 PM

#

X is the counter

hollow flame Mar 3, 2021, 2:57 PM

#

that it goes into the index

inland iron Mar 3, 2021, 2:57 PM

#

oh, the "for" thing?

hollow flame Mar 3, 2021, 2:57 PM

#

u need x+=1

inland iron Mar 3, 2021, 2:57 PM

#

kk

#

and that represents the index, right?

hollow flame Mar 3, 2021, 2:58 PM

#

y

inland iron Mar 3, 2021, 2:58 PM

#

im just asking so i can give the counter variable a clear name

#

like "index" or "counter"

#

not just "t"

spring jasper Mar 3, 2021, 2:59 PM

#

x is the counter

#

Dont make another variable

hollow flame Mar 3, 2021, 2:59 PM

#

spring jasper Dont make another variable

yes

inland iron Mar 3, 2021, 2:59 PM

#

so i change x = x + 1 to x += 1?

spring jasper Mar 3, 2021, 3:00 PM

#

That doesn't matter

#

The problem is that youre not using the counter when indexing

#

In the if statement

inland iron Mar 3, 2021, 3:01 PM

#

so, like py Tnums = [1,6,200,-12,123,2,65] def findMax(nums): x = 0 biggest = nums[0] while x < len(nums): if biggest < nums[x+=1]: biggest = nums[1] x = x + 1 return biggest Tnums = [1,6,200,-12,123,2,65] print("The largest number is:", findMax(Tnums))

#

Cause if so, it gives a syntax error at the counter

hollow flame Mar 3, 2021, 3:02 PM

#

inland iron so, like ```py Tnums = [1,6,200,-12,123,2,65] def findMax(nums): x = 0 b...

no

#

just

#

put x in the index

#

not x+=1

inland iron Mar 3, 2021, 3:02 PM

#

Tnums = [1,6,200,-12,123,2,65]
def findMax(nums):
    x = 0
    biggest = nums[0]
    while x < len(nums):
        if biggest < nums[x]:
            biggest = nums[1]
        x = x + 1
    return biggest
Tnums = [1,6,200,-12,123,2,65]
print("The largest number is:", findMax(Tnums)) ```

hollow flame Mar 3, 2021, 3:03 PM

#

inland iron ```py Tnums = [1,6,200,-12,123,2,65] def findMax(nums): x = 0 biggest = ...

why did u put 1 in the index

spring jasper Mar 3, 2021, 3:03 PM

#

And the other one

hollow flame Mar 3, 2021, 3:03 PM

#

hollow flame why did u put 1 in the index

yert

inland iron Mar 3, 2021, 3:03 PM

#

bro gimme a break, im a relatively new python user

hollow flame Mar 3, 2021, 3:04 PM

#

inland iron bro gimme a break, im a relatively new python user

that's why we say learn algo first

inland iron Mar 3, 2021, 3:04 PM

#

uhhhhh and it works now

hollow flame Mar 3, 2021, 3:04 PM

#

inland iron uhhhhh and it works now

good

#

go next

inland iron Mar 3, 2021, 3:04 PM

#

Tnums = [1,6,200,-12,123,2,65]
def findMax(nums):
    x = 0
    biggest = nums[0]
    while x < len(nums):
        if biggest < nums[x]:
            biggest = nums[x]
        x = x + 1
    return biggest
Tnums = [1,6,200,-12,123,2,65]
print("The largest number is:", findMax(Tnums))

agile sundial Mar 3, 2021, 3:04 PM

#

hollow flame that's why we say learn algo first

i don't think anyone says that. algorithms are not a beginner topic

onyx umbra Mar 3, 2021, 3:04 PM

#

hello

inland iron Mar 3, 2021, 3:04 PM

#

agile sundial i don't think anyone says that. algorithms are not a beginner topic

i mean, i use sololearn

hollow flame Mar 3, 2021, 3:04 PM

#

agile sundial i don't think anyone says that. algorithms are not a beginner topic

before coding u have to know

inland iron Mar 3, 2021, 3:05 PM

#

reccommended by my ICS teacher

spring jasper Mar 3, 2021, 3:05 PM

#

Learn basic python first before you start implementing builtins

onyx umbra Mar 3, 2021, 3:05 PM

#

no u definitely dont need to learn algo to code

#

just solve basic problems on some coding websites

hollow flame Mar 3, 2021, 3:05 PM

#

onyx umbra no u definitely dont need to learn algo to code

so how do u solve problems?

agile sundial Mar 3, 2021, 3:05 PM

#

hollow flame before coding u have to know

uh, how would that even be possible. algorithms are coding

spring jasper Mar 3, 2021, 3:06 PM

#

This wasnt even an algorithms issue

onyx umbra Mar 3, 2021, 3:06 PM

#

lol i know adavced algos and DSA, i m just saying u dont need to know them before hand

old rover Mar 3, 2021, 3:07 PM

#

hollow flame that's why we say learn algo first

what????? do you even know what you're talking about?

onyx umbra Mar 3, 2021, 3:07 PM

#

well python is not very different from pseudo code

inland iron Mar 3, 2021, 3:07 PM

#

spring jasper Learn basic python first before you start implementing builtins

I did that on a website thats like a sort of duolingo for coding, called SoloLearn

old rover Mar 3, 2021, 3:08 PM

#

most algo books teach w psuedocode

inland iron Mar 3, 2021, 3:08 PM

#

cause it was reccomended by my ICS teacher

old rover Mar 3, 2021, 3:08 PM

#

CLRS does

#

algorithms unlocked too

onyx umbra Mar 3, 2021, 3:08 PM

#

old rover CLRS does

yes

inland iron Mar 3, 2021, 3:08 PM

#

lol I started a deep disscussion, pog

onyx umbra Mar 3, 2021, 3:08 PM

#

inland iron I did that on a website thats like a sort of duolingo for coding, called SoloLea...

try hackerrank, its good for beginners

old rover Mar 3, 2021, 3:09 PM

#

I wouldn't recommend random coding problems

#

I would recommend projects

#

that's why you do it in psuedocode

#

that's what TAs did when they taught me how to code

onyx umbra Mar 3, 2021, 3:10 PM

#

if u know pseudo code then implementing is just copying it in good handwriting

#

logic is the main part

old rover Mar 3, 2021, 3:11 PM

#

~~learn itertools for your DS/algos problems on leetcode~~

#

~~not that I know it I just heard about it a lot~~

#

~~also please don't stare at a problem for more than 30 minutes if no thoughts come to mind~~

inland iron Mar 3, 2021, 3:17 PM

#

old rover ~~also please don't stare at a problem for more than 30 minutes if no thoughts c...

Unfortunately thats what I usually do and only afterwards do I realize I have easy access to Discord and the lovely helpful people there as well as an ICS teacher with 30+ years of coding experience

old rover Mar 3, 2021, 3:18 PM

#

inland iron Unfortunately thats what I usually do and only afterwards do I realize I have ea...

oh I only have this server

spring jasper Mar 3, 2021, 3:19 PM

#

Theres google too

inland iron Mar 3, 2021, 3:19 PM

#

google is unhelpful for coding cause the problems are usually too specific

old rover Mar 3, 2021, 3:20 PM

#

I like youtube indian guys who just solve the question no questions asked

onyx umbra Mar 3, 2021, 3:20 PM

#

allow me to introduce "geekforgeeks", its all in one package for competitive programming

spring jasper Mar 3, 2021, 3:21 PM

#

Google is incredibly helpful youre just not using it the right way

onyx umbra Mar 3, 2021, 3:21 PM

#

old rover I like youtube indian guys who just solve the question no questions asked

u indian?

old rover Mar 3, 2021, 3:21 PM

#

onyx umbra u indian?

yep

onyx umbra Mar 3, 2021, 3:21 PM

#

lol figured

#

before starting to learn coding, i would suggest to learn google first😅

old rover Mar 3, 2021, 3:25 PM

#

uhhhh

#

???

#

who are you talking to?

#

I do know how to google

onyx umbra Mar 3, 2021, 3:27 PM

#

no one, murmuring to myself

old rover Mar 3, 2021, 3:28 PM

#

ok

#

sounded like you were talking to me

inland iron Mar 3, 2021, 3:59 PM

#

Okay, now Im making a slightly less useless function that iterates through a list and determines if they are even or odd numbers, and outputs them as such. (if the list is [1, 2, 3, 4, 5, 6] the program will output [Odd, even, odd, even, odd, even] ```py
Tnums = [1, 22, 31, 48, 57, 66]
outputlist = []
evenNum = False
oddNum = False

def evenOrOdd(nums):
x = 0
number = nums[0]
while x < len(nums):
y = number % 2
if y == 1:
evenNum = True
#print("helloo")
elif y == 0:
oddNum = True
#print('helo')
x = x + 1
return number
if oddNum:
#print("odd")
elif evenNum:
#print("even")

#

And it obviously doesnt work

#

the comments are test placeholders

#

what am i doing wrong?

spring jasper Mar 3, 2021, 4:04 PM

#

What is number

#

And how does it change in the loop

inland iron Mar 3, 2021, 4:05 PM

#

idk, i didnt know what to call the variable

spring jasper Mar 3, 2021, 4:05 PM

#

What

#

Look at your code

inland iron Mar 3, 2021, 4:06 PM

#

number is the iteration

spring jasper Mar 3, 2021, 4:06 PM

#

You have a variable called number there

#

Is it?

inland iron Mar 3, 2021, 4:06 PM

#

yeah, i copied the loop code from my minmax function project

#

and tried to change it

spring jasper Mar 3, 2021, 4:06 PM

#

You define number outside the loop and then you dont change it

inland iron Mar 3, 2021, 4:07 PM

#

x = x + 1?

spring jasper Mar 3, 2021, 4:07 PM

#

Thats not number

inland iron Mar 3, 2021, 4:08 PM

#

Uh okay

#

what do i do about it

spring jasper Mar 3, 2021, 4:08 PM

#

You have to change it every iteration

inland iron Mar 3, 2021, 4:09 PM

#

remind me how id do that again?

old rover Mar 3, 2021, 4:12 PM

#

#

so when they say high = len(list) - 1

#

that's just the length of the list - 1 tho

#

that's not an actual value in the list?

#

or is it?

#

I know if you're using binary search it has to be a sorted array

spring jasper Mar 3, 2021, 4:13 PM

#

Its the last element

old rover Mar 3, 2021, 4:13 PM

#

it is????

inland iron Mar 3, 2021, 4:13 PM

#

uhhhhh i have no idea how to use binary

old rover Mar 3, 2021, 4:13 PM

#

doesn't len(list) just return the length of a list?

spring jasper Mar 3, 2021, 4:13 PM

#

Yes?

old rover Mar 3, 2021, 4:13 PM

#

so it's the length of the list - 1

spring jasper Mar 3, 2021, 4:13 PM

#

Yes

#

Its the last element

inland iron Mar 3, 2021, 4:13 PM

#

yet again, the len(list) thing doesnt matter, it just works

old rover Mar 3, 2021, 4:13 PM

#

but how is that a value

#

nvm

#

I am confusing myself

spring jasper Mar 3, 2021, 4:14 PM

#

Its the index for the last element lmao

old rover Mar 3, 2021, 4:14 PM

#

yeah i get that

#

hang on

#

lemme scroll and see how they use it

inland iron Mar 3, 2021, 4:14 PM

#

IT JUST WORKS lmaoo

#

this is unhelpful

old rover Mar 3, 2021, 4:14 PM

#

inland iron this is unhelpful

dude

spring jasper Mar 3, 2021, 4:14 PM

#

Bro this is literally what the channel is about

#

Calm down

inland iron Mar 3, 2021, 4:14 PM

#

i need hep with the loop and the defining of the even and odd numbers

old rover Mar 3, 2021, 4:15 PM

#

this is a channel where other people can ask questions

spring jasper Mar 3, 2021, 4:15 PM

#

Nothing "just works" theres a reason they do

old rover Mar 3, 2021, 4:15 PM

#

deal with it lmao

inland iron Mar 3, 2021, 4:15 PM

#

not off topic, wrong word

old rover Mar 3, 2021, 4:15 PM

#

I'm just trying to understand this stuff

#

oh mariosis

#

the next line makes sense

#

my bad dude

inland iron Mar 3, 2021, 4:17 PM

#

anyways, how do i fix it

spring jasper Mar 3, 2021, 4:18 PM

#

You fix it by first understanding how loops work and how indexing works

old rover Mar 3, 2021, 4:19 PM

#

can he show us what happens with a sample input/output?

inland iron Mar 3, 2021, 4:20 PM

#

input? the list is the input

#

the program literally outputs nothing

old rover Mar 3, 2021, 4:22 PM

#

#

I have another question about this

#

what do they mean by "item"?

agile sundial Mar 3, 2021, 4:23 PM

#

item, element, number

old rover Mar 3, 2021, 4:23 PM

#

yeah I though it was a number based off the code

#

oooooooh it has exercises

#

I already like this book

#

~~I should probably write the code out~~

old rover Mar 3, 2021, 4:27 PM

#

agile sundial item, element, number

does it really matter that the book is in python 2.7?

agile sundial Mar 3, 2021, 4:27 PM

#

probably not

old rover Mar 3, 2021, 4:28 PM

#

ok good

#

probably the wrong place since this doesn't have to do w algos/DS

cobalt cloak Mar 3, 2021, 4:31 PM

#

oops

old rover Mar 3, 2021, 4:31 PM

#

it's all good

#

you can open up a help channel tho

cobalt cloak Mar 3, 2021, 4:32 PM

#

okay thank you i will do that now

old rover Mar 3, 2021, 4:32 PM

#

yep np

#

#

binary search explained in literally one page

#

what a god

#

I have another question

#

Does binary search always have two paramaters?

#

yes right?

agile sundial Mar 3, 2021, 4:39 PM

#

uhh

#

depends on the implementation

spring jasper Mar 3, 2021, 4:39 PM

#

No

old rover Mar 3, 2021, 4:39 PM

#

oh

#

but the overall code structure is the same

agile sundial Mar 3, 2021, 4:39 PM

#

pretty much

old rover Mar 3, 2021, 4:39 PM

#

so if I get this I can use it anywhere

#

cool

agile sundial Mar 3, 2021, 4:40 PM

#

well yeah, that's thep oint

old rover Mar 3, 2021, 4:40 PM

#

~~I feel the power of binary search racing through my veins~~

agile sundial Mar 3, 2021, 4:40 PM

#

ok, but what's the big O

#

best, worst, and average case

old rover Mar 3, 2021, 4:42 PM

#

O(log n) worst case

#

but idk about the best case and average case

spring jasper Mar 3, 2021, 4:43 PM

#

Rhe best case is the element youre looking for is right in the middle of the list

old rover Mar 3, 2021, 4:44 PM

#

so that would be O(N)

spring jasper Mar 3, 2021, 4:44 PM

#

No since you start looking at the middle

old rover Mar 3, 2021, 4:44 PM

#

O(1)?

agile sundial Mar 3, 2021, 4:44 PM

#

old rover O(log n) worst case

nah, it's not log n

old rover Mar 3, 2021, 4:44 PM

#

😦

spring jasper Mar 3, 2021, 4:44 PM

#

You only have to do a couple operations and they dont depend on the size of the array

old rover Mar 3, 2021, 4:44 PM

#

agile sundial nah, it's not log n

then what is it?

agile sundial Mar 3, 2021, 4:45 PM

#

well, how do you arrive at O(log n)

old rover Mar 3, 2021, 4:45 PM

#

I saw a while loop and guessed

#

~~don't do that~~

agile sundial Mar 3, 2021, 4:45 PM

#

well, you're going to be a bit more rigorous

old rover Mar 3, 2021, 4:46 PM

#

Ok so after I guessed I googled the time complexity

#

https://www.geeksforgeeks.org/complexity-analysis-of-binary-search/

GeeksforGeeks

Complexity Analysis of Binary Search - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

#

does it say O(log(n) bc it's a different implementation of binary search?

#

probably

agile sundial Mar 3, 2021, 4:49 PM

#

no

#

the implementation doesn't matter

old rover Mar 3, 2021, 4:50 PM

#

so then why is it not O(log(n)?

agile sundial Mar 3, 2021, 4:50 PM

#

lol wait

#

it's log n, my bad

old rover Mar 3, 2021, 4:50 PM

#

wait I was actually right for once?

#

YAY

#

progress

agile sundial Mar 3, 2021, 4:51 PM

#

well, since you guessed...

spring jasper Mar 3, 2021, 4:51 PM

#

You guessed so no lol

old rover Mar 3, 2021, 4:51 PM

#

ok but why is it actually O(log(n)

agile sundial Mar 3, 2021, 4:51 PM

#

that's why just guessing is not the right way to go about it

#

why do you think it's log n

old rover Mar 3, 2021, 4:53 PM

#

bc at each stage of the while loop you divide the list in half?

agile sundial Mar 3, 2021, 4:54 PM

#

why does that make it log n

old rover Mar 3, 2021, 4:54 PM

#

bc it's log base 2

agile sundial Mar 3, 2021, 4:54 PM

#

what's log base 2

old rover Mar 3, 2021, 4:55 PM

#

isn't base 2 normally used in CS

agile sundial Mar 3, 2021, 4:55 PM

#

sure, but what's log base 2

old rover Mar 3, 2021, 4:56 PM

#

it's the power to which 2 should be raised to get the value of n

agile sundial Mar 3, 2021, 4:56 PM

#

that's not what i meant

#

what in binary search is log base 2, and why does that make it O(log n)

old rover Mar 3, 2021, 4:58 PM

#

#

idk dude this is what the book tells me

agile sundial Mar 3, 2021, 5:00 PM

#

ok, the book says it

#

that's like saying answering the question "why is this true", with "because it is"

old rover Mar 3, 2021, 5:00 PM

#

ok

#

I don't know why

agile sundial Mar 3, 2021, 5:01 PM

#

draw a picture of an array

#

and do binary search on it

inland iron Mar 3, 2021, 5:12 PM

#

lmAO my next assignment is a PALINDROME CHECKER

#

i have a to code a program that can check if a word is the same when its letters are reversed

old rover Mar 3, 2021, 5:18 PM

#

the amount of times you cut the list in half

#

is the exponent

#

that's why it's O(log(N)?

#

no that's wrong

#

~~this is why I shouldn't just watch random youtube videos from people who don't know shit~~

#

https://youtu.be/5Xef2IL02q8?t=771

YouTube

Persistent Programmer

What is Binary Search Algorithm and Time Complexity O(logN) Explain...

🔴Notes - https://medium.com/@1persistentprogrammer/binary-search-algorithm-implementation-and-time-complexity-explained-o-logn-ca55ac38e46b

🔴 Subscribe for more algorithm videos - https://www.youtube.com/channel/UCpTo8a_5OeZkR9tEcwSBbAA?sub_confirmation=1

🔴 Support me on Patreon - https://www.patreon.com/persistentprogrammer

✅Connect with me...

▶ Play video

agile sundial Mar 3, 2021, 5:22 PM

#

the amount of times you cut the list in half is the exponent

old rover Mar 3, 2021, 5:22 PM

#

#

so then what does he mean by "guesses"?

agile sundial Mar 3, 2021, 5:22 PM

#

tries, checks

old rover Mar 3, 2021, 5:22 PM

#

are guesses iterations?

agile sundial Mar 3, 2021, 5:23 PM

#

not necessarily, but since you guess once per iteration, they are equal

old rover Mar 3, 2021, 5:23 PM

#

ok but 2^32 is not 4 million

#

it's around there

#

but not really

agile sundial Mar 3, 2021, 5:23 PM

#

it's about 4 billion

old rover Mar 3, 2021, 5:24 PM

#

oh is that billion

#

sorry my eyes are dying

#

yeah that is billion

#

my bad

#

why couldn't he use the actual precise number?

#

I would've spotted the entire relationship like half an hour ago

#

grrrrr

agile sundial Mar 3, 2021, 5:25 PM

#

what

spring jasper Mar 3, 2021, 5:25 PM

#

log2(100) isnt 7 either

old rover Mar 3, 2021, 5:25 PM

#

it's 128

#

so it's slightly off

agile sundial Mar 3, 2021, 5:26 PM

#

yes, that's why he said "at most"

#

not "it will take x"

spring jasper Mar 3, 2021, 5:26 PM

#

You cant have .664 of a step

#

You round up

#

Actually you dont round up, you ceil

old rover Mar 3, 2021, 5:27 PM

#

~~can't endure CLRS but complains that Grokking is imprecise~~

#

ok well

#

I finally figured it out

#

good shit

agile sundial Mar 3, 2021, 5:27 PM

#

it's not imprecise, it's reasonably accurate

old rover Mar 3, 2021, 5:28 PM

#

whatever

agile sundial Mar 3, 2021, 5:28 PM

#

anyway, since it takes log(n) checks...

#

(continue the reasoning)

old rover Mar 3, 2021, 5:30 PM

#

that means it has a time complexity of O(log(n)?

#

n0

agile sundial Mar 3, 2021, 5:30 PM

#

yeah, but you're missing a step in between

old rover Mar 3, 2021, 5:30 PM

#

idk what the step is here

#

I said that the amount of iterations in the while loop it takes to break the list into smaller pieces is the exponent you put over the 2

agile sundial Mar 3, 2021, 5:31 PM

#

right, mathematically, you could describe that as

#

#checks = log(n)

old rover Mar 3, 2021, 5:31 PM

#

by checks you mean iterations right

agile sundial Mar 3, 2021, 5:31 PM

#

yeah

old rover Mar 3, 2021, 5:33 PM

#

what goes in the N?

#

a large input

#

sorry i'm just very burnt out rn

agile sundial Mar 3, 2021, 5:34 PM

#

maybe you should take a break

old rover Mar 3, 2021, 5:34 PM

#

yeah perhaps

#

#

oh boy here we go again

agile sundial Mar 3, 2021, 5:36 PM

#

if you want a rigorous definition, pick a rigorous resource ¯_(ツ)_/¯

#

otherwise, you're going to have to deal with simplified explanations

old rover Mar 3, 2021, 5:36 PM

#

~~simplified is good for beginners~~

#

it was just a joke

wise dust Mar 3, 2021, 5:38 PM

#

Ok

violet bramble Mar 3, 2021, 6:55 PM

#

Hi anyone know about arc consistency algorithms in constraint satisfaction problems

keen hearth Mar 3, 2021, 7:19 PM

#

violet bramble Hi anyone know about arc consistency algorithms in constraint satisfaction probl...

Yes, hello 😄

#

What's your question?

violet bramble Mar 3, 2021, 7:26 PM

#

keen hearth What's your question?

Im looking to implement the arc consistency 3 algorithm in sudoku to reduce the domain of each variable and potentially solve the sudoku. Is the best way to start by having two python programs one for the ac3 algorithm and one for the sudoku?

keen hearth Mar 3, 2021, 7:27 PM

#

What do you mean by two programs sorry?

violet bramble Mar 3, 2021, 7:28 PM

#

One program where the algorithm is implemented and another for the sudoku i.e sudoku.py and ac3.py

keen hearth Mar 3, 2021, 7:29 PM

#

Oh right. You could do, although I'm not sure how you would structure the code in that case. I would first focus on how you are going to represent a partially-solved sudoku puzzle.

#

You need to keep track of the domains of each of the boxes in the sudoku (which digits you haven't ruled out yet for each box).

#

If the domain of a box is ever empty, that means it is unsolvable.

violet bramble Mar 3, 2021, 7:32 PM

#

Oh okay i guess the first thing would probably be to create rows, columns as the variables and populate the variables with domain 1-9 if it is not already filled

keen hearth Mar 3, 2021, 7:32 PM

#

Yep I think so.

#

Oh actually, I think I get what you meant now. You mean should you write an implementation for constraint satisfaction that works for any CSP, then use it to solve sudoku?

#

Vs writing a constraint satisfaction solver that is specific to sudoku puzzles.

violet bramble Mar 3, 2021, 7:34 PM

#

Just a solver that is specific to sudokus

#

the main issue is coding the constraints and the neighbours and cross checking between them

keen hearth Mar 3, 2021, 7:37 PM

#

You could encode the constraints in a general way that could be used by the AC3 algorithm. Or you could write constraint propagation functions that are specific to Sudoku. The latter approach is taken here: https://norvig.com/sudoku.html

austere sparrow Mar 3, 2021, 7:38 PM

#

Speaking of sudoku, sgtpuzzles (Simon Tatham's Puzzle Collection) seems to be an absolute gem for solving algorithms. It's written in C, but its files have plain English comments on how each solving algorithm works.

violet bramble Mar 3, 2021, 7:42 PM

#

Alright thanks ill have a look at those

old rover Mar 3, 2021, 8:31 PM

#

so do linked lists have no index?

#

is that what Grokking algorithms is trying to say?

spring jasper Mar 3, 2021, 8:32 PM

#

Well yes

#

To get to a particular node you need to traverse all nodes before it

old rover Mar 3, 2021, 8:32 PM

#

#

yeah I'm not gonna get this until I see it in code

spring jasper Mar 3, 2021, 8:33 PM

#

Arrays are different to linkedlists

old rover Mar 3, 2021, 8:33 PM

#

yep ik

#

he says that the elements in a linked list aren't next to each other

#

like if you wanted the fifth element

#

you'd have to from the 1st to the 5th

#

but if you were using an array you could just pull out the 5th one

spring jasper Mar 3, 2021, 8:34 PM

#

In memory he means

#

Linkedlists arent contiguous

old rover Mar 3, 2021, 8:34 PM

#

yeah he mentions it's about memory

#

Suppose you have a sorted list of 128 names, and you’re searching through it using binary search. What’s the maximum number of steps it would take?

#

is this bc 2^7=128?

#

bc binary search has a time complexity of O(log(n)?

spring jasper Mar 3, 2021, 8:37 PM

#

The max num of steps is ceil log2(128)

#

So 7 yes

old rover Mar 3, 2021, 8:37 PM

#

ok cool

#

You have a name, and you want to find the person’s phone number in the phone book.

#

this is also binary search

spring jasper Mar 3, 2021, 8:38 PM

#

Pretty much yes

old rover Mar 3, 2021, 8:38 PM

#

so O(log(n)

#

good shit

#

when they say linked lists have slow reads and fast inserts

#

they mean getting to each element is slow

#

but putting in new elements is fast

#

right?

#

also I watched a video and someone called the "elements" in the array pointers??

spring jasper Mar 3, 2021, 8:42 PM

#

Depends, inserting in the middle of the list is O(n) i think

#

Appending is constant if you have a pointer to the tail

old rover Mar 3, 2021, 8:42 PM

#

should I take a break and learn pointers rn or can I just continue w DS/algos

#

bc Grokking hasn't even mentioned pointers yet in the book so far

onyx root Mar 3, 2021, 8:43 PM

#

@old rover do you understand how a linked list works?

old rover Mar 3, 2021, 8:43 PM

#

onyx root <@!567030124306759710> do you understand how a linked list works?

working on that rn just asking clarifying questions

spring jasper Mar 3, 2021, 8:43 PM

#

Inserting in the middle means you start from the head, traverse the list until you find the index you want to insert at and then change a couple references

onyx root Mar 3, 2021, 8:43 PM

#

old rover working on that rn just asking clarifying questions

I ask because linked lists are made with pointers, so you might already understand pointers

old rover Mar 3, 2021, 8:44 PM

#

onyx root I ask because linked lists are made with pointers, so you might already understa...

I've never heard of pointers

spring jasper Mar 3, 2021, 8:44 PM

#

Well then now's the time haha

old rover Mar 3, 2021, 8:44 PM

#

yep

#

~~why doesn't Grokking even mention them~~

#

I guess in trying to be simple and readable he has to let go of some things

#

which is fine tbh that's why I have Google

spring jasper Mar 3, 2021, 8:47 PM

#

A deep understanding of pointers isnt really needed

#

Theyre things that point to other things

old rover Mar 3, 2021, 8:47 PM

#

https://youtu.be/Ast5sKQXxEU

YouTube

Joe James

Python: Linked Lists (fast)

Linked Lists explained (fast) with animated example, and how to write a Linked List program in Python 3, with add, remove, find and size functions example code implementation.

PYTHON LINKED LISTS
► Linked Lists Intro https://youtu.be/Bd1L64clh34
► Fast Linked Lists Intro https://youtu.be/Ast5sKQXxEU
► Doubly Linked Lists https://youtu.be/sDP_p...

▶ Play video

#

so is a pointer just a value that "points" to the next value in memory?

spring jasper Mar 3, 2021, 8:48 PM

#

It points to another address in memory, not necessarily the next one in line

old rover Mar 3, 2021, 8:48 PM

#

yeah the book says it can go all over the place

#

it doesn't have to be sequential

#

~~maybe just do a re read of it~~

spring jasper Mar 3, 2021, 8:49 PM

#

Im not a C buff, someone else might be better at explaining pointers

austere sparrow Mar 3, 2021, 8:49 PM

#

A linked list is basically

None  # empty list
(1, None)  # [1]
(1, (2, None))  # [1, 2]
(1, (2, (3, None)))  # [1, 2]

the advantage of it is that you can prepend an item in O(1), or take a tail without copying and without mutation

old rover Mar 3, 2021, 8:50 PM

#

so they call the things in linked lists nodes

#

the first thing is called a root node

austere sparrow Mar 3, 2021, 8:50 PM

#

austere sparrow A linked list is basically ```py None # empty list (1, None) # [1] (1, (2, Non...

!e
you traverse it like

def iter_list(list_):
    while list_ is not None:
        item, list_ = list_
        yield item

list_ = (1, (2, (3, None)))

for item in iter_list(list_):
    print(item)

halcyon plankBOT Mar 3, 2021, 8:50 PM

#

@austere sparrow :white_check_mark: Your eval job has completed with return code 0.

001 | 1
002 | 2
003 | 3

spring jasper Mar 3, 2021, 8:50 PM

#

Or the head node

#

Head and tail are more common terms

old rover Mar 3, 2021, 8:51 PM

#

they did this in Scala back at UB

#

but I was gone by then lmao

#

~~irrelevant~~

austere sparrow Mar 3, 2021, 8:52 PM

#

are you familiar with queues?

old rover Mar 3, 2021, 8:52 PM

#

uhh no

spring jasper Mar 3, 2021, 8:52 PM

#

Queues come later in traditional ds textbooks i believe

#

They always start with the linked list

mint jewel Mar 3, 2021, 8:53 PM

#

car cdr are very common terms as well

austere sparrow Mar 3, 2021, 8:53 PM

#

@old rover are you familiar with trees?

old rover Mar 3, 2021, 8:53 PM

#

austere sparrow <@!567030124306759710> are you familiar with trees?

no ...

spring jasper Mar 3, 2021, 8:53 PM

#

Lisper begone

mint jewel Mar 3, 2021, 8:53 PM

#

I have seen at least 2 not lisp examples with car cdr

spring jasper Mar 3, 2021, 8:54 PM

#

What do they even mean

#

fst and snd atleast have intuitive names

mint jewel Mar 3, 2021, 8:54 PM

#

address register, decrement register

#

they never actually never mapped to those registers

#

it was just a neat name

austere sparrow Mar 3, 2021, 8:55 PM

#

old rover no ...

So a tree is a data structure where you can have nodes and branches:

        a
       /  \
      b    c
     /|\
    d e f
   /|   |
  g h   i

you can imagine a table of contents, or an HTML page (if you know HTML), or a family tree, or a phylogenetic tree of species, or an inheritance tree.

#

And a linked list is just a special case of a tree: