Dsa Reviewer For Midterm 1

Front 1

is an environment that is used to write computer programs, to compile them, to run them and to debug them.

Back 1

Integrated Development Environment (IDE)

Front 2

is a piece of software that contains all of the things you need to develop, compile, link, and debug your programs.

Back 2

Integrated Development Environment (IDE)

Front 3

This skeleton includes the basic bones upon which most programs are written.

Back 3

C Skeleton

Front 4

are used to indicate something to the person reading the code, or often used to explain sections of code.

are treated like a blank by the compiler and do not change anything in the code's actual meaning.

Back 4

Comments

Front 5

There are two most commonly used syntaxes used for comments in C

Back 5

the original /* */

the slightly newer //

Front 6

is a set of alphabets, letters and some special characters that are valid in C language.

Back 6

Character Set

Front 7

represent the core of the language.

are predefined, reserved words used in programming that have special meanings to the compiler.

are part of the syntax and they cannot be used as an identifier.

Back 7

Keywords

Front 8

refers to name given to entities such as variables, functions, structures etc.

must be unique. They are created to give a unique name to an entity to identify it during the execution of the program.

Back 8

Identifiers

Front 9

In programming, input and data are stored in ______, is a container (storage area) to hold data.

Back 9

Variables

Front 10

are data used for representing fixed values. They can be used directly in the code.

Back 10

Literals

Front 11

is a numeric literal(associated with numbers) without any fractional or exponential part.

Back 11

Integers

Front 12

is a numeric literal that has either a fractional form or an exponent form.

Back 12

Floating-point Literals

Front 13

literal is created by enclosing a single character inside single quotation marks.

Back 13

Characters

Front 14

Sometimes, it is necessary to use characters that cannot be typed or has special meaning in C programming.

Back 14

Escape Sequence

Front 15

is a sequence of characters enclosed in double-quote marks.

Back 15

String Literals

Front 16

If you want to define a variable whose value cannot be changed, you can use the const keyword.

Back 16

Constants

Front 17

are declarations for variables.

This determines the type and size of data associated with variables.

Back 17

Data Types

Front 18

Integers are whole numbers that can have both zero, positive and negative values but no decimal values.

Back 18

int

Front 19

are used to hold real numbers.

Back 19

float and double

Front 20

is an incomplete type.

It means "nothing" or "no type".

You can think of ______ as absent.

Back 20

void

Front 21

If you need to use a large number, you can use a type specifier ______

Back 21

long

Front 22

If you are sure, only a small integer ([−32,767, +32,767] range) will be used, you can use ______

Back 22

short

Front 23

You can alter the data storage of a data type by using them.

Back 23

signed and unsigned

Front 24

Data types that are derived from fundamental data types are

Back 24

Derived Types or Derived Data Types

Front 25

are values or set of values.

Back 25

Data

Front 26

refers to single unit of values.

Back 26

Data Item

Front 27

Data items that are divided into sub items are called as

Back 27

Group Item

Front 28

Data items that cannot be divided are called as

Back 28

Elementary Item

Front 29

An entity is that which contains certain attributes or properties, which may be assigned values.

Back 29

Attribute and Entity

Front 30

Entities of similar attributes form an

Back 30

Entity Set

Front 31

is a single elementary unit of information representing an attribute of an entity.

Back 31

Field

Front 32

is a collection of field values of a given entity.

Back 32

Record

Front 33

is a collection of records of the entities in a given entity set.

Back 33

File

Front 34

are the programmatic way of storing data so that data can be used efficiently.

is about rendering data elements in terms of some relationship, for better organization and storage.

Back 34

Data Structure

Front 35

Algorithm + Data Structure =

Back 35

Program

Front 36

Data Structure = ______ + ______

Back 36

Organized data + Operations

Front 37

These are the basic data structures and are directly operated upon by the machine instructions, which is in a primitive level.

They are integers, floating point numbers, characters, string constants, pointers etc.

Back 37

Primitive Data Structures

Front 38

It is a more sophisticated data structure emphasizing on structuring of a group of homogeneous (same type) or heterogeneous (different type) data items.

Array, list, files, linked list, trees and graphs fall in this category

Back 38

Non-primitive Data Structures

Front 39

Algorithm to search an item in a data structure.

Back 39

Search

Front 40

Algorithm to sort items in a certain order.

Back 40

Sort

Front 41

Algorithm to insert item in a data structure.

Back 41

Insert

Front 42

Algorithm to update an existing item in a data structure.

Back 42

Update

Front 43

Algorithm to delete an existing item from a data structure.

Back 43

Delete

Front 44

Each data structure has an ______.

______ represents the set of operations that a data structure supports.

Back 44

Interface

Front 45

provides the internal representation of a data structure.

also provides the definition of the algorithms used in the operations of the data structure.

Back 45

Implementation

Front 46

Data structure implementation should implement its interface correctly.

Back 46

Correctness

Front 47

Running time or the execution time of operations of data structure must be as small as possible.

Back 47

Time Complexity

Front 48

Memory usage of a data structure operation should be as little as possible.

Back 48

Space Complexity

Front 49

is a step-by-step finite sequence of instruction, to solve a well-defined computational problem.

Back 49

Algorithm

Front 50

The development phase consists of two phases:

Back 50

Coding Phase and Design Phase

Front 51

the architecture, logic, and implementation details of the algorithm are envisioned and documented.

Back 51

Design Phase

Front 52

the designed algorithm is converted into a computer program.

Back 52

Coding Phase

Front 53

The simplest way to specify the logic for an algorithm is to write the higher-level description of an algorithm in a semi-structured way, called

