README.md 2.47 KB
Newer Older
Chris Dutchyn (cjd032)'s avatar
Chris Dutchyn (cjd032) committed
1
2
3
4
5
6
This is a sample programming assignment for CMPT 360 2017-T1.

It pretends that the stable-matching algorithm from Kleinberg and Tardos was
assigned to be programmed.  We've done it in procedural C++ to demonstrate a
usual and expected level of proficiency with programming, algorithm analysis,
configuration management, and source-code control.
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

Initially we build the inputs and their corresponding outputs to demonstrate
that we understand the problem and its variety of situations.  In each case,
we provide an input file `test`N`.in` and its expected output file `test`N`.exp`.
Our input will tell us the number of companies (wolog equal to the number of
interns), followed by the company names and the intern numbers in decreasing
preference order, followed by the intern names and their company preferences
in decreasing order.  More specifically,
*    LINE 1:          `N` -- the number of companies and interns

*    LINES 2..N+1:    company-name followed by `N` numbers being the interns
   	 	   	       	      in decreasing order of preference
				      
*    LINES N+2..2N+1: intern-name followed by `N` numbers being the companies
    	 	    		     in decreasing order of preference

The expected output will be N lines, one for each company in the order they
appeared in the input, containing the company name, a backward arrow ('<-')
and their assigned intern name.

For example, two companies and two interns might be provide input
>    2

>    BigCorp      1 2

>    LittleCorp   2 1

>    InternA      1 2

>    InternB      2 1

and would be expected to generate output

>    BigCorp <- InternA

>    LittleCorp <- InternB

Note that whitespace is ignored between string and numeric fields on the line
(but cannot appear in the strings, i.e. "Big Corp" is not acceptable, but
"Big_Corp" is allowed).

Note that we allow for comments in the .in and .exp files by ignoring/removing
all patterns matching the regular expression '[ \t]*#.*$'. This regexp matches
whitespace preceding the first octothorpe on a line, as well as the octothorpe
itself and all succeeding characters to the end of the line

Note that we assign '1' to the first company or intern; therefore '0' is
available to indicate free for both companies and interns.
55
56
57
58

We have a `Makefile` and targets
* `all` to build the binary (`pm`)
* `tests` to run all the tests (so far, `test0`, `test1`, `test2A`, `test2B`)
Chris Dutchyn (cjd032)'s avatar
Chris Dutchyn (cjd032) committed
59
60
61

We can try individual tests by `make test1.out`.  Also, the C/C++ standard
macro DEBUG can be defined to enable some debugging output.