Midterm Questions

Question 1

Describe the binary search with proper steps?

Answer 1

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Question 2

Describe the binary search with proper steps (Pseduo code)?

Answer 2

1. Compare x with the middle element.
2. If x matches with the middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half.
4. Else (x is smaller) recur for the left half.

Question 3

Define Machine Language:

Answer 3

A computer programming language consisting of binary or hexadecimal instructions which a computer can respond to directly.

Question 4

Define programming language:

Answer 4

A programming language is a computer language engineered to create a standard form of commands. These commands can be interpreted into a code understood by a machine.

Question 5

What are the difference between machine language and programming language?

Answer 5

Machine learning is the low-level programming langugage represented by 0s and 1s. It is only comprenhensible to computers and its diffcult for humans to understand.

Meanwhile, programming language allows humans to translate human intentions into executable algorithms. It is only comprehensible to humans and not to computers.

Question 6

Define Algorithm:

Answer 6

A set of steps that defines how a task is performed

Question 7

Define Program:

Answer 7

A representation of an algorithm

Question 8

Define Programming:

Answer 8

The process of developing a program

Question 9

Define Software:

Answer 9

Programs and the algorithms they represent

Question 10

Define Hardware:

Answer 10

The machinery

Question 11

How to breakdown a problem and convert them to algorithm:

Answer 11

Step 1: Obtain a description of the problem.

Step 2: Analyze the problem.

Step 3: Develop a high-level algorithm.

Step 4: Refine the algorithm by adding more detail.

Step 5: Review the algorithm.

Question 12

Euclidean Algorithm

Answer 12

One of the oldest numerical algorithms still to be in common use. It solves the problem of computing the greatest common divisor (gcd) of two positive integers

Question 13

Abstraction

Answer 13

The distinction between the external properties of an entity and the details of the entity’s internal composition

Question 14

Data (how to store them)?

Answer 14

Numbers, text, images, sounds, and video

Question 15

Difference between algorithm and programming language

Answer 15

an algorithm is a step-by-step procedure for solving the problem while programming is a set of instructions for a computer to follow to perform a task.

Question 16

Formal definition of algorithm

Answer 16

An algorithm is an ordered set of unambiguous, executable steps that defines a terminating process

Question 17

Pseudo code

Answer 17

Pseudocode is an artificial and informal language that helps programmers develop algorithms.

Question 18

Pseudo code primitives (Assignments)

Answer 18

name = expression

RemainingFunds = CheckingBalance + SavingsBalance

Question 19

Pseudo code primitives (Conditional selection)

Answer 19

if (condition):
activity

if (sales have decreased):
lower the price by 5%

Question 20

Pseudo code primitives (Repeated execution):

Answer 20

while (condition):
body

while (tickets remain to be sold):
sell a ticket

Question 21

Pseudo code primitives (Functions):

Answer 21

Def name():

example: 
def ProcessLoan():

Question 22

Outline Polya’s steps:

Answer 22

Polya created his famous four-step process for problem solving, which is used all over to aid people in problem solving:

Step 1: Understand the problem.

Step 2: Devise a plan (translate).

Step 3: Carry out the plan (solve).

Step 4: Look back (check and interpret).

Question 23

Define Iterative structures:

Answer 23

A collection of instructions repeated in a looping manner

• Examples include:
– Sequential Search Algorithm
– Insertion Sort Algorithm

Question 24

Linear search (sequential search)

Answer 24

A simple approach is to do a linear search, i.e

1. Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
2. If x matches with an element, return the index.
3. If x doesn’t match with any of the elements, return -1.

Question 25

Define Insertion sort

Answer 25

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Question 26

How to store – text, number, image, sounds, etc.

Answer 26

Many different kinds of information can be encoded as bit patterns

• Systems for encoding information have been established for

– Text
– Numeric Data
– Images
– Sound
– Other data

Question 27

Define Error detecting code

Answer 27

Error-detecting codes are a sequence of numbers generated by specific procedures for detecting errors in data that has been transmitted over computer networks

Question 28

Error Correcting code

Answer 28

An error-correcting code is an algorithm for expressing a sequence of numbers such that any errors which are introduced can be detected and corrected (within certain limitations) based on the remaining numbers.