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