Problem solving in general, algorithms, graph theory

computer_science
algorithms

#1

[If I can think of a better intro, ill put it here]


This is after a class that I have been learning about. More information here:

Feel free to just start on any of these/bring anything up. I'll probably post things throughout too (I'm still learning more plus there's all the stuff that I haven't gotten to put on yet)

Thanks to @Stradyvarious for interesting discussions and inspiring me to get started!


#2

Cool first?
Second post!!!
Do u have A general topic


#3

Haha thanks @FCD :smiley: sadly sorry, I don't have a general topic at the moment, but feel free to tag me anywhere :relaxed: i'd be happy to join in your general topic or talk to a Hopscotcher!


#4

I think one of the things that has really got me wondering is abstraction of problems

(from the Alexandria repository resource which we are using):

Coding is the task of translating the algorithm into the language that the computer can understand. Unlike coding, Computer Science is concerned with the algorithm itself, regardless of how it is expressed in a particular programming language.

Pseudocode, writing code with more English-like terms to express an algorithm, is independent of the language that you use.

What is an algorithm?

  • a series of executable, well-defined steps that will solve a problem in a finite amount of time.
  • it will produce the same output no matter who runs it

There are other parts about the top-down approach to problems that I think are fascinating, I am not so great at expressing it back though.


Here is just some code from Snap and Edgy that we have been doing, for @Stradyvarious :smiley:

Recursion

I admit I've been really excited about these because I have wondered about them in Hopscotch for a long time

Oooh now looking back again, there was an idea that we had a think about for website browser histories — when you press the forward/backward buttons on your web browser, or for the concept behind storing undo/redo actions.

We were looking at a concept of abstract data types (like in addition to integers, lists, arrays, there are stacks, queues which I had never heard of before.) more about those two here:

The code for it is here, you can import XML files into Edgy which is straightforward, but I'm just going to have this as a start before I start piling on heaps :laughing:

https://gist.githubusercontent.com/t1-tracey/a07e4eb0950c11a60e21c473739f861b/raw/9bc17f5fd6499ee4a5462b4d0c05019972062942/EdgyBrowserHistory.xml

(you just save this as a file then Import in Edgy)

and let me know if you want to have a look and/or run into any troubles.


#5

Wow! That's a lot of information!
Because I'm very confused, I think I'm just gonna hang out in my Numberphile Topic..

Great topic!
This reminds me of a project I made a while ago, even though it's not that similar: Click me!


#6

Hi @JonnyGamer :smile: if you do want to investigate further at any point, I'll be here :slight_smile:

Here's a video on Prim's algorithm, which can be used to generate mazes (it seems to explain at longer pace though):


I couldn't be bothered watching all of it to be completely confirming... but it doesn't touch on the maze aspect anyway.

Otherwise, in text here are some ideas-

  • If you abstract a maze, you can treat the intersections and dead ends as a concept called nodes (where the paths join) and the paths themselves as edges between the nodes.

  • or you could treat each square as a node and each edge connecting between them. This is what we can do too.

I guess I should explain in case of the rest of the topic, a graph is just a set of nodes and a set of edges, it can be applied to represent whatever you want it to :smile:

whoops I don't want to be overwhelming plus I'm a little bit exhausted after today anyway, let's just take it at an easy pace :blush:

@Stradyvarious feel very free to join in too if this interests you as well :smile: this was another thing that we only briefly touched upon in class.


Nerdy Maths topics [check 'em out here!]
#7

Thanks for the invite.
You have so much info and topics that I can't process it all.
Your topic realy interests me allot , so I keep a close eye on this.


#8

Haha I can't even process either because there's not really much opportunity to spend ages and ages exploring each idea, (like with recursion alone for example I could imagine making so many drawing projects and not even counting the other stuff yet...) and then there's all these resources online.

I take ages to put up anything anyway hehe :upside_down: it is a bit of effort for me though I love it, especially doing it here on HSF :smile: but it will all be casual pace anyway :blush:

Hehe I think from what I've read, it sounds like it is spelled "a lot" :thinking:


#9

The most useful abstract data type is undoubtedly the lambda (anonymous function), as it has the ability to emulate all other data types (such as cons cells for example).

The lambda type alone is turing complete


#10

Ooh wow, I have heard only of cons as an operation on an abstract data type (e.g. for lists) but I don't know very much even about that :relaxed:


#11

Yes, mazes connect a lot with graph theory and topology.
I had never thought about splitting up a maze like that! It's very interesting like it's simplifying the whole thing down to a graph set!


#12

Yeah! :smiley: it is interesting when you simplify a lot of things into graphs – people friendship networks (people as nodes, relationships/friendships as edges), board game states (nodes as states for tic tac toe for example, and edges with arrows indicating a move from one state to another), cities and maps – thinking about abstraction has been something I've really liked about this which I never knew about before hehe :upside_down:


#13

Ooh! Also if there's people in a room, what are the chances that 2 of them have the same birthday. It's really fun thinking of problems like this as well

Also, the seven bridges of Könisgberg is super cool!


#14

Oooh I've seen the birthday one as probability but not for this yet – sounds very interesting to think about – and oooh yes we looked at how the Seven Bridges one can be represented with a graph! Along with the four colouring map problem and 'can you draw these images without lifting your pencil' sort of one! :smiley:


I have class :grimacing: so goodbye for now!


#15

Bye!


#16

This is recursion with drawing a binary tree :smiley: doing recursion in those languages definitely helped with thinking about it Hopscotch :slight_smile: and recursion in general. (– hence me making the topic on Hopscotch functions too)


#17

Wow! That's awesome! (You did it in Hopscotch!?)
There should be a clone every split. I wonder how that'd work?..


#18

Yep, ooh I realised I could link the project too –

this one doesn't use clones, it treats each branch like drawing the original (if you want to watch it, you could make the object visible and play the project too :D)


#19

Woah! That's super awesome! (I love the curved one! :joy:)


#20

Here are some related posts where I've been implementing the abstract thinking ideas that we'd gradually learnt about in this class:

  • top down design — you start with the main ideas, then gradually work down into the details