Department of Computer Science Theory of Computer Algorithms (Winter 2008) 4005-800-01 (Calendar Description)

Home --- Syllabus --- Slides --- Assignments --- Resources

Instructor: Richard Zanibbi, Office hours: Tues 2-4pm, Thursday 10am-12pm (or by appointment), 70-3551 (Golisano College)
Lectures (NOTE: two locations):
Mondays 12-1:50pm (70-2590, Golisano College)
Wednesdays 12-1:50pm (70-3435, Golisano College)

Assignment 1 (Due: Start of Class, Wednesday Dec. 17, 2008)

1. A .pdf file containing the answers to the written questions
2. A short paragraph explaining how to compile and run your C/C++ or Java program. Your C/C++ program should compile using gcc/g++ (the GNU compiler collection tools), and any java programs must compile using the standard Java compiler (for Java 1.6).
3. The files containing your solution to the programming question, as a .zip archive. Please name this file rit_solution.zip, to avoid the file from being removed by the RIT email system, and save effort for the grader.

Questions (Total of 50 points)

1. (15) Chapter 2, Exercise 6 (Kleinberg and Tardos)
2. (15) Chapter 4, Exercise 17 (Kleinberg and Tardos) Make sure to analyze the run-time and prove the correctness of your algorithm.
3. (20) Programming Question. Implement a version of Dijkstra's shortest path algorithm, using your own binary heap-based implementation of a priority queue (do not use an existing library, or copy code; the code should be your own. You may look at various sources/implementations, however).

   You will be graded based on the correctness, efficiency, and simplicity of your program. Extensive javadoc/documentation is unecessary; comment just enough to allow the instructor and grader to understand your solution. Include a brief analysis of the worst-case run time of your implementation in the submitted .pdf file.

   The grader will test your code using text files in the format shown below. Your program must be able to read files in this format, skipping any whitespace (tabs, newlines, spaces, etc.). Points will be deducted if there are problems reading input files when the programs are tested. All input files will provide an edge list with weights, using nodes labeled from A-Z, and the source node will always be A. Your output should list the minimum path costs for each node in alphabetical order, as shown below.

   Example Input

   Input File	Graph (created using 'dot')
   A B 8 A C 17 B C 5 C A 2

   Example Output

   A 0
   B 8
   C 13
   

   Example Dot (GraphViz) File

   You are not required to use 'dot' for the assignment; this is just for your information. 'dot' was used to create the graph shown above using the input file below:
   
   digraph g {
  A -> B [label=8];
  A -> C [label=17];
  B -> C [label=5];
  C -> A [label=2];
}