Sample Latex File

Here is a sample latex file. Read it carefully to extract the most information you can! You can compile and convert it to ps or pdf file.

Lecture slides

(Disclaimer: The material below has not been proof-read and may contain errors. I expect to put a polished version of the notes in the near future. Comments and suggestions are welcome.)
Lecture 1: Course Overview 1.ps 1.pdf
Lecture 2: Intro to Probability Theory 2.ps 2.pdf notes2.ps notes2.pdf
problem of the week (potw 1) pw1.ps pw1.pdf
Lecture 3: Min-Cut Algorithm, Random Variables 3.ps 3.pdf notes3.ps notes3.pdf
Lecture 4: Expectation, Quicksort 4.ps 4.pdf notes4.ps notes4.pdf
problem of the week (potw 2) pw2.ps pw2.pdf
Lecture 5: Distributed Algorithms, MIS 5.ps 5.pdf notes5.ps notes5.pdf
Lecture 6: Deviation 6.ps 6.pdf notes6.ps notes6.pdf
problem of the week (potw 3) pw3.ps pw3.pdf
Lecture 7: Chernoff Bounds 7.ps 7.pdf notes7.ps notes7.pdf
Lecture 8: Packet Routing 8.ps 8.pdf notes8.ps notes8.pdf
problem of the week (potw 4) pw4.ps pw4.pdf
Lecture 9: Packet Routing 9.ps 9.pdf notes9.ps notes9.pdf
A good reference for routing is F.T. Leighton's Introduction to Parallel Algorithms and Architectures.
Lecture 10: Dynamic Analysis 10.ps 10.pdf notes10.ps notes10.pdf
problem of the week (potw 5) pw5.ps pw5.pdf
Lecture 11: Universal Packet Routing 11.ps 11.pdf notes11.ps notes11.pdf
The reference for this is: F.T. Leighton, B. Maggs, S. Rao. Packet Routing and Job Shop Scheduling in O(Congestion + Dilation) steps.
Other related papers to check out:
Leighton, Maggs, Richa. Fast Algorithms for finding O(Congestion+Dilation) packet routing schedules, Combinatorica, 19(3), 1999.
Yuval Rabani, Eva Tardos. Distributed packet switching in arbitrary networks.
Lecture 12: Lovasz Local Lemma, Universal Packet Routing 12.ps 12.pdf (refer to notes11.*)
problem of the week (potw 6) pw6.ps pw6.pdf
Lecture 13: Contention Resolution Protocols 13.ps 13.pdf
The reference for this is: J. Hastad, F.T. Leighton, B. Rogoff. Analysis of Backoff protocols for multiple access channels. SIAM Journal on Computing, 25(4) 1996, 740-774. (Also in ACM STOC 1987 - available online.)
A related paper to check out:
P. Raghavan and E. Upfal. Stochastic Contention resolution using short delays.
Lecture 14: Contention Resolution 14.ps 14.pdf
problem of the week (potw 7) pw7.ps pw7.pdf
Lecture 15: Queueing Theory 15.ps 15.pdf notes15.ps notes15.pdf
Lecture 16: Queueing Theory 16.ps 16.pdf
Lecture 17: Queueing Theory 17.ps 17.pdf notes17.ps notes17.pdf
Lecture 18: P2P Networks 18.ps 18.pdf notes18.ps notes18.pdf
The reference for this is: G. Pandurangan, P.Raghavan, and E. Upfal. Building Low-Diameter P2P Networks. IEEE FOCS 2001.
problem of the week (potw 8) pw8.ps pw8.pdf
Lecture 19: P2P Networks 19.ps 19.pdf notes19.ps notes19.pdf
Lecture 20: P2P Networks20.ps 20.pdf notes20.ps notes20.pdf
Lecture 21: P2P, Martingales 21.ps 21.pdf notes21.ps notes21.pdf
problem of the week (potw 9) pw9.ps pw9.pdf
Lecture 22: Social Networks 22.ps 22.pdf notes22.ps notes22.pdf
The reference for this is: J. Kleinberg. Small-world Phenomenon: An algorithmic perspective, STOC 2000.
Lecture 23: Social Networks 23.ps 23.pdf notes23.ps notes23.pdf
problem of the week (potw 10) pw10.ps pw10.pdf

Talks

Please send me an email soon regarding the title of the work and the day you want to present your work. It is on a first-come first-serve basis.
The slot allocation is currently as follows:
April 10: K. Hong: "Randomized Routing Algorithm on (n,k) Star Graphs"
April 15: M. Carney: "Using Genetic Algorithms to detect Network attack signatures"
April 17: M. Kwon: "Analysis of fault-tolerant overlay networks."
April 22: O. Younis: "A data dissemination protocol for sensor networks"
S. Chakraborty: "Distributed Construction of Sparse Spanner for Wireless Ad Hoc Networks"
April 24: M. Khan: "An energy efficient routing scheme in sensor networks"
April 29: R. Cheng: "A New Model to Explain the Power Laws of the Internet"
J. Pandey: "Small World Phenomenon in Dynamic Networks"
May 1: M. Fouad: "Power Control in Wireless Ad Hoc Networks"

