[Courses] [C] New topic: I/O

[Laura Bowser]

In addition to Mary's suggestions, I'm going to add one of my own.
I taught an intro to C class for freshman CS majors last year, and here's one 
of the exercises they were assigned (not as easy as it looks):
It requires the use of file and terminal I/O and bit operations.

given a file with sets of integers, one set on every other line, and a value, 
print out all possible subsets which add up to that value.

Input file example:
12 57 32 26 72 69 23 28 62 51
143
25 62 72 93 12 94 73 82 34 20 94 86
230
<... continue as long as you wish...>

1) you need to read in the first set of values, and the total you're looking 
for (in this case: 12 57 32 26 72 64 23 28 62 51)
2) test all possible subsets for a sum equaling the total you read in (in this 
case: 143)
3) print out all the subsets (in a pretty form) that sum to that total, or 
print a statement that there are no such subsets.
(in this case, one of the subsets is:
{69, 23, 51}   
69+23+51 = 143)

There is no known way to do this other than "brute force" - if you do find a 
way, almost any school you wish will give you a PhD in Computer Science.

The most common way of doing this is to create a "bitmap" of your set and 
store it in an integer. then loop over the integer, summing all the values in 
your set that match the 1's in the integer

example set:
4 87 23
there are 8 possible subsets
{} 	{23} {87} {87 23} 	{4}	 {4 23} {4 87} {4 87 23}
000 001	010    011        100    101       110         111
0	1	2	   3		4	   5		6		7

so, if you have a for loop that loops over the integers from 1 (you don't need 
the empty set) to 2^(size) -1, then you will have a "bitmap" of all possible 
subsets.



I hope I explained this well, but there's a link to the original assignment 
here:
http://www-2.cs.cmu.edu/~thoffman/S02-Mini4-15-113/labs/lab4/lab4.html
(how long this page will remain up is a different story)
If you look at the helper code, you won't learn as much!

Laura


-- 
Public Key available at 
http://callista.dyndns.org/~elwing/lbowser.gpg