Problem 1
Suppose you are given a list of COS111 students that contains the name and
the class year of each student. Write an algorithm that finds the numbers
of first year students, sophomores, juniors, seniors, and others (we do
get special students, graduate students and high school students occasionally;
assume they are marked in some special way).
The result provided by your algorithm should be the counts for the
5 categories. Organize your description in a step-by-step fashion.
Be as precise as possible. What are the basic steps used by your algorithm?
What is the input?
There are many ways to write this algorithm. Here is one:
frosh := 0 sophs := 0 juniors := 0 seniors := 0 others := 0 foreach student in studentlist do if (student is freshman) then frosh := frosh+1 if (student is sophomore) then sophs := sophs+1 if (student is junior) then juniors := juniors+1 if (student is senior) then seniors := seniors+1 if (student is other) then others := others+1 return (frosh, sophs, juniors, seniors, others)
The program gets its input in the "studentlist". Each line of the above description is a basic step; these include storing values, addition, and checking which category an individual student is in.
Problem 2 :
Write an algorithm to schedule laboratory assistants
for COS 111. Assume that there are 4 lab sections,
and each needs 3 assistants. Assume you
have a list of free afternoons for each of 12 lab assistants.
Since I am not giving you the actual schedules of the assistants, you have to
write in general terms how you would proceed. Assume that the lab sections on
Monday, Tuesday, Wednesday, and Thursday afternoon.
Organize your description in a step-by-step fashion.
Be as precise as possible. What are the basic steps used by your algorithm?
What is the input?
There are several correct algorithms, and there are several ways to write down each of the correct algorithms. Here is an example:
assigned[0] := 0
assigned[1] := 0
assigned[2] := 0
assigned[3] := 0
foreach assistant in assistantlist
assignedthisone := false
foreach session in {0,1,2,3}
if (not assignedthisone)
if (assistant can work during session)
if (assigned[session] < 3)
assign assistant to session
add one to assigned[session]
assignedthisone := true
if (assignedthisone = false) then
print "Sorry, can't find solution."
give up and end algorithm
The input to this algorithm is the list of assistants, and the information about which sessions each assistant can work. The basic steps are given by the individual lines of the algorithm.
Problem 3:
Is there always a solution to problem 2? In other words, is it possible that
you can be given a list of free times that makes it absolutely impossible
to put three assistants in each session? Justify your answer.
What do you think a computer program
should do if it discovers that the problem it is trying to solve doesn't
have a solution?
There is not always a solution to problem 2. For example, if only two assistants can work on Monday afternoon, then there will be no way to find three assistants who can work then. In that case, any algorithm would have to fail.
When a computer program discovers that it cannot solve the problem it was given, it should let people know that it has failed, so anybody who is relying on the correctness of the answer will know to look elsewhere for help. Ideally, the computer should tell the person whether the problem has no solution, or whether there is a solution but the program wasn't clever enough to find it. But it's not always easy to tell the difference between these two situations.