Module 1 Flashcards
a sequence of unambiguous instructionsfor solving a problem.
algorithm
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
sequenceof computational steps that transform the input into the output.
algorithm
Algorithm Requirements
ü Finitenessü Definitenessü Clearly specified inputü Clearly specified/expected outputü Effectiveness
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
T or FBefore you start to work on the the solution the developer, programmer must be able to understand fully the problem statement.
True
Three Elements of Problem Statement
- The Problem Itself* The Method of Solving the Problem* The Purpose
Which element of the Problem Statement is stated clearly and with enough contextual detailto establish why it is important?
The Problem Itself
Which element of the Problem Statement is often stated as a claim or a working thesis?
The Method of Solving the Problem
Which element of the Problem Statement is a statement of objective and scope of the document the writer is preparing
The Purpose
involves the definition of model objectives,conceptualization of the problem, translation into a computational model, and model testing, revision, and application.
Model Development
an iterative process, in which many modelsare derived, tested and built upon until a model fitting the desired criteria is built.
Model Development
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
All algorithms must satisfy the following criteria:
InputOutputDefinitenessFinitenessEffectiveness
An algorithm has zero or more inputs, taken from a specified set of objects.
Input
An algorithm has one or more outputs, which have a specified relation to the inputs.
Output
Each step must be precisely defined; Each instruction is clear and unambiguous.
Definiteness
The algorithm must always terminate after a finite number of steps.
Finiteness
All operations to be performed must be sufficiently basic that they can be done exactly and in finite length.
Effectiveness
In theoretical computer science, __________ of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification.
Correctness
Refers to the input-output behavior of the algorithm.
Functional Correctness
Requires that if ananswer is returned it will be correct
Partial Correctness
Additionally requires that the algorithm terminates.
Total Correctness
A type of mathematical proof that plays a critical role in formal verification because total correctness of an algorithm depends on termination.
Termination Proof
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
