In this lab you and two other class mates design pseudo code.
To prepare for this lab, before the lab you must:
· Read this lab description
· Write your own pseudo code solution and have a text file to share with your class mates.
· Submit your pseudo code as roomAssign.txt to cs2321 secGlab or secIlab, preLab3 where secGlab is for students participating in groups and secIlab is for students participating in individual labs before the pre-lab assignment due date.
If you are performing this lab individually then you are to perform the entire lab by yourself and submit before the due group lab due date including the pre-lab assignment. Although the pre-lab and lab assignment appear to be the same your submitted files may be different, in other words the lab submittal may be an improvement over the pre-lab submittal.
The instructor will divide the class into triplets, and the partners will have the whole lab time to design the pseudo code
In particular the partners will design pseudo code to make room assignments for courses.
You will write an algorithm for a room scheduler, which assigns class rooms to courses. The goal is to schedule the maximum number of students to the smallest available class rooms for each period of the day.
We will assume that there are a finite number of periods in a day.
Courses have 4 attributes:
Rooms have three attributes
Your algorithm will assign rooms to courses for each period. Note the
algorithm should arrange the seating for the maximum number of students in the
smallest rooms. The best solution uses the smallest possible rooms and
reserves larger rooms for later use. Because we want the best solution
the problem is an optimization problem.
Some optimization problems can be solved using a greedy algorithm. A greedy algorithm builds a solution iteratively. At each iteration the algorithm uses a greedy rule to make its choice. Once a choice is made the algorithm never changes its mind or looks back to consider a different perhaps better solution; the reason the algorithm is called greedy. Generally the greedy rule can be expressed using priority queue of possible candidates (partial solution) to build the solution. So each iteration of the greedy algorithm removes the next best candidate from the priority queue and checks if the solution can add the candidate to build a larger solution. The algorithm terminates when the priority queue is empty
Iterative Algorithm Greedy(Set of candidate component_solution each with value and other attribute)
// returns sequence, S, of component_solution representing the complete solution
make
a Priority Queue, Q, of candidate component_solution
keyed by value
make
a empty Sequence, S
while Q is not empty do
remove maximum value candidate component_solution, c, from Q
if S + c a good partial solution then add c to S
return S
A greedy algorithm is not guaranteed to always generate the optimal solution. But the algorithm is generally easy to design and implement, and when it does generate the optimal solution it does so efficiently. Also when the greedy algorithm does not generate the optimal solution, the solution is close to optimal.
An example of a greedy algorithm is a solution to the problem of cashier returning change to a customer. The cashier wants to return the minimum number of coins from the cash register. So the candidate solutions are the coins in the cash register. Each coin has the attribute of denomination. Because the optimal solution is the correct change with the least number of coins we can make the value or key for the priority queue the coin’s denomination. Then a greedy algorithm for making change is
Iterative Algorithm Change1( Coins c[0..n], amount )
make Priority Queue, Q, of coins keyed by denomination
make empty Sequence of coins, S
while Q is not empty do
remove maximum denomination coin from Q, c
if total_denomination(S) + c.denomination ≤ amount then add c to S
return
S
where total_denomination(S) = ∑cεS c.denomination
If the cash register has an infinite amount of coins then the algorithm can be written
Iterative Algorithm Change2( denominations d[0..n], amount )
make Priority Queue, Q, of denomination- keyed by denomination
make empty array of integers, S[0..n]
while Q is not empty do
remove
maximum denomination Q, d
number
= (int) amount/d
amount = amount – number*d
return
S
Try the algorithm using denominations {1, 5, 10, 25, 100} to make change on any amount. The algorithm does produce an optimal solution. Whether the algorithm always produces an optimal solution is dependent on the set of denominations; consider denominations {1, 4, 6} and trying making change for 8. The greedy algorithm will generate the solution; one 6 coins and two 1 coins. The optimal solution is two 4 coins.
You are to show up for the lab with a pseudo code for the room assignment already written. The instructor will divide the class into triplet. You and the other students will compare your pseudo code and write a better pseudo code. As you write the new pseudo code try to make use as much as possible standard data structures. Also specify how you would implement the data structure and the cost of the algorithm.
When time is called, submit the file, roomAssignment.txt. At the top of the text should be the name of the students making up the triplet, followed by your joint pseudo code solution. The description of the data structures and the cost of the algorithm should follow the joint pseudo code. At the bottom of the file should appear the pseudo code that you each wrote before the lab. So the format of the file is:
Name of three students
Joint pseudo code
Description data structure used in pseudo code
Cost analysis of algorithm
Student 1 name
Pseudo code that student 1 wrote before lab
Student 2 name
Pseudo code that student 2 wrote before lab
Student 3 name
Pseudo code that student 3 wrote before lab
Now submit only one copy of roomAssignment.txt to cs2321, lab3 where secGlab is for students participating in groups and secIlab is for students participating in individual labs.
After finishing the lab you must individually complete a short survey to receive full credit for the lab, links to the surveys are found on the course home page.