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 Rivest Read 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).