Computer Science Test 3 (Chapters 7,8,9,10)

Polya’s How to Solve It List

List for problem-solving process

Simple type

non-composite data type

composite type

date type made up of multiple simple types

recursive problem

problem that can be solved by calling the same function

arrays

as data is being read into it, a counter is updated so that we always know how many data items were stored

List

if an array is called list we are working with:

list[0] to list[length-1] or

list[0]..list[length-1]

unsorted array

array without a specific order

sorted array

array with elements arranged in a specific order

selection sort

sorting algorithm that selects the smallest element and swaps it with the first unsorted element

insertion sort

sorting algorithm that inserts each element into its correct position in sorted subarray

quicksort algorithm

sorting algorithm that uses a splitting value to divide the array into smaller subarrays

binary search

search algorithm that finds the position of a target value in a sorted array

records

heterogeneous collection of items accessed by name

arrays

homogeneous collection of items accessed by index

subprogram

section of code with a name that can be called from another part of the program

recursion

ability of a subprogram to call itself

information hiding

practice of hiding module details to control access

abstraction

model of a complex system that includes only essential details

data abstraction

separation of logical view of data from implementation

procedural abstraction

separation of logical view of actions from implementation

control abstraction

separation of logical view of control structure from implementation

identifiers

names gives to data and actions

open-source software

software with source code that is freely available to the public

rosetta stone

key to translating ancient Egyptian hieroglyphs

National Intellectual Property Rights Coordination Center

organization warning about intellectual property rights violations

piggybacking

using someone else’s wireless network without permission

philosophy

study of fundamental questions about existence, knowledge, values, reason, and more

algorithm

a set of unambiguous instructions for solving a problem of subproblem in a finite amount of time using a finite amount of data

abstract step

an algorithmic step containing unspecified details

concrete step

an algorithm step in which all details are specified

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

The functionality of psuedocode

pseudocode serves as a bridge between human understanding and computer programming; allows developers and stakeholders to communicate and understand the logic of an algorithm without getting bogged down in specific programming language syntax

Is the statement “Enter temperature“ concrete or abstraction

it is abstract; it describes the action to be taken but doesn’t specify how the temperature is actually entered

Is “Read temperature“ concrete or abstract

concrete; it specifies a clear and specific action to be taken

Is “Determine Dress“ concrete or abstract

abstract; while it outlines the goal of the algorithm it does not provide specific details on how this determination is made

sequential search

examines each item in turn and compares it to the one we are searching for; if it matches, we have found the item; if not, we look at the next item in the array

abstract data type

a date type with specified properties and operations

abstraction

the most powerful tool for managing complexity

application level

view of data within a specific problem

logical level

abstract view of data and operations to manipulate them

implementation level

specific representation of data structure and operations in a programming language

composite data type

a named collection of data values

data structures

implementation of composite data fields in an abstract data type

containers

objects that hold and manipulated other objects

array-based implementation

container with objects kept in an array

linked-based implementation

container with objects not physically together, but linked

stack

abstract data type with LIFO access and push/pop operations

3 everyday stack structures

stack of books, stack of trays, stack of plates

queue

abstract data type with FIFO access and enqueue/dequeue operations

3 everyday structures that are queues

market checkout line, bus top line, print line

list

container of items with operations like add, remove, get next, and check for more items

trees

structures such as lists, stacks, and queues are linear in nature; only one relationship is being modeled

3 complex relationships

Graphs, trees, databases

binary tree

linked container with a root and each node having two child nodes

binary search tree(BST)

binary tree with values satisfying a specific property

graph

data structure with nodes and edges that relate them

undirected graph

graph with edges having no direction

directed graph(Digraph)

graph with directed edges

depth-first searching algorithm

algorithm that explores paths form a starting vertex to the deepest branch

breadth-first search

algorithm that examines vertices adjacent to the staring vertex before moving to deeper levels

subprogram statements

section of code with a name that can be used as a statement in another part of the program

value parameter

parameter that expects a copy of its argument to be passed

reference parameter

parameter that expects the address of its argument to be passed

subprogram

a name given to a collection to a sequence; divide and conquer

subprogram statements

a statement that represents a section of code in another part of the program

parameters

identifiers listed in parentheses beside the subprogram declaration

arguments

identifiers listed in parentheses on the subprogram call; actual parameters

object

a thing or entity that makes sense within the context of the problem

problems are solved by

isolating the objects, determining their properties and actions, and letting the objects collaborate to solve a problem

class

a description of a group of similar objects

classes

contain fields that represent properties and behaviors

method

a named algorithm that defines behavior

top-down design

decomposes problems into tasks

steps for object-oriented design

isolate, abstract, determine

4 stages to the decomposition process

brainstorming to locate possible classes, filtering duplicates, scenarios to make sure you understand, responsibility algorithms for actions that classes must exhibit

scenarios

assign responsibilities to each class, knowledge, and behavior

encapsulation

the bundling of data and actions in a way into a single object class

responsibility algorithms

knowledge returns, actions manipulate it

CRC cards

notational device to record information about a class, what it must do, and with whom it must collaborate

translation process

a program written in a high level language must be translated into machine code

high level language

a language the proves a higher(very formal, English like) set of instructions

compiler

a program that translates a high level language(source code) into machine language

byte code

doesn’t care with it is running on

interpreter

a translating program that translates and executes the statements in a sequence

portability

the ability of a program to be run on different machines

compiler portability

a program in a standardized language can be compiled and run on any machine that has the appropriate compiler

bytecode portability

can be run on any machine that has a JVM

Java portability

portability was of primary importance, is compiled into Bytecode, a software interpreter called the JVM takes the byte code program and executes it

imperative paradigm

program describes the processing, Procedural and Object Oriented Model

Declarative paradigm

program describes the results

C++

a procedural language with some object-oriented features

Java

an object-oriented language with some procedural features

Declarative

functional, which is based on the mathematical concept, and logic; used on principles of symbolic logic

scheme

form of lists, lots of parentheses and nested operations

prolog

followed by a series of questions, nonprocedural

functionality of a language

is power of a language, 2 parts, syntax

sequence

executing statements until an instruction is encountered that changes

selection

deciding which action to take