# An example of Citation

In this example we cite some research conducted by others. All references are shown in the references section which is written in IEEE format.

In classical uniform hashing with chaining, a set of s keys is inserted into a hash table with n separate chains (or linked lists) via a uniform hash function. The insertion time is constant, and the average search time is proportional to the load factor of the hash table α := s/n. However, even for a constant load factor, the worst-case search time (the length of the longest chain) is asymptotic to log n/log log n in probability [18, 27].

Azar et al. [3] suggested a novel approach called the greedy two-way chaining paradigm. It uses two independent uniform hash functions to insert the keys, where each key is inserted on-line into the shorter chain, with ties broken randomly. The insertion time is still constant, while the average search time cannot be more than twice the average search time of classical uniform hashing. However, the expected maximum search time is only 2 log2 log n+2α+O(1) [3, 4, 24]. The two-way chaining paradigm has been effectively used to derive many efficient algorithms [5, 6, 7]. A further variant of on-line two-way chaining [28] improves the maximum search time by a constant factor.

On the other hand, one can show that the off-line version of two-way chaining, where all the hashing values of the keys are known in advance, yields better worst-case performance [3, 8, 25]. Czumaj and Stemann [8] proved that if s ≤ 1.67545943 …×n, one can find an assignment for the keys such that the maximum chain length is at most 2 w.h.p. (with high probability, i.e., with probability tending to one as n→∞).

Appendix A: Title of the Appendix

Here you should append any appendices. The appendix title should follow same style as your chapter titles. If the titles of your appendices are long then you can write the appendices in font size 20pt instead of 24pt but you should do it for all appendices and not just one. You can also number your appendices in capital roman numbers, I, II, III, etc.

Appendix B: Title of the Appendix

Here is the second appendix.

References

Alon and J. H. Spencer, The Probabilistic Method, 2nd ed., John Wiley, New York, 2000.

Angluin and L. G. Valiant, “Fast probabilistic algorithms for Hamiltonian paths and matchings,” Journal of Computer and Systems Science, vol. 18, pp. 155—193, 1979.

Azar, A. Z. Broder, A. R. Karlin and E. Upfal, “Balanced allocations,” SIAM Journal on Computing, vol. 29 (1), pp. 180—200, 2000. A preliminary version of this paper appeared in Proceedings of the 26th ACM Symposium on Theory of Computing (STOC), pp. 593—602, 1994.

Berenbrink, A. Czumaj, A. Steger, and B. VÄocking, “Balanced allocations: the heavily loaded case,” in: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 745—754, 2000.

Broder and M. Mitzenmacher, “Using multiple hash functions to improve IP lookups,” in: Proceedings of the IEEE INFOCOM 2001 Conference, Anchorage, Alaska, USA, April 2001. Full version available as Technical Report TR–03–00, Department of Computer Science, Harvard University, Cambridge, MA, 2000.

Byers, J. Considine, and M. Mitzenmacher, “Simple load balancing for distributed hash tables,” in: Proceedings of the 2nd International Workshop on Peer-to-Peer Systems, pp. 80—87, 2003.

Czumaj, F. Meyer auf der Heide, and V. Stemann, “Contention resolution in hashing based shared memory simulations,” SIAM Journal on Computing, vol. 29, No. 5, pp. 1703–1739, 2000.

Czumaj and V. Stemann, “Randomized allocation processes,” Random Structures and Algorithms, vol. 18, Issue 4, pp. 297–331, June 2001.

Devroye, “Branching processes and their applications in the analysis of tree structures and tree algorithms,” in: Probabilistic Methods for Algorithmic Discrete Mathematics, ed. M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed, pp. 249–314, 1998.

Devroye and P. Morin, “Cuckoo hashing: further analysis,” Information Processing Letters, vol. 86, pp. 215–219, 2004.

Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. Tarjan, “Dynamic perfect hashing: upper and lower bounds,” SIAM Journal on Computing, vol. 23 (4), pp. 738–761, 1994. A preliminary version appeared in: Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 524–531, 1988.

Dietzfelbinger and F. Meyer auf der Heide, “A new universal class of hash functions and dynamic hashing in real time,” in: Proceedings of the 17th International Colloquium on Automata Languages and Programming, LNCS 443, Springer-Verlag, pp. 6–19, 1990.

Dietzfelbinger and F. Meyer auf der Heide, “High performance universal hashing, with applications to shared memory simulations,” in: Data Structures and Efficient Algorithms, LNCS 594, Springer-Verlag, pp. 250–269, 1992.

Erdos, “Some remarks on the theory of graphs,” Bulletin of the American Mathematical Society, vol. 53, pp. 292–294, 1947.

ErdÄos and A. Renyi, “On the evolution of random graphs,” Publ. Math. Ins. Hunger. Acad. Sci., Vol. 5, PP. 17-61, 1960.

Fredman, J. Koml¶os, E. Szemer¶edi, “Storing a sparse table with O(1) worst case access time,” Journal of the ACM, vol. 31, pp. 538–544, 1984.

Gajewska and R. E. Tarjan, “Deques with heap order,” Information Processing Letters, vol. 22(4), pp. 197–200, 1986.

H. Gonnet, “Expected length of the longest probe sequence in hash code searching,” Journal of the ACM, vol. 28, pp. 289–304, 1981.

Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American Statistical Association, vol. 58, pp. 13–30, 1963.

Janson, D. E. Knuth, T. ÃLuczak, and B. Pittel, “The birth of the giant component,” Random Structures and Algorithms, vol. 4 (3), pp. 233–358, 1993.

Janson, T. ÃLuczak and A. Ruci¶nski, Random Graphs, John Wiley & Sons, New York, 2000.

M. Karp, “The transitive closure of a random digraph,” Random Structures and Algorithms, vol. 1, PP. 73-93, 1990.

Malalla, Two-way Hashing with Separate Chaining and Linear Probing, Ph.D. thesis, School of Computer Science, McGill University, 2004.

Mitzenmacher, A. Richa, and R. Sitaraman, “The power of two random choices: A survey of the techniques and results,” in: Handbook of Randomized Computing, (P. Pardalos, S. Rajasekaran, and J. Rolim, eds.), pp. 255–305, 2000.

Pagh, “On the cell probe complexity of membership and perfect hashing,” in: Proceedings of 33rd ACM Symposium on Theory of Computing (STOC), pp. 425–432, 2001.

Pagh and F. F. Rodler, “Cuckoo hashing,” in: Proceedings of the European Symposium on Algorithms, LNCS 2161, Springer-Verlag, pp. 121–133, 2001. A previous version is available as BRICS Report Series RS–01–32, Department of Computer Science, University of Aarhus, 2001.

Raab and A. Steger, ““Balls into bins”|a simple and tight analysis,” in: Proceedings of the 2nd Workshop on Randomization and Approximation Techniques in Computer Science, vol. 1518, Lecture Notes in Computer Science, Springer-Verlag, pp. 159–170, 1998.

Vocking, “How asymmetry helps load balancing,” in: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 131–141, 1999.