Module 1 Flashcards by MATTHEW BARCELON

a sequence of unambiguous instructionsfor solving a problem.

algorithm

How well did you know this?

Not at all

Perfectly

any well-defined computational procedure thattakes some value, or set of values, as input and produces some value, or set of values, as output.

algorithm

How well did you know this?

Not at all

Perfectly

sequenceof computational steps that transform the input into the output.

algorithm

How well did you know this?

Not at all

Perfectly

Algorithm Requirements

ü Finitenessü Definitenessü Clearly specified inputü Clearly specified/expected outputü Effectiveness

How well did you know this?

Not at all

Perfectly

Problem Development Steps

Problem definition* Development of a model* Specification of an Algorithm* Designing an Algorithm* Checking the correctness of an Algorithm* Analysis of an Algorithm* Implementation of an Algorithm* Program testing* Documentation

How well did you know this?

Not at all

Perfectly

T or FBefore you start to work on the the solution the developer, programmer must be able to understand fully the problem statement.

True

How well did you know this?

Not at all

Perfectly

Three Elements of Problem Statement

The Problem Itself* The Method of Solving the Problem* The Purpose

How well did you know this?

Not at all

Perfectly

Which element of the Problem Statement is stated clearly and with enough contextual detailto establish why it is important?

The Problem Itself

How well did you know this?

Not at all

Perfectly

Which element of the Problem Statement is often stated as a claim or a working thesis?

The Method of Solving the Problem

How well did you know this?

Not at all

Perfectly

Which element of the Problem Statement is a statement of objective and scope of the document the writer is preparing

The Purpose

How well did you know this?

Not at all

Perfectly

involves the definition of model objectives,conceptualization of the problem, translation into a computational model, and model testing, revision, and application.

Model Development

How well did you know this?

Not at all

Perfectly

an iterative process, in which many modelsare derived, tested and built upon until a model fitting the desired criteria is built.

Model Development

How well did you know this?

Not at all

Perfectly

T or FSubsequent modelling work may need to begin the search at the same place as the original model building began, rather than where it finished.

True

How well did you know this?

Not at all

Perfectly

All algorithms must satisfy the following criteria:

InputOutputDefinitenessFinitenessEffectiveness

How well did you know this?

Not at all

Perfectly

An algorithm has zero or more inputs, taken from a specified set of objects.

Input

How well did you know this?

Not at all

Perfectly

An algorithm has one or more outputs, which have a specified relation to the inputs.

Output

How well did you know this?

Not at all

Perfectly

Each step must be precisely defined; Each instruction is clear and unambiguous.

Definiteness

How well did you know this?

Not at all

Perfectly

The algorithm must always terminate after a finite number of steps.

Finiteness

How well did you know this?

Not at all

Perfectly

All operations to be performed must be sufficiently basic that they can be done exactly and in finite length.

Effectiveness

How well did you know this?

Not at all

Perfectly

In theoretical computer science, __________ of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification.

Correctness

How well did you know this?

Not at all

Perfectly

Refers to the input-output behavior of the algorithm.

Functional Correctness

How well did you know this?

Not at all

Perfectly

Requires that if ananswer is returned it will be correct

Partial Correctness

How well did you know this?

Not at all

Perfectly

Additionally requires that the algorithm terminates.

Total Correctness

How well did you know this?

Not at all

Perfectly

A type of mathematical proof that plays a critical role in formal verification because total correctness of an algorithm depends on termination.

Termination Proof

How well did you know this?

Not at all

Perfectly

The determination of the amount of timeand space resources required to execute it.

Analysis of Algorithms

T or FUsually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps, knownas time complexity, or volume of memory, known as space complexity.

True

A series of steps that you expect will arrive at aspecific solution.

Algorithm

T or FWriting a program is equal to expressing code, that idea ignores and neglects the entire idea of writing code to solve a problem.

False (Not Equal)

The process of executing a program with theintent of finding errors.

Program Testing

A good _____ is one that has a high probability of finding an error.

Test

Cannot show the absence of errors. It can onlyshow if errors are present.

Program Testing

For a programmer reliable ________ is always a must.

Documentation

T or FThe presence of documentation helps keep track of all aspects of an application and it improves on the quality of a software product.

True

Main Focuses of Documentation

DevelopmentMaintenanceKnowledge transfer to other developers.

T or FSuccessful documentation will make information easily accessible, provide alimited number of user entry points, help new users learn quickly, simplify theproduct and help cut support costs

True

Documentation is usually focused on the following components that make upan application:

Server environmentsBusiness rulesDatabases/filesTroubleshootingApplication installationCode deployment.

The main characteristics of algorithms are

- Must have a unique name- Should have explicitly defined set of inputs and outputs- Well-ordered with unambiguous operations- Halt in a finite amount of time, Should not run for infinity, Must end at some point

gives a high-level description of an algorithm without the ambiguity associated with plain text but also without the need to know the syntax of a particular programming language.

