CS401A's Prelims: Design and Analysis of Algorithms Flashcards
For preliminary exams.
“A computer is a stupid machine
with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things.”
Bill Bryson
A set of finite and detailed step-by-step instructions performed to complete a specific task is what we call an
algorithm
Did you know that the word algorithm comes from Persian scientist, mathematician, and author
Abu Abdullah
Muhammad bin Musa al-Khwarizmi?
on the other hand, is the design and analysis
of computer algorithms.
Algorithmics,
pertains to the method or mathematical process behind the conception of an algorithm
The design part
while the
deals with the determination of the
computational complexity of an algorithm.
analysis part
starts from defining the
problem cautiously by describing the set of instances
Notion of Algorithm
The algorithm
will often be divided into sections:
Parts/Components (Input)
Actions/Steps/Methods (Processing)
Outcome (Output)
5 properties of Algorithm or the Characteristics of Algorithm
Input Specification
Output Specification
Definiteness
Finiteness
Effectiveness
(Characteristics of Algorithm)
The inputs must be clearly
identified.
Input Specification
(Characteristics of Algorithm)
The output, as well as its
relationship to the input/s, must be clearly
identified
Output Specification
(Characteristics of Algorithm)
The steps in the algorithm must be
precisely defined;
Definiteness
The algorithm must always come to an
end after a finite number of steps and using a finite
amount of resources.
Finiteness
All operations to be performed
must be sufficiently basic that they can be done
exactly and in finite time.
Effectiveness
An algorithm is represented using two (2) common
techniques:
pseudocode and flowchart.
_____ means imitation
Pseudo
_____ refers to instructions written in a programming
language.
code
This term is a generic way of describing an algorithm without using any specific
programming language-related notations.
Pseudocode
It is a method of expressing an algorithm
by a collection of connected geometric shapes containing descriptions of the algorithm’s steps.
Flowchart
There is no strict set of standard notations for
pseudocode, but the most widely recognized are:
Input
Output
If-then-else
For
Repeat-Until
While
a user will be inputting
something.
Input
an output will
appear on the screen.
Output
a decision (selection) in
which a choice is made
If-then-else
counting loop (iteration)
For
loop (iteration) that has a condition at the end
Repeat-Until
loop (iteration) that has a condition at the beginning
While
It asks to rearrange the items of a given list in ascending order.
Sorting Problem
It deals with finding a given value called the “search key” in a given list or set.
Searching Problem
It deals with non-numerical data that intensifies the interest of researchers and
computing practitioners in string-handling algorithms.
String Processing Problem
This is a sequence of characters from an alphabet
String
comprise letters, numbers, and special characters .
Text strings
comprise zeros and ones.
Bit strings
can be modeled by strings of characters from the four-character alphabet {A, C, G, T}.
Gene sequences
It deals with objects and their connections
Graph Problem
It deals with how one can reach all the points in a network.
Graph-traversal algorithms
a traversing algorithm where one should start traversing from a
selected node (source or starting node) and traversing the graph layerwise
Breadth First Search (BFS)
a recursive algorithm that uses the idea of backtracking. The word
“backtrack” means that when one is moving forward, and there are no more nodes along the
current path, s/he moves back on the same path to find nodes to traverse.
Depth First Search (DFS)
It deals with what is the best route between two (2) cities.
Shortest-path algorithms
It deals with a set of courses with their prerequisites
consistent or self-contradictory
Topological sorting for graphs with directed edges
It’s about finding the right arrangement (like a permutation, combination or subset) that meets specific rules and has a desired feature. Tough computing stuff.
Combinatorial problems
It deals with finding the shortest tour through 𝑛 cities that visits every
city exactly once
Traveling Salesman Problem (TSP)
It deals with assigning the smallest number of colors to the vertices of a graph
so that no two (2) adjacent vertices are the same color.
Graph-coloring problem
It deals with geometric objects such as points, lines, and polygons.
Geometrical problems
Two (2) Classic Problems of Computational Geometry
Closest-pair problem
Convex-hull problem
given 𝑛 points in the plane, find the closest pair among them.
Closest-pair problem
this asks to find the smallest convex polygon that would include all the points of a
given set
Convex-hull problem
It involves mathematical objects of continuous nature
Numerical problems
