Algorithms/Data Structures: Difference between revisions
From charlesreid1
(→Notes) |
|||
| (8 intermediate revisions by the same user not shown) | |||
| Line 10: | Line 10: | ||
* 10 - hash efficiency, probabilistic analysis of skip list | * 10 - hash efficiency, probabilistic analysis of skip list | ||
* 11 - amortization of splaying/balancing | * 11 - amortization of splaying/balancing | ||
[[Algorithms/Recursion Analysis]] | |||
==Skiena book== | ==Skiena book== | ||
Already reviewed Skiena's data structures section, see [[Advanced Data Structures]] page. | Already reviewed Skiena's data structures section, see [[Advanced Data Structures]] page. | ||
==6.006== | |||
=MIT OCW= | |||
==MIT 6.006 intro to algorithms== | ==MIT 6.006 intro to algorithms== | ||
| Line 21: | Line 27: | ||
Fall 2011 version of 6.006 provided via Youtube: | Fall 2011 version of 6.006 provided via Youtube: | ||
* Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb | * Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb | ||
* Lecture 4 - heaps | * Lecture 4 - heaps: https://www.youtube.com/watch?v=B7hVxCmfPtM&index=4&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb | ||
* Lecture 5 - binary search trees | * Lecture 5 - binary search trees: https://www.youtube.com/watch?v=9Jry5-82I68&index=5&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb | ||
* Lecture 6 - avl trees | * Lecture 6 - avl trees: https://www.youtube.com/watch?v=FNeL18KsWPc&index=6&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb | ||
* Lecture 9 - hash table doubling | * 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== | ==MIT 6.046 design and analysis of algorithms== | ||
| Line 52: | Line 57: | ||
==MIT 6.854 advanced algorithms | ==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 | |||
Latest revision as of 00:42, 12 July 2017
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
Skiena book
Already reviewed Skiena's data structures section, see Advanced Data Structures page.
6.006
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
 |
Algorithms Part of Computer Science Notes
Series on Algorithms
Algorithms/Sort · Algorithmic Analysis of Sort Functions · Divide and Conquer · Divide and Conquer/Master Theorem Three solid O(n log n) search algorithms: Merge Sort · Heap Sort · Quick Sort Algorithm Analysis/Merge Sort · Algorithm Analysis/Randomized Quick Sort
Algorithms/Search · Binary Search · Binary Search Modifications
Algorithms/Combinatorics · Algorithms/Combinatorics and Heuristics · Algorithms/Optimization · Divide and Conquer
Algorithms/Strings · Algorithm Analysis/Substring Pattern Matching
Algorithm complexity · Theta vs Big O Amortization · Amortization/Aggregate Method · Amortization/Accounting Method Algorithm Analysis/Matrix Multiplication
Estimation Estimation · Estimation/BitsAndBytes
Algorithm Practice and Writeups Project Euler · Five Letter Words · Letter Coverage
|