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

Recursion

Example: drawing an English ruler. An English ruler is a ruler in which each major unit has major tick marks, and minor units have minor tick marks occurring at successive halves. Between marks for whole inches, there are minor ticks at 1/2 inch intervals; between the 1/2 inch intervals, minor ticks at 1/4 inch intervals; etc.

To draw in ascii:

---

0

- -- - --- - -- -

---

1

- -- - --- - -- -

---

2

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