From Baylor to Baylor preserves the legacy of the ACM-ICPC World Finals. The book contains all the problems used during the 1991 to 2006 competitions, carefully typesetted and formatted to the highest standard. Also, almost 100 figures have been completely redrawn to improve their printed quality. Prefaced by William B. Poucher from Baylor University (Texas) and coordinated by Miguel A. Revilla from Universidad de Valladolid (Spain), this work is the definitive guide to 16 years of history of the International Collegiate Programming Contest, published thanks to the collaboration of the Competitive Learning Institute and the Competitive Infrastructure Initiative. This book is tribute to all the staff, contestants, judges and volunteers that made it possible.
- Contest rules
- Rules for this year are not ready yet. However, they should be very similar to last year’s rules.
- Hosted by: Rutgers University, Piscataway, NJ.
- Environment: Like last year, the contest will be run from a bootable CD. You are encouraged to download the contest CD and use it in your training. You want the FC10 image, md5 checksum = 36abe1868bcd684ade04d6926196b1a0.
- Languages: ADA, C/C++ and Java.
- 2009 at Hofstra University: standings or problems or rules
- 2008 at St. Joseph’s College: standings or problems or rules
- 2007 at Kean University: standings or problems
- 2006 at Nassau Community College: standings or problems
- 2005 at Kean University: standings or problems
- 2004 at Iona College and Stevens Tech: standings or problems
- 2003 at New York Institute of Technology: standings or problems
- 2002 at Columbia University: standings or problems
- 2001 at Nassau Community College: standings or problems
- 2000 at Kean University: standings or problems
- 1999 at USMA: standings or problems
- 1998 at Bloomfield College: standings or problems
- 1997 at USMA: problems
- 2010 – Shanghai Jiao Tong University, China
- 2009 – Saint Petersburg State University of Information Technologies, Mechanics and Optics, Russia
- 2008 – Saint Petersburg State University of Information Technologies, Mechanics and Optics, Russia
- 2007 – University of Warsaw, Poland
- 2006 – Saratov State University, Russia
- 2005 – Shanghai Jiao Tong University, China
- 2004 – Saint Petersburg State University of Information Technologies, Mechanics and Optics, Russia
- 2003 – University of Warsaw, Poland
- 2002 – Shanghai Jiao Tong University, China
- 2001 – St. Petersburg State University, Russia
- 2000 – St. Petersburg State University, Russia
- 1999 – University of Waterloo, Canada
- 1998 – Charles University, Czech Republic
- 1997 – Harvey Mudd College, United States
- 1996 – University of California, Berkeley, United States
- 1995 – Albert-Ludwigs-Universität, Freiburg, Germany
ACMSolver :: Art of Programming site - was initiated by Ahmed Shamsul Arefin back in 2002 and now it is being refered by ACM UVa Online Judge, Timus (Russian) Online Judge, Sphere- Polish Online Judge and Wikipedia ACM-ICPC page (and several other university programming contest pages) as a ACM-ICPC and programming contest training blog!
This is a collection of programs implementing a wide variety of sorting algorithms. The code has been optimized for speed instead of readability. You will find them to perform better than the perspective standard algorithms. The Combo Sort should be suitable for production usages.
These examples were constructed by studying the following text books:
- Robert Sedgewick, “Algorithms in C”
- Mark Allen Weiss, “Data Structures and Algorithm Analysis”
- Tenenbaum, Langsam, Augenstein, “Data Structures Using C”
Some short descriptions on each of the algorithms:
- Bubble Sort :Exchange two adjacent elements if they are out of order. Repeat until array is sorted. This is a slow algorithm.
- Selection Sort: Find the largest element in the array, and put it in the proper place. Repeat until array is sorted. This is also slow.
- Insertion Sort :Scan successive elements for out of order item, then insert the item in the proper place. Sort small array fast, big array very slowly.
- Quicksort :Partition array into two segments. The first segment all elements are less than or equal to the pivot value. The second segment all elements are greater or equal to the pivot value. Sort the two segments recursively. Quicksort is fastest on average, but sometimes unbalanced partitions can lead to very slow sorting.
- Mergesort :Start from two sorted runs of length 1, merge into a single run of twice the length. Repeat until a single sorted run is left. Mergesort needs N/2 extra buffer. Performance is second place on average, with quite good speed on nearly sorted array. Mergesort is stable in that two elements that are equally ranked in the array will not have their relative positions flipped.
- Heapsort :Form a tree with parent of the tree being larger than its children. Remove the parent from the tree successively. On average, Heapsort is third place in speed. Heapsort does not need extra buffer, and performance is not sensitive to initial distributions.
- Shellsort: Sort every Nth element in an array using insertion sort. Repeat using smaller N values, until N = 1. On average, Shellsort is fourth place in speed. Shellsort may sort some distributions slowly.
- Combo Sort: Sorting algorithms can be mixed and matched to yield the desired properties. We want fast average performance, good worst case performance, and no large extra storage requirement. We can achieve the goal by starting with the Quicksort (fastest on average). We modify Quicksort by sorting small partitions by using Insertion Sort (best with small partition). If we detect two partitions are badly balanced, we sort the larger partition by Heapsort (good worst case performance). Of course we cannot undo the bad partitions, but we can stop the possible degenerate case from continuing to generate bad partitions.