## CSci 2101 Lab 12.

#### 40 points

#### Due Monday, May 1st.

#### Part 1: AVL trees feedback (10 points)

You will be assigned AVL tree code from another group. Your goal would be to determine if their implementation is correct and if it is efficient (i.e. doesn't traverse irrelevant part of the tree). Comments on their design choices (positive comments and suggestions) are welcome.

#### Part 2: Graphs (30 points)

Work in pairs on this lab.

Your goal is to finish the graph implementation that we
started in class. The most recent version was sent to you by the class email.

Finish the graph
implementation that you started on Friday. You will need to add testing
code and the implementation for breadth-first and depth-first
traversals and the shortest path algorithm.

Feel free to use the predefined Java
classes LinkedList (essentially, a queue),
Stack,
and PriorityQueue
for breadth-first search,
depth-first search, and the shortest path method, respectively.
The standard priority queue is impelmented as a priority heap so it
has log N efficiency for both addition and removal. Alternatively feel
free to use your own. Note that you would need to either make objects
that you are putting into the queue Comparable, or provide a
Comparator (also see the Comparator API). I recomemnd the latter approach, see an example in class.

#### How to submit

Submit
the java file(s) with your testing code by e-mail to me. The subject of the message
must
be **2101 Lab 12**. Make
sure to CC your group partners.

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.