Heinz Nixdorf Institut
Universität Paderborn
Algorithms and Complexity

Home
Contents
Schedule
Exercises
Exam
Lecture Notes
Literature

Orientation:

Heinz Nixdorf Institute
Algorithms and Complexity
 
Web master
  

»Search Algorithms«

Christian Schindelhauer

Literature

  • Lecture 1+2:
    • Thomas Cormen, Charles Leiserson, Ronald Rivest, Introduction to Algorithms, The MIT Press, 1989
      The first two (or three) lectures are based on chapter 34: String Matching 853-876
  • Lecture 3:
    • W. Weaver and C. E. Shannon, The Mathematical Theory of Communication, Urbana, Illinois: University of Illinois Press, 1949, republished in paperback 1963
    • There is a number of good presentations in  Wikipedia: Huffman Code (german), Shannon encoding (german)
    • Ming Li, Paul  Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications,  Springer-Verlag, 1993
  • Lecture 4:
    • LZW: Terry A. Welch: "A Technique for High Performance DataCompression",  IEEE Computer vol. 17 no. 6, Juni 1984, p. 8-19
    • LZ77: J. Ziv, A. Lempel: "A Universal Algorithm for Sequential DataCompression", IEEE Transactions, p. 337-343
    • LZ78: J. Ziv, A. Lempel: "Compression of Individual Sequences Via Variable-Rate Coding", IEEE Transactions on Information, p. 530-536<>
  • Lecture 5:
    • A. Amir, G. Benson and M. Farach, Let sleeping files lie: pattern-matching in Zcompressed files, in SODA'94 (1994).
  • Lecture 6:
    • Sergey Brin and Lawrence Page, "The Anatomy of a Large-ScaleHypertextual Web Search Engine", Computer Networks and ISDNSystems, Vol. 30, 1-6, p. 107-117, 1998
  • Lecture 7:
  • Lecture 8:
    • Jon Kleinberg, „Authoritative Sourcesin a Hyperlinked Environment“,Journal of the ACM 46(5): 604-632(1999)
  • Lecture 9:
    • Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in random networks. Science, 286(5439):509–512, October 1999.
    • Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. Graph structure in the Web. Computer Networks (Amsterdam, Netherlands: 1999), 33(1–6):309–320, June 2000.
    • Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. Trawling the web for emerging cyber-communities. In Proceedings of the Eighth International World-Wide Web Conference, 1999.
    • See also script of lecture "Algorithmen des Internets" (german), 2002
    • Pumain D. 2004, Scaling laws and urban systems. Santa Fe Institute, Working Paper n°04-02-002, 26
    • Adamic, L.A., Huberman, B.A.: Zipf's law and the internet. Glottometrics 3 (2002)
    • Mark Crovella, Murad, Taqqu, Azer Bestavros, Heavy-Tailed Probability Distributions in the World Wide Web, A practical guide to heavy tails: statistical techniques and applications, 3-25, 1998, Birkhauser Boston.
    • A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A.Tomkins, and J. Wiener. “Graph Structure in the Web: Experiments andModels.” In Proc. of the 9th World Wide Web Amsterdam: Elsevier Science, 2000.
  • Lecture 10:
    • William  Aiello  Fan  ChungLinyuan  Lu, A Random Graph Modelfor Massive Graphs, Symposium on Theory of Computing (STOC) 2000
    • Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, and Bernardo A. Huberman. Search in power-law networks. Physical Review E, 64(46135), 2001.
  • Lecture 11:
    • Kranakis, Krizanc, “Searching with Uncertainty”, SIROCCO, 1999, 194-203
    • Ming-Yang  Kao. John  H.  Reil, Stephen  R.  Tate, Searching  in  an  Unknown  Environment:  An  Optimal  Randomized  Algorithm  for  the  Cow-Path  Problem
    • Allan Borodin, Ran El-Yaniv, Online Computation and Competitve Analysis, Cambridge University Press, 1998
    • Ricardo A. Baeza-Yates, Joseph C. Culberson, Gregory J.E. Rawlins, Searching in the Plan, Information and Computation 106, 234-252, 1993.
  • Lecture 12:
    • Ming-Yang Kao, John H. Reif, Stephen R. Tate, Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem, In Proc. 4th ACMSIAM SODA, 304-313, 1993.
    • C. Papadimitriou, and M. Yannakakis, Shortest Paths Without a Map. Theoretical Computer Science, 84 (1991), pp. 127-15
    • Avrim Blum, Prabhakar Raghavan, Baruch Schieber,  Navigating in Unfamiliar Geometric Terrain, SIAM Journal on Computing, Volume 26, Number 1, pp. 110-137, 1997.
    • Piotr Berman, Avrim Blum, Amos Fiat, Howard Karloff, Adi Rosén, Michael Saks, Randomized robot navigation algorithms, SODA, 1996, 75-84.
    • E. Bar-Eli, Piotr Berman, Amos Fiat, and Peiyuan Yan. On-line Navigation in a Room. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 237-249, Orlando, FL, January 27-29 1992.
  • Lecture 13:
  Further literature links will be added as soon as necessary.

Created: 2004-09-15
Last change: 2005-01-30
Christian Schindelhauer (email: schindel@upb.de)