Algorithms

Spring 2017
course
navigation

assignments

  due Thu Jan 26

getting started

  due Thu Feb 2

analysis and "big-O" notation

  due Thu Feb 9

linked lists

  due Thu Feb 23

recursion

  due Thu Mar 2

searching

  due Fri Mar 10

midterm sorting project

  due Tue Apr 4

trees

  due Tue Apr 11

graph basics

and a cyclic graph
Pick any node, call it X. From X, do a depth-first search, and from that find the maximum depth and a vertex furtherst down, call it A. Now starting at A, do another depth first search, and find the deepest node from A, call it B. Return the diameter (we hope) as the depth from A to B.
Consider running this on a tree (an acyclic undirected connected graph) and a cyclic graph, like the two illustrated above. Does the algorithm work in either of these cases? Explain why you think so. What is it's O() behavior? Extra credit: prove your claim in both cases.
  due Tue Apr 18

more graphs

  due Fri May 5

final project

 

term grade

http://cs.marlboro.edu/ courses/ spring2017/algorithms/ special/assignments
last modified Tuesday May 9 2017 3:53 pm EDT