Design and Analysis of Algorithms

Instructor - Robert Hochberg 
Office-         STC C-121 
Phone-         328-9685 
Email-         hochberg@cs.ecu.edu		 Text - Introduction to Algorithms
second edition
by:  Cormen, Leiserson, Rivest and Stein.
 Office Hours
MWF       11-12
W              2-4

 
Download secure shell here, for access to the Solaris machines from home.  Get "SSHSecureShellClient-3.2.9.exe."

Notes from various class sessions can be found here.
Code can be found here.

Homework Assignments
HW 1 - Due Monday, Jan 26
 3-2, 3-3 and 3-4 on pages 58-59
HW 2 - Due Monday, Feb 16
 6.2-1, 3, 6 p. 132
6.3-2, 3, p. 135
6.4-1, 2, 3, p. 136
6.5-1, 2, 4, p. 140
6-1 and 6-2, pp. 142-3
HW 3 - Due Wednesday, Feb 25
 7.1-2, 3 p. 148
7.2-2, 3 p. 153
7-2, 3, 4, 6 pp. 161-3
Implement Stooge-Sort(A, i, j) in python, and
send a file called Stooge-mylastname.py to me at
hochberg@cs.ecu.edu
HW 4 - Due Friday, March 20
 This assignment concerns the file graph.py found here. 

Your assignment for Friday has two parts.  The first part is to write two new methods for this class: 
1. Test whether the graph is strongly connected (defined in the text.)  Note that this can be done very simply, without the need to perform a topological sort. This should be called with "g.stronglyConnected()"
2. Find the length of the longest path between start and end. This should be called with "g.longest(start, end)"

The second part is to modify the "Digraph" class to produce a "Graph" class, representing an undirected graph. The user ought to be able to construct a graph the same way he does with Digraph, but the class will automatically add an edge in each direction. Thus if L = {1:[2], 2:[3, 1], 3:[4], 4:[1, 3]}, then "g = Graph(L)" ought to produce a 4-cycle 
1 --- 2
|     |
|     |
4 --- 3
Notice how forgiving the constructor is, in that edges can be represented twice or once in the list L, and the graph still give undirected edges.

Finally, your graph class ought to use DFS to count the number of connected components there are in the graph.
HW 5 - Due Wednesday, March 25
 22.3-1, 6, 11 page 547
23.1-1, 3, 9 page 567
23.2-1, 4 (see "counting sort"), 8, page 573
23-4, page 577
Python Programs
 These can be found here.  Please let me know if you would like to work alone or with one other person (by email) and I will tell you which of these problems you ought to solve.
Who Which
Brian Holloman 1
Matt Rucker 2
Will Martin 3
Chance Norman 4
Tyler Hurley 5
Ken Karosy 6
Matt McClintock 20
Mitzi Ponce 21
Philip Kennedy 7
Ray Stevens 7
Joe Hang 8
Brandon Moody 8
Troy West 24
Bill Gorman 23
Brandon Mathis 9
Adam Rawlings 9
James Sigmon 22
Logan Miller 25
Seth Melugin 10

10
Miciah 26
Robert Johnson 27
Ismael Cruz 28

HW 6 - Due April 27
 22.4-1, 2, 3, page 551
22.5-1, 2, page 557
25.2-1, 3 (without the proof part), 4, page 634