Explore the vast range of titles available.

We consider the problem of scheduling a set of classes to classrooms with the objective of minimizing the number of classrooms used. The major constraint that we must obey is that no two classes can be assigned to the same classroom at the same time on the same day of the week. We present an algorithm that produces a nearly optimal schedule for an arbitrary set of classes. The algorithm's first stage produces a packing of classes using a combination of a greedy algorithm and a non-bipartite matching and the second stage consists of a bipartite matching. First we show that for one variant of the problem our algorithm produces schedules that require a number of classrooms that is always within a small additive constant of optimal. Then we show that for an interesting variant of the problem the same algorithm produces schedules that require a small constant factor more classrooms than optimal. Finally, we report on experimental results of our algorithm using actual data and also show how to create schedules with other desirable characteristics.

Collaborative tagging has emerged as a popular and effective method for organizing and describing pages on the Web. We present Treelicious, a system that allows hierarchical navigation of tagged web pages. Our system enriches the navigational capabilities of standard tagging systems, which typically exploit only popularity and co-occurrence data. We describe a prototype that leverages the Wikipedia category structure to allow a user to semantically navigate pages from the Delicious social bookmarking service. In our system a user can perform an ordinary keyword search and browse relevant pages but is also given the ability to broaden the search to more general topics and narrow it to more specific topics. We show that Treelicious indeed provides an intuitive framework that allows for improved and effective discovery of knowledge.

We report on the CS/M Scholars Program which is supported by an NSF S-STEM grant that began in 2011. The program aims to increase the number of women graduating with degrees in Computer Science or Mathematics. It is well known that women are underrepresented in these fields nationally and this is also the case at our university. Our efforts include targeted recruitment of female high school students with a record of academic achievement and leadership potential. In addition to providing scholarships, student success is bolstered by required first-year seminars, early advising, and monthly events focused on professional development and expanding awareness of opportunities. All of these activities have fostered a tight-knit learning community and provided ample opportunities for peer mentoring and networking with alumnae. Because we focus on recruiting first-year students and retaining them through graduation the program has grown from nine freshmen in the first year to over forty students now who range from freshmen to seniors. Our recruitment efforts have become more successful as the program has grown which we attribute to the active involvement of current students in recruiting and a record of the program’s accomplishments. Retention is higher than expected; moreover, retention rates are increasing. Students are excelling academically and have become visible, successful female members of male-dominated departments. This is having a positive effect on the cultures of the departments which is in turn encouraging other female students. Herein, we provide an overview of the CS/M Scholars Program and highlight the features that may be adaptable to other institutions without external funding. We report on statistics for recruitment, retention and graduation; share our ideas and experiences for impactful monthly events; explain how conference participation has been transformative for both students and their departments; and discuss funding conference participation with few institutional resources. We view our work so far as a pilot project in part because the program took four years to grow to its full size. We have recently submitted a new S-STEM proposal that, if funded, will initiate a design and development project that will include quantitative and qualitative assessment of the achievement of the program’s ultimate goals, which include shifting the demographics of graduates at our institution and observing continued employment of CS/M Scholars in their field.

In this dissertation we will examine centralized and distributed algorithms for network scheduling. The input to the network scheduling problem is a network of machines and a set of independent jobs such that each job originates on some machine in the network. A job may be processed on the machine it originated or it may be moved to another machine to be processed. Unlike many previous parallel machine scheduling models, our model accounts for communication between processors. If a job is moved from one processor to another processor it will incur a time delay. The delay is proportional to the distance between the two machines in the network. Another aspect of the network scheduling model is that each edge has a capacity which restricts the number of jobs that can be passed over it in one time step. We present two polynomial time centralized scheduling algorithms. One is for scheduling jobs optimally in a ring of processors with unit capacity edges. The other is for scheduling jobs optimally in arbitrary networks with infinite capacity edges. We also present three distributed approximation algorithms for network scheduling. All three of the distributed algorithms have extremely simple control structures and produce schedules with lengths that are within a small factor of optimal. The first of these results handles infinite capacity rings. We present a 4.22-approximation algorithm as well as provide simulation results that suggest the algorithm performs better than our analysis implies. Furthermore, we give a lower bound on the performance of any distributed scheduling algorithm for rings with infinite capacity links. The next algorithm we present is a simple d-approximation algorithm for scheduling jobs in d-regular networks with unit capacity links. We also show how to improve the analysis for rings; the improved analysis reduces the approximation factor to 5/3. The final algorithm is also for unit capacity networks and is very similar to the algorithm for d-regular networks. We prove that this algorithm is an O(log m)-approximation algorithm for arbitrary m machine networks given that the optimal schedule length is sufficiently large.