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.

cheers

Rao

a recent CACM article on career opportunities for CS majors

..is attached. makes promising reading..

rao

(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. 

cheers

Rao

(reply to this mail) Attendance assessment

Folks:

 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:  http://rakaposhi.eas.asu.edu/asu101 )

regards

Rao

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

Folks:

 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).

Rao

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). 

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

Folks

 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.

regards

Rao

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

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

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

 

Yann-Hang

(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

e-mail: ron.askin@asu.edu

Phone: 480-965-2567

http://engineering.asu.edu

*****************************************************

 

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 30^th and is featured in the community.asu.edu website. He did a fantastic job and we thought that you might be interested in seeing the video. http://community.asu.edu/exchange/2010/10/ignite-asu-a-recipe-for-change/

 

Best,

 

Regina Duran

Social Embeddedness Intern

Office of University Initiatives

Arizona State University

 

Agenda for today and the next two classes..

Folks

 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 ;-)

Rao

Results of class survey

Folks:

 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

http://rakaposhi.eas.asu.edu/asu101/survey-f10.pdf

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.

regards

Rao

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:

http://computingcareers.acm.org/

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 :->)  http://www.youtube.com/watch?v=yUTgCACDuUA&feature=related

Pathways in Computer Science (talks about careers that you may not have thought of ):  http://www.youtube.com/watch?v=RENVVTNsVHg&feature=related

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

Rao

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)

Article:  http://www.cs.cmu.edu/afs/cs/usr/wing/www/publications/Wing06.pdf 

Slides (in pdf): http://www.cs.cmu.edu/afs/cs/usr/wing/www/Computational_Thinking.pdf

Video (on youtube; 65min):  http://www.youtube.com/watch?v=C2Pq4N-iE4I

cheers

Rao

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:

http://www.youtube.com/watch?v=piWCBOsJr-w

Rao

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

                   ~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? 

                

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: http://en.wikipedia.org/wiki/Boolean_satisfiability_problem )

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

Rao

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)

man(SOCRATES)

The "theorem" you want to prove is

dies(SOCRATES)

==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).

regards

Rao

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 

Undergraduate Research Opportunities (and CSE Clubs)

http://engineering.asu.edu/furi  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:

http://www.nsf.gov/funding/pgm_summ.jsp?pims_id=5517&from=fund

Here are links to CSE related student clubs:

The most active one seems to be women in Computer Science:  http://wcs.asu.edu/blog/

Others include OS-specific interest groups such as Linux Users group http://asulug.org/ (there is one for macs and pcs too)

rao

Engineering Tutoring Center (focusing on non-CSE courses)

http://engineering.asu.edu/students/tutoringcenter

rao

Fwd: Tutoring available for CSE 100, 110, 205

---------- Forwarded message ----------
From: Yann-Hang Lee <yhlee@asu.edu>
Date: Tue, Aug 31, 2010 at 6:16 PM
Subject: FW: Tutoring available for CSE 100, 110, 205
To: CSEFaculty@asu.edu
Cc: Fred Morstatter <fmorstat@asu.edu>, Manuel Aroz <maroz@asu.edu>

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.

 

Yann-Hang

(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:

 

http://courses.eas.asu.edu/cse205/current/tutorSchedule.html

 

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

 

 

 

CIDSE ACADEMIC ADVISING CENTER

 

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

 

  

 

 

 

 

 

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

Folks:

 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. 

rao

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..)   http://en.wikipedia.org/wiki/Bogosort 

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 http://en.wikipedia.org/wiki/Stirling's_approximation

honors students in ASU101 section..

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

Rao

[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?

Rao

Milo, the virtual boy

Found this:

http://www.ted.com/talks/lang/eng/peter_molyneux_demos_milo_the_virtual_boy.html

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.

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

The "Harvard Guide to Happiness"   http://www.physics.ohio-state.edu/~wilkins/physics/College-happiness.html

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 

  

   Loop

       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?

regards

Rao

[ASU101] Blog Introductions (Response on blog required)

Folks:

 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

regards

Rao

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. 

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

Folks:

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

Rao