Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithms > Module 1 > Flashcards

Module 1 Flashcards

1
Q

a sequence of unambiguous instructionsfor solving a problem.

A

algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

sequenceof computational steps that transform the input into the output.

A

algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Algorithm Requirements

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Problem Development Steps

A
  • 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?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Three Elements of Problem Statement

A
  • The Problem Itself* The Method of Solving the Problem* The Purpose
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

The Problem Itself

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

The Method of Solving the Problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

The Purpose

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

Model Development

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

Model Development

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

All algorithms must satisfy the following criteria:

A

InputOutputDefinitenessFinitenessEffectiveness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

Input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

Output

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

Definiteness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

Finiteness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

Effectiveness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A

Correctness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Refers to the input-output behavior of the algorithm.

A

Functional Correctness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Requires that if ananswer is returned it will be correct

A

Partial Correctness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Additionally requires that the algorithm terminates.

A

Total Correctness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

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

A

Termination Proof

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

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

A

Analysis of Algorithms

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

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.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

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

A

Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

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.

A

False (Not Equal)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

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

A

Program Testing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

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

A

Test

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

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

A

Program Testing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

For a programmer reliable ________ is always a must.

A

Documentation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

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.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Main Focuses of Documentation

A

DevelopmentMaintenanceKnowledge transfer to other developers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

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

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

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

A

Server environmentsBusiness rulesDatabases/filesTroubleshootingApplication installationCode deployment.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

The main characteristics of algorithms are

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

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.

A

Pseudocode

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

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.

A

The Running Time

40
Q

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

A

Algorithm

41
Q

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

A

Algorithm

42
Q

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

A

Pseudocode

43
Q

T or FWriting a pseudocode has a restriction of styles

A

False

44
Q

The only objective of Pseudocode

A

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

45
Q

9th Century Mathematician

A

Muhammad ibn Musa al-Khwarizmi

46
Q

Euclid’s Algorithm

A

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

47
Q

Algorithms often use _______ as a key subroutine.

A

Sorting

48
Q

A specially chosen piece of information used to guide sorting.

A

Sorting Key

49
Q

Examples of sorting algorithms

A

Selection sort Bubble sortInsertion sort Merge sort Heap sort

50
Q

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

A

Stable

51
Q

Examples of searching algorithms.

A

Sequential SearchBinary Search

52
Q

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

A

In Place

53
Q

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

A

Sequential Search

54
Q

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

A

Binary Search

55
Q

A sequence of characters from an alphabet.

A

String

56
Q

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

A

Text Strings

57
Q

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

A

String Matching

58
Q

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

A

Graph

59
Q

Examples of graph algorithms

A

Graph traversal algorithmsShortest-path algorithmsTopological sorting

60
Q

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.

A

Arrays

61
Q

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.

A

Linked List

62
Q

Arrays Characteristics

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

Linked List Characteristics

A
  • Dynamic length- Arbitrary memory locations- Access by following links- Insert/delete
64
Q

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

A

Stacks

65
Q

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

A

Queues

66
Q

Two Operations of Stack

A

Push and Pop

67
Q

Two Operations of Queue

A

Enqueue and Dequeue

68
Q

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

A

Priority Queue

69
Q

Operations of Priority Queue

A

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

70
Q

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

A

Graph

71
Q

Two types of Graphs:

A

Undirected and directed graphs

72
Q

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

A

True

73
Q

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.

A

False

74
Q

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

A

True

75
Q

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

A

Adjacency linked lists

76
Q

Graphs or digraphs with numbers assigned tothe edges.

A

Weighted Graphs

77
Q

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.

A

True

78
Q

T or FAll edges of a path are distinct.

A

True

79
Q

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

A

Connected

80
Q

The maximum connected subgraph of a given graph.

A

Connected Component

81
Q

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

A

Cycle

82
Q

A graph without cycles

A

Acyclic Graph

83
Q

A connected acyclic graph.

A

Tree

84
Q

A graph that has no cycles but is not necessarilyconnected.

A

Forest

85
Q

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

A

True

86
Q

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

A

Ancestors

87
Q

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

A

Descendants

88
Q

Vertices that have the same parent are called

A

Siblings

89
Q

A vertex without children is called a

A

Leaf

90
Q

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

A

Subtree

91
Q

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

A

Depth of a Vertex

92
Q

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

A

Height of a tree

93
Q

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

A

Ordered Tree

94
Q

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.

A

Binary Tree

95
Q

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.

A

Binary Search Tree

Algorithms (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions