CIS 3020 Part 1

Introduction to CIS

Introduction to:

• The art and science of programming
• The fundamentals of computer science
• The basic concepts of Object Orientation:
  • Abstraction - representing the key features
  • Polymorphism - "many forms"
  • Inheritance - reuse of existing code from ancestors
  • Encapsulation - containing and controlling access to

What this course entails

• This course is not a Java programming course
• "Introduction" does not mean "easy"
• Prior programming experience is strongly recommended
  • in none, take CIS 3022/3023
• This course moves quickly, so attempt assignments early
• Don't get discouraged if you feel confused after one week of class. You hopefull will feel more comfortable by the 3rd week.

Philosophy

• Goal is to learn fundamental principles of programming and obtain an overview of the field of computer science.
• This goal is independant of any language
• Java is used to make these principles concrete but "learning Java" is not the primary goal of the course.
• We will not cover most or all of Java.
• We will teach the basics with emphasis on thinking and analysis.

Class Web Page

WebCT/Vista
Douglas Denkel's Homepage

• Announcements, homework assignments, etc. will be posted here.
• You are responsible to be aware of what information is there.
• Check it frequently -- no less than every other day!

Lecture Notes

• Copies of the lecture slides are available in the Lectures folder in WebCT/Vista
• These slides do NOT contain everything on my slides to encourage you to come to class.
• You are strongly encouraged to print a copy of these notes.
• Having a copy will make taking notes significantly easier!

Grading

Option 1 15% 20% 30% - 20% 15%

Option 2 15% 15% 15% 20% 20% 15%

Examination 1 Examination 2 Examination 3 Final Pop quizzes and in class exercises Group/Ind Homework Assignments

What to Expect

• Difficulty: This course has had a drop rate as high as 33%
• Effort Required: Expect to spend a minimum of 10 hours/week
• Intended for: Those needing a firm foundation in CS principles (majors)
• Education Value: Understanding the vocabulary of CS and concepts of OOP (Object-Oriented Programming)

Necessary Skills

• Helpful to know Java, but not a requirement
• Prior programming experience is helpful
• Willingness to work outside of class
• Willingness to work in groups
• Self discipline
• Ability to tolerate frustration
• Ability to switch between high and low level views
• Ability to think abstractly
• Ability to see what is actually there:

       This is the
       the answer

• • The computer executes exactly what you give it
  • The ability to see the duplicate "the" can greatly help in debugging code

Self Test

If (a<b) then x=a & y=b otherwise x=b & y=a z=0 if (x<=0) goto step 7 z=z+y x=x-1 goto step 3 print z

What did the author of this algorithm intend for it to do? For what values of a & b does the algorithm work as intended? How many times is step 3 executed?

Should I stay?

• If you found the self test to be easy or not difficult in spite of no prior programming experience, then this course should not be too difficult for you.

What is Computer Science?

"...the science of abstraction - creating the right model for a problem and devising the appropriate mechanizable techniques to solve it"
       - Aho and Ullman

• Not the "science of computers"
• The study of computation:
  • Systems that produce the solutions
  • Methods used to develop solution strategies for these systems to follow
  • Application areas in which automated problem solving is useful

Foundations (COT 3100)

• Formal mathematical structures forming the basis of Computer Science
• Questions:
  • What types of problems can be solved.
  • What syntax and semantics
  • Meaure complexity -- How?
  • How to verify correctness

Algorithms & Data (COP 3530)

• Structures for representing data
  • Space complexity
• Fundamental and basic algorithms for manipulating these structures
  • Time complexity
• Advantages and disadvantages of representations
• Tradeoffs between space and time

Systems

• Architecture (CDA 3101)
  • Organization and structure of hardware
  • Design of computing hardware
• Operating Systems (COP 4600)
  • Design of resource management software
  • Management of disks, memory, processors...
• Networking (COP 4500C)
  • Connecting machines together to share resources
  • Highly related to operating systems

Applications

• Artificial Intelligence (CAP 4621)
  • Attacking problems viewed as requiring "human intelligence"
• Database Management (COP 4720)
  • Organizing large quantities of data so items can be easily extracted
• Graphics (CAP 4730)
  • Rendering

Methods

Design and assessment of techniques and software tools for creating solutions

