Entry problems

The Laboratory for Network and Information Systems receives many requests for graduate research assistantships or undergraduate research opportunities. We encourage students with an interest in the lab to submit a solution to one of these problems within their communications with us. The problems are rated according to the application level, but feel free to answer any of the questions.

Postdoc

1. Pose three problems relevant to the research at the lab. Make sure to explain why these problems are (i) interesting, (ii) important, (iii) relevant to the lab’s research.

2. Provide credible plans of attack to two of the problems in the PhD category. Make sure to reference relevant literature and provide as many technical details as possible.

PhD student

1. Provide a substantive improvement of the distributed ID-CODE algorithm in Robust Location Detection with Sensor Networks from JSAC 2004 (available at http://ipsit.bu.edu/documents/jsac_web.pdf). The improvement should be in either the (i) computational complexity, (ii) communication complexity [message or round], or some other measurable quantity. Alternatively, provide an efficient method for a network to self-organize an ID-CODE from scratch.

2. Compute the parameters of all dimension 4 lexicographic error-correcting codes (see for reference Designing Lexicographic Codes with a Given Trellis Complexity, IEEE Trans. Info. Theory ’02 (available at http://ipsit.bu.edu/documents/lexi_preprint.pdf). More generally, analytically compute the parameters of all lexicographic codes.

3. Provide an efficient method for computing the i-th Eulerian cycle in a connected graph according to any ordering of the cycles, or prove that none exists. The algorithm should run in w(iE) – that is, asymptotically less time than i×E, where E is the number of edges in the graph.

4. Perform an analysis of the masked node problem in a network where each node has enough buffer space for only 1 packet. Consider first the five-node scenario described in the paper Evaluation of the Masked Node Problem in Ad-Hoc Wireless LANs (available at http://people.bu.edu/staro/masked.pdf) and then try to extend the analysis to a general linear network.

5. Develop a distributed version of the TP-algorithm described in Application of Network Calculus to General Topologies using Turn-Prohibition (available at http://people.bu.edu/staro/TP-ToN.pdf ). Consider first the basic version and then try to extend it to the general version.

MS student

1. Provide a method for synchronizing vertex-labeled graphs with a minimal amount of communication. You may assume that each vertex is uniquely labeled. Make sure to prove how good your algorithm is with respect to an information-theoretic lower bound.

2. Provide a communication-efficient method for estimating the edit distance between two remote string (ie, one string is on one host and the other string is on another host – your optimization criterion is how much communication occurs between the hosts). Make sure to quantify the communication used by your algorithm and compare it to the information-theoretic lower bound.

3. Consider a traffic light that oscillates between being red for t_r seconds and green for t_g seconds. Assume the following model for a car: starting at rest, it accelerates at a meters per second (m/s) until it is traveling 10 m/s. If at any time it is within 1 meter of a car in front of it, it breaks with a deceleration of b m/s until it is at least 2 meters behind the car in front of it (deceleration stops if the car stops moving), and then it accelerates again as before. Assuming 1 car / second sets out for the traffic light from a distant location, what is the maximum number of cars that will be at rest at any given time, as a function of the variables in this problem.

4. Consider the analysis of the hidden node problem, as described in the paper Performance of Wireless Networks with Hidden Nodes: A Queueing-Theoretic Analysis (available at http://people.bu.edu/staro/ray_hidden.pdf). Extend the simple, approximated “random-look analysis” to a general linear network and compute numerical results for the same parameters as used in Section 6.2.2 of the paper. Compare your results with those in the paper and explain the discrepancies, if any.

5. Read the paper Efficient Clustering Algorithms for Self-Organizing Wireless Sensor Networks (available at http://people.bu.edu/staro/self-org-krishnan.pdf). Propose an algorithm that has a lower message complexity than Persistent, but can still achieve the desired bound B, assuming that enough nodes around the initiators are not yet clustered.

Undergraduate

1. What is the fastest way to compute the Hamming weight of a 32-bit integer? Recall that the Hamming weight of an integer is the number of ones in its binary representation. For the purposes of this problem, assume that byte-level C operations (|, &, ^, >>, <<, ==, constant) each require one clock cycle.

2. Write a small program that implements the basic version of the TP-algorithm described in the reference Application of Network Calculus to General Topologies using Turn-Prohibition (available at http://people.bu.edu/staro/TP-ToN.pdf ). The input should accept any graph of up to 100 nodes. The output should compute the fraction of prohibited turns in the network and state whether the resulting graph (after turn-prohibition) is connected or not.

3. Define a frankness phrase to be a concatenation of words (not necessarily correct English) with the property that the substring formed by looking at every other letter in the phrase, starting with the first letter, is a concatenation of correct English words. For example, “feedlot swampy” is a frankness phrase because it contains the substring “feltsap” that can be represented as the concatenation of the English words “felt” and “sap”. Find the shortest frankness phrase that contains all the letters of the alphabet, in any order. Use any reasonable English word list, for example http://puzzlers.org/anonftp/pub/wordlists/web2.txt. If possible, prove that your phrase is the shortest one possible.

Problems are copyrighted 2004 by Ari Trachtenberg and David Starobinski at Boston University and may not be reused without permission.