CS3110 Take Home Quiz

Due: Thursday July 17th Before Class

Change log
July 4th, 2003 - Document Created.

Instructions

You may work in groups of size 1, 2 or 3. Each group will receive a single mark. Any inter-group cooperation will be dealt with harshly. Please check this page for any updates or new information. Note that the presentation of your answers is as important as the results themselves! Note,

Question A1: A point p in 3-space dominates a point q if and only if x(q) < x(p), and y(q) < y(p), and z(q) < z(p). Given a set S of n positively weighted points in 3-space (ie. (x,y,z,weight) quads) describe and analysis an efficient algorithm for determining for each point r in S the sum of the weight's of points t in S where r dominates t. (Hint: O(n * n) is easy, try for O(n log n))

Question A2: Cindy's garage fixes all the cars in the little town of WasteNoTime. As cars come in to her garage Cindy gives each job an unique id number, an estimate of the jobs length in minutes, and a priority number between 1 and 100, where 1 has the highest priority and 100 the lowest. She then records the job in her work order book with all of this information. During the day Cindy needs to do the following:

  1. Add a new job to her work order book. (Remember, each job consists of an unique id, a job length estimate, a priority number, and some text.)
  2. Given a job id number, remove the job from her workbook (when, for example, a customer decides it is too costly to fix).
  3. Determine the next car to be worked on (ie. the one with highest priority).
  4. Estimate for a customer how long until their car is fixed, assuming no more work orders come in or are deleted.
Design a data structure and a set of operations to automate Cindy's workbook. Assume all operations are equally likely. Answers will be judged on correctness, efficiency and clarity - Draw pictures!

Question A3: Given a set S of n axis parallel rectangles, defined by their top-left and bottom right points, describe and analysis an efficient algorithm for determining the area of the union of S. Note that since the rectangles my overlap the answer in not simply the sum of the areas of the rectangles. Hint: Imagine sweeping a line over the rectangles and performing operations on a data structure when the line hits either the start or end of a rectangle.

Question A4: Given a ordered sequence S of n positive integers, describe and analysis an efficient algorithm for determining the longest non-decreasing subsequence of S. For example, given S = {3,2,2,0,6,4,1,5,5,9,2,3,4,8,1,9} return S' = {2,2,4,5,5,8,9}. The answer is not unique in that there may be several longest subsequences.

Assume all operations are equally likely. Answers will be judged on correctness, efficiency and clarity - Draw pictures!

Question B5: Do Exercise 9.3-6 from the text.

Question B6: Do Problem 8-4 from the text.

Question B7: Do Problem 14-2 from the text.

Good Luck!


Home * Publications * Research * Pointers
Teaching * Contact me