Homework8: Some Notable Algorithms
Due: In class on Monday, April 21 (12 noon), 2008

Each one of you will be assigned an algorithm from the following set as your assigned topic for this last assignment. You are to research, explore, and then write a technical essay, in the spirit of Bentley, on the topic assigned to you. The topics are all related to the domain of algorithms. Some of the most important algorithms in use make up the bulk of the list. There are many other important algorithms that are not in this list, partly because we have already discussed them in class already (or in another course).

Mini-Conference on Computing Algorithms
April 22, April 24, April 29, May 1, 2008
Room 236 PSB
10:00a to 11:30a

Speaker Schedule

Tuesday, April 22
Session Chair: Caitlin Evans
10:10a - 10:30a Heapsort by Lauren Maksym
10:30a - 10:50a Fisher-Yates Shuffle by Simona Radu
10:50a - 11:10a Hashing by Jesse Rowher
11:10a - 11:30a Memoization by Natasha Eilbert

Thursday, April 24
Session Chair: Natasha Eilbert
10:10a - 10:30a Monte Carlo Methods by Mansi Gupta
10:30a - 10:50a The RSA Algorithm by Marwa Muhammad
10:50a - 11:10a Simplex Algorithm by Shikha Prashad
11:10a - 11:30a Data Compression by Priscy Pais

Tuesday, April 29
Session Chair: Joe Huttner
10:10a - 10:30a Porter Stemmer by Caitlin Evans
10:30a - 10:50a String Matching by Emily Somach
10:50a - 11:10a Page Rank Algorithm by Stephanie Hilton

Thursday, May 1
Session Chair: Lauren Maksym
10:10a - 10:30a Map Coloring by Ashley Gavin
10:30a - 10:50a Dijkstra's Shortest Path Algorithm by Joseph Huttner
10:50a - 11:10a The MiniMax Algorithm by Jessica Billings

What to hand in:

1. Your essay should be approximately 5 pages long (single-spaced, 1-inch margins, on letter size paper), give or take 1 page. The essay should be formatted using an appropriate word processing/text formatting system of your choice. It should be in your own language and list appropriate citations where applicable. Using other's words/content without appropriate citations will be considered as plagiarism, so be mindful of that.
   
2. It should introduce the problem (or the set of problems where the algorithms is commonly used), motivate its use, present its history/development, analysis if known, the algorithm(s) itself (pseudocode or actual code), discuss relevance, etc.
   
3. As much as possible, try to implement it and do some experimentation of your own. This would be expected of all algorithms that can be easily implemented. If not feasible, you will explain why that is so. Your essay may or may not include implementation details (again, in Beltley's style, feel free to include an appendix if you do the work and would like to include it in your submission). You can/should use the implementation in your presentation (see below).
   
4. You will give a presentation (dates will be assigned in class) on the topic assigned to you. Your presentation will be responsible for everyone in class to come away with a good idea of what the topic/algorithm is and its relevance. You will have to make decisions about the level of details you will include in the presentation. A copy of the essay you write will be distributed to everyone in class.
   

Back to CS330 Materials