Computer Science 111  
version of November 26, 2001 4PM

Problem Set 7:

Due by 5PM Tuesday December 4.
You can hand this in at class or leave it in the folder on
the 2nd floor of the CS building (near the student mailboxes).

In class we discussed algorithms for various tasks.  In this
assignment, we will talk about a few pieces of the process by
which the registrar does scheduling for University classes.
In particular we will focus on the task of determining if a
schedule that you have created is valid under the University's
rules.

For this assignment, we will assume that there are 2 rules
about schedules

i)	A student cannot take 2 classes that meet at overlapping times 
ii)     A student can take no more than 5 hours of classes on any day


We will also assume that the registrar maintains a database
that your algorithm can use to determine when a class meets.
The database assumes that courses are named by a 3 letter
department code followed by the 3 digit number of the course
in the department. For example, COS 111 is the name for this
course. You are able to query the database using this name to
get the meeting times for a course.  So, for this assignment,
you can assume that the registrar has provided a primitive that
would respond to a query of  COS 111 with the text 2 Tue 1100
1220 Thu 1100 1220 telling you that the course has 2 meeting
times and that they are on Tuesday from 11:00 to 12:20 and on
Thursday from 11:00 to 12:20.  You can assume that the days
are represented as Mon, Tue, Wed, Thu, Fri and that time is
given on a 24 hour clock (so that 1PM is 1300, etc.).

You can also assume that someone has built a program that
interacts with the user and determines what courses he/she
wants to take.	This information is presented to you by a
number giving the number of courses (we'll call this NCOURSES
below) and by NCOURSES array elements COURSE[1], COURSE[2], ...
COURSE[NCOURSES] that give the names of the courses.

For each part of the assignment you need to write pseudocode
that describes how the problem would be solved.  As in class,
your pseudocode should be at a high enough level to be easy
for you to write.  But, it must contain enough detail so that
a programmer can understand and use it.

For example, if you wanted to describe the process of getting
your course times from the registrar, you might write the
pseudocode

		Determine NCOURSES 

		For each course, so for each i from 1 to NCOURSES

			ask the registrar for times on COURSE[i]
			record how many times there are 
			record what the times are

You would also have to tell how you were going to store the
information that came back from the registrar.

(Problem 1)
	Write pseudocode to determine the times of all classes
	that meet on Monday for a given schedule( NCOURSES, COURSE[1], 
	COURSE[2], ..., COURSE[NCOURSES] )..

(Problem 2)
	Write pseudocode to determine if the schedule violates
	either of the rules given above.  Your code needs to 
	output corresponding information: either "Violate rule 1!", 
	or "Violate rule 2!", or "No violation!" 


(Problem 3)
	You can speed up the processes in the first 2 parts
	of this assignment by organizing the registrars list
	of courses.  This could be done by first putting
	courses in alphabetical order and then by building
	indices that can be searched to speed the process.
	Write pseudocode for each of these parts.