Math 3770 - Combinatorial Computing

Spring 2014

Last updated April 17, 2014

Welcome to the web site for Mathematics 3770. You will find links to the syllabus, tentative course schedule, a list of homework assignments, notes & slides.

- Show means prove: state what is known, what you intend to prove, how you intend to prove it, then give the steps of the proof.
- Explain how you determine your answers — do not simply write down a number.

Book | Section | Problems | Due Date |

Tucker | 1.1 | 4, 7, 14 (all maximum), 20, 24, 25, 38, 39 | F 1/17 |

Rosen | 9.1 | 1, 13ab | F 1/17 |

Rosen | 9.2 | 27 | F 1/17 |

Tucker | 1.2 | 1, 5a-d, 6a-d, 7, 8, 14, 16 | W 1/22 |

Rosen | 9.2 | 15, 20abc, 26A, 53b | W 1/22 |

Tucker | 1.3 | 1, 3, 4, 5, 7, 8, 11, 12, Restate Ex. 4, pg 29 in plain English | M 1/27 |

Rosen | 9.3 | 1, 5, 9a, 10, 19, 34–38 | M 1/27 |

Tucker | 1.4 | 2, 3bcfgh, 4, 5, 7bdeg, 9a, 12, 16a, 21 | W 1/29 |

Rosen | 9.2 | 4, 5 (why or why not?), List vertices and colors: { 21, 22, 23 } | W 1/29 |

Rosen | 9.4 | 1, 2, 4, 5, 38 | W 2/5 |

Rosen | 9.7 | 1, 4, 5, 6, 7, 23 | W 2/5 |

Tucker | Pg 52–54 | 2, 3, 4, 5a, 15a, 17ab, 18a, 20, 23a, 26a | F 2/7 |

Rosen | 9.5 | 1, 2, 4, 13, 15, 18, 20, 26a/27a, 37, 39, 41, 50, 51 | M 2/10 |

Tucker | 2.1 | 1, 3 (w/ pic), 4, 5, 7, 16, 17, 19 | W 2/12 |

Rosen | 9.8 | 5, 6, 7, 8, 13, 16, 19, 21 (5-8), 22ab, 24 | M 2/17 |

Tucker | 2.2 | 2 (draw graphs, label vertices for c), 4cdeh, 8ac, 14, 18a | W 2/19 |

To model a problem as a graph,
include descriptions of what a vertex
represents, and what relationship
between vertices are represented by an
edge between them. If applicable, an
explanation of edge weights is necessary
as well.
| |||

Rosen | 9.8 | 9, 10, 11, 20, 21 (9-11) | F 2/21 |

Rosen | Pg 677 | 2, 6, 7, 11, 12, 13ac, 14, 20abd | F 2/21 |

Tucker | 2.3 | 1acegi, 2, 4, 7, 8, 12, 17 | M 2/24 |

Tucker | 2.4 | 1, 2, 4, 7a | W 2/26 |

Rosen | 10.1 | 2, 14 (prove both directions), 16, 17, 19, 27, 28 | F 2/28 |

Tucker | 3.1 | 1c, 2, 3, 12, 22, 24b, 26 | M 3/3 |

Rosen | 10.3 | 7–15 (7, 8 & 9 with pre-, in-, and postorder traversals), 28, 29 | W 3/5 |

Tucker | 3.2 | 4a, 7, 8, 10 | F 3/7 |

Tucker | 3.3 | 1, 2, 7ad, 17 | |

Rosen | 10.4 | 1, 2, 3, 4, 7a, 10, 13, 14, 16(13/14), 24, 33, 34, 35 | |

Tucker | 3.4 | 2, 6 | |

Rosen | 10.5 | 1, 2, 4, 6, 8, 10, 19, pg 746: 26 | |

Tucker | 4.1 | 1, 7, 9 | |

Rosen | 9.6 | Set one: {1, 5, 8, 9, 10, 14} Set two: {7, 11, 12, 17, 25} | |

Tucker | 4.2 | 1, 2, 3, 6, 17 | |

- Binary Tree, Induction Proof
- Tree Search Homework Sheet
- Heapify Worksheet
- Dijkstra’s Shortest Path Worksheet
- Dijkstra’s Shortest Path Worksheet II
- TSP Worksheet
- Bin Packing Worksheet
- Flow Worksheet I
- Flow Worksheet II
- Flow Worksheet III

- Week1 Slides Handout
- Week 2 Slides Handout
- Week 3 Slides Handout
- Week 4 Slides Handout
- Week 5 Slides Handout
- Week 7 Slides Handout
- Week 8 Slides Handout
- Week 9 Slides Handout
- Week 10 Slides Handout
- Week 11 Slides Handout
- Steiner Trees Slides Handout
- Algorithmic Paradigms Slides Handout
- Bin Packing Slides Handout
- Network Flows Slides Handout
- Week 13 Slides Handout

For feedback, please feel free to e-mail me.

All materials copyright 2000–2014.