• What is required within a programming language? (COP 4620 - Translators)
• What methods are required for producing and evaluating software? (CEN 3031 - Introduction to Software Engineering)

Changing Face of Computer Science

Through the years, computer science has seen many changes:

• 1950's: Expensive hardware, programming in machine and assembly language.
• 1960's: Development of imperative languages
• 1970's: Decreasing hardware cost, microprocessors, introduction of software engineering, and rising programming costs.
• 1980's: Personal computers, object oriented programming.
• 1990's: Visual languages.

Shift in Emphasis

• 1950's: How computers are designed
• 1970's: Higher level languages
• 1990's: Problem modeling

What is a computer?

Types of Computers

• Representation of information: Digital or analog
• Execution: Synchronous or asynchronous
• Composition: Biological, electronic, optical, quantum

What is a computer?

• CPU: Where all the calculation are performed
• I/O: Allow communication with outside world
• Memory: Stores program and data

Numbering system

Decimal Numbers

• We use base 10
• 10 unique glyphs - digits 0 through 9
• Meaning of a number is based on the symbols used and their position
  • 123 = 1x10^2 + 2x10^1 + 3x10^0

Binary Numbers

• Computers use Base 2
• 2 unique glyphs - 0 and 1
• Meaning of a number is based on the symbols used and their position
  • 1011 = 1x2^3 + 0x2^2 + 1x2^1 + 1x2^0
• A single digit binary number is called a bit
• 8 bits = byte and 4 bits = nibble
• Number of bits determines how many symbols can be represented
• These symbols might represent numbers, letters, instructions, etc.
  • ASCII (American Standard Code for Information Exchange) uses 7 bits
  • Unicode uses 16 bits

Units of Storage

Unit	Symbol	Size
Byte		8 bits
Kilobyte	KB	2^10 = 1024 bytes
Megabyte	MB	2^20 = 1048576 bytes
Gigabyte	GB	2^30 = 1,073,741,824 bytes
Terabyte	TB	2^40 bytes

Main Memory

Series of memory locations. In each location is data, instructions or garbage. Somve values are stored in consecutive locations. Can be read (non-destructive) or writte (destructive).

CPU Components (Simplified)

• ALU (Arithmatic and Logic Unit) - Performs specified operations on information stored in the registers
• Control Unit
  • Determines what operations should be performed
  • Controls transfer of information between the ALU and registers
• Registers
  • Program Counter: Holds address of next instruction
  • Instruction Register: Holds current instruction
  • General Purpose Registers: Store results of arithmatic calculations

Fetch-Decode-Execute Cycle

1. Fetch: Get instruction at address in Program Counter (PC). Load it into Instruction Register (IR).
2. Increment: Increment the program counter.
3. Decode: Decode the instruction.
4. Execute: Activate the circuitry in ALU to perform instruction.
5. Repeat.

Programming

Properties of High Level Languages (HLL)

• Tend to look like English
• Easier to express ideas in HLL
• Easier to understand than programs in machine/assembly language
• Support Abstraction
• HLL Code is more platform independent than machine/assembly language
• HLL Code cannot be executed directly

Compiler

• Translates a program (written in a particular programming language) into a target language (usually machine or assembly)
• Often the target language is a machine language but sometimes is another HLL

SNOBOL -> C -> Machine language

• This translation is performed once - the result can be executed many times

Program P in Language L -> Compiler -> P', an equivalent program in machine language

Interpreter

• Translates a program written in a particular language
• Translation is performed while the program is executing
• Each time a statement is encountered it is re-interpreted
• Execution is typically slower than with compiled code
• Eliminates the need for a seperate compilation phase
• Can make program development easier
• Interpreter is easier to write than compiler

Java Design Goal

• Platform independence
• "Write once, run anywhere"
• Solution 1: (not used)
  • Distribute source code and let end-user compile on their machine
  • Pro: Is platform independent
  • Cons:
    • Reveals intellectual property/trade secrets
    • Source code is bulky
    • Recipient is forced to compile or interpret
• Solution 2: (used)
  • Use both interpreter and compiler
  • Pro:
    • Platform independent
    • Source is not distributed
    • Code is compact
    • Code can be executed fairly fast
  • Con:
    • Usually does not run as fast as compiled code

Java