Pseudocode

Can be estimated in a more general manner byusing Pseudocode to represent the algorithm as a set of fundamental operations which can then be counted.

The Running Time

A formal definition with some specificcharacteristics that describes a process, which could be executedby a Turing-complete computer machine to perform a specific task.

Algorithm

Generally, the word "________" can be used to describe any high level task in computer science.

Algorithm

An informal and (often rudimentary) human readable description of an algorithm leavingmany granular details of it.

Pseudocode

T or FWriting a pseudocode has a restriction of styles

False

The only objective of Pseudocode

Describe the high level steps of algorithm in a much realistic manner in natural language.

9th Century Mathematician

Muhammad ibn Musa al-Khwarizmi

Euclid's Algorithm

while n ≠ 0 dor ← m mod nm← nn ← rreturn m

Algorithms often use _______ as a key subroutine.

Sorting

A specially chosen piece of information used to guide sorting.

Sorting Key

Examples of sorting algorithms

Selection sort Bubble sortInsertion sort Merge sort Heap sort

A sorting algorithm is called ______ if it preserves the relative order of any two equal elements in its input.

Stable

Examples of searching algorithms.

Sequential SearchBinary Search

A sorting algorithm is _________ if it does not require extra memory, except, possibly for a few memory units.

In Place

What type of search goes throughwhole data sequentially until you findthe match.

Sequential Search

What type of search makes you divide data into two (bi) parts at each stage. Here you don’t have to traversethrough whole data.

Binary Search

A sequence of characters from an alphabet.

String

What strings are made up of letters, numbers, and special characters.

Text Strings

What is searching for a given word/pattern in a text.

String Matching

A collection of points called vertices, someof which are connected by line segments callededges.

Graph

Examples of graph algorithms

Graph traversal algorithmsShortest-path algorithmsTopological sorting

A sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a value of the arrayʼs index.

Arrays

A sequence of zero or more nodes each containing two kinds of information: some data and one or more links called pointers to other nodes of the linked list.

Linked List

Arrays Characteristics

- Fixed length (need preliminary reservation of memory)- Contiguous memory locations- Direct access- Insert/delete

Linked List Characteristics

- Dynamic length- Arbitrary memory locations- Access by following links- Insert/delete

Follows LIFO/FILO (Insertion/Deletion can only be done at the top.)

Stacks

Follows FIFO/LILO (Insertion/enqueue from the rear and deletion/dequeue from the front.)

Queues

Two Operations of Stack

Push and Pop

Two Operations of Queue

Enqueue and Dequeue

A data structure for maintaining a set ofelements, each associated with a key/priority

Priority Queue

Operations of Priority Queue

Finding the element with the highest priority Deleting the element with the highest priority Inserting a new element Scheduling jobs on a shared computer

Defined by a pair of two sets: a finite set V of items called vertices and a set E of vertex pairs called edges.

Graph

Two types of Graphs:

Undirected and directed graphs

T or Fn x n boolean matrix if |V| is n.

True

The element on the ith row and jth column is 0 if thereʼs an edge from ith vertex to the jth vertex; otherwise 1.

False

True or FalseThe adjacency matrix of an undirected graph is symmetric.

True

A collection of linked lists, one for each vertex, that contain all the vertices adjacent to the listʼs vertex.

Adjacency linked lists

Graphs or digraphs with numbers assigned tothe edges.

Weighted Graphs

T or FA path from vertex u to v of a graph G is defined as a sequence of adjacent (connected by an edge) vertices that starts with u and ends with v.

True

T or FAll edges of a path are distinct.

True

A graph is said to be ________ if for every pair of its vertices u and v there is a path from u to v

Connected

The maximum connected subgraph of a given graph.

Connected Component

A simple path of a positive length that starts andends a the same vertex.

Cycle

A graph without cycles

Acyclic Graph

A connected acyclic graph.

Tree

A graph that has no cycles but is not necessarilyconnected.

Forest

T or FFor every two vertices in a tree there always exists exactly one simple path from one of these vertices to the other.

True

For any vertex v in a tree T, all the vertices on thesimple path from the root to that vertex are called

Ancestors

All the vertices for which a vertex v is an ancestor are said to be ________ of v

Descendants

Vertices that have the same parent are called

Siblings

A vertex without children is called a

Leaf

A vertex v with all its descendants is called the_______ of T rooted at v.

Subtree

The length of the simple path from the root to the vertex.

Depth of a Vertex

The length of the longest simple path from the root to a leaf.

Height of a tree

A rooted tree in which all the childrenof each vertex are ordered.

Ordered Tree

An ordered tree in which every vertexhas no more than two children and each children isdesignated s either a left child or a right child of its parent.

Binary Tree

In this type of tree, Each vertex is assigned a number, and a number assigned to each parental vertex is larger thanall the numbers in its left subtree and smaller than all the numbers in its right subtree.

Binary Search Tree