CSE5311 Projects (Spring 2007)

Listed below are the programming projects for Spring 2007
The problems can be attempted individually or in groups
Group discussions are encouraged. However, each participant is expected to know the details of the project work done.
You will have to write and execute the code for each problem and demonstrate the working with a sample input.
All references must be listed
Read the problem selection section below carefully to understand the number and weights of problems for individual or group (2 or 3) teams
After completion of the project, each team member will be required to complete a feedback form summarizing the contributions of teammates.
Sample feedback form
All questions regarding the project should be emailed to the TA with CC's to Dr. Kumar and all the teammates.

PART I.

Design an algorithm that picks the best sorting techniques given a set of data. The following Sorting Techniques are to be considered:

* Insertion Sort

* Merge Sort

* Heap Sort

* Counting Sort

* Bucket Sort

The best-sorting-technique algorithm should be designed to run in O(n). The input should consist of a set of data values which call the best-sorting-technique routine and run the most appropriate sorting algorithm for the given data set. Give a justification for your algorithm’s choice of sorting technique.

(OR)

Question (Click on Link)

PART II.

Question (Click on Link)

(OR)

Question (Click on Link)

PART III.

Chapter 3, Problem no. 11 (page 111-112)
Chapter 7, Problem no. 26 (page 430-431)
Chapter 7, Problem no. 28 (page 431-433)
Chapter 4, Problem no. 12 (page 193-194)
Chapter 6, Problem no. 14 (page 324-325)

6. Chapter 4, Problem no. 24 (page 200-201). The text book mentions the first part of the problem. In addition to the solutions asked the following is also to be determined for this problem:

Given the above scenario, design and analyze an efficient algorithm to generate a uniform random sample of the leaves in the balanced binary tree. The uniform random sample (for a tree where all edge weights are equal) is a set of leaves picked at random such that each leaf has an equal probability of getting picked. It is to be noted that the binary tree is weighted by distance. At a particular node, the chances of its children getting picked are proportional to the edge weights. Thus, in Fig 4.20 (page 201), the probability of leaf ‘a’ getting picked is more than the probability of leaf ‘b’ getting picked. Analyze your algorithm for N samples from a tree having M leaves.

Chapter 11, Problem no. 11 (page 657-658) (ONLY for ONE PERSON TEAMS)

Text Book:

Algorithm Design
by Jon Kleinberg, Éva Tardos

Pearson Addison-Wesley

ISBN 0-321-29535-8

Problem Selection and Grade Distribution

ONE Person Team

PART I and II – 50%

PART III – Select ONE out of problems III.1 to III.7 – 50%

TWO Person Team

PART I and II – 40%

PART III – Select TWO out of problems III.1 to III.6 – 60%

THREE Person Team

PART I and II – 33.33%

PART III – Select THREE out of problems III.1 to III.6 – 66.66%

SUBMISSION FORMAT

Any platform or language can be used.
During the project demo, each team is requested to bring a laptop where they have built and tested their code. Another option is to run the code on OMEGA or GAMMA (no laptops are required in this case).
All problems are to be run on an input set of data (can be conceptualized by the team members) to generate an output. Varied test data sets will be used to test the correctness of the code.
Each team has to submit detailed documentation for each part (steps to run the code, description of each module, etc.)
All code and documentation (.ZIP format please) is to be emailed to the TA (CC’ Dr. Kumar) before the submission deadline with “CSE5311 SPRING 2007 PROJECT + <Team member last names (comma separated)>” as the email Subject.
Teams selecting Problem III.7 need to submit their solution in writing (a scanned copy in the email submission will do too) to the TA before the submission deadline.
Late Submissions will not be encouraged. The penalty for late submission is 20% per day. If you miss the deadline due to unavoidable circumstances (e.g., health), email the instructor for an appointment or meet with him during office hours.

Submission Deadline: April 30, 2007 (09:00 AM CST)