Chapter 7: Review

Exam structure
18:12

  1. Apply a graph algorithm by hand and show your work
    • BFS, DFS, Topological sort
    • Dijkstra/Ford-Bellman, A*
    • Kruskal, Prim
  2. One dynamic programming or divide-and-conquer question
  3. One or two graphs questions (a variation of an algorithm seen in class)

Divide and conquer
18:12

Divide and conquer with arrays. Note that strings are arrays too.

Dynamic programming
18:12

Dijkstra
18:12

Dijkstra 2
18:12

Bellman-Ford
18:12

Exercise 1: find the town judge
18:12

Leetcode

Loading

Exercise 2: Find the center of a star graph
18:12

Leetcode

Loading

Exercise 3: Connecting cities with minimum cost
18:12

Leetcode

Loading

Exercise 4
18:12

Exercise

Given a string and a set of valid words , design an algorithm that determines if the input string can be segmented into a space-separated sequence of valid words.

For example, if and the input string is "Iamimportant", the string can be split into I am important

Assuming that checking containment in takes constant time, your algorithm should run in .

Exercise 5: Graphs
18:12

Exercise

Let be a directed graph, whose edges are coloured either red or blue. We want to find the shortest path from some vertex to some vertex .

One additional constaint: our shortest path must consist of first red edges (though potentially 0 of them), and then exclusively blue edges (or 0).

Hints:

  • Consider the graph with only the red edges
  • Consider the graph with only the blue edges

Coloured graphs again
18:12

Consider a connected undirected graph where each edge has an integer weight as well as a color which is either red or blue. Give an efficient algorithm to find an MST of the graph with the smallest number of red edges. In other words, among all possible MSTs, the algorithm should output one that has the least number of red edges. Your algorithm should run in time O(|E| log |V |). Prove the correctness of your solution.

(Hint: reduce the problem to a standard MST problem on weighted graphs without edge colors)