Friday, December 17, 2010

Happy winter solstice..

Dear all

 I hope all of you--especially the freshmen--survived the semester ;-). Please feel free to drop me a note and
let me know how things went for you and what you are doing next semester. 

 In the meantime, enjoy the glorious arizona winter weather (yesterday and today excluded of course), and feel free to
email/drop-in etc if you need any CS-related advice.


Friday, October 22, 2010

(Final) Blog questions on AI and Intelligent Agent Design..

1. Consider the game of chess. If you are developing a chess playing agent, is the environment in question accessible? deterministic? static?  There is a variant of Chess called "kriegspiel". Find out what it is and how its environment differs from that of chess (in our three dimensions). 

 2. Is it possible for an environment to be fully observable for one agent and only partially observable for another one?

3. Is it possible that an agent can model the same  environment either as (a) partially observable but with deterministic actions or (b) fully observable but with stochastic actions? Philosophically, what does this tell us about the nature of "randomness ? (bonus points: see if you can make a connection to the way we understand eclipses now vs. the way there were understood by our ancestors). 

4. Suppose you are trying to design an  agent which has goals of achievement (i.e., it is judged based on whether or not it ended up in a state where the "goal" holds). Would you want the agent to be given "hard goals" (i.e., goals that must be satisfied) or "soft goals" (i.e., goals which, if satisfied, will give the agent a reward; but if skipped won't stop the agent from experiencing the rewards it gets from other goals).  Focus on which is a harder "computational" problem.
(bonus: see if you can make a connection between this question and your high-school life vs. your university life..)

5. An environment is called "ergodic" if an agent in that environment can reach any state from any other state.   Can you think of examples of ergodic vs. non-ergodic environments? Which are easier for an agent? (in particular, think of an agent which doesn't want to "think too much" and prefers to do some random action and see what happens. How does such an agent fare in an ergodic vs. non-ergodic environment?)

6. We talked about the fact that the agent needs to have a "model" of the environment--where the model tells it what are properties of a state in the environment, and how the environment "evolves" both when left to itself and when you do an action on it.   A model is considered "complete" if it is fully faithful to the real environment. Do you think it is reasonable to expect models to have (a) complete models (b) no models or (c) partial models?    Suppose an agent has a partial model, and according to its model, it should pick some action A at this point. Should it *always* pick A or should it once in a while "live a little" and pick something other than A?    The question here has something to do with a fundamental tradeoff called "Exploration vs. Exploitation" tradeoff. See if you can relate this to the question of  when you should make the decision about which area of computer science you should specialize in. 


(reply to this mail) Attendance assessment


 As you know there were 10 meetings for ASU 101. Please respond to this mail and let me know

1. how many classes you missed in total

2. which classes, if any, you missed with prior notification to me

Please send this information just to me (*NOT* on the class blog)

(if you need to jog your memory as to what happened in which class, here is the list: )


*Required*: Acquired Wisdom Assignment (to be completed on the Blog)


 Here is the last *required* assignment for ASU101. Please enter your answer to the following question
as a comment on the blog:

  List 5 things (pieces of advice and/or technical ideas) that you took away from this course


Your answers will be a sort of the interactive summary of what actually happened in this class (and will be linked as 
"acquired wisdom" from the class page).


ps: There will be another mail from me with a set of blog questions on the intelligent agents. That one is not required but
recommended (like all the other blog questions were). 

Thursday, October 21, 2010

Please come to tomorrow's class with questions...


 As I said, tomorrow is the last officially scheduled meeting for ASU101. Although I have the "intelligent agent design" 
as the scheduled topic, I am happy to convert the class into a general discussion session for your questions. So, please
come prepared with questions if you have any. If you have nothing, then I will do the scheduled topic.


Friday, October 8, 2010

A talk by a CS undergrad that may be of interest (video included)

---------- Forwarded message ----------
From: Yann-Hang Lee <>
Date: Fri, Oct 8, 2010 at 11:07 AM
Subject: FW: a blog about one of your students

A nice presentation by Joseph about Ability Counts. If you teach ASU101, please share it with your students in the class.



(480) 727-7507


From: Ronald Askin
Sent: Friday, October 08, 2010 10:32 AM
To: Regina Duran
Cc: Yann-Hang Lee
Subject: RE: a blog about one of your students


Thanks for forwarding this link.

Ron Askin



Ronald G. Askin, Professor and Director                                                    

School of Computing, Informatics, and Decision Systems  Engineering

Arizona State University

Tempe, AZ   85287-8809


Phone: 480-965-2567



From: Regina Duran
Sent: Friday, October 08, 2010 9:54 AM
To: Ronald Askin
Subject: a blog about one of your students


Mr. Askin,


Joseph Caglio, a Computer Science graduate student, spoke at Ignite @ ASU on September 30th and is featured in the website. He did a fantastic job and we thought that you might be interested in seeing the video.




Regina Duran

Social Embeddedness Intern

Office of University Initiatives

Arizona State University


Agenda for today and the next two classes..


 Just to give you a heads-up, I plan to conclude the discussion of search engines today, and start a new topic (hopefully by the end of today's class, but if not starting next week), on
artificial intelligence and an overview of issues involved in designing intelligent agents.   I picked this as the last topic since several comments on the class blog over the semester
seemed to suggest that many of you are more interested in AI-related issues (robots, game-ai, machine learning), than I realized. Of course, it doesn't hurt that proselytizing unsuspecting populace
into the pleasures of AI is my favorite passtime ;-)


Friday, October 1, 2010

Results of class survey


 8 students (out of 18) took time to do the class survey that I had posted last week. An unedited version of all the comments is available for your viewing at

Thanks to all those who responded; I read them all. 

75% of those who responded seem to think that they are getting useful information out of the meetings; so we will basically stick to that format.

Several students requested for information about career paths in CS and CE. I have sent some resources about this in mail yesterday; and I expect to monitor the blog to 
respond to any questions people have after looking at those resources. We might also devote class time if that seems warranted.


Thursday, September 30, 2010

Careers in computing (or "Job advice")

Some of you asked for some information on careers in computer science.

The most comprehensive resource on careers in computer science is the one maintained by ACM:

If you want something short before you dig into that site, here are two short videos you might want to take a look. The first one is more about the traditional careers in CS, and the second talks about more "Out there"  careers in CS. The first is made by Columbia U and the second by Univ of Washington, so you have to suffer through some Columbia/UW advertisement. However, the directions they mention are all available to any CS students. [In fact, if you find any specific career direction more interesting to you, and want to know what is happening in that direction at ASU, I will be happy to point you in the right direction.]

CS Career Opportunities (if you can overlook the advertisement of Columbia :->)

Pathways in Computer Science (talks about careers that you may not have thought of ):

Feel free to add your questions/comments on these to the blog; I will respond to anything that needs a response from me..


Required Exercise: "Computational Thinking" --listen to the lecture and write your comments on the blog

Here is a "guest lecture" for this course--titled "Computational Thinking". In this, Jeannette Wing, who was the chair of CS in CMU and was, until recently the head
of National Science Foundation's  Computer and Information Science and Engineering, talks about how computational thinking--that Computer Scientists do for a living, 
is going to play a major part in everyone's  (not just CS students') life (just like philosophical thinking is not just for philosophy students).  

I would like you to either read either the article, or  the slides or hear the youtube lecture (they are not exactly identical but
close enough). Once you do, I would like you to comment on any points that caught your attention. 

You will have to do this by 8th October (i.e., you have a full week)

Video (on youtube; 65min):


Friday, September 17, 2010

Blog questions on document similarity measurement

1. A search engine that my friend wrote tries to return *all* the documents in its database no matter what the query. Comment on its
precision and recall (qualitatively--as in "high" and "low")

2. You are trying to find all the movies directed by Woody Allen, and so gave the query "woody allen directed" to your search engine. 
Suppose it returns IMDB records (IMDB is the internet movie database). What is more important in this case--precision or recall?

3. I am considering viewing documents as bags and use the bag similarity measure to compute their similarity. I am considering three different bag representations:

     a. documents as bags of letters (alphabetic characters)
     b. documents as bags of words 
     c. documents as bags of sentences

Comment on the relative precision/recall values offered by the three approaches.

4. One of the CSE faculty members used to have a bunch of magnetic words stuck to his (then metallic) doors. All the students passing by will try to arrange the magnetic words to make interesting english messages. If we assume that each student was making it a point to use *all* the words in his/her message, then what would the bag-of-words similarity measures say about the pair-wise difference among those messages? Considering that I told you that search engines use these as the default similarity metrics, what does it make you think about the intelligence of search engines?

5. Suppose I have a document D1: "Rao is a happy chap"   I make another document D2 by copying all the text from D1 and pasting it 2 times into D2 (so D2 is
"Rao is a happy chap Rao is a happy chap"). What will the bag similarity metric say about the similarity between D1 and D2? What will the cosine-theta (or vector) similarity metric
say about the similarity between D1 and D2? Which do you think is better for this case?


Fruit self defense...

Some of you seemed to be amused at all the fruit analogies in the class today (e.g. similarity between bags of fruit).

Fruit are no laughing matter; please see the following link for pointers on how to handle fruit:


Friday, September 10, 2010

Problem reduction and SAT questions...

Qn 1.

Give a solution to the following SAT problem:

Variables: P , Q, R

Clauses:  P V Q
                 ~P V R
                 ~Q V R

Qn 2. We saw that 3-SAT, which is the special case of boolean satisfiability problem where all clauses are of length 3, is NP-complete (i.e., as hard as any NP-complete problem).   How about 1-SAT? (i.e., SAT problem where all clauses are of length 1)

Qn 3.  Continuing Qn 2, how about 2-SAT (i.e., all clauses are of length 2)

Qn 4. We saw that boolean satisfiability is NP-Complete in that every other NP-problem can be reduced to it in polynomial time. Does this hold also for Sorting? Can you think of a way a 2 number sorting problem can be converted into a boolean satisfiability one? 


Saturday, September 4, 2010

Qns on NP-Completeness etc

1. My friend was asked by his boss to come up with an efficient algorithm for a time-tabling problem for the company.
My friend was unable to come up with anything that runs in less than exponential time. He wanted to convince his boss that
no one else could have done any better. He went and told the boss this: "Look, this time-tabling problem can be easily (i.e., in polynomial time)
converted into a boolean satisfiability problem. Now, it is well known that boolean satisfiability is an NP-Complete problem (i.e., it is one of 'em
monster problems in class NP). So it is no bloody surprise that I am unable to come up with anything other than an exponential algorithm".

What do you think of my friends' reasoning?

2. Explain why the arguments based on reductions to/from NP-complete problems is needed? Can't we just prove that a problem can't have anything
other than exponential (or polynomial) solution? Do you know of any famous problems that were thought to be exponential for a long time until someone found a polynomial algorithm?

3. Here is a "boolean satisfiability" problem. (If you need background, look at the wikipedia entry: )

Propositions:  P, Q, R , 

Clauses:  P V Q  ;    ~Q V ~R   [~ means "not"]

Explain, for each of  the following complete assignments, whether the assignment is a solution to the problem or not:

3.1.  P=True, Q=True; R=True

3.2.  P=False, Q= False,  R=False

3.3  P=True, Q=False, R=True


First order logic (+ peano arithmetic etc)

Yesterday, I mentioned that proving a theorem in first-order logic is "semi-decidable" in that if the theorem is true then your program will halt in finite time, and if it is 
false, it may never halt. 

This probably didn't make much sense to you as none of you seemed to recognize the phrase "first order logic". Let me explain what it is (you all actually probably know about it without that particular name).

Suppose you have the statements:   All mortals will die. All men are mortal.  Socrates is a man. 
From this, you can conclude "logically" that Socrates will die.  First order logic supports doing this inference. Specifically, in the syntax of first order logic, the statements above are written as

FORALL_x  mortal(x) => dies(x)     

FORALL_y  man(x) => mortal(x)


The "theorem" you want to prove is


==It is the proof of theorems like these that is semi-decidable (an informal technical reason is that that FORALL quanitification can be over infinite number of objects)==

Now, normal first order logic doesn't subsume arithmetic, and in particular, doesn't support mathematical induction (the rule that you may have used to prove the truth of statments such as  Sum of 1..n = n*(n+1)/2      You would have done this by showing that the formula holds for n = 1 (the base case); and showing that *if* it holds for n=k then it will hold for n=k+1, and thus by induction it holds for all numbers).  If you strengthen first order logic with mathematical induction, then for the resulting logic, Godel's incompleteness theorem holds--i.e., there may be theorems that are true given what you know, but you cannot prove that).


ps: Boolean logic is also called propositional logic, and is a *weaker* logic than first-order one. Where as first-order logic assumes that the world is made up for objects and relations "predicates" between them, boolean logic believes that the world is made up just of atomic statements that are either true or false. 

So, P & Q => R is a boolean logic formula

M(a,b) & N(a) & L(b) => R(a,b) is a predicate logic formula 

Friday, September 3, 2010

Undergraduate Research Opportunities (and CSE Clubs)  gives details on how you can apply for FURI scholarships

For NSF REU, you will have to talk to faculty members in the area(s) of your interest, but you can get the background on the program itself from here:

Here are links to CSE related student clubs:

The most active one seems to be women in Computer Science:

Others include OS-specific interest groups such as Linux Users group (there is one for macs and pcs too)


Engineering Tutoring Center (focusing on non-CSE courses)


Fwd: Tutoring available for CSE 100, 110, 205

---------- Forwarded message ----------
From: Yann-Hang Lee <>
Date: Tue, Aug 31, 2010 at 6:16 PM
Subject: FW: Tutoring available for CSE 100, 110, 205
Cc: Fred Morstatter <>, Manuel Aroz <>

Not sure whether this announcement from advising center went to you or not.


The tutoring service is a joint effort of CSE program, WCS student organization, and Engineering Tutoring Center. In total, there are 60 hours per week provided by 5 tutors in BYENG 214 AE/AD and in ECF100. As far as we know, Mr. Manny Aroz plans to interview one or more tutors. So, we will get additional hours to help the students in CSE 100/110/205.


If you teach ASU 101 sections, please let your students know this service and encourage them to utilize it. Also, we would like to hear from you any suggestions to improve our programs.



(480) 727-7507


From: CIDSE.Advising
Sent: Tuesday, August 31, 2010 4:29 PM
Subject: Tutoring available for CSE 100, 110, 205


Hello Students!


The Computer Science and Computer Systems Engineering Department is offering tutoring to students that need assistance in their CSE 100, 110, or 205 courses. 


See the link to a schedule that lists the times and courses the available tutor can assist you with.  Tutoring will begin September 1, 2010.  The location will be BYENG 214 AE/AD cubicle.


The tutoring schedule can be viewed at:


The schedule can change so keep this link in order to see any updates in real time.






Arizona State University   Ira A. Fulton Schools of Engineering

School of Computing, Informatics, and Decision Systems Engineering


Brickyard Building  -  CIDSE Academic Advising Center

699 South Mill Avenue, Brickyard, Suite 208 - Tempe, AZ  85281


P: 480-965-3199   F: 480-965-6630


Schedule an advising appointment online: Click Here

Parking information: Click Here








Sunday, August 29, 2010

Office Hours: M/W 8:00--9:00AM


 I will have my regular office hours from 8:00--9:00AM on M/W. You can either come to my office or meet with me by video skype (subbarao2z is the username) or google mail video chat (subbarao2z2 is the username).   If you cannot  make it for regular office hours, you can meet me by appointment. 


Complexity of Bogosort...

The really inefficient sorting program we discussed in the class--the one where you find all permutations of n numbers and see if any of them are sorted--is also called
"Bogosort" (or monkeysort etc..) 

As we saw, it does N* N! comparisons.

We saw that the CS folks' nightmare is exponential complexity, and I mentioned that N*N! is basically exponential complexity. 
To see why this is true, you need to remember Stirling's approximation, which says that for large N, N! is approximatly O(sqrt(N))* (N/e)^N  
(where e is the base of natural logarithms).   See's_approximation

Saturday, August 28, 2010

honors students in ASU101 section..

If you are an honors student (i.e., admitted to Barretts honor college), please let me know.


Friday, August 27, 2010

[ASU 101] Questions on Complexity...

Consider answering the following questions:

0. Write a brief summary of what you understood from today's class. [Each of you are encouraged to answer this--so I get an idea what is getting through]

1. There was a factual inaccuracy when I discussed Knuth. See if you can find what it is.

2. How long will it take for the world to end if the priests working in the Tower of Hanoi have been working out on the sly and are ready to do this problem round the clock, with 1 sec per move. 

3. For a given problem, your friend wrote an algorithm with 2^n steps (of unit time each). You wrote one with 4000*(n^5) steps  (where n is the problem size). Up to what input size is your friend going to beat you (alternately, beyond what input size are you going to cream your friend?)

4. In problem 3, suppose your friend, with his 2^n algorithm was able to solve instances of size up to n=K (K is some constant) in "reasonable time". His boss feels sorry for him and buys him a machine that is twice as fast. Now, what is the size of the largest instance that your friend can solve in reasonable time?


Monday, August 23, 2010

Milo, the virtual boy

Found this:

I was really amazed that the Kinect Camera finally had some thing worth while developed for it.
Well before the last few days I may have known why I was going CSE. Now I have doubts. I have transferred in from Community College. I take the shuttle into ASU each day.
Well it seems I may be living on campus now.
I always thought of CSE as more of they lock you in a room and slip pizza under the door to feed you. Nope four of my classes have group projects worth up to 40% of the grade. Now of course being new to ASU even though somewhere between a freshman and junior I feel out of touch already. Some already know others in the classes and most likely have teams picked out before the classes started.
I guess I had thought or more going information assurance and CSE with some telecom and becoming self employed at the end even if not highly paid. Some nice little niche to get away from the corporate grind. Now I hope to make it through the next weeks. It feels now as if my niche will not fit in. I need to go to the Intel, Microsoft, and Google dream of teamwork.
I know mostly rant on my first post. ;) Maybe things will look better by Friday.
just seems I will have to rethink if what I was looking for actually fits in.

