Final Project COMP 6030/4030

Final Project COMP 6030/4030

Fall 2000

General guidelines

The goal of the project is for you to demonstrate that you mastered the material of this course and you are able to use it for problem solving. It is important that you work continuously on your project during the second part of the semester. We will spend plenty of time during the class to discuss the progress. If needed, please also use the consultation time: Room 202 Dunn, Thursday 1-2 pm, or other time by appointment with R. Kozma, email kozma@socrates.berkeley.edu or kozmar@msci.memphis.edu .

After selecting your topic, you can structure your project as follows:

motivation of your choice of the topic, related problems, context of the problem
description of the problem studied
introducing the algorithm you will use. This section may include the following part: justification of your algorithm, why it would work, pseudocode, etc.
analysis of the algorithm, e.g., asymptotic behavior, memory allocation, comparison with other possible algorithms, alternative solutions
possible application(s) of the algorithm, demo case, or others
referenced literature.

Please use the above list just as a guideline. In your actual project you could omit or add other sections depending on the nature of the topic.

Requirements

There are written and oral parts of the project.

You should prepare a 1 page project proposal in which you can address (some of the) above issues. The deadline of this step is October 12: proposals are due at the start of the class.

You should be able to explain to the class in a few minutes the essence of your project, why did you chose it, what are the important and interesting aspects, etc.

Your complete project (6 pages) is due on Dec. 5.

We will organize project presentations on November 28, 30, and December 5, about 10 presentations per day. Please watch carefully other students' presentations and participate in the following question-and-answer discussions.

Evaluation

Project proposal (1p) 5%

Final written part (6p) 20%

Presentation 20%

List of possible topics

Your project should supplement class material. You must learn something extra during your project and the class should learn from you during your presentation! So you should go beyond the lecture and this can be done in several ways: (i) you can select a topic that hasn't been dealt with in details in the class; (ii) you could describe a given algorithm in details and describe its implementation and pseudo code; (iii) you could choose to describe a novel application of a given algorithm; (iv) you could compare several different algorithms or methods, regarding their performance (time, memory, optimality). The topics in italics in the list below are the ones which go beyond the basic course material.

Sort:

Insertion sort

Bubble sort

Divide and conquer algorithms

Quick sort, basic and improvements

Merge sort

Heap sort

Shell sort

Radix sort

Search:

Find max/min

Amortized time analysis

Dynamic sets

Red-Black trees, optimality in binary search

Insertion in RBT, rotation, color flip

Hashing, closed address

Hashing, open address

Choice of hash function

Graphs:

Binary relations, equivalence, ordering

Traversing graphs, depth first search

Traversing graphs, breadth first search

Greedy algorithm

Critical path analysis

Prim's minimum spanning tree algorithm

Dijkstra's shortest path algorithm

Kruskal's minimum spanning tree algorithm

Graph colorings

Transitive closure:

Transitive closure, Warshall algorithm

Multiply bit-matrices, Kronod algorithm

Dynamic programming

Constructing optimum binary trees

N-queens problems

String matching, Knuth-Morris-Pratt algorithm

Knapsack problem

Traveling salesman problem

Complexity and computation

NP hard problems, algorithms

Fast Fourier Transformation FFT

Evaluating polynomials

Matrix multiplication

Novel and parallel computing

DNA computing algorithms

Massive parallel computing (neural)

Walks on graphs and neural networks

Chaos computing algorithms

Your choice:

You can propose other topics, please see me.

Topic selection advice

You are free to select a topic as given above. If two or more students choose the same topic, you can still do it! However, in that case we need to discuss it and you must be more specific and select a certain sub-problem from that field. We will resolve such possible collisions during the week following Oct. 12.