CPSC448: Homework


Weekly homework assignments will consist of a number of programming problems, which will appear on this page. You task is to produce a piece of code for each problem, that solves it. The code must be written in C, C++ or Java (see below for compiler specs), must read the problem parameters from standard input (stdin in C, cin in C++, System.in in Java) and print the result to standard output (stdout inC, cout in C++, System.out in Java).

Submission and evaluation

Each problem will contain sample input and output. It is there to clarify any ambiguities in the problem description and for you to test the execution of your code. Once you are reasonably certain that your solution is correct, you will need to submit it to the automatic judge. The judge will run your program on a large set of input cases and tell you how well you did. The judge's reply will be one of:

Your program has correctly solved the problem
No-Compile error
Could not compile. Make sure you have selected the correct file and and compilation options
No-Runtime error
Segmentation fault, Bus error, Abort, etc.
No-Time limit exceeded
You program too too much time to execute. Check for infinite loops or try to find a better algorithm
No-Wrong answer
Your program did not produce the correct output after reading the judge's input
No-Excessive output
A sign of an infinite loop.
No-Output format error
Check for leading/trailing spaces, empty lines, stray spaces.

You can submit solutions as many times as you want, without penalty, until the specified assignment due date. Solutions that receive the "Yes" reply are deemed correct. Incorrect sumbissions will be checked manually for the possibility of part marks.


# Assignment Due date
0 Practice problem January 17
1 IO and datastructures January 24
2 DP and Memoization February 2
3 Graphs I - DFS and BFS February 9
4 Graphs II - (shortest) paths February 23
Midterm practice never
5 Graphs III - Spanning trees March 16
6 Number Theory I - GCD March 23
7 Number Theory II - Horner's Rule and more March 30
8 Number Theory III - Euler's totient function and Successive squaring April 6