Computer Science 2 Overview

Overview

Software Engineering

Data Structures

Collections

Abstract Data Types

Algorithm Analysis

Software Engineering

The discipline devoted to the design, production, and maintenance of computer programs that are developed on time and within cost estimates, using tools that help to manage the size and complexity of the resulting software products.

SE includes supporting activities such as

• cost estimation
• documentation
• team organization
• use of tools

The Software Life Cycle

• Problem analysis
• Requirements elicitation
• Software specification
• High- and low-level design
• Implementation
• Testing and Verification
• Delivery
• Operation
• Maintenance

The Waterfall Life-Cycle model

The Spiral Life-Cycle Model

The Agile Manifesto

We are uncovering better ways of developing software by doing it and helping others do it.

Through this work we have come to value:

• Individuals and interactions over processes and tools
• Working software over comprehensive documentation
• Customer collaboration over contract negotiation
• Responding to change over following a plan

That is, while there is value in the items on the right, we value the items on the left more.

Goals of Quality Software

Regardless of approach!

• Complete: it does everything specified
• Correct: it does everything right
• Usable: the interface is easy to work with
• Efficient: the solution and performance is as efficient as it needs to be (especially with all potential data sizes)
• Modifiable: the software can be upgraded easily
• Reusable: the software is developed in a manner that parts can be used in other settings
• Finished within budget and time constraints

Development Toolboxes

Hardware—the computers and their peripheral devices

Software—operating systems, editors, compilers, interpreters, debugging systems, test-data generators, and so on

Ideaware

• Algorithms
• Data structures
• Programming methodologies

Design aids

• CRC cards
• Unified Modeling Language
• Scenarios

Software Concepts

• Information hiding
• Data encapsulating
• Abstraction
• Object oriented

Recommended Program Specification

• Processing requirements
• Sample inputs with expected outputs
• Assumptions
• Definition of terms
• A test plan

Detailed Program Specification

• Tells what the program must do, but not how it does it.
• Is written documentation about the program.

Stepwise Refinement

A problem is approached in stages. Similar steps are followed during each stage, with the only difference being the level of detail involved. Some variations:

• Top-down
• Bottom-up
• Functional decomposition
• Round-trip gestalt design
• Visual Aids—CRC cards

A Quick Review of Object-Oriented Programming

Three inter-related constructs: classes, objects, and inheritance

• Objects are the basic run-time entities in an object-oriented system. Objects have different values or state.
• A class defines the common structure of its objects. There may be many objects from a class.
• A class can be built upon another class in an “is-a” hierarchy defined by inheritance.

Objects represent

• information: we say the objects have attributes
• behavior: we say the objects have responsibilities

Objects can represent “real-world” entities such as bank accounts as well as abstract entities such as a particular organization of objects.

Objects well-designed are self-contained and therefore easy to implement, modify, and test for correctness.

Object-oriented classes, when designed properly, are very easy to reuse.

Data Structures

Data structures is the common name for this level of course.

• Study the structures in which data can be organized
• Data structures can be studied independent of the language (abstraction)
• Data structures are mathematical in nature
• Analysis is mathematically based
• Reason for MA 115 "Discrete Structures" as a prerequisite

Most languages support primitive data structures:

• arrays (homogeneous aggregate),
• records (heterogeneous aggregate) and
• primitives for relating together objects and other data structures such as pointers or object references

Modern languages such as Java provide modules or packages in support of more complex data structures

CS 240 is not about how to train you to necessarily reinvent these structures when you need them, but for you to know how to use the right structures at the right time.

Abstract Data Types

Abstractions are a theme in this course and in programming:

• Programs are abstractions:
• Collections are an abstraction of data organization
• Functions are an abstraction of computation
• Classes are an abstraction of objects

ADTs give the ability to define new types along with the operations appropriate for that type. 

Collect operations in one place with the definitions (encapsulation). 

The abstract definitions are independent of implementation (information hiding).

ADTs with encapsulation and Information Hiding are implemented in Java classes.

Collections

"Collections" is another term for data structures. Collections are sets of data, multiple values, that are organized and related in some manner.

Typically the data types (integers, floats, strings) or objects within the collection are the same.

Linear collections

• data is ordered by position
• each item has a predecessor, except the first
• each item has a successor, except the last
• there are variations on the accessibility of linear collections
• The facts that B follows A, C follows B, etc. and that D is between C and E has meaning and is information

Hierarchical collections

• each item has exactly one predecessor, except the root
• upside down tree
• B and E are directly related to A, C and D to B, etc.

Graphs

• each item may be related to one or more other items
• A is relateld to B and E but the converse doesn't hold, etc.

Unordered collections

• items are not related in any manner; position doesn't matter
• there are no relationships among the items

Operations on Collections

• Search and retrieval-- return a position value (address or counter), or a code (null) that the search was unsuccessful
• Removal or deletion -- return a success flag (i.e., it was there or not)
• Insertion -- may need to provide position of insertion; also consider whether duplicate values are permitted
• Replacement or update -- change a value in the collection
• Traversal -- want to visit or process every element in the collection; some order may be required
• Test for equality -- if items can be equal then collections can be tested for equality (items and positions are the same)
• Size of collection
• Cloning -- need to make a full copy of the collection

What are costs for each of these operations?  That is the analysis part of the course.

Algorithm Analysis

There are multiple solutions to a given problem.  

• How do we know what solution may be best?

• What defines best?  Speed? Space? Clarity? Simplicity?

• Time efficiency -- the primary gauge

• Space efficiency -- no longer as critical (as in the days of 16K memory)

Time efficiency 

• We will be interested in what happens to an algorithm when the amount of data it process grows large.

• Linear growth to the data size

• Quadratic growth

• Exponential

• Logarithmic

Algorithm Types

• Greedy -- processing proceeds with the easiest next step, e.g., take the next item in the collection

• Divide-and-conquer -- cut the data into parts and process the parts (fast sorting does this)

• Backtracking -- try solution and if fail go back to a decision point and try again (fill a figure with a color)

• (other examples are in the text)