What is an algorithm
A set of unambiguous instructions for solving a problem or subproblem in a finite amount of time using a finite amount of data
List the four steps in Polya's "How To Solve It List".
Understanding the problem, devising a plan, carrying out the plan & Looking Back
Computer Problem-Solving
Algorithm Development Phase
Develop algorithm
Test algorithm
Implementation Phase
Code algorithm
Test algorithm
Maintenance Phase
Use
Maintain
Abstract Step
An algorithmic step containing unspecified details
How do you solve problems?
Understand the problem
Devise a plan
Carry out the plan
Look back
Implementation Phase
Code algorithm
Test algorithm
Maintenance Phase
Use Maintain
Methodology
Analyze the Problem
Understand the problem!!
Develop a plan of attack
List the Main Tasks (becomes Main Module)
Restate problem as a list of tasks (modules)
Give each task a name
Write the Remaining Modules
Restate each abstract module as a list of tasks
Concrete Step
An algorithm step in which all details are specified
Algorithm Development Phase
Develop algorithm
Test algorithm
Two methodologies used to develop computer solutions to a problem
Top-down design focuses on the tasks to be done
Object-oriented design focuses on the data involved in the solution
Control structure
An instruction that determines the order in which other instructions in a program are executed
Binary search (list must be sorted)
Search begins at the middle and finds the item or eliminates half of the unexamined items; process is repeated on the half where the item might be "say that again...
Sorting
Arranging items in a collection so that there is an ordering on one (or more) of the fields in the items
Sorting algorithms
Algorithms that order the items in the collection based on the sort key
Sequential search
search begins at the beginning of the list and continues until the item is found or the entire list has been searched
Sort Key
The field (or fields) on which the ordering is based
Bubble Sort
A sort in which the first two items to be sorted are examined and exchanged if necessary to place them in the specified order; the second item is then compared with the third (exchanging them if required), the third is compared with the fourth, and the pr
Insertion Sort
A sorting algorithm that sequentially removes an item from a list and adds it back to the list in the appropriate position relative to the previous items in the list.
Selection Sort
A sort in which the items in a set are examined to find an item that
fits specified criteria. This item is appended to the sorted set and
removed from further consideration, and the process is repeated until
all items are in the sorted set. See also the d
Subprogram Statements
A statement that represents a section of code in another part of the program
Recursion
The ability of a subprogram to call itself
Base case
The case to which we have an answer
, a simple case that can be solved easily, without recursion.
The case to which we have an answer
General case
the case in a recursive definition in which a smaller version of itself is called; recursive case.
The case that expresses the solution in terms of a call to itself with a smaller version of the problem
Quicksort
a divide-and-conquer sorting algorithm that works by partitioning its input's elements according to their value relative to some preselected element. Noted
Information Hiding
The practice of hiding the details of a module with the goal of controlling access to it
Abstraction
A model of a complex system that includes only the details essential to the viewer
Information Hiding and Abstraction are two sides of the same coin
Data abstraction
The separation of the logical view of data from its implementation
Control abstraction
Separation of the logical view of a control structure from its implementation
Why is information hiding important?
Information hiding defers details until the level where the details are important. This process keeps an algorithm from being dependent on the implementation details, which may change.
Procedural abstraction
Separation of the logical view of actions from their implementation
Write a top-down design for sorting a list of names into alphabetical order.
WHILE input names
Scan list for name closest to beginning of the alphabet
Copy name to new list
delete name off original list
write names back onto original list
Differentiate between a concrete step and an abstract step.
An abstract step is one in which further development is needed. A concrete step is one in which all the steps are fully specified
Describe the steps in the maintenance phase
Program and modifying the program to add functionality or correct errors
Describe the steps in the implementation phase
Coding and testing
What does it mean when we say that a computer is a programmable device?
This means that data and instructions are logically the same and are stored in the same place. The consequence of this fact is that the program the computer executes is not wired into the hardware but entered from outside.
Describe the top-down design process
the process is characterized by successive layers of refinement. The top-level tasks are listed. At each succeeding level, the tasks from the previous one are further developed.
Describe the steps in the algorithm development phase
Understand the problem, propose a solution, and test the algorithm.
List the three phases of the computer problem-solving model.
Algorithm development phase, Implementation phase & Maintenance phase
five operations of machine language
Store, retrieve, and process data, to input data and to output data.
How many low-level tasks can each machine language instruction perform?
One low-level task
What is a virtual machine?
Discuss this definition in terms of the Pep/8 computer. A hypothetical machine designed to illustrate important features of a real computer. The Pep/8 computer is a virtual machine designed to illustrate the features of the von Neumann architecture. It ha
Distinguish between the IR (instruction register) and the PC (program counter).
IR contains an instruction "the one being executed". PC contains an address "the address of the next instruction to be executed".
Distinguish between the Pep/8 menu options Assemble, Load, and Execute (run).
Assemble translates the assembly language program into machine code. Load puts the program into memory ready to be executed. Execute executes the loaded program.
What are the constructs that pseudocode must be able to express?
Variables, assignment, input/output, repetition, selection ex. "if then, if then else
Machine language
The language made up of binary coded instructions built into the hardware of a particular computer and used directly by the computer
Distinguish between the looping construct and the selection construct.
Looping repeats an action or actions while a condition is true. A selection determines if a condition is true and does one thing if it is and another thing if it is not.
Computer
A programmable electronic device that can store, retrieve, and process data
Characteristics of machine language:
Every processor type has its own set of specific machine instructions
The relationship between the processor and the instructions it can carry out is completely integrated
Each machine-language instruction does only one very low-level task
Virtual computer
A hypothetical machine designed to contain the important features of a real computer that we want to illustrate
Features in Pep/8
Pep/8 Registers/Status Bits Covered
The program counter (PC) (contains the address of the next instruction to be executed)
The instruction register (IR) (contains a copy of the instruction being executed)
The accumulator (A register)
The memory unit is
Operation code
Specifies which instruction is to be carried out
Pep/8
A virtual computer designed by Stanley Warford that has 39 machine-language instructions
Register specifier
Specifies which register is to be used (only use A in this chapter)
Pep8/Simulator
A program that behaves just like the Pep/8 virtual machine behaves
To run a program
Enter the hexadecimal code, byte by byte with blanks between each
Assembly language
A language that uses mnemonic codes to represent machine-language instructions
Addressing-mode specifier
Says how to interpret the operand part of the instruction
Assembler
A program that reads each of the instructions in mnemonic form and translates it into the machine-language equivalent
Pseudocode
A mixture of English and formatting to make the steps in an algorithm explicit
Input
Getting values from the outside word and storing them into variables
Get, Read
Output
Printing a value on an output device
Write, Print
Selection
Making a choice to execute or skip a statement (or group of statements)
Read number
IF (number < 0)
Write number + " is less than zero."
or
Write "Enter a positive number."
Read number
IF(number < 0)
Write number + " is less than zero."
Write "You didn't
Test plan
A document that specifies how many times and with what data the program must be run in order to thoroughly test it
Code coverage
An approach that designs test cases by looking at the code
Testing Programs
All programs must be tested; code coverage testing and data coverage (black-box testing) two common approaches
Repetition
Repeating a series of statements
Set count to 1
WHILE ( count < 10)
Write "Enter an integer number"
Read aNumber
Write "You entered " + aNumber
Set count to count + 1
Test plan implementation
Using the test cases outlined in the test plan to verify that the program outputs the predicted results
Operations of a Computer
Computer can store, retrieve, and process data
Machine Language
A set of instructions the machine's hardware is built to recognize and execute
Data coverage
An approach that designs test cases by looking at the allowable data values
Machine-language Programs
Written by entering a series of these instructions in binary form
Pep/8 Assembly Language
A language that permits the user to enter mnemonic codes for each instruction rather than binary numbers
Pep/8 One Register (A) and two-part instructions
One part tells which action the instruction performs; the other part details where the data to be used can be found
Pseudocode
Shorthand-type language people use to express algorithms