Friday, August 20, 2010

Links from today's class plus *Thinking Cap* Questions (that you should respond to if you can)

It is equally relevant to any university..

Questions from the class that you can comment on (comment on all or some or none. If you have nothing to say this time, I am sure you will have opportunities later in the semester. I would only be worried if you never had anything to say... The following link from Love and Death has some insightful comments on the quantity vs. quality tradeoff: expounded in the context of a slightly different situation (start at min 3:30)

1. What is i^i  

2. If we have access to a program that tests a sequence of numbers to see if they are sorted or not (and returns yes if they are and no if they aren't), we can use it to *make* a sequence sorted by 
       Generate each permutation of the sequence
       Test if the sequence is sorted; if it is, exit loop and return the sequence
   end Loop

What do you think of this as a sorting algorithm?

3. What is the "famous" CS theorem that someone claimed to have proved recently and why is that theorem famous to begin with?


[ASU101] Blog Introductions (Response on blog required)


 Each of you should "comment" on the following blog message and write your introductions 

1. Your name
2. Why you chose CS or Computer Systems major
3. What ares of CS/Computer systems seem to be of particular interest to you right now
4. Something interesting about yourself


ps: This message is going both as an email to you and will be archived on the blog. Your responses have to be entered on the blog. 

Wednesday, August 18, 2010

Welcome to the ASU 101 Fall 2010 (Rao's section) Blog


 This is a generic welcome message. A more emotional, no holds-barred,  full-throated welcome shall be given in class come Friday ;-)