Randomized Computation

Randomized Computation
from Jhoirene Clemente


Lecture on Randomized Computation for our Computational Complexity class.

This lecture includes a short introduction to randomized algorithms.  It includes discussion on probabilistic Turing Machines (PTMs), TMs that make use of random number in its computation, as well as different complexity classes that it recognize. The complexity classes include the Bounded Error Probability Polynomial (BPP), RP, co-RP, and ZPP. Relationship of the said classes where also presented as well as their relationship to known complexity class such as P and NP.






(SMACS 2012)

4 – 8 DECEMBER 2012

La Carmela Hotel


organized by

The Computing Society of the Philippines

SIG-Mathematical Aspects of Computer Science




About the Symposium…

SMACS 2012 is the sixth meeting on the mathematical aspects of computer science that will be held in the Philippines organized by the Computing Society of the Philippines. The first was in 1997 (UPCB), the second was in 2004 (UP-Baguio), the third was in 2006 (AUP, Cavite), the fourth was in 2008 (UP Cebu Colleges), and the fifth was in 2010 (UP Lon Banos, Laguna).


This year’s SMACS will be divided into two parts, workshop (4-6 December 2012) and seminar (7-8 December 2012). The workshop is designed such that researchers and instructors/lecturers of computing and mathematical sciences could interact on selected topics. Topics of the workshop will be tutorial in character which would lead to possible research collaboration. This year’s topics are:


    1. Computer Security and Cryptography

    2. Parallel Algorithms

    3. Coding Theory


The seminar will consist of paper presentations on researches in the mathematical aspects of computer science. There will be invited talks on the current and still potent area of mathematical aspects of computer science.


SMACS provides a venue for teachers, researchers and graduate students of Computer Science, Computing, and Mathematics to share and upgrade knowledge on areas of Computer Science which are mathematical or theoretical in character.


Topics of Interest (but not limited to):

Computability, Automata Theory and Formal Languages, Complexity Theory, Theory of Algorithms, Parallel Algorithms, Numerical Analysis, Combinatorial Optimization, Network Theory, Mathematical Modeling and Simulation, Logic and Logic Programming, Theory of Programming Languages, Coding Theory, Cryptography and Computer Security, Discrete Mathematics for Computer Science, Computational Mathematics, BioInformatics, Natural Computing


Submission and Proceedings:

Paper to be submitted must be written in English and must be at most 12 pages including title page; if appropriate, proofs should be attached in an appendix. We highly recommend electronic submission using the SMACS submission webpagehttps://www.easychair.org/conferences/?conf=smacs2012Simultaneous submission of papers or submission of previously submitted papers to any other conference with published proceedings are not allowed.


Proceedings of the Seminar will be available during the Symposium. Selected papers from the symposium will be published in a special issue of the Philippine Computing Journal, the Official journal of the Computing Society of the Philippines.


Organizing Committee: Jimmy D.L. Caro, UPD, Chair 

Program Committee:  Allan A. Sioson, ADNU, Co-Chair, Henry N. Adorna, UPD, Co-Chair


Important Dates:

Deadline of Paper Submission ………… 15 October 2012 (extended)

Notification of Acceptance …………….. 15 November 2012

Submission of Revised Paper ………….. 30 November 2012

Conference Date …………………………. 4-8 December 2012

Workshops on Game AI and Learning Sciences

The Department of Information Systems and Computer Science cordially invites 
faculty and students to two workshops on January 14, 2012:

Game AI: Yesterday, Today and Tomorrow by Dr. Taesik Kim of Keimyung 


Integrating Computer Science and the Learning Sciences by Dr. Ma. Mercedes 
T. Rodrigo of the Ateneo de Manila.

Please see details below.

Game AI: Yesterday, Today, and Tomorrow
Dr. Taesik Kim
Keimyung University, South Korea
14 January 2012, 8:00-12:00
Venue TBA
Department of Information Systems and Computer Science
Ateneo de Manila University, Loyola Heights, Quezon City

In many movies and science fiction stories, AI is one of the most popular 
themes of the story. Whether the characters have evolved to hate people and 
start eliminating all mankind, or fall in love with real people, they all 
share a common concept of ‘thinking and learning like humans.’ 
Unfortunately, in the real world, complexities of AI algorithms have not yet 
evolved to that point. In this lecture Game AI: Yesterday, Today, and 
Tomorrow, we will discuss true definition of artificial intelligence within 
games. All games are divided into two categories: perfect games and 
imperfect games. Game developers need to apply an appropriate game AI engine 
to maximize the user’s game experience in both types of games. Each AI 
engine is deigned to respond and react in specific situations in the game 
environment. Nowadays, due to the sharp increase of smart phone devices, 
mobile games are becoming a new popular playground for AI system engineers 
and game developers. However, since mobile phones contain many limitations, 
developers now face the difficulty of modifying previous AI engines to fit 
into mobile platforms. Moreover, going back to the actual concept of 
artificial intelligence, current concepts of AI algorithms are much further 
distanced from the ‘thinking and learning like human’ intelligence than AI 
which we see in movies and stories. We still have many steps which need to 
be climbed in the near future in order to create true artificial 

About Dr. Kim:

Dr. Kim received his PhD in Computer Science from North 
Dakota State University. Since 1992, he has been a Prfessor in the 
Department of Game and Mobile Contents of Keimyung University in South 
Korea. He is also the Director the Cultural Contents and Technology Project 
Group of Keimyung University, a center dedicated to research and development 
in the area of game and mobile contents. His areas of specialization are 
artificial intelligence in games and the development of iOS based AI games.