• Java source code is compiled into instructions called java byte code, designed for a Java Virtual Machine (JVM)
• This byte code is interpreted by a JVM - a simulator
• Provides better performance than a typical interpreter because byte code is closer to machine language

What can be done with Java Byte Code?

• Interpret it with a program that acts like a CPU that uses the Java Virtual Machine instructions
• Translate it into machine code for a particular hardware CPU (JIT - Just In Time compilers)
• Execute it on a CPU designed to use JVM instructions (Java Chip)

Virtual Machines

• An emulated computer system or emulated ISA (Instruction Set Architecture)
• Can be software or hardware VM
• Software examples:
  • Pascal: Imperative language
    • Intermediate code called "P" code, byte code for "P" machine
  • LISP: Functional language
    • Both interpreted and compiled (native or byte)
  • Smalltalk: Object oriented language - interpreted or byte compiled.
• Hardware:
  • CISC: Complex instruction set computing
    • Instructions do a lot
    • Complex
  • RISC: Reduced instruction set computing
    • Very simple set of instructons
• Examples:
  • Pentium Pro: Looks like CISC, but was RISC
  • Pentium II, III, and IV
  • AMD K-5, K6, and K6-2

Abstraction

• Keep what is essential while discarding everything else
• What is essential depends on the context
• Cat:
  • Sound:
    • Meow, Hiss, purring
  • Visual:

Data Abstraction

• Use programming language construct to model information
  • Age: integer
  • Name: sequence of letters
  • Time: HH:MM or milliseconds since 1/1/1970
• Represent single conceptual entity
• Giving symbolic names to pieces of data
  • Done for communication:
    • "Call me at home" vs "Call me at 555-1235"
  • Facilitates communication

Procedural Abstraction

• Capture and name a computational process
• Allows us to state what not how
  • "Give me a call"
  • "Add the numbers three and seven" -- Use of arguments
• Allows hiding details of process
• We invoke a process through its' interface
• Allows us to reuse abstractions by building libraries

Programming Paradigms

Imperative

• Program consists of sequence of commands describing how to perform desired computational process
• Programmer describes how to do task
• Example: Brewing coffee

1. Gather coffee, filter, and water
2. Take ingredients to coffee maker
3. Put filter in basket
4. Put coffee in basket
5. Put basket in coffee maker
6. Add water to coffee maker
7. Put pot under basket
8. Turn on coffee maker

Declarative (Logic Programming)

• Given a set of facts, rules, and a goal
• Use inference engine to satisfy goal
• Programmer states what they want to do

Facts	Rules
mother (marge, lisa)	parent (X,Y) :- mother (X,Y)
father (homer, lisa)	parent (X,Y) :- father (X,Y)
father (abe, homer)	gparent (X,Z) :- parent (X,Y), parent (Y,Z)
mother (marge, bart)	Goal
father (homer, bart)	gparent (X, lisa)

Functional

• Emphasizes the evaluation of expressions, not the evaluation of commands
• Compute the sum of 1, 3, 7, and 9:
  • Imperative: 1+3+7+9
  • Functional: (+ 1 3 7 9)
• Program consists of functons built from simpler functions
• Encourages "black box" approach of modular programming in software engineering

Object Oriented

• Objects are responsible for performing computations
• The program is a collaborative effort between a set of specialized agents (objects), each with a well defined role
• The interaction between objects cause the computations to be performed
• Objects communicate by passing messages
• A message is given to an object to identify what it must do
• Message consists of:
  • What to do
  • What to do it with
• Recipient of a message must have ability to perform the required action
• Objects encapsulate (contain and control)
  • State: What the object knows
  • Behavior: What the object can do
• Every object is an instance of exactly one class
• State and behavior are defined by object's class
• All instances of a class respond similarly when their behavior is involved
• Objects exhibit behavior when you invoke them by sending them a message
• Try to reuse code whenever possible
• A good parallel to draw is to compare Object Oriented programming to building a house:
  • There are a large number of sub-contractors (objects) involved:
    • Plumbers
    • Carpenters
    • Dry wall installers
    • etc.
  • All of these are coordinated by the general contractor (the main program/procedure) who specifies what will be done when

Characteristics of Object Oriented Programming

These characteristics were first developed by Alan Kay.

A program consists of a set of objects

