$LastChangedDate: 2007-10-28 16:25:37 +0800 (Sun, 28 Oct 2007) $
Student's Guide to the Special Problem was written for undergraduate Computer Science students who are going to enroll or are currently enrolled in CMSC 190 (Special Problem). My motivation for writing this guide is to help students by giving them some guidelines on how to succesfully complete the course. A lot of students are delayed from graduating because they never finish this course within the prescribed period. The guidelines presented here can at least give them some sense of direction on how to complete CMSC 190.
The Special Problem is almost equivalent to a thesis. However, unlike a thesis which is more theoretical, the SP is more of application. The main purpose of the SP is for you to prove that you are capable of formulating your own problem (the SP) and developing a solution (in a form of software) for the problem. Doing your SP involves independent study where you get to apply the things you learned from other courses or from your own effort. Ideally, you should be able to apply everything that you learned in doing your SP. However, majority will come from your programming, database, and software engineering classes.
The scope of the SP should be broader compared to the projects you have worked on in regular courses. Since the SP is done individually, defining the scope is a challenge and should be done with your adviser. The SP is essentially a software development project and thus, the software development process applies.
The SP is done in two stages (in line with its purpose): proposal(1 unit credit) and implementation (2 units credit). These two stages are distributed in two semesters during the fourth year of your stay in the university.
The adviser is a faculty member who will mentor you as you do your SP. Ideally, you need to select an adviser who shares the same interest with you. Each faculty in the institute has his/her own field of specialization. However, many students avoid advisers who are "experts" in a field because they are scared to be reprimanded when they commit mistakes. Reprimands should be taken lightly and constructively.
If you cannot find a faculty member who specializes in your interests, look for a senior faculty member because they have more experience in advising than junior faculty members. On the other hand, junior faculty members tend to be more approachable than senior faculty members. Also, senior faculty members are busy with other administrative duties, thus it is easier to get help from junior faculty members.
The amount of support you receive will vary depending on who your adviser is. Some advisers are good in managing their advisees. They make themselves available to you throughout the entire process and provides help every step of the way. If you find yourself under this kind of adviser, consider yourself lucky. Other advisers allow their advisees to work independently and present only significant results near the end of the semester. If you do not like presenting minor progress, this kind of adviser is for you.
A lot of students are having a hard time in finding topics for their SP. To get you started, ask questions.
General categories of SP topics:
Doing your SP involves a lot of independent work. Make sure that you are really interested in the topic that you are working on so that you will not lose interest in it later.
You will also need a good title for your SP. Make sure that your title tells all of what you are going to do or accomplish. Make sure that it is catchy and relevant.
Performance Analysis of Sorting Algorithms on a Random Sequence of Integers
Your proposal describes and defines the problem that you are going to work on. It is presented to a panel of three faculty members (one of which is your adviser) for approval as a SP. The panelists evaluate the scope, complexity, relevance, and practicality of your proposal. If your proposal is approved, then you can move on to the implementation stage, otherwise you may need to revise it and present again. Writing your SP proposal is as challenging as finding a topic, you will need technical writing skills.
A proposal is composed of six sections: Introduction, Objectives, Review of Related Literature, Theoretical Framework, Methodology, and Bibliography. The content of each section is discussed below.
This section gives a short overview of your chosen topic. It is further divided into two subsections: Background of the Study and Statement of the Problem. Background of the Study should discuss the relevance of your topic, answering the question of why is the problem worth solving. You can also mention a brief history here. In the Statement of the Problem subsection, you state your problem concisely in one or two sentences.
Several algorithms, with varying performance characteristics, for sorting a given sequence of numbers have been invented in the past two decades...Emperical analysis will show the actual performance of a sorting algorithm in practice. ...This study will compare the performance of sorting algorithms on a randomly generated sequence of integers.
In this section you state what you want to accomplish. First state the general objective then the specific objectives. Your results after the implementation should achieve the objectives you stated.
The general objective of this study is to compare the performance of different sorting algorithms on a randomly generated sequence of integers. Specific objectives: 1)to write a program that generates a random sequence of integers; 2)to implement sorting algorithms (Bubblesort,Quicksort,Heapsort); 3)to use the randomly generated sequence of numbers as input on the sorting algorithms
In this section, you describe works of others that are in some way related to what you are working on. You can mention the strengths and limitations of their approach to solving the problem. Normally, each related work is presented chronologically, from the oldest to the latest. Thus, do not forget to mention the year and the name of the researchers.
In the past, comparative analysis of algorithms.... ...In 1976, Belviz conducted a comparative analysis of search algorithms using different data structures. He observed that BS performs better than LS in some input cases. However, the main limitation of Belviz' approach was...
In this section, you discuss in detail the underlying theories that you will use. Definitions, theorems, lemmas, proofs, algorithms, among others should be stated. Relevant technologies and architectural design can also be described.
The sorting problem is defined as finding a permutation... Theorem 1. The worst case running time of Bubblesort is O(n^2). Proof: Let n...
The Methodology section should describe the approach you are going to take to solve the problem. You can use the software development lifecycle as an outline: Requirements, Design, Implementation, and Testing. A timeline is also required in this section. You can use a Gantt chart for this at least at the week level granularity. At the proposal stage, you should write the methodology in future tense.
The study will use the incremental and iterative approach... The tests will be conducted on a Pentium 4 computer with 512MB RAM...
In this section, you cite the references you used in writing the proposal. There is no standard, as far as I know, on the format for citing references.
The implementation stage is where you actually begin the analysis, design, implementation, and testing phases of the software development lifecycle. At this stage, you should review your software engineering course. It is sad to say that majority of the software produced by students are not following sound software engineering practices. I think this is because the panelists do not look at the source code but only on the output. The following are tips to help you at this stage.
The final manuscript will be based on your proposal. If there are minor changes in the scope and in the objectives, they should be reflected in the final manuscript. The final manuscript will contain the same sections as the proposal with the addition of the Results and Discussion, Conclusion,and Recommendations and Future Work sections. Another change that must be made in the final proposal is the tense used in the methodology section, from future tense to past tense.
The study used the incremental and iterative approach... The tests were conducted on a Pentium 4 computer with 512MB RAM...
In this section, you describe the results of your implementation. You can include discussions of typical use cases for your software. If your SP is about comparative analysis, you can discuss the performance of the algorithms you used, and if possible present a graph. The results should achieve the objectives you set in the proposal.
A program that generates a random sequence of integers was created... After the execution of the sorting algorithms using the randomly generated sequence of integers as input, the number of comparisons made by each algorithm was recorded...The result shows the Quicksort has the...This may be due the the partition step of the algorithm...
In three to five sentences, make a summary of what you have accomplished in your SP.
This study has shown, by experimental results, that Quicksort is the...
State in this section the things that you would like to improve later on if given the time and resources.
The main drawback of the analysis is the use of simplifying assumptions.. It is possible that by relaxing these, a more significant result will be obtained.
The final stage of the SP is the defense. The purpose of the defense is to present the results of your study to a panel of faculty members. The panel will then evaluate your output and decide whether it is substantial for you to get a final grade. The only way to a successful defense is preparation. First, make sure that your adviser approves that you present to a panel. Your adviser's approval will contribute a lot to the success of your defense. Never present an incomplete SP.
$Id: sp.html 93 2007-11-23 13:57:10Z jachermocilla $