Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Dijsktra's Shortest-Path Algorithm.
• Algorithm design principles.
• Greedy algorithms.
• Quick review of asymptotic analysis.
• Additional characteristics of Big-Oh.

Preliminaries

Admin

• If you have not filled out the department course preferences survey, please do so asap.
• The department has a new academic honesty policy, available at http://www.cs.grinnell.edu/academic-honesty-policy.
  
  • I expect all of you to read it.
  • I will ask you to sign something attesting to it.
  • Chat with me if you have questions about it.
• My normal office hours are MWF 11:00-11:50. You sign up for those at https://rebelsky.youcanbook.me. My paperwork times are M-F, 8-9 am. Those are probably the best times to try to schedule alternate appointment times. Check my schedule for more. (I'll give up the occasional class prep time if necessary, but I prefer advance notice.)

Upcoming Work

• For Friday: Read chapter 2 of Skiena.
• For Monday: Problems 2-1, 2-2, 2-3, 2-8, 2-13, 2-14, 2-15, 2-18, 2-23, 2-32, 2-37, any two interview problems from chapter 2.
  
  • Turn in hardcopy.
  • I prefer that you write your homework in LaTeX. If you don't know LaTeX, now is a good time to start learning!
  • Discuss with anyone. Cite.

Extra Credit

Academic

• CS Table, Tuesdays, topic tbd.
• CS Extras, Thursdays, topics forthcoming. (No extras this week.)

Peer

• Men's Soccer, 5pm, 9/4 vs. Crown College
• Women's Soccer, 2pm, 9/5 vs. Simpson.

Questions

Dijkstra's Shortest-Path Algorithm

Slightly modified version of the version from Wikipedia, available at https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.

 1  function Dijkstra(Graph, source, target):
 2
 3    dist[source] = 0              // Distance from source to source
 4    prev[source] = undefined      // Previous node in optimal path initialization
 5
 6    create vertex set Q           // Unvisited nodes
 7
 8    for each vertex v in Graph:   // Initialization
 9      if v != source:             // (unvisited nodes)
10        dist[v] = INFINITY        // Unknown distance from source to v
11        prev[v] = UNDEFINED       // Previous node in optimal path from source
12      add v to Q                  // All nodes initially in Q (unvisited nodes)
13      
14    while Q is not empty:
15      u = vertex in Q with min dist[u]    // Source node in the first case
16      remove u from Q 
17          
18      for each neighbor v of u:   // where v is still in Q.
19        alt = dist[u] + length(u, v) // length of path through u
20        if alt < dist[v]:         // A shorter path to v has been found
21          dist[v] = alt 
22          prev[v] = u 
23
24    return dist[target]           // or the path using prev

What's the running time? You can use n for the number of nodes and m for the total number of edges.

• Two outer loops, one inner loop in the second loop
• for each vertex, v, in Graph runs n times.
  • Body takes constant.
  • First loop is O(n)
• while Q is not empty runs n times
  • Body ignoring the loop - Constant. But may depend on how remove is implemented.
  • Inner loop - # edges around the node - could be as bad as O(n)
• This analysis: O(n^2)
• But it doesn't count carefully. For example, we could have only two edges from each node.
  • First loop, O(n)
  • Second loop, ignoring inner loop, O(n)
  • Sum of all inner loops is O(m)
  • Total work: O(n+m)
• What about 'find thing with minimum distance' and 'remove that thing'?
• What do we know that helps?
  • min-heap - O(1) to find smallest, O(logn)
  • Whoops, that complicates the "change the priority/distance" operation
• Even if we ignore that difficulty, the second loop is O(nlogn) plus the inner loop.

Morals

• Not every operation is constant. Make sure you know how your data are organized.
• Know good ways of organizing data.
• Sometimes running time involves multiple variables and formulae.

What's the underlying design principle?

• Greed!
• Greedy algorithms take the thing that seems best at the current moment (smallest, largest, etc.)

Algorithm design principles

• Selection sort
  • Greedy
• Merge sort
  • Divide and conquer
• Quick sort
  • Divide and conquer
  • Randomization can make some things easier (but analysis harder)
• Heap sort
  • Use of clever data structures
  • Heaps are arranged like trees - perhaps D&C
  • Greed: Smallest value is always at the top

Questions for the class

• Is this model working okay for you? Generally yes.
• Should I randomize partners? Certainly (or no)

Greedy algorithms

Quick review of asymptotic analysis

Additional characteristics of Big-Oh