Brainscape's Knowledge GenomeTM

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


See full index

Algorithm > Module 1 > Flashcards

Module 1 Flashcards

yeah

1
Q

a sequence of unambiguous instructions
for 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 that
takes 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

sequence
of 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
4
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
5
Q

T or F

Before 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
6
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
7
Q

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

A

The Problem Itself

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
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
9
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
10
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
11
Q

an iterative process, in which many models
are 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
12
Q

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.

A

True

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

All algorithms must satisfy the following criteria:

A

Input
Output
Definiteness
Finiteness
Effectiveness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
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
15
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
16
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
17
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
18
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
19
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
20
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
21
Q

Requires that if an
answer is returned it will be correct

A

Partial Correctness

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

The determination of the amount of time
and 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
25
Q

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.

A

True

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

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

A

Algorithm

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

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.

A

False (Not Equal)

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

The process of executing a program with the
intent of finding errors.

A

Program Testing

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

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

A

Program Testing

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

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.

A

True

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

Main Focuses of Documentation

A

Development
Maintenance
Knowledge transfer to other developers.

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

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

A

True

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

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

A

Server environments
Business rules
Databases/files
Troubleshooting
Application installation
Code deployment.

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

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.

A

The Running Time

38
Q

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.

A

Algorithm

39
Q

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

A

Algorithm

40
Q

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

A

Pseudocode

41
Q

T or F

Writing a pseudocode has a restriction of styles

A

False

42
Q

The only objective of Pseudocode

A

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

43
Q

9th Century Mathematician

A

Muhammad ibn Musa al-Khwarizmi

44
Q

Euclid’s Algorithm

A

while n ≠ 0 do
r ← m mod n
m← n
n ← r
return m

45
Q

Algorithms often use _______ as a key subroutine.

A

Sorting

46
Q

A specially chosen piece of information used to guide sorting.

A

Sorting Key

47
Q

Examples of sorting algorithms

A

Selection sort
Bubble sort
Insertion sort
Merge sort
Heap sort

48
Q

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

A

Stable

49
Q

Examples of searching algorithms.

A

Sequential Search
Binary Search

49
Q

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

A

In Place

50
Q

What type of search goes through
whole data sequentially until you find
the match.

A

Sequential Search

51
Q

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.

A

Binary Search

52
Q

A sequence of characters from an alphabet.

A

String

53
Q

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

A

Text Strings

54
Q

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

A

String Matching

55
Q

A collection of points called vertices, some
of which are connected by line segments called
edges.

A

Graph

56
Q

Examples of graph algorithms

A

Graph traversal algorithms
Shortest-path algorithms
Topological sorting

57
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

58
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

59
Q

Arrays Characteristics

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

Linked List Characteristics

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

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

A

Stacks

62
Q

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

A

Queues

63
Q

Two Operations of Stack

A

Push and Pop

64
Q

Two Operations of Queue

A

Enqueue and Dequeue

65
Q

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

A

Priority Queue

66
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

67
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

68
Q

Two types of Graphs:

A

Undirected and directed graphs

69
Q

T or F

n x n boolean matrix if |V| is n.

A

True

70
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

71
Q

True or False

The adjacency matrix of an undirected graph is symmetric.

A

True

72
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

73
Q

Graphs or digraphs with numbers assigned to
the edges.

A

Weighted Graphs

74
Q

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.

A

True

75
Q

T or F

All edges of a path are distinct.

A

True

76
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

77
Q

The maximum connected subgraph of a given graph.

A

Connected Component

78
Q

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

A

Cycle

79
Q

A graph without cycles

A

Acyclic Graph

80
Q

A connected acyclic graph.

A

Tree

81
Q

A graph that has no cycles but is not necessarily
connected.

A

Forest

82
Q

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.

A

True

83
Q

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

A

Ancestors

84
Q

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

A

Descendants

85
Q

Vertices that have the same parent are called

A

Siblings

86
Q

A vertex without children is called a

A

Leaf

87
Q

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

A

Subtree

88
Q

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

A

Depth of a Vertex

89
Q

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

A

Height of a tree

90
Q

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

A

Ordered Tree

91
Q

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.

A

Binary Tree

92
Q

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.

A

Binary Search Tree

Algorithm (2 decks)

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