CSSAP 443: Homework Assignment #1

Mathematical Tools, Threads, and

Algorithm analysis

Assigning Date: April 28, 2003

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 Kelvin Sung proposed the following best sorting algorithm known to humankind:

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 Kelvin Sung teach algorithm classes?

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 Kelvin Sung came up with what he thinks as the best idea to control the termination of cooperating threads. Here is his TsyncObject:

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.