I was sick last week - oops.

The main thing do today is to see where we we are and to plan for the next two weeks before spring break.

I would like each of you to do a midterm graph project: read some literature, write some code, and show some results of how some algorithm works.

I'm setting the due date for the project as the Friday before spring break; however, if you would like to work on it over the break you may turn it in at the end of the break. In either case, expect to share it with the class after break.

- graph search general ideas
- depth-first
- breadth-first
- backtracking
- min/max game search
- examples: knight's tour, maze solving, word ladder

- minimum spanning tree
- Kruskal's algorithm
- Prim's algorithm

- shortest path (weighted graph)
- Djikstra's algorithm (and its A* variation)
- Floyd-Warshall algorithm

The general ideas are covered in the next two chapters of the text, 6 & 7 ("weighted graphs" and "search"); the details are in the second part in sections 15.3 (minimum spanning tree) and 15.4 (shortest path).

This material is in many other sources as well; browse around and see which explanations make the most sense to you.

There are too many variations and possibilities to explore them all in detail. Your goal is to (a) get an overview of the ideas, and (b) dive into (at least one) one in detail.

I'll be discussing all of these in class over the next few weeks and showing examples.

Some of this stuff gets persnickity and you may well get stuck or confused. That's OK. Persist, ask for help, and treat it as a learning experience.

- cyrus - Knight's tour
- eoghan - word ladder
- jimmy - Knight's tour
- kat - Knight's tour
- nick - Knight's tour

- tree vs graph , depth & breadth search
- recursive vs loop search order - problem 5.1
- knight's tour
- word ladder

https://cs.marlboro.college /cours /spring2019 /algorithms /notes /planning

last modified Thu July 16 2020 2:42 am

last modified Thu July 16 2020 2:42 am