15-853: Algorithms in the Real World (Guy Blelloch and Bruce Maggs, Fall 00)

Assignment 2 Notes

Handin procedure: Please put a directory with your code in it in the the directory /afs/cs/academic/class/15853-f00/assignments/assign2/handin/. This should incluse a makefile where make will generate an encode and a decode executable. The directory should also include a short README file describing what you did. A paragraph or two is fine.

Since I was not specific about the time it is due, the assignment is due by 11:59pm on Thursday (Oct 12).

Answers to Questions

  • What does it mean for the graph to be connected?

    Answer: Consider the graph G gotten by replacing each triangle with a vertex, and placing an edge between two vertices if the corresponding triangles share an boundary-edge. You can assume this graph is connected. You can also assume that each boundary-edge belongs to at most two triangles (i.e. the triangulation is a proper surface). BTW: If you pass on the examples I give you, that will get you most of the credit.

  • Is it OK to use gzip or bzip as a subroutine, so that we can focus on the unique features of the problem without having to implement Huffman coding or arithmetic coding or dictionary lookups?

    Answer: You are free to use other people's code as long as (a) you properly reference it, and (b) you understand how it works. Using existing packages for arithmetic or Huffman coding is fine.

  • Does the order of the vertices and/or triangles need to be the same in the output as in the input?

    Answer: NO---they can be ouput in in any order. Technically it is lossy compression on the ASCII file, but no real information is lost since the vertices and triangles should be viewed as sets.

  • Will the names necessarily be increasing integers as in the example files?

    Answer: No for the point of view of correctness, but you can assume that many files have that form and therefore you can take advantage of it when possible. I should note that the format I have specified is based on a standard format (I've simplified it a little bit). The reason it is important to have named vertices, or at least non-consecutive integers, is that you can have multiple meshes and might need to make associaciation between subsets of vertices in the different meshes.

  • Could you please use integer instead of floating-point vertex coordinates? The point being that this would make it easier to use some form of difference coding.

    Answer: OK. I've created files in the directory called *.idata which use integer coordinates (actually the float coordinates * 10^6). You are free to use those files instead (with the same compression grading criteria). You could use difference coding even with the floats, but I agree that it might be too messy to deal with for the purpose of this assignment.

  • I'm not sure if your previous post addressed this, but does the order in which the vertices of a triangle are specified matter? i.e. is ABC == ACB?

    Answer: The orientation matters, but not the order. This means that ABC, BCA and CAB are equivalent and you are free to return any, but that ACB, CBA and BAC have the opposite orientation. In general in 2d any rotation of the labels does not change the orientation. More generally for any dimension, any even permutation does not change the orientation.

  • Since you do not say anything about performance, is quadratic complexity acceptable?

    Answer: Lets just put a limit of 5 minutes on a 450Mhz pentium (the one I have on my desk) for encoding and decoding the crack10 file.

  • Can we assume that the number of vertices in a file will always fit into a machine integer (eg 32 bits)?

    Answer: Yes.

  • Back to the Algorithms in the Real World page (V. 2000).
    Guy Blelloch, guyb@cs.cmu.edu.