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