References:
1. Algorithms - Robert Sedgewick, Kevin Wayne. Lections. Part 1/2
2. Tim Roughgarden. Algorithms: Design and Analysis, Part 1/2
Simple open problems for which nobody knows the answers:
1. What is performance garantee in worst case or best case for Shell Sort for particular sequence of "strides"?
2. What is the best sequence of "strides" for Shell Sort ? (People try to find it for 50 years)
3. Is it possible to create inplace(like insertion sort, but not merge sort), and stable (like merge sort, but not like quick sort) sorting algorithm with worst,average,best time proportional to Nlg(N)?
4. For long sequence during "building" random balanced search tree via insert&delete operation the depth of the tree will be square root of N. How to fix this? How to delete element from BST tree in efficient way? I heard it from [1], prof. R. Sedjvik mentioned of course usual binary trees without extra balancing schema.
This question is not really very critical for society because in real life for such functionality we usualy use balanced trees which perform all need operation in logarithmic time : 2-3 tree, Red-Black trees, or AVL trees....
It's great but we still don't know how effectively remove item from bst !
5. Minimum Spanning Tree. It's exist Kruskal's algorithm based on disjoint datastructures which can implemented via union-find + priority queue. Running time for Kruskals is O(Elg(V)).
Prim's algorithm gives V*T_extract_min + E*T_descrease_key. If use Binary heap it will be equal to O((E+V)lg(V)),
if use Fibonacci heap => Time will be equal to O(Vlg(V)+E*1)=O(Vlg(V)+E*1)
Nobody didn't show that it exist algorithm for finding MST in worst case O(E+V) time.
Karger, Klein, Tarjan [1993] show a randomized algorithm that run in O(E+V) expected time, but it is expected time.
6. Integer Linear Programming - Does it exist a poly-time algorithm for this problem? We don't know does it exist or not.
7. Does it exist algorithm which solves all pairs shortest path more faster then O(n^3) ? Once society have already been wrong that there is no better matrix multiplication algorithm rather then do it naively in ~(n^3). But Shtrassen have shown that it is possible! Maybe similar situation here, maybe not. Nobody knows right now.
Interesting things:
1. In Bell Labs(1991) Allan Wilks and Rick Beker discovered that qsort suddenly start to eat hours of CPU time. The problem if it is exist a lot of duplicate keys until this year C implementation qsort() give quadratic times, and most implementations from textbook had this.
Possible way to upgrade quicksort with "3-way partitioning" schema and now it's incorporated into C library.
BSD Unix(1983), Version 7 Unix (1979) had this problem.
2. After paper [Guibas-Sedgewick, 1979] a lot of libraries implement red-black trees.
In 2007 Sedgewick discrovered that it is exist a more simple way to implement red-black tree.