Download PDF
Linked lists
Doubly linked lists
Reversing linked lists
Insertion sort on linked lists
Merging sorted linked lists
Dynamic arrays
Implementing stacks with arrays or linked lists
Implementing queues with doubly linked lists
Implementing dequeues with doubly linked lists
Binary search trees and sets
Self-balancing binary search trees, including red-black trees
Self-balancing non-binary search trees, including B-trees
Using hash tables to create associative arrays
Tries
Implementing priority queues with a heap
Heaps and heapsort
Finding any path between nodes using stacks and depth-first search
Finding the shortest path between nodes using queues and breadth-first-search
Finding the shortest path on weigthed graphs using Dijkstra's algorithm and priority queues
Using heuristics for greedy search and A* search
The travelling salesman problem and the Christofides algorithm
Hamiltonian paths and Hamiltonian cycles
Identifying Eulerian paths
Constraint Satisfaction Problem (CSP) and Sudoku
Divide and conquer algorithms and merge sort and quick sort
Memoisation using search trees for associative arrays
Dynamic programming and the Bellman equations
Modify BFS to prioritise cost not depth. expand node with lowest path cost. could be "deep".
This is the same as Dijkstra’s algorithm.
Can do this in algo by using heaps
Informed: No
Time: \(O(b^{?})\)
Space: \(O(b^{?})\)
Complete: Yes
Optimal: Yes