A Clustering Approach to the Bounded Diameter Minimum Spanning Tree Problem Using Ants

You are invited to Tyler Derr's Master's Thesis defense.

Thesis Title: "A Clustering Approach to the Bounded Diameter Minimum Spanning Tree Problem Using Ants"
Thesis Advisor:  Dr. Thang Bui

Date/Time:  Friday, March 27, 2015, 1 pm
Location:  Olmsted E309

Abstract
The bounded diameter minimum spanning tree problem is the problem of finding a minimum cost spanning tree of a graph such that the number of edges along the longest path in the tree is at most d. This problem is well known to be NP-hard. We present an ant-based algorithm for this problem in which we use two species of ants. The first species is used to discover clusters in the vertex set and then a bounded diameter spanning tree is created within each cluster. The second species is then used to connect the tree in the clusters together building a bounded diameter spanning tree for the whole graph. This tree is then local optimized yielding a solution to the overall problem. Experimental tests have been conducted on two types of complete graphs, 135 Euclidean and 120 non-Euclidean, totalling 255 graphs. Each Euclidean graph consists of a set of vertices randomly placed in the unit square and the edge cost between two vertices is the Euclidean distance between them. The non-Euclidean graphs are structured such that all the edge weights in the graph have been randomly selected from [0.01,0.99]. For the Euclidean graphs the results show that our algorithm achieves solutions close to the best known for most of the instances. However, on the non-Euclidean graphs our algorithm has obtained new best known solutions for the majority of the graphs and has come very close to the best known in the others.

Information Theory, Jokes, and Logic Puzzles

Ever wonder what kinds of jokes information theory professors tell?  Or how you can apply ideas from information theory to logic puzzles?  Or how you might write an algorithm to determine whether a joke is funny?  Or whether pizza is suitable for a late breakfast or early lunch?

If so, come to the following Pizza with a Professor talk:

Title:  "Information Theory, Jokes, and Logic Puzzles"
Speaker:  Dr. Jeremy Blum
Location:  Olmsted 212W
Date/Time:  Tuesday, March 31, 11:15 am
Topic: "Information Theory, Jokes, and Logic Puzzles"
Speaker: Dr. Blum
Day & Time: Tuesday (3/31/15) from 11:15am - 12:45pm
Location: Olmsted W212

Thesis Defense: Word Sense Disambiguation

You are invited to Saket Kumar's thesis defense.
Thesis Title: Word Sense Disambiguation
Thesis Advisor: Dr. Omar El Ariss

Date/Time:  Tuesday, March 24, 2015, 11:15am
Location: Olmsted E310.

Abstract
Semantics or the meaning of a given sentence is an important step in communication and knowledge acquisition. Humans are good with understanding the meaning of a given text, but how do we do that? Is it simply looking up the definition of each word one at a time or is it more than that? Also, is it possible for a program to automate the process of language understanding?

Humans can infer meaning through the use of not only the definition of word, where one word might have various conflicting definitions, but also based on their experience and the text’s context and domain. Word Sense Disambiguation is a problem in natural language processing that automates the process of text interpretation. In other words, WSD is an algorithm that finds the most appropriate word meaning in a particular context. The importance of Word Sense Disambiguation (WSD) lies in the processing of large amount of data without the need of constant help and human intervention. It is crucial for many applications such as translation, summerization, information retrieval and many other natural language applications.

We introduce an unsupervised knowledge based approach for word sense disambiguation using a bee colony optimization algorithm. We also present several variations to our bee colony approach that improves the overall performance of the algorithm. The Results are compared with recent unsupervised approaches such as ant colony optimization, genetic algorithm, most frequent sense and simulated annealing.

"Codebreaker" Movie Sceening and Q&A Session with the Executive Producer

You are invited a screening of the award winning documentary CODEBREAKER, which tells the remarkable and tragic story of one of the 20th century’s most important people. Alan Turing set in motion the computer age and his World War II code breaking helped turn the tide of the Second World War.  After the screening, there will be a Q&A session with Patrick Sammon,  the executive producer of the documentary.


