308-360 Tutorial #1

308-360 Tutorial #2

308-360 Tutorial #3

308-360 Tutorial #4

308-360 Tutorial #5

308-360 Tutorial #7

308-360 Tutorial #8

308-360 Tutorial #9

308-360 Assignment #1 Solution

Cormen, Leiserson and RivestRead the book Know the algs Do the proofs |

How to Write Proofs every thing you need to know, including Proof by Contradiction, If and Only If, Direct Proofs, Proof by Mathematical Induction.

Main Topics

- Induction
- Dynamic programming
- General form for dynamic programming algorithm
- Problem to recursion to dynamic programming algorithm.
- How to prove correctness, time complexity
- Dynamic programming on directed acyclic graphs Topological sort
- BFS
- How to apply BFS to a graph or digraph.
- Computing the shortest number of edges.
- BFS search, BFS trees and their properties
- DFS
- How to apply DFS to a graph or digraph
- Components in a graph
- DFS trees, DFS search, and their properties
- Start times and funish times and what they mean
- Strong components of a graph
- Condensation graphs
- Algorithm for strong components
- Dijsktra's algorithm
- Bellman Ford algorithm and detection of negative weight cycles
- Matrix multiplication solution for shortest paths
- Minimum spanning trees
- Prim's algorithm
- Kruskal's algorithm

Key Algorithms

- Generic dynamic programming (loop version and memoization version)
- DFS
- BFS
- Fast strong components algorithm
- Topological search
- Dijsktra's algorithm
- Bellman Ford algorithm
- Prim's algorithm
- Kruskal's algorithm

How to properly answer algorithm questions

- "show how..." = "Convince me that you know how to..."
- "Give pseudo code" = "Write out full pseudo code"
- "Prove that" or "Give a formal proof that" = write out a proof in detail - clearly identiy induction basis, step etc. Detail of pseudo code should be at the same level as in lectures (i.e. not assembly code).