Algorithms/Data Structures

Notes

Goodrich book

Sections covering algorithmic analysis:

• 4 - analysis of recursive algorithms
• 5 - dynamic array amortization
• 8 - tree traversal algorithms
• 9 - heap construction
• 10 - hash efficiency, probabilistic analysis of skip list
• 11 - amortization of splaying/balancing

Algorithms/Recursion Analysis

Skiena book

Already reviewed Skiena's data structures section, see Advanced Data Structures page.

MIT OCW

MIT 6.006 intro to algorithms

Preferred - youtube videos are available and high quality.

Fall 2011 version of 6.006 provided via Youtube:

• Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb
• Lecture 4 - heaps: https://www.youtube.com/watch?v=B7hVxCmfPtM&index=4&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb
• Lecture 5 - binary search trees: https://www.youtube.com/watch?v=9Jry5-82I68&index=5&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb
• Lecture 6 - avl trees: https://www.youtube.com/watch?v=FNeL18KsWPc&index=6&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb
• Lecture 9 - hash table doubling: https://www.youtube.com/watch?v=BRO7mVIFt08&index=9&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb

MIT 6.046 design and analysis of algorithms

Preferred:

Fall 2015 version of 6.046 provided via YouTube:

• Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp
• Lecture 4 - divide and conquer - van emde boas trees: https://www.youtube.com/watch?v=hmReJCupbNU&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=6
• Lecture 5 - amortization - amortized analysis: https://www.youtube.com/watch?v=3MpzavN3Mco&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=7
• Lecture 6 - randomization - quicksort: https://www.youtube.com/watch?v=cNB2lADK3_s&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=8
• Lecture 7 - randomization - skip lists: https://www.youtube.com/watch?v=2g9OSRKJuzM&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=10
• Lecture 8 - randomization - perfect and universal hashing: https://www.youtube.com/watch?v=z0lJ2k0sl1g&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=11
• Lecture 9 - data structure augmentation: https://www.youtube.com/watch?v=xVka6z1hu-I&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=13

Fall 2005 version of 6.046 provided on MIT's Open CourseWare page:

• Main page: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/
• Video lectures: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/
• Lecture 4 - randomized algorithms
• Lecture 5 - linear time sorting, lower bounds
• Lecture 9 - analysis of random BST
• Lecture 12 - skip lists
• Lecture 13 - amortization, table doubling
• Lots of advanced material

MIT 6.854 advanced algorithms

Spring 2016 version of 6.854 provided on Youtube:

• Playlist: https://www.youtube.com/playlist?list=PL6ogFv-ieghdoGKGg2Bik3Gl1glBTEu8c
• Entire course, really, but here are a few lectures in particular to focus on:
• Lecture 5 - Johnson Lindenstrauss lemma: https://www.youtube.com/watch?v=Tw0J5Xv6xQw&list=PL6ogFv-ieghdoGKGg2Bik3Gl1glBTEu8c&index=4
• Lecture 6 - nearest neighbor search: https://www.youtube.com/watch?v=vAboxtLEeH0&list=PL6ogFv-ieghdoGKGg2Bik3Gl1glBTEu8c&index=5
• Lecture 8 - min cost matching: https://www.youtube.com/watch?v=JxbPdIHNLqc&list=PL6ogFv-ieghdoGKGg2Bik3Gl1glBTEu8c&index=7