SUNY Geneseo Department of Computer Science

Conditionals and Logic

Previous Lecture

Misc

I'm out of town Thursday (1/29)

• Attend "town meeting" on plagiarism for extra credit instead of coming to regular class
• 12:45 - 1:50, Milne 104

Questions?

Reading Summary

Sections 5.1 - 5.5

Conditionals are how to use logic

Boolean logic

Logic operators

• Conjunction
• Disjunction (inclusive or exclusive)
• Negation
• Implication

Law of excluded middle

• "No maybe" -- propositions are true or false

Manipulating expressions

• Double negation
• Commutativity
• Associativity
• de Morgan's law
• Distributive laws

Proof by case

• Divide possibilities into cases (e.g., satisfy assumption and don't)
• Prove result for each case

Execution time

• Average execution time, but hard to do without more information
• Bounding execution time
  • Upper bound (worst case)
  • Lower bound (best case)
• Worst case more common, want to know worst possible time
• Time analysis describes time as function of problem size.
• Best and worst cases may be close, and so tell expected time well
• Expected time hardly ever measured in terms of lines of code, rather in terms of problem size
  • Time depends not on how many lines there are but on how many times they're executed e.g.,

            for ( i = 0; i < 1000000000;   i++ ) {
                a[i] = 0;
            }

Logic Examples

Determine whether a point (x,y,z) lies inside a cylinder (from computer graphics)

    if (    y >= 0
         && y <= h
         && x*x + z*z <= r*r )

Determine if point is outside the cylinder

    if (    y < 0
         || y > h
         || x*x + y*y > r*r	)

Make a robot move forward until it either comes to a wall or a red tile

    // not (robot at wall or a red tile)
    while (    robot.okToMove()
            && robot.colorOfTile() != Color.red ) {
        robot.move();
    }

Move at least 3 tiles, then continue until a wall or red tile

• Logic: loop while robot hasn't moved 3 tiles yet or ( no wall or red tiles )

    int tiles = 0;
    while (    tiles < 3
            || (    robot.okToMove() 
                 && robot.colorOfTile() != Color.red )	) {
        robot.move();
        tiles = tiles + 1;
    }

• Or, another idea (but this moves robot in groups of 3 steps at a time)

    do {
        move
        move
        move
    } while( not red and not wall)

Digression: Why Robot.NORTH instead of NORTH or Color.red instead of red?

• Those constants are static members of the Robot or Color classes
• Java's rule for naming static things:

    Class . Name

Database application

• Database is made of records
• Records contain fields
• Queries are boolean combinations of tests involving field values
• e.g., imagine a database version of my schedule/calendar
  • Record = appointment
  • Fields =...
    • Date
    • Day of Week
    • Start Time
    • End Time
    • Description
    • ... etc ...
  • This class meeting might be
    • Date = Jan. 27, 2004
    • Day of Week = Tuesday
    • Start Time = 2:00 PM
    • End Time = 3:15 PM
    • Description = "CSci 141"
  • Query might be
    • Find records with
      • (Day of Week = Tuesday
      • or Day of Week = Thursday)
      • and Description = "CSci 141"
    • (i.e., find all the lecture meetings of this course)
• How about "find all appointments that conflict with any meeting of this course"
  • Find records with
    • ( Day of Week = Monday
      • and ( ( Start Time > 10:30
        • and Start Time < 12:20 )
        • or ( Start Time > 1:30
          • and Start Time < 3:20 ) )
        • or ( ... same for end time ... )
    • or ( (Day of Week = Tuesday
      • or Day of Week = Thursday)
      • and ( ... start time and end time as above ... )

Proof by Case

Where have you seen it recently?

Northeast corner algorithm

Next

Introduction to Recursion

Read Section 6.1

Next Lecture