Neuroscience
- This Blog Is Brought To You By The Number 9 And The Letter K
The Neurocritic (the blog) began 9 years ago today. I've enjoyed the journey immensely and look forward to the years to come, by Nodes of Ranvier (the band — not the myelin sheath gaps). Node of Ranvier And now a word from our sponsors, ...
- Monopoly Is A Perfect Example Of Embodied Cognition
I teach a Matlab programming class. The main project I get people to work on is programming up a version of the game Monopoly. It’s a great project, I think, because it makes you use all the things Matlab is good at (loops, matrices, data in and output,...
- Float Like A Butterfly; Sting Like A Bee.
Your hands can't hit what your eyes can't see. For this reason, we have to be careful when feeding numbers into our computer. Check out what happens when you ask a basic math question to Python: Pictured: the folly of man Huh, that's strange....
- De Brujin Graphs And Velvet Optimiser
I'm working with the Velvet Assembler as part of my virus identification project. When I'm not trying to write a perl module to complement the already-bulky script files that I'm working with, I like to do something that I usually wish...
- Violence Intervention Assistant's Trainings
The VIA trainings are a "safe space" type training for issues of power-based interpersonal violence: sexual assault, relationship violence, stalking and sexual harassment. It is designed for, and presented by, undergraduate students. Participants learn:...
Neuroscience
Building a Heap
Binary heaps are binary trees that are sorted in such a way that the parent leaf is either greater or lesser than both of its child nodes. When the root node is the greatest and each parent is greater than its children, then it's a max heap. In the opposite scenario, we have a min heap. When presented with an array, we simply line up each element in the array from left to right, top to bottom in a binary tree format.
For example, the array [1, 3, 6, 5, 9, 8] would correspond to the following binary tree, sorted as a min heap:
When presented with the problem of turning an array into a max heap, my initial thought was "Why don't you just sort the array from greatest to least? Surely that will satisfy the binary condition without any fancy schmancy algorithms or recursion."
Turns out, it doesn't.
In order to solve this problem, you need to individually check each node and guarantee it follows the heap rule (that is, whether it is greater or lesser than its children if it's, respectively, max or min heap).
Confused out of my mind, I consulted MIT Open Courseware's lecture on the subject, and, after that, I was even more confused. Just to get the slightest idea of what I was dealing with, I decided to get a solution down in Xcode, whether it was great or faulty, and scripted out something like this:
1. Check every node in the tree if it follows the rule. If it doesn't, switch the node with its parent.
2. Check the tree if each node follows the rule. If not, go back to step 1. If yes, then you win!
From a computational standpoint, the errors are fairly obvious. You'd have to check each node individually over and over again until you found the mistake, and then, you'd have to check the entire tree over again.
What might make more sense would be to check each node if it follows the rule and, if it doesn't, check the parents recursively until you climb to the top of the tree, checking for errors along the way. This will rearrange the nodes in such a way that it fixed more errors more efficiently. My original solution does not "bubble-up" through the entire tree.
I'll have to fix this sometime in the future. In the meantime, I'm still working on breadth-first searches, Dijkstra's theorem, and sorting by reversals. Hopefully those will be the subjects I touch upon in the future as I get my gears in shape.
My solution to Building a Heap can be found at https://github.com/HussainAther/rosalind/HEA.py
- This Blog Is Brought To You By The Number 9 And The Letter K
The Neurocritic (the blog) began 9 years ago today. I've enjoyed the journey immensely and look forward to the years to come, by Nodes of Ranvier (the band — not the myelin sheath gaps). Node of Ranvier And now a word from our sponsors, ...
- Monopoly Is A Perfect Example Of Embodied Cognition
I teach a Matlab programming class. The main project I get people to work on is programming up a version of the game Monopoly. It’s a great project, I think, because it makes you use all the things Matlab is good at (loops, matrices, data in and output,...
- Float Like A Butterfly; Sting Like A Bee.
Your hands can't hit what your eyes can't see. For this reason, we have to be careful when feeding numbers into our computer. Check out what happens when you ask a basic math question to Python: Pictured: the folly of man Huh, that's strange....
- De Brujin Graphs And Velvet Optimiser
I'm working with the Velvet Assembler as part of my virus identification project. When I'm not trying to write a perl module to complement the already-bulky script files that I'm working with, I like to do something that I usually wish...
- Violence Intervention Assistant's Trainings
The VIA trainings are a "safe space" type training for issues of power-based interpersonal violence: sexual assault, relationship violence, stalking and sexual harassment. It is designed for, and presented by, undergraduate students. Participants learn:...