1. Introduction
- What is an algorithm?
- Semantic analysis
- Correctness
- Complexity
- Time complexity
- Elementary operation
- Principle of invariance
Resources
2. Algorithmic Trading
- Project in algorithmic trading
3. Incremental Paradigm
- Incremental Paradigm
- Insertion sort
- Incremental Recurrences
4. Divide and Conquer I - Merge Sort
- Divide and Conquer Paradigm
- Merge Sort
- Time Complexity Merge Sort
5. Growth of Functions
- Asymptotic notation
- Common functions
Resources
- CLRS I.3
- DVP 0.3
- grofun.pdf
- grofun.zip
- MIT Introduction-to-algorithms 2005
- Lab 4
6. Divide and Conquer Paradigm II
- Other Examples of D-C
- Chip Testing Problem
- Binary Search
- Convex Hull
- Towers of Hanoi
- Alternative Methods to Solve D-C Recurrences
- Characteristic equation method
- Substitution method
- Master method
- Z transform
Resources
- CLRS I.4
- DVP 2
- divcon2.pdf
- divcon2.zip
- DISI Applets
- Binary and Linear Search Visualization
- Divide and Conquer - Convex Hull
- https://visualgo.net/en/convexhull
- Divide and Conquer, Merger Sort y complejidad de recurrencias Programacion Competetiva UNAL
- MIT Introduction-to-algorithms 2005
- Towers of Hanoi Animation
- Videos
- Algorithms UN 6.1 Divide and Conquer Paradigm II - Youtube
- Algorithms UN 6.2 Divide and Conquer Paradigm II - Youtube
- Algorithms UN 6.3 Divide and Conquer Paradigm II - Youtube
- Algorithms UN 6.4 Divide and Conquer Paradigm II - Youtube
- Algorithms UN 6.5 Divide and Conquer Paradigm II - Youtube
- Algorithms UN 6.6 Divide and Conquer Paradigm II - Youtube
7. Dynamic Programming
Resources
- CLRS IV.15
- DVP 6
- IPython notebook: fibonacci
- IPython notebook: lcs
- IPython notebook: cutrod
- IPython notebook: timeitexmaples
- Lecture 15: Dynamic Programming, Longest Common Subsequence MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
- https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- DISI LCS applet
- CS 97SI: Introduction to Programming Contests - Jaehyun Park - Stanford University, 04-dynamic-programming.pdf change-integer partitions
- Ch15 Dynamic Programming Charles Tappert, Pace University
- CS3233 Competitive Programming - old teaching materials - Steven Halim - NUS, week04_dp_1.pdf, week04_dp_2.pdf
8. Efficient Data Structures - Heap Sort
- Binary heaps
- Heap sort
- Priority queues
Resources
- CLRS II.6
- heapsort.pdf
- heapsort.zip
- VisuAlgo - https://visualgo.net/en/heap
- IPython notebook: montículos
- Lecture 4: Heaps and Heap Sort MIT Introduction to Algorithms( 6.006) Fall 2011
- Udacity CS 215 Lesson 4: It’s Who You Know Keeping track of your best friends using heaps
- DISI HeapSort
- Sorting Comparison Demos
9. Randomization - Select and Quick Sort
- Medians and Order Statistics
- Randomized Select
- Deterministic Select
- Quicksort
- Randomized Quicksort
Resources
- CLRS II.7
- DVP 2.4
- selectquicksort.pdf
- selectquicksort.zip
- https://visualgo.net/bn/sorting
- DISI Quicksort
- Lecture 6: Order Statistics, Median MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
- Median - Wikipedia
- Percentile - Wikipedia
- Quantile - Wikipedia
- Order Statistic -- from Wolfram MathWorld
- Computer Generation of Statistical Distributions
- Lecture 4: Quicksort, Randomized Algorithms MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
- Quicksort form interactivepython.org
- IPython notebook:quicksort from interactivepython.org
- IPython notebook: randomquicksort distr comps(tiempo)
- IPython notebook: quicksort two finger comp distrib (tiempo)
- DISI Applets
- Sorting Comparison Demos
- Distributional Convergence for the Number of Symbol Comparisons Used by QuickSort from JA Fill, Johns Hopkings U.
- Distributional Convergence for the Number of Symbol Comparisons Used by QuickSelect.from JA Fill, Johns Hopkings U.
10. Input Tuning - Sorting in Linear Time
- Lower bound for sorting
- Counting sort
- Radix sort
- Bucket sort
Resources
- CLRS II.8
- DVP Pg 63
- sortinginlineartime.pdf
- sortinginlineartime.zip
- https://visualgo.net/bn/sorting
- Lecture 5: Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort MIT Introduction to Algorithms (SMA 5503) Fall 2005
11. Graph Algorithms
Resources
- IPython notebook: búsquedas
- IPython notebook: Dijksitra
- IPython notebook: Djkstra_eppstein
- IPython notebook: BellmanFord
- IPython notebook: FloydWarshall
- DISI decompositions_of_graphs.rar
- DISI ch04-paths-in-graphs.ppt
- Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search ,
- Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints and
- Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
- CS3233 Competitive Programming - old teaching materials - Steven Halim, NUS, week05_graph_1.pdf
- Udacity CS 215 Lesson 5: Strong and Weak Bonds Working with social networks with edge weights
12. Greedy algorithms
Resources
- CLRS IV.16
- DVP 5
- Lecture 16: Greedy Algorithms, Minimum Spanning Tree MIT Introduction to Algorithms (SMA 5503) Fall 2005