CSC 413/513 ALGORITHMS

GROUPS and THEIR PROJECTS (over time these links may become unavailable)


CRYPT DE MANDELBROT - study of encryption algorithms
FARSIDE - string matching algorithms
LOST MINORITY - parallel matrix multiplication
pFFT - parallel Fast Fourier Transforms
SQUEEZE - study of compression algorithms
THREE JAKES - algorithms for the maximum flow problem
2 DATA GUYS AND STRUCTURE GIRL - study of data access times



Material covered:
Introduction to analysis of algorithms
Factors influencing cost -- input size vs. problem difficulty
Selection sort -- complexity evaluation
Insertion sort -- complexity evaluation
Megre sort and its complexity
Introduction to growth functions
Matrix multiplication -- does ordering matter?
Basic summation formulas
Solution of recurrences
Quicksort and its variants
Heapsort
Non-comparison sorting algorithms
Finding i-th statistics
Solution of n linear systems with n unknowns
LU decomposition
LU decomposition for tridiagonal linear systems



HOMERWORK:

1. Sorting homework I (individual). In class we have argued that selection sort can be faster than insertion sort for a special class of problems. Experimentaly verify this hypothesis. Present a short report (which in form follows what was discussed in class) --> due by 06/08/98

2. Group-work --> create a WWW site for your group project --> due by 06/08/98

3. Matrix multiplication homework (individual). It was argued in class that when matrices are multiplied then loop ordering matters. Experimentaly verify this hypothesis. Present a short report (which in form follows what was discussed in class) --> due by 06/11/98 (midnight).

4. Summation (individual). Problems 3.1-2, 3.1-3, 3.1-4., 3.2-4, 3.2-5. Due by 06/15/98.

5. Group-work --> update WWW site for your group project --> due by, midnight, 06/16/98

6. Prepare a presentation (about 12-15 minutes) summarizing the group work done thus far --> to be presented on Thursday, 06/18/98.

7. Study the performance of various pivoting strategies in QUICKSORT. More precisely, consider:
• leftmost pivot
  
• random pivot
  
• median of three pivot
  
• mean of three pivot
  
• data randomization + leftmost pivot
  
study their behavior for:
• random
  
• sorted
  
• reverse sorted
  
data. Report due by midnight, Friday, 06/19/98.

8. Recurrences (individual). Problems 4.1-1, 4.1-2, 4.2-1,4.3-1, 4.3-3. Due by 06/22/98.

9. It has been claimed that the performance of Quicksort can be substantially improved if in the final stages of the algoruthm the recursion is replaced by Inserion sort. Experimentally verify this hypothesis. Due by midnight, Tuesday, 06/23/98. 10. Update the group WWW pages to include information about the current status of the project. Due by Wednesday, 06/24/98.

Reading assignment: pages 1-76, 153-194 and 749-762.

A useful links (do they still work?):
Similar Course
Sorting demo in JAVA