CS401A's Prelims: Design and Analysis of Algorithms

Question 1

Review of Algorithms

“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.”

Answer 1

According to Bill Bryson,

Question 2

Review of Algorithms

A set of finite and detailed step-by-step instructions performed to complete a specific task is what we call an

Answer 2

algorithm.

Question 3

Review of Algorithms

Did you know that the word algorithm comes from Persian scientist, mathematician, and author

Answer 3

Abu Abdullah
Muhammad bin Musa al-Khwarizmi,

Question 4

Review of Algorithms

on the other hand, is the design and analysis of computer algorithms.

Answer 4

Algorithmics,

Question 5

Review of Algorithms

pertains to the method or mathematical process behind the conception of an algorithm

Answer 5

The design part

Question 6

Review of Algorithms

while the
deals with the determination of the
computational complexity of an algorithm.

Answer 6

analysis part

Question 7

Review of Algorithms

starts from defining the
problem cautiously by describing the set of instances

Answer 7

Notion of Algorithm

Question 8

Review of Algorithms

The algorithm
will often be divided into sections:

Answer 8

Parts/Components (Input)

Actions/Steps/Methods (Processing)

Outcome (Output)

Question 9

Review of Algorithms

Characteristics of Algorithm
For an algorithm to be useful, it must help find the solution to a specific problem. For that to happen, an algorithm must satisfy five (5) properties.

Answer 9

1. Input Specification
2. Output Specification
3. Definiteness
4. Finiteness
5. Effectiveness

Question 10

Review of Algorithms

Characteristics of Algorithm

The inputs must be clearly
identified.

Answer 10

1. Input Specification

Question 11

Review of Algorithms

Characteristics of Algorithm

The output, as well as its
relationship to the input/s, must be clearly
identified

Answer 11

2. Output Specification

Question 12

Review of Algorithms

Characteristics of Algorithm

The steps in the algorithm must be
precisely defined;

Answer 12

3. Definiteness

Question 13

Review of Algorithms

Characteristics of Algorithm

The algorithm must always come to an
end after a finite number of steps and using a finite
amount of resources.

Answer 13

4. Finiteness

Question 14

Review of Algorithms

Characteristics of Algorithm

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

Answer 14

5. Effectiveness

Question 15

Review of Algorithms

Representation of Algorithm
An algorithm is represented using two (2) common
techniques:

Answer 15

• Pseudocode
• Flowchart

Question 16

Review of Algorithms

_____ means imitation

Answer 16

Pseudo

Question 17

Review of Algorithms

_____ refers to instructions written in a programming
language.

Answer 17

code

Question 18

Review of Algorithms

This term is a generic way of describing an algorithm without using any specific
programming language-related notations.

Answer 18

Pseudocode

Question 19

Review of Algorithms

It is a method of expressing an algorithm
by a collection of connected geometric shapes containing descriptions of the algorithm’s steps.

Answer 19

Flowchart

Question 20

Review of Algorithms

Common Pseudocode Notation
There is no strict set of standard notations for
pseudocode, but the most widely recognized are:

Answer 20

○ Input
○ Output
○ If-Then-Else
○ For
○ Repeat-Until
○ While

Question 21

Review of Algorithms

- indicates a user will be inputting
something.

Answer 21

○ Input

Question 22

Review of Algorithms

- indicates that an output will
appear on the screen.

Answer 22

○ Output

Question 23

Review of Algorithms

- a decision (selection) in which a choice is made any instructions that occur inside a selection or iteration are usually indented.

Answer 23

○ If-Then-Else

Question 24

Review of Algorithms

- a counting loop (iteration)

Answer 24

○ For

Question 25

# **Review of Algorithms** `-` a loop (iteration) that has a condition at the end.

Answer 25

○ *Repeat-Until*

Question 26

# **Review of Algorithms** `-` a loop (iteration) that has a condition at the beginning

Answer 26

○ *While*

Question 27

# **Review of Algorithms** **Algorithm design and analysis process**

Answer 27

1. *Understanding the problem completely.* 2. *Deciding on the computational device, data structures, and algorithm design technique.* 3. *Designing an Algorithm and Data Structure* 4. *Proving the correctness of algorithm* 5. *Analyzing the Algorithm* 6. *Coding the Program for Implementation*

