York University - CSE 3101 - Summer 2006
Phuong Nguyen

Summary of Lecture 7:

1. Kruskal's algorithm and Prim's algorithm for The Minimum Spanning Tree Problem.

2. The Generic algorithm for MST. Correctness of the Generic algorithm.
Showing that Kruskal's and Prim's algorithms are special case of the GenericMST algorithm.
References: Chapter 23.

3. Another graph problem that can be solved using Greedy algorithm: The
Shortest Path Problem [Introduction to Chapter 24, and Section 24.3]

3. The Longest Common Subsequence Problem. Going from top-down to bottom-up approach.
Improvement by storing the length of the longest common subsequences instead of their lengths.
[Section 15.4]