CSSAP
443: Homework Assignment #1
Mathematical Tools, Threads, and
Algorithm analysis
Assigning Date:
Due Time: May 5, 2003 at
3:40pm
Problem 1 (20%). Give asymptotically tight upper (big-O) bounds for T(n) in each of the following recurrences. Justify your solutions by naming the particular case of the master theorem, or by iterating the recurrence.
a. (5%)
b. (5%)
Use the substitution method to show that
c. (10%) satisfies the recurrence
.
Problem 2 (20%). Professor
KelvinSort(A, startIndex, endIndex)
// A is the array containing all the input numbers
// startIndex is the starting position we will sort
// endIndex is the end position
if A[startIndex] > A[endIndex] then
exchange A[startIndex] ßà A[endIndex]
if startIndex + 1 >= endIndex then
return
// now recursively
call ourselves with smaller subproblem.
offset= floor((endIndex-startIndex+1)/3) // round down
KelvinSort(A, startIndex, endIndex-offset) // First two-thirds
KelvinSort(A, startIndex+offset, endIndex) // Last two-thirds
KelvinSort(A, startIndex, endIndex-offset) // First two-thirds again
a. (10%) Use A[3 4 8 1] to show that KelvinSort(A,1,n) correctly sorts the input array A[1..n]. You must include the tracing of each recursive calls to KelvinSort, clearly indicating the values of startIndex, endIndex, offset and the contents of the array A before and after each calls to KelvinSort.
b. (10%) Give a recurrence for the
worst-case running time of KelvinSort and a tight
asymptotic () bound on the worst-case running time. Compare this with
other sorting algorithms we have learned. Should Professor
Problem 3 (10%). Refer the following array based linked list implementation:
const int kNullAddress = -1
int fSystemMemory[20];
int keyField(int ptr) { return fSystemMemory[ptr]; }
int nextField(int ptr) { return fSystemMemory[ptr+1]; }
//
// takes a list, do something and return a new list
//
// the input list is assumed to contain at least
// one element
//
int WhatAmIDoing(int list) // ptr to the head of the input list
{ int resultsList, currentPtr; // ptrs to the list we will return
int tmpPtr; // temp ptrs to the two input lists
// new list initialization ...
resultsList = list;
tmpPtr = nextField(list);
fSystemMemory[resultsList+1] = kNullAddress;
while (tmpPtr != kNullAddress) {
currentPtr = tmpPtr;
// advance the input lists
tmpPtr = nextField(tmpPtr);
fSystemMemory[currentPtr+1] = resultsList;
resultsList = currentPtr;
}
return resultsList;
}
Given that initially fMemorySystem
looks like:
Also, the initial values for list=18.
a. (3%) Draw the initial content of list.
b. (5%) Please refer to the routine WhatAmIDoing(), what does fMemorySystem look like after WhatAmIDoing()?
c. (2%) What does WhatAmIDoing() do?
Problem 4. (20%) One night Professor
class TsyncObject {
private:
int fCommand;
CMutex *fCommandMutex;
CEvent *fCommandReady;
CEvent *fCommandIsRead;
void
ChangeCommand(int id) {
fCommandMutex->Lock();
fCommand
= id;
fCommandMutex->Unlock();
}
public:
TsyncObject()
: fCommand(-1)
{
fCommandMutex
= new CMutex();
fCommandMutex->Unlock(); //
initially command is _NOT_ locked
fCommandReady
= new CEvent(true,true); //
initially assume command is ready and manual reset
fCommandIsRead
= new CEvent(false,true); //
initially command is not read and manual reset
}
void
SetCommand(int id) {
fCommandIsRead->ResetEvent();
fCommandReady->ResetEvent();
ChangeCommand(id);
fCommandReady->SetEvent();
}
void
CommandIsRead() {
fCommandIsRead->Lock();
}
bool
Identified(int id) {
bool
found = false;
fCommandReady->Lock();
if
(id == fCommand) {
found
= true;
fCommandIsRead->SetEvent();
}
return
found;
}
};
This is
what his TthreadBase looks like:
class TthreadBase {
private:
static TsyncObject sfSyncObj;
protected:
int fID; // id of this thread
public:
static TsyncObject& GetSyncObject() { return sfSyncObj; }
TthreadBase(int id) : fID(id) {}
const int ThreadID() const { return fID; }
void StartThread() {
_beginthread(StupidThreadWorker, 0, (void *) this );
}
};
where
StupidWorkerThread() looks like:
void StupidThreadWorker(void *parm) {
TthreadBase *td = (TthreadBase *) parm;
TsyncObject &syncObj = td->GetSyncObject();
while ( !syncObj.Identified(td->ThreadID()) );
cerr << "Thread: id[" << td->ThreadID() << "]: Done!" << endl;
_endthread();
}
and here is his test driver:
int main() {
TsyncObject &sync = TthreadBase::GetSyncObject();
//
// Start all the worker threads ...
//
for (int i=0; i<kLastThread; i++) {
TthreadBase *td = new TthreadBase(kLastThread-1-i);
td->StartThread();
}
int command;
cout << "Command [0 1 2 3]? ";
cin >> command;
int seq = command+1;
while (seq != command) {
sync.SetCommand(seq);
sync.CommandIsRead();
Sleep(1);
if (seq == kLastThread-1)
seq = 0;
else seq += 1;
}
sync.SetCommand(seq);
while (!sync.Identified(command));
cerr << "Main terminates!" << endl;
return 0;
}
a. (5%) When the user enters a 3 as input, what does the output look like? Please provide descriptions justifying why the output.
b. (5%) If you run the above program n-times, where n is some large number, would you get the same output every time? Would this program always terminate? Please comment on the output you would expect and explain if there are any potential problems with this termination sequence design. Justify your answer. Yes/no without reasons will not earn you any credit.
c. (5%) After looking at the code for 8.6 seconds, Student Mary pointed out this is a really bad design because before the user enters the command all the worker threads are performing busy wait. How can you fix this problem? Is Student Mary correct? Please justify your answers. Yes/no without reasons will not earn you any credit.
d. (5%) Looking at the code closer, after 12.7 seconds, Student Mary claimed that the fCommandMutex in TsyncObject is redundant and there is really no need for it. Is she correct? Can students really be so harsh on Professors’ work? Once again, please justify your answers.
The source code for
this problem is here for you to download. Please try to read and understand
the code, predict the output before you run and just copy J.
Please include explanations accompanying outputs for Parts a & b.
Please make sure you understand why the output are so, and know how to explain
the reasons. In an exam, I do expect you to read and analyze simple designs
like this one and be able to predict output and/or fix problems with the
design.
Problem 5. (30%) Refer to the mergeSort, insertionSort, and the RandomInput programs (the source codes of these programs are available off the CSS443 course web-site, next to this homework assignment spec). The mergeSort and insertionSort programs are implemented based on the algorithm we have discussed in the lectures. The RandomInput program is capable of generating random numbers suitable for the two sorting programs. Please download these three programs to help you answer this question. RandomInput can generate input for the sorting routines by:
RandomInput 50 > Input.50 // Input.50 is a file containing 50 random numbers
Now you can test the sorting of 50 numbers with merge/insertion sorts by:
mergeSort < Input.50 // Sort the 50 numbers with mergeSort
insertionSort < Input.50 // Sort the 50 numbers with insertionSort
a. (2%) Run and record the average timing of the above two programs sorting n-number of input integers, where n equals to 10, 50, 100, 1000, 5000, 10000. For example, for n equals to 5000, you would randomly generate 5000 integers and then sort these 5000 integers with the two sorting routines. Run the programs against each input at least twice and record the average run time. There are 6 different input sizes (6 different n-values) this means you have to run the programs at least 12 times.
b. (10%) If your manager tells you that the run time of mergeSort is and run time of insertionSort is . Based on your results from input size of 10000 in Part a, how long a coffee break would you take if you are given an input size of 100,000 to be sorted by both of the algorithms? Guessing with no scientific reasoning will result in your being fired by your manger, and will not get you any credit to this problem.
c. (4%) Now run your sorting algorithm against input size of 100,000. How good was your prediction? Explain to your manager why the prediction did not match the actual run time exactly. Note, please pay attention to your analysis on insertionSort, you probably really want to take a coffee break :-).
d. (2%) If we were to solve Part c by using the results from input size of 10 in Part a to help us predict the run time of 100,000, would you expect the prediction to be more accurate or less accurate. Why?
e. (10%) Now, your manager wants you to predict the run time of sorting an input size of 100 million integers, with your promotion depending on the accuracy of your prediction, show the formulation of your new prediction based on all the above results.
f. (2%) Do you have enough time to insertionSort 100 million integers in this week? Why? Once again, guessing with no scientific reasoning will not get you any credit to this problem.
PLEASE REMEMBER: This is not
a group assignment. Each student must work individually on the problems. This
means you have to articulate the solutions to the problems in this assignment by
yourself. If you insist on copying solutions and/or collaborate closely
with friends, please inform me in writing so that I will not give you
the corresponding credits and you will not ended up being accused of committing
plagiarism.
This homework assignment contributes 15% towards your final grade for this course.