cs2223 Exam 2

[WPI] [cs2223] [cs2223 text] [News] [Syllabus] [Exams]

cs2223, D97/98 Exam 2

Question 2.1

Prove or disprove these statements:

Q1.1. The square of any even positive integer is even

Q1.2. The square of any odd positive integer is odd

Question 2.2

A "WPI heap" is a heap of integers in which there are no duplicate values. WPI heaps, as other heaps, are stored in arrays. Write a program in C or C++ which turns a WPI heap into a binary search tree. A binary search tree has these properties:

Each node is greater than or equal to its children.

Each node's left child is always greater than or equal to its right child

Question 2.3

A printing shop charges the same amount to print a job, no matter how many pages are printed. Each job has a deadline, a time by which it must be printed or it won't be paid, and an estimated print time (duration). Here is an example:

Job Deadline Duration

1 5 1

2 9 3

3 6 3

4 7 1

5 2 2

6 8 2

The shop has only one printing press. Write an algorithm which schedules print jobs so that the shop earns the maximize amount of money.

Demonstrate your algorithm using the above data. This is only a small part of the problem - your algorithm is more important than your answer.