Yesterday I gave a talk in the joint Mathematics and Computer Science seminar, at CI. Here are the slides.
Refreshments will be served
Title: Algorithms on Strings
Speaker: Michael Soltys
Date/Place: February 4th, 2015, at 6pm, in Del Norte 2530
Abstract: This talk is going to be centered on two papers that are going to appear in the following months:
- Neerja Mhaskar and Michael Soltys, Non-repetitive strings over alphabet lists
to appear in WALCOM, February 2015.
- Neerja Mhaskar and Michael Soltys, String Shuffle: Circuits and Graphs
to appear in the Journal of Discrete Algorithms, January 2015.
Visit http://soltys.cs.csuci.edu for more details (these two papers are number 3 and 19 on the page), as well as Python programs that can be used to illustrate the ideas in the papers. We are going to introduce some basic concepts related to computations on string, present some recent results, and propose two open problems.
Mobile Robots for Exploration, Assistance and Education
a talk by
Professor David P. Miller
College of Engineering, Aerospace and Mechanical Engineering,
The University of Oklahoma
Tuesday, February 3rd, 6-7 pm
Del Norte 1500
Abstract: Mobile robots share some basic characteristics with animals and even people. This makes them ideal for carrying out some tasks normally done by people. This talk will discuss some past and present research I have done using mobile robots to explore natural terrain, and how a correct balance between mechanical and cognitive capabilities can significantly improve performance in certain aspects over what has been demonstrated by NASA rovers. Current work using an assistive co-robot to help children at risk for cerebral palsy to learn how to crawl will also be presented. We will conclude with a discussion of why robotics is an effective CS and engineering outreach tool, and how the sense of deification robotics can create amongst students is useful for promoting STEM education.
Bio: David Miller has a Bachelors in Astronomy from Wesleyan and a PhD in Computer Science from Yale University. While at JPL (1987-1993) he formed the Robotics Intelligence Group and started the work in small rovers that led to Mars Pathfinder Mission and the Sojourner Rover. in 1994 he co-founded the KISS Institute for Practical Robotics, a non-profit that continues to create and deliver educational robotics programs and robot technology world-wide today. Since 1999 he has been the Wilkonson Chair and Professor of Intelligent Systems at the University of Oklahoma attached to the schools of Aerospace and Mechanical Engineering, Computer Science, and Bio-Medical Engineering. His research concentrates in two main areas: robotics technology (particularly exploration and assistive applications) and robotics as a mechanism for technology education. His interests in robotics technology are in automated planning, robotics, and communications between people and robot systems.
Refreshments will be served
Speaker: Neerja Mhaskar
Time/Place: Monday February 16, 2015, 7:00-8:00pm, in Del Norte 1545
Title: Repetition in Strings and String Shuffles.
Bio: Neerja Mhaskar is a PhD candidate in Computer Science at McMaster University. She did her masters in Engineering Science with Information Technology as major at Louisiana State University, and her undergraduate in Mechanical Engineering at Jawaharlal Nehru Technological University, Hyderabad, India. Her research interest is in the general area of string algorithms and combinatorics on words with an emphasis on computational complexity of the problems.
Abstract: There are several areas of emerging and continued interest such as bioinformatics, text searching, data compression, signal processing, abstract algebra which benefit from research in the general area of string algorithm.
A string (word) is traditionally a sequence of characters. A string (word) is said to be non-repetitive (square-free) if it does not contain a subword of the form vv. Given a list of alphabets L=L_1,L_2,…,L_n, we investigate the question of generating non-repetitive words w = w_1w_2,…,w_n$, such that the symbol w_i is a letter in the alphabet $L_i$. This problem has been studied by several authors (e.g., Grytczuk et al., Shallit), and it is a natural extension of the original problem posed and solved by A. Thue. In the first half of the talk, I will present our work on this problem, where we show that such strings exist over many classes of lists and suggest techniques for tackling the problem, ranging from online algorithms, to combinatorics over 0-1 matrices, and to proof complexity. Finally, we show some properties of the extension of the problem to abelian squares.
In the remainder of the talk, I will present our contribution in the area of string shuffles. A shuffle of two strings is said to be formed by interleaving the characters into a new string in a way that keeps the characters of each string in order. In the paper “String Shuffle: Circuits and Graphs” we show that shuffle, the problem of determining whether a string w can be composed from an order preserving shuffle of strings x and y, is not in AC^0, but it is in AC^1. The fact that shuffle is not in AC^0 is shown by a reduction of parity to shuffle and invoking the seminal result of Furst et~al., while the fact that it is in AC^1 is implicit in the results of Mansfield. Together, the two results provide a lower and upper bound on the complexity of this combinatorial problem. We also explore an interesting relationship between graphs and the shuffle problem, namely what types of graphs can be represented with strings exhibiting the anti-Monge condition.
Refreshments will be served
Speaker: Ryszard Janicki
Time/Place: Monday February 16, 2015, 6:00-7:00pm, in Del Norte 1545
Title: On Pairwise Comparisons Based Rankings
Bio: Ryszard Janicki received the M.Sc. degree in applied mathematics from the Warsaw University of Technology, Poland in 1975, and the Ph.D. and Habiliatation in computer science from the Polish Academy of Sciences, Warsaw, Poland in 1977 and 1981 respectively. He taught computer science and mathematics at the Warsaw University of Technology, Poland and Aalborg University, Denmark in, before joining McMaster University, Hamilton, Ontario in 1986. He published more than 120 papers and coauthored a monograph on concurrency theory. He is a member of the Editorial Board of Fundamenta Informaticae and Journal of Computational Science. His research interests include concurrency theory, fundamentals of software engineering, mereology, ranking theory and relational methods in computer science.
Abstract: The talk will be devoted to various aspects of pairwise comparisons based ranking. Both standard numerical case and more abstract non-numerical case and their relationship will be discussed. The concept of consistency, for both models, numerical and non-numerical, will be analyzed. Moreover, partially ordered approximations of arbitrary binary relations will formally be defined and some solutions proposed. The problem of testing and the importance of indifference and the power of weak order extensions will also be discussed.
Today I gave a talk at TAPPS (the Toronto Association of Police and Private Security), tilted How safe is your data? Here are the slides on SlideShare.
Here are some of the sources cited in the presentation:
- CRS Report for Congress 2008
- Vanity Fair: Operation Shady Rat 2011
- Vanity Fair: Enter the Cyber-Dragon 2011
- Malicious PDF (ISC)
- Networks Course Password Cracking Challenge (post from March 19, 2014)
I have also used the following videos:
and the presentation included this video that I did not show:
Also, I would like to point out that for the presentation slides I used the the Google Go present package. It runs a web server that presents slide and article files from the current directory. It may be run as a stand-alone command or an App Engine app. The stand-alone version permits the execution of programs from within a presentation. I have written some more about it in post 448.