Question 28

# **Review of Algorithms** *Different Types of Problems Encountered in Designing and Analyzing Algorithms*

Answer 28

* *Sorting Problem* * *Searching Problem* * *String Processing Problem* * *Graph Problem* * *Combinatorial problems* * *Geometrical problems* * *Numerical problems*

Question 29

# **Review of Algorithms** — This asks to rearrange the items of a given list in ascending order.

Answer 29

* *Sorting Problem*

Question 30

# **Review of Algorithms** — It deals with finding a given value called the “search key” in a given list or set.

Answer 30

* *Searching Problem*

Question 31

# **Review of Algorithms** It deals with non-numerical data that intensifies the interest of researchers and computing practitioners in string-handling algorithms.

Answer 31

* *String Processing Problem*

Question 32

# **Review of Algorithms** is a sequence of characters from an alphabet.

Answer 32

A **string**

Question 33

# **Review of Algorithms** * *String Processing Problem* Strings of particular interest are as follows:

Answer 33

○ Text strings ○ Bit strings ○ Gene sequences

Question 34

# **Review of Algorithms** comprise letters, numbers, and special characters .

Answer 34

○ Text strings

Question 35

# **Review of Algorithms** comprise zeros and ones.

Answer 35

○ Bit strings

Question 36

# **Review of Algorithms** can be modeled by strings of characters from the four-character alphabet {A, C, G, T}.

Answer 36

○ Gene sequences

Question 37

# **Review of Algorithms** — It deals with objects and their connections ## Footnote like determining whether all of the locations are connected, visiting all of the locations that can be reached from a given location, or finding the shortest path from one (1) location to another.

Answer 37

* *Graph Problem*

Question 38

# **Review of Algorithms** — It deals with how one can reach all the points in a network.

Answer 38

`>` *Graph-traversal algorithms*

Question 39

# **Review of Algorithms** is a traversing algorithm where one should start traversing from a selected node (source or starting node) and traversing the graph layerwise,

Answer 39

— Breadth First Search (BFS)

Question 40

# **Review of Algorithms** is a recursive algorithm that uses the idea of backtracking.

Answer 40

— Depth First Search (DFS)

Question 41

# **Review of Algorithms** 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.

Answer 41

The word “backtrack”

Question 42

# **Review of Algorithms** — It deals with what is the best route between two (2) cities.

Answer 42

`>` *Shortest-path algorithms*

Question 43

# **Review of Algorithms** — It deals with a set of courses with their prerequisites consistent or self-contradictory

Answer 43

`>` *Topological sorting for graphs with directed edges*

Question 44

# **Review of Algorithms** — 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.

Answer 44

* *Combinatorial problems*

Question 45

# **Review of Algorithms** — It deals with the most difficult problem in computing that ask to find a combination of an object such as permutation, combination, or a subset that satisfies certain constraints and has some desired property. | (explicitly or implicitly)

Answer 45

* *Combinatorial problems*

Question 46

# **Review of Algorithms** — It deals with finding the shortest tour through 𝑛 cities that visits every city exactly once.

Answer 46

* *Combinatorial problems* ○ *Traveling Salesman Problem (TSP)*

Question 47

# **Review of Algorithms** — 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.

Answer 47

* *Combinatorial problems* ○ *Graph-coloring problem*

Question 48

# **Review of Algorithms** It deals with geometric objects such as points, lines, and polygons.

Answer 48

* *Geometrical problems*

Question 49

# **Review of Algorithms** *Two (2) Classic Problems of Computational Geometry*

Answer 49

○ *Closest-pair problem* ○ *Convex-hull problem*

Question 50

# **Review of Algorithms** given 𝑛 points in the plane, find the closest pair among them.

Answer 50

○ *Closest-pair problem*

Question 51

# **Review of Algorithms** asks to find the smallest convex polygon that would include all the points of a given set.

Answer 51

○ *Convex-hull problem*

Question 52

# **Review of Algorithms** — It involves mathematical objects of continuous nature ## Footnote such as solving equations, system equations, computing definite integral, evaluating functions, etc.

Answer 52

* *Numerical problems*