Back 53

Pseudocode

Front 54

are used instead of pseudocode wherever possible as they save one additional step.

Back 54

Snippets

Front 55

are designed to deal with a large amount of data.

Back 55

Data-intensive Algorithm

Front 56

have considerable processing requirements but do not involve large amounts of data.

Back 56

Compute-intensive algorithms

Front 57

is the expected size of the data that the algorithm will process.

Back 57

Volume

Front 58

is the expected rate of new data generation when the algorithm is used. It can be zero.

Back 58

Velocity

Front 59

quantifies how many different types of data the designed algorithm is expected to deal with.

Back 59

Variety

Front 60

is about the processing and computing needs of the problem at hand.

Back 60

Compute Dimension

Front 61

All the data transformation and preparation is implemented in three mappers.

For that, we divide the video into three different partitions, called

Back 61

Splits

Front 62

After the mappers are executed, the resulting processed video is inputted to the two aggregators, called

Back 62

Reducers

Front 63

______ is heavily procedural. The focus is entirely on writing code (functions).

Data is passive in ______.

Back 63

Modular Programming

Front 64

dictates that a program should be divided into a main module and its related modules.

is a technique for organizing and coding programs in which a hierarchy of modules is used, and breaking the specification down into simpler and simpler pieces, each having a single entry and a single exit point, and in which control is passed downward through the structure without unconditional branches to higher levels of the structure.

Back 64

Top-Down Algorithm Design

Front 65

is the opposite of top-down design. It refers to a style of programming where an application is constructed starting with existing primitives of the programming language, and constructing gradually more and more complicated features, until the all of the application has been written.

Back 65

Bottom-Up Algorithm Design

Front 66

is the study of how complicated algorithms are.

Back 66

Complexity theory

Front 67

An algorithm won't do you much good if it doesn't give you the right answers.

Back 67

It should be correct.

Front 68

The best algorithm in the world won't do you any good if it's too complicated for you to implement on a computer.

Back 68

A good algorithm should be understandable.

Front 69

Even if an algorithm produces a correct result, it won't help you much if it takes a thousand years or if it requires 1 billion terabytes of memory.

Back 69

A good algorithm should be efficient.

Front 70

Estimates the runtime memory requirements needed to execute the algorithm.

Back 70

Space complexity analysis

Front 71

Estimates the time the algorithm will take to run.

Back 71

Time complexity analysis:

Front 72

need to have efficient resource allocation mechanisms that are aware of the memory requirements at different execution phases of the algorithm.

Back 72

Resilient Distributed Datasets (RDDs)

Front 73

Space needed to store the executable version of the program and it is fixed.

Back 73

Instruction Space

Front 74

Space needed to store all constants, variable values and has further two components

Back 74

Data Space

Front 75

This space is needed to store the information to resume the suspended (partially completed) functions.

Back 75

Environment Stack Space

Front 76

The amount of space needed by recursive function is called the

Back 76

Recursion Stack Space

Front 77

In this approach, different candidate algorithms are implemented and their performance is compared.

Back 77

Post-implementation Profiling Approach

Front 78

In this approach, the performance of each algorithm is approximated mathematically before running an algorithm.

Back 78

Pre-implementation Theoretical Approach

Front 79

the data given as input is organized in a way that the algorithm will give its best performance.

Back 79

Best Case

Front 80

This starts by dividing the various possible inputs into various groups.

Back 80

Average Case

Front 81

The second way to estimate the performance of an algorithm is to try to find the maximum possible time it will take to get the job done under a given set of conditions.

Back 81

Worst Case

Front 82

In many situations, data structures are subjected to a sequence of instructions rather than one set of instruction.

Back 82

Amstrong Complexity

Front 83

can be used to show that the average cost of an operation is small, if one averages over a sequence of operations, even though a simple operation might be expensive.

guarantees the average performance of each operation in the worst case.

Back 83

Amortized analysis

Front 84

There may be more than one approach (or algorithm) to solve a problem.

Back 84

Time-Space Trade Off

Front 85

______ is a characteristic scheme that measures properties of algorithm complexity performance and/or memory requirements.

Back 85

Big OH

Front 86

If an algorithm takes the same amount of time to run, independent of the size of the input data, it is said to run in ______

Back 86

Constant Time

Front 87

An algorithm is said to have a complexity of ______, represented by O(n), if the execution time is directly proportional to the size of the input.

Back 87

Linear Time

Front 88

An algorithm is said to run in ______ if the execution time of an algorithm is proportional to the square of the input size.

Back 88

Quadratic Time

Front 89

An algorithm is said to run in ______ if the execution time of the algorithm is proportional to the logarithm of the input size.

Back 89

Logarithmic Time

Front 90

confirms that it is actually providing a mathematical solution to the problem we are trying to solve.

Back 90

Validation an Algorithm

Front 91

Algorithms can also be divided into the following two types based on assumptions or approximation used to simplify the logic to make them run faster:

Back 91

Exact Algorithm and Approximate Algorithm

Front 92

are expected to produce a precise solution without introducing any assumptions or approximations.

Back 92

Exact Algorithm

Front 93

When the problem complexity is too much to handle for the given resources, we simplify our problem by making some assumptions.

The algorithms based on these simplifications or assumptions are called approximate algorithms, which doesn't quite give us the precise solution.

Back 93

Approximate Algorithm

Front 94

The ability to exactly identify the features that are used directly or indirectly to come up with a particular decision is called the ______ of an algorithm.

Back 94

Explainability

Front 95

There are three steps in refinement process, which is illustrated

Back 95