Groups and Topics

Groups

Red Team: Goldsmith, Abuelsaad, Standish, Mourino

          Network Flow

Green Team: Busby, Dodge, Fleming, Negrusa

         Branch & Bound/Backracking

Orange Team: McGregor, Harrison, Law, Sheehan

         Bayesian Networks

Topics

Backtracing    & Branch and Bound                                                                        Notes

            Write a backtracking algorithm that outputs all permutations of 1, 2, 3, …, n.

            What is the worst-case run-time of this algorithm?

            Write a backtracking algorithm that outputs all subsets of {1, 2, …, n}. 

            What is the worst-case run-time of this algorithm?

            Write a backtracking algorithm that finds all k-colorings of a graph g. What is the worst-case run-time of this algorithm?

            Write a backtracking algorithm that searches an N x N board for a knight's tour.  If a tour exists, the algorithm outputs one such tour; if no tour exists,

            it outputs a statement to that effect. What is the worst-case run-time of this algorithm?

Given a fully connected graph with weighted edges, find the minimum TSP tour in this graph.  What is the worst-case run-time of this algorithm?

            Write a branch and bound algorithm to find a solution to the 0-1 Knapsack problem.  What is the worst-case run-time of this algorithm?

Network Flow                                                                         Chapter 7

            Problems          text, Chapter 7 pp 415-426  # 2, 7, 17, 18, 19

Approximate Algorithms                                                       Chapter 11

            Problems          text, Chapter 11 p

Local Search                                                                          Chapter 12

            Genetic Algorithms, Simulated Annealing, Neural Networks

Solving Quantified Problems and Games in PSPACE         Chapter 9

Extending the limits of tractability                                        Chapter 10

            Problems          text, Chapter 10 pp 550-551 # 1, 2, 3

Bayesian Networks                                                                  Notes 

Over the next week or so, the individual group members should read over the material related to their topic.  By the 3^rd of November, the team captains should have called a meeting at which the team will discuss the reading and work to develop in each other a better understanding of their topic.  By the 9^th I will have posted a complete list of problems that the team is to answer in addition to their electronic presentation.  The team captain should assign these problems to team members and schedule additional meetings to discuss the progress of each of the team members on the problems and the presentation. 

            I will be available for help, but not before the 19^h of November.  I want to see a substantial effort by the teams to study and learn this material before I have any involvement with the project.  When and if you come for help, the state of preparation that I observe will affect the grade I give to the team.  The default assumption is that each of the team members will contribute equally to the effort.  If that is not the case it is up to the captain and other team members to inform me otherwise.