Each talk is not more than 40 min duration including questions. There can be more than one talk in one class; unfinished talks will be continued in the next class.

Papers

Here are some papers to look at. The best way to find online copies of the papers is to type the title (or authors) of these papers at Google. Our library should also have copies, some of them even online (if Purdue has online subscriptions to those journals.) You should also explore related papers cited in the references to get ideas. (More will be added later. Suggestions are welcome.)

Routing:
* A. Broder and E. Upfal. Dynamic Deflection Routing on Arrays, Proc. of Symposim on Theory of Computing (STOC) 1996.
* A. Broder, A. Frieze, E. Upfal. A General Approach to Dynamic Packet Routing with Bounded Buffers, IEEE FOCS, 1996.
* J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, O. Waarts. Online Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling. Journal of the Association for Computing Machinery 44(3):486-504, May 1997.
* Y. Aumann and Y. Rabani. Improved Bounds for All Optical Routing. SODA 95.
* M. Andrews and L. Zhang. Packet Routing with Arbitrary End-to-End Delay Requirements., STOC 99.
* A. Kamath, O. Palmon and S. Plotkin. Routing and Admission Control in General Topology Networks with Poisson Arrivals. SODA 1996.

P2P networks:
* I. Stoica, R. Morris, D. Karger, M. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications, in Proceedings of ACM SIGCOMM, 2001.
* G. Pandurangan, P. Raghavan, and E. Upfal. Building Low-Diameter Peer-to-Peer Networks, IEEE Journal on Selected Areas of Communications, to appear. (Conference version in 42nd Annual IEEE FOCS, 2001).
* D. Liben-Nowell, H. Balakrishnan, and D. Karger, Analysis of the Evolution of Peer-to-Peer Systems. ACM Conf. on Principles of Distributed Computing (PODC), Monterey, CA, July 2002.
* J. Aspnes, Z. Dimadi, and G. Shah. Fault-Tolerant Routing in Peer-to-Peer Systems, Proceedings of the ACM Principles of Distributed Computing (PODC), 2002.
* J. Saia, A. Fiat, S. Gribble, A. Karlin, and S. Saroiu. Dynamically Fault-Tolerant Content Addressable Networks, in Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS'02), March 2002, Cambridge, MA.
* S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker. A Scalable Content-Addressable Network in Proceedings of ACM SIGCOMM, 2001.
* Bong-Jun Ko and Dan Rubenstein. A Greedy Approach to Replicated Content Placement Using Graph Coloring Invited Paper SPIE ITCom Conference on Scalability and Traffic Control in IP Networks II, Boston, MA, July 2002.

WWW/Internet:
* R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic Models for the Web. In Proceedings of the 41st Annual Symposium on the Foundations of Computer Science, 2000.
* G. Pandurangan, P. Raghavan, and E. Upfal. Using PageRank to Characterize Web Structure, In Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON), LNCS 2387, Springer-Verlag, 330-339, 2002.
* W. Aiello, F. Chung-Graham and L.Lu. Random evolution of massive graphs, Handbook on Massive Data Sets, (Eds. James Abello et al.), Kluwer Academic Publishers, (2002), 97-122. Extended abstract appeared in FOCS 2001, 510-519.
* A. Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science , 286 (509), 1999.
* A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S.Rajagopalan, R. Stata, Andrew Tomkins, J. Weiner.Graph Structure in the Web. In Proceedings of the 9th WWW Conference, 2000.
* Alex Fabrikant, Elias Koutsoupias, C.H.Papadimitriou Heuristically Optimized Trade-offs: A new paradigm for the power laws of the Internet, Proc. of STOC 02.

Adhoc Networks:
* A. Amis, R. Prakash, T. Vuong, and D.T. Huynh. Max-Min Cluster Formation in Wireless Ad Hoc Networks. In Proc. IEEE INFOCOM, 1999.
* P. Gupta and P. Kumar. Critical Power forAsympototic Connectivity in Wireless Networks, in Stochastic Analysis, Control, Optimizationand Applications: A Volume in Honor of W.H.Fleming, W. M. McEneaney, G. Yin, and Q. Zhang(Eds.), Birkhäuser, Boston, 1998.
* S.Meguerdichian, F. Koushanfar, M. Potkonjak and M.Srivastava. Coverage problems in wireless ad-hoc sensor networks. Infocom 2001, 1380-1387.
* A.Tsirigos, Z.Haas, S.Tabrizi. Multipath routing in mobile adhoc networks or how to route in the presence of topological changes. IEEE MILCOM, 2001.

Social Networks:
* J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
* A. Goel, R. Govindan, and H. Zhang. Using the Small-World Model to Improve Freenet Performance, Proc. of IEEE INFOCOM, 2002.

Misc:
* G. Pandurangan and E. Upfal, Static and Dynamic Evaluation of QoS Properties, Journal of Interconnection Networks, 1(2), 2000, 135-150.
* C. G. Plaxton, R. Rajaraman, and A. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment, Theory of Computing Systems, 32, 1999, 241-280.
* R. Rajaraman, A. Richa, B. Vocking ,and G. Vuppuluri, A Data Tracking Scheme for General Networks, In Proc. of ACM Symposium on Parallel Algorithms and Architectures, 2001, 247-254.