Computer Science 111  
Fall 2001

Problem Set 7 Solution
======================

2 rules:
--------

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

Given:
------

- Registrar maintains a database we can use to determine when a class
  meets.

- Courses are named by a 3 letter department code followed by the 3
  digit number of the course in the department.

- We can query the database using this name to get the meeting times
  for a course.

- Results have the format:

  2 Tue 1100 1220 Thu 1100 1220

  (2 meeting times: on Tuesday from 11:00 to 12:20 and on
  Thursday from 11:00 to 12:20)

- Days are represented as Mon, Tue, Wed, Thu, Fri

- Time is given on a 24 hour clock (so that 1PM is 1300, etc.).

- A program tells us what courses a student wants to take, following
  the format:

  NCOURSES, COURSE[1], COURSE[2], ..., COURSE[NCOURSES]

- Example of 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

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]).

	for i in 1 to NCOURSES
		ask the registrar for times on COURSE[i]
		if COURSE[i] meets on Monday
			record the time COURSE[i] meets on Monday

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!"

	for i in 1 to NCOURSES
		ask the registrar for times on COURSE[i]
		record what the times are

	for i in 1 to (NCOURSES - 1)
		for j in (i + 1) to NCOURSES
			if COURSE[i] overlaps with COURSE[j]
				output "Violate rule 1!"

	for day in Mon, Tue, Wed, Thu, Fri
		initialize HOURS[day] to 0

	for i in 1 to NCOURSES
		for each day that COURSE[i] is offered
			get the number n of hours that COURSE[i] takes that day
			add n to HOURS[day]
			if HOURS[day] > 5
				output "Violate rule 2!"

	output "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.

(i) Putting courses in alphabetical order.  Let A be the array with
all courses.  Let N be the total number of courses.  The following
pseudocode is known as bubblesort (there are many other sorting
methods that are better than bubblesort).

	for i in 1 to (N - 1)
		for j in 1 to (N - i)
			compare the letter codes for courses A[j] and A[j + 1]
			if A[j] should be after A[j + 1]
				swap A[j] and A[j + 1]

We make N - 1 passes over the array.  At each pass i, we compare the
first N - i pairs of elements, swapping elements if necessary.  At
each pass the largest element "bubbles" to righ place.

(ii) Building indices.  Here we assume the array has been sorted.

	output the letter code for A[1] and 1
	for i in 1 to (N - 1)
		compare the letter codes for courses A[i] and A[i + 1]
		if they are different
			output the letter code for A[i + 1] and i + 1