• Computation is performed through the interaction of the objects with each other
• The objects tell each other what to do through messages
• A message consists of:
  • A request
  • The data necessary to serice that request

When a program is executing, everything is an object

• The object stores data, and you can "make requests" of that object - ask it to perform operations on itself
• Note: Java violates this rule by having non-object "primitives": boolean, byte, short, int, long, double, float, and char

Each object has its own memory or state

• Consists of references to other objects (and/or primitives, in Java)
• The object encapsulates (contains/controls) the state

Each object is an instance of a single class

• A class is a grouping of objects having similar:
  • State
  • Behaviors - which the object also encapsulates

The class defines the state and behaviors

• All instances of a class perform the same actions - respond to the same set of messages
• Each instance behaves similarly, but not necessarily identically

Classes are organized into a single rooted inheritance hierarchy (or tree)

• States and behaviors associated with a particlar class are accessible to descendant classes

Unified Modeling Language

Graphical notation used to describe object-oriented software systems

Rules

• In computer science trees are drawn with the root at the top and leaves at the bottom
• As you move up the tree, you generalize
• As you move down you specialize
• Each class can define its own behaviors but also inherits the behaviors of its superclasses or ancestors
• In Java, all classes are derived from the class Object

Simple Program

class Program1 {
  public static void main(String[] arg) {
    // statements to execute
  }
}

• All programs consist of at least one class
• The start and end of a class definition are encapsulated in curly braces ( "{" and "}" )
• Line two above is a method that defines the driver program
• The start and end of the program are also encapsulated in curly braces
• Actual statements of the program go inside these braces
  • NOTE: The "//" is a comment, and comments are critical to understanding a program
