<strong> <br><a href="http://www.unlv.edu/">University of Nevada Las Vegas </a> <br><a href="http://www.egr.unlv.edu/"> Howard R. Hughes College of Engineering </a> <br><a href="http://www.cs.unlv.edu/"> School of Computer Science </a><br> <a href="http://www.cs.unlv.edu/~larmore"> My Home Page</a><br> </strong> UNLV CS Spring 2007 Assignment 9

CS 302 Assignment 9

Due date: Tuesday, April 24, 2007, 8:30 AM.

All programming assignments must be submitted electronically. Submit them to the graduate assistant, James Oravec, on or before the due date.
All written assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Homework 9 is a hand-written assignment, on which Homework 10 will be based.
Do not write C++ (or other) code for Homework 9.
Last update: April 19, 2007
  1. Minimum Spanning Tree.
    1. Read the following wikipedia pages: Wiki link: Minimum Spanning Tree Wiki link: Prim's Algorithm Wiki link: Kruskal's Algorithm
    2. Work the following problem described in the following links: postscript version or pdf version
  2. Components of a Graph, using Union-Find.
    1. Read the following wikipedia pages: Wiki link: Disjoint-set data structure Wiki link: Connected component (graph theory)
    2. Work the problem described in the following links: postscript version or pdf version
  3. Huffman's Algorithm.
    1. Read the following wikipedia pages: Wiki link: Huffman Coding Wiki link: Greedy Algorithm
    2. Using Huffman's algorithm, find a minimal prefix code for the alphabet {D,E,K,M,Q,X} where the frequencies are given as follows:
      • - D 15
      • - E 18
      • - K 7
      • - M 12
      • - Q 2
      • - X 3
  4. Dijkstra's Algorithm and Bellman-Ford Algorithm.
    1. Read the following wikipedia pages: Wiki link: Dijkstra's Algorithm Wiki link: Shortest Path Problem Wiki link: Bellman-Ford Algorithm
    2. Use Dijkstra's algorithm, showing steps, to solve the single source minimum weight path problem, where A is the source, for the following weighted directed graph, represented as a list of weighted edges:
      • - A B 5
      • - A C 1
      • - A E 2
      • - B C 2
      • - B F 1
      • - D B 1
      • - E C 0
      • - E F 5
    3. Use the Bellman-Ford algorithm, showing steps, to solve the single source minimum weight path problem, where A is the source, for the following weighted directed graph:
      • - A B 2
      • - A C 5
      • - B D 1
      • - B E -1
      • - C D -4
      • - D B 3
      • - E D -2
    4. Use the Bellman-Ford algorithm, showing steps, to solve the single source minimum weight path problem, where A is the source, for the following weighted directed graph:
      • - A B 2
      • - A C 5
      • - B D 1
      • - B E -1
      • - C D -4
      • - D B 2
      • - E D -2
  5. Strong Components of a Directed Graph.
    1. Draw a picture of the directed graph G which is defined below by an array out-neighbor lists:
      • - 1: (2)
      • - 2: (3,5)
      • - 3: (4)
      • - 4: (2,5)
      • - 5: (4,6)
      • - 6: (6)
    2. Indicate the strong components of G, by circling them in red (or any other different color). You do not have to show any steps.
  6. Write down the array of in-neighbor lists of G, the directed graph given in problem 5. You do not have to show any steps.
  7. Tropical Matrix Multiplication.
    1. Write the matrix representation of the weighted directed graph G given below:
      • - A B 2
      • - B C 1
      • - B D 1
      • - C B 5
      • - C D 1
      • - D A -1
    2. Use tropical matrix multiplication to compute the graph which represents the solution to the all-pairs minimum path problem for G.
  8. To help satisfy the "communication" part of your degree, please write two essays an essay. Each essay should be about 300 words. Use LaTeX to write your essays.
    1. Why are data structures imporant? You may include details about abstract data types.
    2. What is dynamic programming? What are some problems that can be solved with dynamic programming? Provide a simple example of a dynamic programming problem, and wrok through the solution of one instance of that problem, showing steps.
      You may use a problem that you find elsewhere as inspiration, but please do not copy it exactly, i.e., make it your own.
    Problem 8 is the only problem in this homework that should be typed and printed. Please submit a printed copy of your LaTeX code, as well as the compiled essay. The other problems must be hand-written, as usual. Wiki link: LaTeX
    Use the LaTeX Section, at the bottom of the linked page, as a reference for a template and a tutorial: James Oravec
    The Not So Short Introduction to LaTeX: PDF Version
  9. Dynamic Programming.
    1. Read the following wikipedia pages: Wiki link: Dynamic Programming Wiki link: Optimal substructure Wiki link: Overlapping subproblems
    2. Work the problem described in the following links: postscript version or pdf version
  10. Read and understand the following topics; they may be present on the final exam.
    1. Breath First Search and Depth First Search-
      1. Read in your text about breath first search and depth first search, work any associated problems in the text on your own. Questions may be answered during class or during office hours.
      2. Read the following wikipedia pages:
        Wiki link: Backtracking
        Wiki link: Breadth-First Search
        Wiki link: Depth-First Search
        Wiki link: Heuristic
    2. B-Trees and Other Tree Topics
      1. Read about B-Trees in your textbook, and work any associated problems in the text on your own. Any questions you have will be answered during class or during office hours.
      2. Read the following wikipedia pages:
        Wiki link: 2-3 Tree
        Wiki link: Associative array
        Wiki link: AVL Tree
        Wiki link: B-Tree
        Wiki link: Self-balancing binary search tree
  11. Advanced Topics that you are not required to know, but you can read for your enjoyment.
    Wiki link: kd-tree
    Wiki link: Knuth's Up-Arrow Notation
    Wiki link: Linear Programming
    Wiki link: Max-flow Min-cut Theorem
    Wiki link: Online Algorithms
    Wiki link: Randomized Algorithm
    Wiki link: T-theory