Course Introduction

These notes are (obviously) not slickly-designed for presentations. They are intended primarily as notes for myself, as well as an outline of class material for students. These are typical of the notes for the course, although I use PowerPoint slides for some topics.

The beginning and end of topics will not necessarily correspond to the beginning and end of class periods.

Course pragmatics

• Notes, assignments, exams — home page. First assignment will be posted soon — due the 15th.
• Staff, office hours, textbook, policies, etc. — info page.
• Mailing list — You'll be signed up automatically this week.
• Browser & fonts (Part of that page hasn't been working, so see also this page.)
• Students come in with diverse backgrounds. There are some pieces of math background that the occasional student hasn't seen (e.g., binary numbers, set theory). The course starts with some basics, but moves fairly quickly. Please ask questions if/when I go too quickly.

What is this course?

See syllabus on home page.

• Logic
  • Foundation of modern computers — digital logic circuitry
  • Central to writing & understanding programs
    • Program control flow — conditional branching
    • Fundamental to definition of programming language — formal semantics
    • Interface specifications
    • Database queries
    • Testing program correctness
      • Individual tests (very simple application)
      • Test coverage analysis
      • Assertions
    • Proving program & algorithm (partial) correctness, by hand or by tools
      • Code refactoring & Code optimization — does it apply to this code? is new code equivalent to old?
      • Static analysis — Type checking, FindBugs (Java), FxCop/Visual Studio (from Microsoft), DoubleCheck (C/C++) (from Green Hills Software, a consistent Rice recruiter)
      • Communicating threads/processes
      • New networking protocols
      • New algorithms
    • … and this is just a small sampling!
  • Using logic is similar to writing a program.
  • Writing proofs is just a more formalized version of creating a convincing argument. Very useful life skill. Grading will be based on not only having the correct answer, but also how you arrived at this answer and how it is presented.
• Sets, functions, …
  • Should be somewhat familiar already.
  • Will use to describe data. E.g., how are sets useful in describing data in your program?
• Arithmetic math -- some useful numeric math not typically taught in previous "math" courses.
  • Includes formalizing O()-notation mentioned in intro COMP courses
  • Includes math for understanding the bounded-size integers often used in CS. Also useful for things like cryptography.

Overall -- How to really understand your programs

Logic — Fun example

A "proof" of 90=100:

	Line #	Conclusion	Reason	Using line #s
	1	|AB| = |ED|	Construction
	2	|BC| = |EC|	C is on the perp. bisector of BE. (BEC is isosceles.)
	3	∠CBE ≅ ∠BEC	Base angles of isoceles BEC are congruent.
	4	|∠CBE| = |∠BEC|	Congruent angles have equal measure.	3
	5	|AC| = |DC|	C is on the perp. bisector of AD. (ADC is isosceles.)
	6	△ABC ≅ △DEC	Side-side-side	1, 2, 5
	7	∠ABC ≅ ∠DEC	Corresponding angles of congruent triangles are congruent.	6
	8	|∠ABC| = |∠DEC|	Congruent angles have equal measure.	7
	9	|∠ABC| - |∠CBE| = |∠DEC| - |∠BEC|	Algebra	4, 8
	10	|∠ABE| = |∠DEB|	Construction	9
	11	90 = 100	Construction	10

Sure seems convincing, but clearly wrong. Being careful and picky is important. If you didn't already know 90≠100, would you be suspicious of this "proof"?

1. Previous "math" courses concentrated on proving various interesting facts.
2. We will first concentrate on the form of proofs. This emphasizes how to avoid making wrong steps in proofs.
3. The rest of the course concentrates on some interesting things to prove in CS.

Summary of "to do's"

• Buy textbook.
• Find the bug in 90=100 proof. (If it wasn't already described in class.)
• Prepare your browser for MathML.
• Take the learning styles questionnaire below.

An Aside: Learning Styles Questionnaire

• Try this questionnaire.
• FYI, my results, having taken it three times:
  • REF 7 -- I generally think about things, before or instead of doing.
  • SEN 1 -- fairly evenly balanced between sensory vs. intuitive
  • VIS 9 or 11 -- very visual, not very verbal
  • SEQ 9 or 7 or 5 -- more detail-oriented than big-picture-oriented
• Knowing your learning style helps you understand yourself better. Knowing my learning style helps you understand my biases in how I teach.