• White space and carriage returns or line feeds (CRLF's) do not matter

The above is the same as:

class Program1 {Public static voide main(String[] arg){
//statements to execute
}}

Real Program

class RectangleDemo {
    public static void main (String[] arg) {
	//create an island and a turtle and associate them
	Island hawaii = new Island(400,400);
	Turtle tina = new Turtle();
	hawaii.putTurtleAtCenter(tina); //faces east
	//instruct turtle to draw rectangle
	tina.tailDown();
	tina.move(10.0);
	tina.turnLeft(90.0);
	tina.move(30.0);
	tina.turnLeft(90.0);
	tina.move(10.0);
	tina.turnLeft(90.0);
	tina.move(30.0);
    } //end main()
} //end class RectangleDemo

Terminology

• Operation:
  • Behavior which is invoked by a request
  • The abstract description of what is done
• Method:
  • A specific implementation of an operation
  • The actual code implementation
• Operation's signature consist of:
  • Name
  • Parameters
  • The returned value's type
• Interface:
  • A set of related operation signatures
• Type:
  • A named interface
• Object's Interface:
  • The set of all operations supported by that object
  • Defined by the class of which the object is an instance
• An object is an instance of a single class

Software Life Cycle

The Iterative Waterfall Model:

• Marketing - Requirements
• Analysis - Specifications
• Design - Architecture
• Implementation - Untested Software
• Testing - Product
• Maintenance

Any of the above can relegate the software back up the chain however many steps are necessary if something needs to be fixed that was not thought of before. The further up the chain the software needs to be relegated (number of hops) for a single problem, the larger the problem and the bigger the mistake in the first place.

Traditional Software Life Cycle costs

Phase	% of Effort
Requirements Definition	3%
Specification	15%
Implementation (Coding)	14%
Testing	8%
Maintenance	60%

Important Issues in the Real World

Note:

• Recent graduate working at Intel identified:
  • Six months spent on analysis and design
  • Two weeks for implementation
• Documentation is not mentioned
  • Is an on-going process
  • Occurs throughout the entire software lifecycle
• Software Prototyping
  • Don't develop the entire system at once
  • Develop a rough prototype that does not have complete functionality
  • Test this prototype with user to verify it meets all of the required specifications
  • Therefore, early changes can be made reducing modifications in the maintenance phase - saving time and cost.
• Maintenance
  • Code is continually being modified, rewritten, and improved.
  • Much of your effort will be in maintenance
  • Important to develop code that is:
    • Well structured
    • Readable
    • Well documented

Problem Solving Methodology

Analysis:

• Examine the problem statement (do you really know what you need to do?)
• Work the problem by hand with a simple set of data to verify you understand what needs to be done
• Describe the input, output, constraints, assumptions, and relationships

Design:

• Design a solution based upon the analysis

Implementation:

• Translate the design into code

Testing:

• Thoroughly test the solution with data
• Pay close attention to boundary cases

Analysis

Abstract from the problem statement the data and their relationships

• Read the problem statement CAREFULLY
• Identify:
  • Inputs: the data provided to solve the problem
  • Output(s): the desired solution to the problem
    • Return values (eg cash from ATM)
    • Side effects (eg change in account balance)
  • Constraints: requirements that limit the solution
  • Relationships: relationships between the inputs and outputs given the constraints (eg new balance = previous balance - withdrawn amount)
  • Assumptions: information not explicit in problem statement that were used to develop relationships - make as few as possible
• When reading the problem statement, underline the phrases that identify the inputs, outputs, and constraints

Example

Problem: Given the weight of a set of apples and the price per pound of apples, compute the price of those apples.

Underline the phrases identifying inputs, outputs, and constraints.

What are the inputs?	What are the constraints?	What are the outputs?
Weight of apples Price per pound of apples	None	Price of apples

What are the relationships? 

Abstractly phrased: Price = Weight X Price / Weight

Price of Apples = weight of apples X price per lb of apples

How do we identify relationships?

Look for an abstract relationship

Rephrase the problem's terminology

What are the assumptions?

The weight will be given in lbs

Design

• Once we have performed an analysis of the problem, we can construct a design
• Top Down Design/Analysis:
  • Decompose the problem into subproblems until each subproblem is trivial to solve
  • Note: A subproblem is a problem, therefore break it down into subproblems
• Example: Writing a term paper
  • Create a list of topics to cover
  • Take each topic in turn and outline it

Object Oriented Design

• Identify the existing class that apply to the domain
• Identify and reuse existing classes that can be adapted to the solution using:
  • Aggregation
    • Use one or more instances of class(es) working together to solve problem
    • example: make a cart from board, wheels, etc.
  • Inheritance
    • Create a specialized version of existing class
    • Add new behaviors and/or modify the state
• Write a new class from scratch
  • This is not preferred... don't reinvent the wheel!

UML - Revisited

• Unified Modeling Language
• Graphical notation used to describe object-oriented software system

Class Name
State (attributes)
Operations

Turtle Class

Turtle	Class Name
	Attributes of class
<<constructor>>	Operations of class
+ Turtle()	Used to create instance of class always has same name as class initializes the starting state of the instance
<<pen status>>	Stereotype: provides descriptive information
+ tailUp(): void
+ tailDown(): void
<<movement>>
+ move(Distance:double): void	UML Signature of an operation
<<orientation>>
+ faceEast(): void
+ turnLeft(Change:double): void	double is equivalent to real number
+ turnRight(Change:double): void

Problem

Display a picture consisting of a square with a side length of 75 units.

What is our first step?

underline phrases identifying inputs, outputs, and constraints

Analysis

In this problem, if we consider 75 as an input, we will produce a general solution, but if we consider it a constraint, we get a specific solution

What items must we identify in our analysis?
Inputs	Side Length
Outputs	Picture of a square
Constraints	Canvas must be large enough
Relationships	Square has the side length
Assumptions	None

Design

Assumption: We will use existing Turtle and Island classes to solve problem

Here we describe and detail our algorithm. A computational process typically decomposes into:

1. Initialization
2. Do the required work
3. Clean up

It is often helpful to try the task by hand to make sure you know what to do

Design of the Algorithm

1. Initialization
   1. Create an island
   2. Create a turtle
   3. Put the turtle on the island
2. Do the work: tell turtle to draw square
   1. Put down the tail
   2. Draw first side
      1. Move forward 75 units
   3. Draw second side
      1. Turn left
      2. Move forward 75 units
   4. Draw third side
      1. Turn left
      2. Move forward 75 units
   5. Draw fourth side
      1. Turn left
      2. Move forward 75 units
3. Cleanup
   1. Point in the starting direction
      1. Turn left
   2. Pick tail up

Note: Sometimes one or more of these steps will require refinement. Just repeat the Analysis & Design process for each of these.