Tuesday, February 17, 2009

Final Project Group Topics

Group

Project

1

Trees Root, Siblings, External Node, Ancestors, Descendant, Depth, Height, Degree

Operations: Insert, Remove, Search, Display

2

Traversal -

Trees PreOrder

Operations: Insert, Remove, Search, Display

3

Traversal -

Trees InOrder

Operations: Insert, Remove, Search, Display

4

Traversal - Trees PostOrder

Operations: Insert, Remove, Search, Display

5

Tree Application

Arithmetic Expression Tree

Operations: Display

6

Binary Tree –

Number of nodes, number of external nodes, number of internal nodes, height

Operations: Insert, Remove, Search, Display

7

Directed Graph Operations

make-graph(): graph

Create a new graph, initially with no nodes or edges.

make-vertex(graph G, element value): vertex

Create a new vertex, with the given value.

make-edge(vertex u, vertex v): edge

Create an edge between u and v. In a directed graph, the edge will flow from u to v.

get-edges(vertex v): edge-set

Returns the set of edges flowing from v

get-neighbors(vertex v): vertex-set

Returns the set of vertexes connected to v

8

Undirected Graph Operations

make-graph(): graph

Create a new graph, initially with no nodes or edges.

make-vertex(graph G, element value): vertex

Create a new vertex, with the given value.

make-edge(vertex u, vertex v): edge

Create an edge between u and v. In a directed graph, the edge will flow from u to v.

get-edges(vertex v): edge-set

Returns the set of edges flowing from v

get-neighbors(vertex v): vertex-set

Returns the set of vertexes connected to v

9

Weighted Graph Operations (an extension of undirected/directed graph operations)

make-edge(vertex u, vertex v, weight w): edge

Create an edge between u and v with weight w. In a directed graph, the edge will flow from u to v.

10

Graph Traversal

Depth – First Traversal

11

Graph Traversal

Breadth-First Search

12

Weighted graphs: Dijkstra’s algorithm

13

Travelling Salesman Problem

Friday, February 13, 2009

Reporting Update

Report Schedule
IT2A - Thursday/February 19, 2009
IT2B - Thursday/February 19, 2009
IT2C - Wednesday/February 18, 2009
CS2 - Friday/February 20, 2009

The presentation of your topics will start according to the date specified above for your respective classes.