Integrating Computer Science and the Learning Sciences
Dr. Ma. Mercedes T. Rodrigo
Ateneo Laboratory for the Learning Sciences
14 January 2012, 1:00 to 5:30
Venue TBA
Department of Information Systems and Computer Science
Ateneo de Manila University, Loyola Heights, Quezon City

The Ateneo Laboratory for the Learning Sciences brings together artificial 
intelligence, data mining and statistics, education, cognitive psychology, 
human factors and other disciplines to study, enhance, and develop 
environments that improve student achievement and the learning experience. 
In this workshop, we will give participants an overview of laboratory’s 
goals and directions. We will discuss our work in affect and behavior 
detection and response in programming environments and intelligent tutors, 
as well as the design and development of interfaces that are sensitive to 
biometric readings and use behaviors. The purpose of this workshop is to 
acquaint fellow faculty members and current or prospective graduate students
with our ongoing research, and in so doing to foster collaboration and 
encourage participation.

About Dr. Rodrigo:

Dr. Rodrigo is an Associate Professor in the Department 
of Information Systems and Computer Science, Ateneo de Manila University and 
head of the Ateneo Laboratory for the Learning Sciences. Under her 
direction, the Ateneo’s Affective Computing group was recently named the 
first runner up of the CHED Best Higher Education Institution Research Award
for NCR. Her research interests include affective computing, artificial 
intelligence in education, intelligent tutoring systems, and computer 
science education.

Workshop costs and registration

The costs of the workshops are:

• P600.00 to attend both workshops. These fees cover lunch, two snacks, 
and handouts for both workshops.
• P400.00 to attend only one workshop. These fees cover lunch, two 
snacks, and handouts for both workshops.

Payment procedures will be announced at a later date.

To register, please email the following details to Melinda Nicdao 

Subject line: Workshop(s) title(s)
Institutional Affiliation:
Designation: (e.g. faculty member, student, etc.)
Contact Phone Number:
Email Address:

For more information

Please email your inquiries to Melinda Nicdao (mnicdao@ateneo.edu).

(Repost from CSP Invitation)

Math majors, rejoice. Businesses are going to need tens of thousands of you in the coming years as companies grapple with a growing mountain of data. Data is a vital raw material of the information economy, much as coal and iron ore were in the Industrial Revolution. But the business world is just beginning to learn how to process it all. The current data surge is coming from sophisticated computer tracking of shipments, sales, suppliers and customers, as well as e-mail, Web traffic and social network comments. The quantity of business data doubles every 1.2 years, by one estimate. Mining and analyzing these big new data sets can open the door to a new wave of innovation, accelerating productivity and economic growth. Some economists, academics and business executives see an opportunity to move beyond the payoff of the first stage of the Internet, which combined computing and low-cost communications to automate all kinds of commercial transactions. The next stage, they say, will exploit Internet-scale data sets to discover new businesses and predict consumer behavior and market shifts. 

Mining of Raw Data May Bring New Productivity, a Study Says – NYTimes.com

Church-Turing Thesis

I was completely fascinated by Godel’s Incompleteness theorem.

The theorem say’s that

Not all true statements are provable.

Though simplistically I can say that in a short sentence as previously mentioned, that statement ruined the life of so many mathematicians back then.  Mathematicians are known to devote their lives in a problem that seems to have no application in daily life but   only  for the sake of artbeauty and truth. As I quote one of the books I’ved read “Uncle Petros and the Goldbach’s Conjecture” by Apostolos Doxiadis(this book is one of my favorites, it depicts a mathematical obsession for the search of truth and beauty),

Mathematicians are born and not developed.

It’s  a destiny to be a Mathematician, one must be born with the gift of intellectual capability to be able to contribute a fraction of the Mathematical foundations.

Godel’s proof was so beautiful that, I myself cannot perceive it’s beauty. I must admit I am  not one of those geniuses who are meant to unravel that  life’s one of the greatest mystery.

Father of Computation

The great Alan Turing

When I entered Computer Science, I appreciate and love what Mr. Alan Turing proved in the  1920’s, Instead of explaining it the Godel way, He  introduced the concept of Computation, and proved that not all problems are solvable.

The commonly known as the first mathematical model of a computer is the Turing Machine, unlike Finite State machine and Push down automata, a Turing Machine can do whatever a present computer can do, and both are restricted to the limit of computation.

This Turing Machine is  a finite automaton with an access to an infinite tape, that serves as its memory. Initially the tape contains the input string and is blank everywhere else. The machine can read and write on the string and can move on either sides. The machine continues to move depending on the control sequences given by the finite state machine of the Turing machine. It either accepts or reject the input if it decides on the input.

Formal Definition of a Turing Machine

Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle where

  • Q is a finite, non-empty set of states
  • Γ is a finite, non-empty set of the tape alphabet/symbols
  • b \in \Gamma is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
  • \Sigma\subseteq\Gamma\setminus\{b\} is the set of input symbols
  • q_0 \in Q is the initial state
  • F \subseteq Q is the set of final or accepting states.
  • \delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows “no shift”, say N, as a third element of the latter set.)

Anything that operates according to these specifications is a Turing machine.

The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):

Γ = { 0, 1 }
b = 0 = “blank”
Σ = { 1 }
δ = see state-table below
q0A = initial state
F = the one element set of final states {HALT}

Variants of Turing Machine

  1. Single Tape Deterministic Turing Machine
  2. Multitape Deterministic Turing Machine
  3. Nondeterministic Turing Machine

Though multitape or non deterministic Turing machine looks deceivingly powerful than the usual Turing Machine. They are proven to have the same expressive power. The three variants  differ on the resources needed.