Memorizing computer science algorithms

[moo]

Hi All,

I would love some help with memorizing CS algorithms. I’m currently taking the Coursera algorithms specialization. I would like to be able to recall all the algorithms from memory by the end of the course. (There are probably only going to be about 20 or so in total). I was using Anki to quiz myself, but my answers are always wrong somehow because my memory of each algorithm is fuzzy and vague. Also, pulling out a text editor and writing out 6 lines of code doesn’t lend itself well to Anki. It seems self-quizzing from a memory palace would be better.

I need help coming up with a good method, then probably I could stuff each algorithm mnemonic in a memory palace at the end of each class.

Here are two examples.

Ex 1. Random Contraction Algo (pseudocode)

given Given graph G=(V,E)

while there are more than 2 edges
    pick a remaining edge (u,v) uniformly at random
    merge u and v into one vertex
    remove any self-loops
return the cut represented by the final 2 vertices

Ex 2. Partition Function

def partition(A, l, r):
  p = A[l]  # naïve emplementation
  i = l+1
  for j in range(l+1,r+1):
    if A[j] < p:
        swap(A[j], A[i])
        i += 1
    swap(A[l], A[i -1])

Ex. 3 Quicksort (pseudocode)

1. Select a pivot element p
2. Partition the array around p such that first < p < last
3. recurively sort array halves “first” and “last”

Any ideas?

Thanks!
moo

[bjoern.gumboldt]

@moo

I would like to be able to recall all the algorithms from memory by the end of the course. (There are probably only going to be about 20 or so in total).

Let’s assume in addition to quick sort, there will also be merge sort, bubble sort, etc… now what exactly are you planning on memorizing, if I may ask?

@moo

pulling out a text editor and writing out 6 lines of code doesn’t lend itself well to Anki.

Any decent IDE has code completion these days, so it’s very different from using a text editor. Secondly, any half decent language will let you do array.sort() or array.sorted() in some sort of way. There is really no need in knowing how to type out the algorithm.

Also, if I hired you and you started typing out your own sorting routine for the kind of trivial problems Coursera most likely discussed, we’d need to have a talk. These days, there is extremely rarely the need for someone to write their own sorting routine.

@moo

I’m currently taking the Coursera algorithms specialization.

There is however a need to understand the performance differences of the three aforementioned algorithms: on average, best case, and worst case. Really you should be able to answer why this list:

2, 5, 7, 9, 11, 17

is fasted sorted by a bubble sort and not a quick sort, even though quick sort outperforms bubble sort on average any day of the week.

@moo

Any ideas?

First things first… there is no need to memorize pseudo code for an algorithm you don’t understand. Can you actually describe in your own words how a quick sort works? Because if you can, I don’t understand how you’d have trouble memorizing the algorithm because clearly, you already know it.

Also have a look here in case this is not the book you are using for the course… this is the standard text at most good universities.

Any one know a book or video course about algorithm basic to advanced

[moo]

Hi @bjoern.gumboldt thanks for the reply. Despite what you’re saying , I still have the same goal and request as in the original post. My goals are to recall from memory the pseudocode for all the algorithms in the course I’m taking . I would love help with creating mnemonics for these so that I can recall them 7 months from now.

I think you’re saying that (paraphrasing)

1. with modern IDEs and code frameworks I shouldn’t need to know how to implement sorting because I can use framework.sort().

   • On a practical level sure, that’s an argument against learning and memorizing this. However, my goal is not to become more efficient in daily programming. I studied this decades ago, and now I’m relearning it. Exactly because of what you mentioned (autocomplete, and no need to implement oneself) this information gets forgotten easily. Now, since I"m bothering to put in the effort to relearn this material, I want to commit it to memory with some mnemonics.

2. This ability to recall algorithms from memory is not professionally relevant.

   • I disagree, more most programmers sure you don’t need to use this. However, it’s used in hiring. For example, if you want to get hired at google you’ll have to recall things like how to balance a RB-tree on the whiteboard, all from memory without an IDE. Additionally, there are real-life algorithm development tasks in data science and text mining. For example, implementing locality-sensitive hashing for a particular application isn’t available out of the box.

3. I also need to know time complexities

   • I totally agree, however, I think I have a handle on memorizing these.

So, @bjoern.gumboldt what do you think?

Maybe I need to turn each algo into some story and memorize that…