Date and Time:  Friday, March 27, 2015, 6:00 pm
Location:  104 Educational Activities Building (EAB)


This event is open to the public, and is sponsored in part by the ACM Student Chapter.  More information about the movie is available at:

http://www.turingfilm.com/tag/codebreaker

Null and Lobur earn third “Texty” award

Dr. Linda Null, associate professor of computer science and Julia Lobur, instructor in computer science in Penn State Harrisburg’s School of Science, Engineering and Technology, have won their third “Texty” Textbook Excellence Award for the fourth edition of their textbook The Essentials of Computer Organization and Architecture (Jones & Bartlett Learning, LLC), given by the Text and Academic Authors Association (TAA). Null and Lobur previously won in 2013 for the third edition and 2007 for the second edition.

The Texty, recognizes works for their excellence in the areas of content, presentation, appeal, and teachability.

Null has taught mathematics and computer science for more than 30 years and currently serves as the computer science graduate program coordinator and associate program chair for Penn State Harrisburg.

Lobur, who earned her baccalaureate and master’s degrees in computer science at the college, has been a practitioner in the computer science industry for more than 30 years.  

The TAA is a nonprofit, membership association dedicated to assisting textbook and academic authors enhance the quality of textbooks and academic materials by providing educational and networking opportunities.

From Penn State Harrisburg News Release

Thesis Defense: Course Scheduling with Preference Optimization

You are invited to Siddharth Dahiya's thesis defense.

Thesis Title: Course Scheduling with Preference Optimization

Thesis Advisor: Dr. Thang Bui

Abstract

The university course timetabling problem is a well-researched NP-Hard problem where the goal is to create a course timetable with a given number of professors, courses and time slots. There are certain constraints that need to be followed to ensure that professors are not over booked and that courses that may be scheduled by a student in the same semester, are not scheduled during overlapping time. A new perspective of preferences for courses and professors is presented and upon it a new problem is introduced called course scheduling with preference optimization. The focus of this problem is given sets of courses, professors, time slots, and preferences in terms of time of day for each professor and each course, a schedule is generated where maximum possible preferences are satisfied. To solve this problem, a hybrid genetic algorithm called Course Scheduling Algorithm is also presented. The course scheduling algorithm returns a schedule where the preferences for professor and courses are maximized as well as the difference between the number of credits that may be assigned to a professor and the number of credits actually assigned to a professor is kept to a minimum.

Date/Time: Tuesday, March 17th, 11:15 am
Location: Olmsted E310

Talk: "Lessons from the $1,000,000 Netflix Prize"

Date/Time:  Thursday, March 19th, 6 pm
Location:  Olmsted 211C
Speaker:  Dr. Robert Bell (formerly with AT&T Labs-Research, soon to be with Google)

You are invited to hear Dr. Robert Bell discuss collaborative filtering and recommender systems for the COMP 597: Data Mining course.  Dr. Bell is one of the winners of the $1,000,000 Netflix Prize, a competition sponsored by Netflix to improve the accuracy of their movie recommendation system.  Since space is limited, if you are interested in attending and you are not enrolled in the Data Mining course, please RSVP to Dr. Blum (jjb24@psu.edu).

Speaker Biography:

Dr. Robert Bell is scheduled to join Google in April of this year.  Until recently, he was a member of the Statistics Research Department at AT&T Research since 1998.  He previously worked at RAND doing public policy analysis.  His current research interests include machine learning methods, analysis of data from complex samples, and record linkage methods.  He was a member of the team that won the Netflix Prize competition.  He has served on the Fellows Committee of the American Statistical Association, the board of the National Institute of Statistical Sciences, the Committee on National Statistics, the advisory committee of the Division of Behavioral and Social Sciences and Education, and several previous National Research Council advisory committees studying statistical issues from conduct of the decennial census to airline safety.   Dr. Bell received his Ph.D. in Statistics from Stanford University, an M.S. Statistics from the University of Chicago, and a B.S. in Mathematics from Harvey Mudd College.