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