CS 436 Winter 2010 - Assignment 1

(Version: Jan 28 16:09:18)

Due Date: Monday, Feb 8, 2010, 22:00

Notes

Questions

  1. Assume the following code:

    0000000000
    0000011111
    0011100011
    0011111100
    1100100101
    1100111010
    1111000110
    1111011001

    1. (1 point) What is the minimum Hamming distance of this code?
    2. (1 point) What maximum bit errors can be detected?
    3. (1 point) What maximum bit errors can be corrected?

    Briefly explain how you have obtained your results.

  2. (1 point) Explain why PPP must have a byte stuffing mechanism, while Ethernet does not.

  3. Assume a network that uses a "token passing" medium access control protocol with the following parameters:

    1. (2 points) What is the overall efficiency, if only a single station has data to send?
    2. (2 points) What is the overall efficiency, if all stations have data to send?

  4. (2 points) Why does the frame size not play a role for the efficiency of the Aloha protocol, but for Ethernet's CSMA/CD medium access control?

  5. (2 points) Assume an Ethernet network with the following parameters:

    Compute the minium frame size for CSMA/CD to guarantee that all collisions can be decteted by a sender.

  6. (12 points) Implement the Dijkstra algorithm in your favourite programming language. Use the submit tool to submit the source code along with a suitable Makefile/script, etc. (depending on your programming language) as a zip/tar/gzip/bzip2 archive with any of the following corresponding names: dijkstra.{zip,tgz,tbz}.

    Make sure that your submission works in the student.cs environment and include a file named README that explains how to compile (if necessary) and invoke the program. Your program must adhere to the following interface:

    ./dijkstra <origin> <file>
    
    <origin> is the number of the node at which the algorithm is executed. <file> is the name of an input file that lists multiple network links (one per line) according to the following format:
    <node1> <node2> <cost>
    
    Each line describes a symmetric link between <node1> and <node2> with cost <cost>. Nodes are identified by numbers.

    The program must produce output on standard output of the form

    <total cost> <origin> <node1> <node2> ... <destination>
    
    that is, each line describes the shortest path to an destination the path's total cost. The order of the output lines does not matter.

    Your program should perform basic error checking, i.e., it should not just crash when receiving faulty input, but either try to perform the computation or produce an error message and quit. As stated, you can consult 3rd-party resources (example) for this assignment, but you must implement your own solution. You can used third-party unsorted list or array data types, but must not use higher-level container libraries (map, set, queue, etc.). You can implement/use your own container classes.