[elitely (Mamunur Rashid)]

@moo

while there are more than 2 edges pick a remaining edge (u,v) uniformly at random merge u and v into one vertex remove any self-loops return the cut represented by the final 2 vertices

This should be easy,I think. You need to select the important words that convey hints to the main idea,convert the words into images, and put them in the Memory palace. You visualize the words/pegs/images,make a story and your brain fill up the rest of the equation:

Wheel=While
Eggs=Edges
Pickup truck=Pick

This lines “while there are more than 2 edges” becomes “wheel” and 2 Eggs
A pickup truck does something with the remaining “Egg”…etc

[elitely (Mamunur Rashid)]

@moo

Ex 2. Partition Function

def partition(A, l, r):
  p = A[l]  # naïve emplementation
  i = l+1
  for j in range(l+1,r+1):
    if A[j] < p:
        swap(A[j], A[i])
        i += 1
    swap(A[l], A[i -1])

I’d convert the symbols into images like below and put them in a Memory Palace:

Symbols	Images
$	Dollar
%	unicyclist
&	Russian Doll
’	Head Push Pins
(	longBow
)	longBow
*	Star
+	Car Nut loosening tool
,	rusty nail
-	ruler scale
.	Pingpong ball
/	(L)oft hatch door
:	Hand Cuff
;	sea horse
<	Loud Speaker
=	Rail line
>	bellows of a blacksmith
?	coat hanger
@	paperclip
¿	wheelchair
!	baseball stick
"	testicals
#	Window
£	pound coin
¢	hack saw
[	Telephone Mouthpiece
\	slide of a playground
]	Telephone Mouthpiece
^	dunce’s hat
_	Floor
`	CCTV camera
{	recurve bow
¦	Pipe
}	recurve bow
~	drill bit
For	Fur
While	Wheel

[bjoern.gumboldt]

@moo

thanks for the reply. Despite what you’re saying , I still have the same goal and request as in the original post. My goals are to recall from memory the pseudocode for all the algorithms in the course I’m taking .

Lol… fair enough, more power to you. I just wanted to point out why that whole exercise may not be as beneficial as you might imagine.

@moo

with modern IDEs and code frameworks I shouldn’t need to know how to implement sorting because I can use framework.sort() .

That’s not really what I’m saying… of course you should “know how to,” but why would that mean memorizing pseudo code? Pseudo code is just one way, I could also ask you to give it to me as a flow chart OR check your conceptional understanding (see first post) asking you when a quick sort that normally outperforms a bubble sort wouldn’t do so. Maybe I’ll just simply give you a list and ask you to write down what it looks like in the next iteration.

@moo

For example, if you want to get hired at google you’ll have to recall things like how to balance a RB-tree on the whiteboard, all from memory without an IDE.

See my point above… I’d see you actually drawing exactly “that” on the board though… not the pseudocode of the algorithm. Anyways… on to your question…

@moo

Maybe I need to turn each algo into some story and memorize that…

Well yeah… story method or place the individual steps in a memory palace. Really up to you…

@elitely

You need to select the important words that convey hints to the main idea,convert the words into images, and put them in the Memory palace. You visualize the words/pegs/images,make a story

Think about that for a second… most algorithms can be visualized easily as the steps that they perform, so unless you want to memorize the algorithm in a particular language there isn’t much need to visualize things as other things.

@elitely

I’d convert the symbols into images like below and put them in a Memory Palace:

Symbols	Images
$	Dollar
%	unicyclist
&	Russian Doll
’	Head Push Pins
(	longBow
)	longBow

Which proves my point… let’s simply take line 2 from above:

@moo

p = A[l] # naïve emplementation

Some languages use // or /* */ instead of #, so what are we doing here… especially, once we consider that it’s used to mark a comment… don’t tell me that you need to know where inside the pseudo code comments go is important.

DItto for [ and ] because not all languages use that notation for subscripts. I could also write the pseudo code as A_l if that’s possible. Certainly possible with pen and paper… and on this forum I can do it by writing A_l and putting it inside of $s but that’s not the point. That line simply says:

Place the \color{blue}value that is in position \color{red}l in the array \color{red}A into a variable called \color{blue}p.

What you need is an image for your variable and an image that represent a certain array at a certain subscript position. The individual letters are obviously not chosen randomly, so that shouldn’t be much of an issue.

So if that’s what you want to do, that is how I’d approach it. Also, if you do need mathematical notation, just use braille instead of making up your own like suggested above. There are a few standards in braille and there is no need to reinvent the wheel for that… plus you can just use the images from your binary system… I’ve written about it here:

Using Braille to Memorize Mathematical Formulas

Continuing the discussion from Learn Braille In No Time Using Your Binary System: There have been quite a few times that people here have asked for ways to memorize mathematical formulas and things of that nature. Just like in the post linked above, you can use braille for that as well. Quick recap: If you have a 00-99 image system, you can create a binary system, and that in turn let’s you encode braille cells. So all of this can be done using your existing system. Click the link above to see…

[moo]

Thanks, @bjoern.gumboldt, and @elitely!

@bjoern.gumboldt it seems from your comment that you’re advising/cautioning against memorizing a specific implementation verbatim as well as pointing out the risks of memorizing something you don’t understand. All of which I completely agree with.

I suppose I want to recall what each algorithm does (in a basic sense) and enough detail to reason about it. I thought memorizing pseudo code would be a reasonable way to go. I think you’re saying if I want to recall sequences of code (which you caution against) then converting to braille is one method to check out. Is that right?

@elitely suggested using pegs to convert the code, then sort of treat the whole endeavor like memorizing a poem.

I just binge-read @LynneKelly 's Memory Craft (which is great!!) One thing that struck me from her book is that dry abstract info (like algorithms) needs to be made concrete and using characters, stories and narrative devices is a good way to do that.

So trying to apply all of that advice, I think making a story with characters around each algorithm can concretize and exemplify what is happening.

Taking quickstort as an example, I suppose I want to recall:

pseudocode steps

1. select pivot element p
2. partition around p, s.t. first <= p <= last
3. recursively quickstort first
4. recursively quickstort last

important points

• selecting the pivot is the most important aspect affecting average time complexity
• method to select pivot: first element (naive), median element (of 3), randomized p selection
• swaps are done in memory without data copying overhead (vs. mergesort)
• partition is a linear scan, that only compares each element with subarrays against p

story with linking-method

• Allan Turing (Benedict Cumberbatch from The Imitation Game) is sorting his boxes of stolen enigma machine parts. He has got to do this quickly [quicksort] to beat the Nazi’s.
• Deep down, Allan knows this is about to be the most important choice of his life. Sweat is dripping down his brow. He has got to choose now, under so much pressure—face wincing—he decides to pick one at random [randomized qsort].
• He selects a important pivot P-element—like E.T., kind of anointing it with a glowing finger. P-element is activated and comes alive, also glowing. [selecting p is the first and most important step]
• P-element looks like the letter P made out of industrial plumbing and rocks a late-80’s mullet.
• P-element grows arms and legs and walks alongside all the boxes one by one. [linear scan]
• P-element is kind of a selfish d***head with a “small man complex” he and only cares about (compares against) himself. You can tell by the way he struts when walking. [comparison sort only check if A[i] > p]
• While walking, whenever P finds someone smaller, he shoves them into one of the smaller-parts box. He gives the smaller part a “whatcha gunna do about it ?!” smirk. [swap elements in place]
• Deep down, P knows his harsh ways are faster than Marge’s (Simpson) friendlier copy-machine sort [merge-sort is slower due to copies]
• Finally P-element tries to hang out with the bigger elements… but because he is so sensitive about his size, he places himself right between the small and big boxes [final partition function step is to place p]
• Allan zaps the small and large boxes with his magic recursion wand. ZAP! ZAP! “Recursion-lightening” bolts hit the small and large boxes.

I suppose I need to locate this story somewhere. So if I had algorithms class memory palace, then Allan (and this scene) could go in the “divide and conquer” room

So, I suppose I see if that works for the others…

[bjoern.gumboldt]

@moo

I think you’re saying if I want to recall sequences of code (which you caution against) then converting to braille is one method to check out. Is that right?

@bjoern.gumboldt

if you do need mathematical notation, just use braille

Not exactly what I said.

@moo

Taking quickstort as an example, I suppose I want to recall:

You might want to watch this video before committing your story to memory… just to make sure you got the concept right.

[moo]

@bjoern.gumboldt Thanks for clarifying what you meant and for the video.

When I compare the video to my story, I see that I left out walking both i,j pointers down the array. I wonder how much detail to include? Do you think it’s worth adding that detail level of detail?

Thanks!
Moo

[bjoern.gumboldt]

@moo

Do you think it’s worth adding that detail level of detail?

@moo

While walking, whenever P finds someone smaller, he shoves them into one of the smaller-parts box. He gives the smaller part a “whatcha gunna do about it ?!” smirk. [swap elements in place]

Well, what exactly is it “swapping”?

[moo]

Well, this whole thing led me down a rabbit hole .

I wanted to make completely sure that I don’t memorize something that’s filled with bugs , so I took the prettiest quicksort implementations I could find from StackOverflow and autogenerated test cases against them. And… every single one had issues . Crazy!

But the whole activity got me wondering why each one was wrong. So after walking my favorite implementation on paper , drawing out arrays of numbers I came up with the following. I know this is outside the scope of the art of memory… but in case this helps someone with memorizing:

def qsort(L, first, last):    
    if first >= last:  # recusion base case
        return
    
    p = L[random.randint(first, last)]  # select pivot

    i, j = first, last
    while i < j:
        while L[i] < p:
            i += 1
        while L[j] > p:
            j -= 1
        L[i], L[j] = L[j], L[i]  # swap

        # NB: L_i and/or L_j may == p, so we must either i++ or j--
        if L[i] != p:  # avoid slipping by the pivot
            i += 1  # push i forward if L_i != p
        else:
            j -= 1  # back up j if L_i == p
    qsort(L, first, i-1)
    qsort(L, j+1, last)

story

1. Allan Turing (Benedict Cumberbatch from The Imitation Game) is sorting his boxes of stolen Enigma-machine parts. He has got to do this quickly [quicksort] to beat the Nazis.
2. Allan scratches his head confusedly. He’s worried about the time-bending effects of his recursion wand he checks if Igor and Jackrabbit have already crossed paths [base case]
3. Sweat drips down his brow. Deep down, Allan knows this is about to be the most important choice of his life. He has got to choose now, under so much pressure—face wincing—he points one element out at random ! Allan anoints P-element with an E.T.-like glowing finger P-element is activated and comes alive and glows bright pink. P-element looks like the letter P made out of industrial plumbing and sports a late-80’s mullet. [randomized pivot selection].
4. P-element is kind of a selfish dickhead with a “small man complex” and only cares about [compares against] himself. You can tell by the way he struts when walking. [compare against P only]
5. P shoots two little minions out of his arms. It’s Igor and Jack the jackrabbit [i,j pointers]!
6. The minions race across the boxes from opposite ends. [linear scan from both sides]
7. Igor stops when he finds someone bigger than P
8. Jack stops when he finds someone smaller than P
9. Whenever P notices that his minions have stopped moving, he forces the elements next to the minions to swap. He gives the smaller element a “whatcha gunna do about it ?!” smirk. [swap elements in place]
10. A Ford EDGE pulls up and HONKS [edge cases].
11. Startled by the sound, Igor takes out his measuring tape and checks that the next box doesn’t contain anyone exactly the same size as P. He takes one deliberate step forward. Igor knows that if the next box is the same size as P, then his friend Jack will move instead.
12. They continue on, repeating this, until they’re standing in the same spot. Igor and Jack high-five each other once because their work is done for now.
13. Startled by the high-five, Allan zaps the small and large ranges of boxes with his magic recursion wand. ZAP! ZAP! “Recursion-lightening” bolts hit the small and large boxes .

[moo]

Does anyone else memorize algorithms? Do you do it like I did or are there better ways?

[HigherLearning]

Hi @moo,

I have no understanding about algorithms so I was avoiding this post for the last 3 days.

Yesterday, elitely posted the symbols list and so I stopped by to give it a like,since I was looking for it myself.

Today I see that u r still having difficulty with the algorithm, so I thought, let me check, what its really about.

To me, ur story is extremely complicated.It seems like u r trying to be a fiction writer,more than trying to memorize an algorithm(I maybe wrong).

Also, nowhere in ur entire post u have tried to explain what the algorithm really means,so that someone with no knowledge about this field can help u out. If I had any understanding of ur equation, I dont think it would be difficult to memorise it.

(I wanted to quote the exact part,but for some reason I m not able to).

Here are some of my suggestions:

Convert the Enigma Machine into a memory palace.

Eg.

Notice the various pegs.

According to ur story,it seems there are 13 points.

If it were me, I’d convert most of the elements to marvel movie characters.
Eg.
Quicksort = Quicksilver/Quasar

I = Ironman
J = Juggernaut

p = Pivot(ie, a fulcrum)

Iron man & juggernaut on the 2 ends of the fulcrum & battling out using their powers.

I’d place all these characters on the Enigma machine pegs.

Am I making sense?..Maybe not, since I dont understand the inter-relations among the algorithm.

Just thought I’ll give it a try

[moo]

@HigherLearning

It seems like u r trying to be a fiction writer,more than trying to memorize an algorithm(I maybe wrong).

I was trying to use the techniques of: a character, narrative, and emotion. In my head, it’s like a comic strip with some of the frames animated. What I’m trying to memorize has nothing to do with the Enigma machine, it’s just that Allan Turing was a computer scientist who appeared in that movie “Imitation Game” which I saw. So that provides a nice memory hook to something known.

@HigherLearning

Also, nowhere in ur entire post u have tried to explain what the algorithm really means,so that someone with no knowledge about this field can help u out. If I had any understanding of ur equation, I dont think it would be difficult to memorise it.

That’s a good point. Let me try:

• Quicksort takes an array and sorts it “in-place” without making any copies of data. It does this in three basic steps:
  1. Select a pivot element p
  2. Partition the array A around p such that A_first_half < p < A_last_half
  3. Recursively sort array halves “first” and “last” using quicksort

That’s the basic algorithm called quicksort. I was wondering out loud if I should memorize the basic algorithm (i.e. the three steps above) or if I should memorize a specific implementation in a programming language. I opted for the latter.

I’ve connected the story bullet point numbers to the code below

implementation with mnemonics as comments

def qsort(L, first, last):
    if first >= last:  # story line 2
        return

    p = L[random.randint(first, last)]  # story line 3

    i, j = first, last # story line 5
    while i < j:
        while L[i] < p:  # story line 4, 6, 7
            i += 1
        while L[j] > p:  # story line 4, 6, 8
            j -= 1
        L[i], L[j] = L[j], L[i]  # story line 9
        # story line 10
        if L[i] != p:  # story line 11
            i += 1 
        else:
            j -= 1  # story line 11
    # story line 12
    qsort(L, first, i - 1)  # story line 13
    qsort(L, j + 1, last)  # story line 13

[HigherLearning]

@moo

I was trying to use the techniques of: a character, narrative, and emotion. In my head, it’s like a comic strip with some of the frames animated

I get that,but IMO the less emotion u give to a character the better.I presum, u have many of such codes to memorize,its always better to be as minimalistic as possible.

@moo

What I’m trying to memorize has nothing to do with the Enigma machine

Agreed.But dont u think that Machine is perfect for your purpose.I can fit so much data on that alone.And since u made the Cumberbatch reference,U can also make a story about Cumberbatch being Turing in the day but at night he becomes Dr strange which may well be of help for some of the other codes(Again,just guessing).

I’m just trying to brainstorm some ideas.Trying to see what I’d have done in your place.

@moo

Quicksort takes an array and sorts it “in-place” without making any copies of data. It does this in three basic steps:

1. Select a pivot element p
2. Partition the array A around p such that A_first_half < p < A_last_half
3. Recursively sort array halves “first” and “last” using quicksort

Quicksort = Quicksilver.There are 2 Quicksilvers in the movies(one from the marvel universe and the other from the Xmen franchise)

Quicksilver is a refree in a battle between Ironman & Juggernaut.
Before the match starts,Quicksilver puts a partition around the Pivot(Fulcrum)
The first & last arrays are sorted by the 2 quicksilver characters.

My version of ur story line:

Iron man & Juggernaut are positioned on either end of the fulcrum/Pivot/See Saw(whatever).
Quicksilver is the referee in the middle

Both ironman[ i ] & juggernaut [j ] have the power to shrink/magnify in size (ala Ant man).

If ironman shrinks, he will get +1 point ,whereas, if juggernaut magnifies he will have a point deducted.

Story line 9 = Both characters swapping their positions.

Something along these lines.

[melissatowner]

The best way to learn algorithms is to implement each one, making it do something non-trivial and useful in the real world.

If you can’t find a real-life application, look harder. This is a sign of not knowing the algorithm well enough.