Module 1 Flashcards by Deleted Deleted

a sequence of unambiguous instructions
for solving a problem.

algorithm

How well did you know this?

Not at all

Perfectly

any well-defined computational procedure that
takes 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

sequence
of 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 F

Before 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 detail
to 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 models
are 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 F

Subsequent 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:

Input
Output
Definiteness
Finiteness
Effectiveness

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 an
answer 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 time and space resources required to execute it.

Analysis of Algorithms

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

True

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

Algorithm

T or F Writing 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 the intent 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 only show if errors are present.

Program Testing

For a programmer reliable ________ is always a must.

Documentation

T or F The 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

Development Maintenance Knowledge transfer to other developers.

T or F Successful documentation will make information easily accessible, provide a limited number of user entry points, help new users learn quickly, simplify the product and help cut support costs

True

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

Server environments Business rules Databases/files Troubleshooting Application installation Code 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 by using Pseudocode to represent the algorithm as a set of fundamental operations which can then be counted.

The Running Time

A formal definition with some specific characteristics that describes a process, which could be executed by 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 leaving many granular details of it.

Pseudocode

T or F Writing 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 do r ← m mod n m← n n ← r return 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 sort Insertion 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 Search Binary 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 through whole data sequentially until you find the match.

Sequential Search

What type of search makes you divide data into two (bi) parts at each stage. Here you don’t have to traverse through 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, some of which are connected by line segments called edges.

Graph

Examples of graph algorithms

Graph traversal algorithms Shortest-path algorithms Topological 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 of elements, 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 F n 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 False The 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 to the edges.

Weighted Graphs

T or F A 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 F All 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 and ends 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 necessarily connected.

Forest

T or F For 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 the simple 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 children of each vertex are ordered.

Ordered Tree

An ordered tree in which every vertex has no more than two children and each children is designated 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 than all the numbers in its left subtree and smaller than all the numbers in its right subtree.

Binary Search Tree

Module 1 Flashcards

yeah