MIDTERM REVIEWER Flashcards by RIZALINA ORTEGA

It is the organization of data.

Data Structures

How well did you know this?

Not at all

Perfectly

Raw, unorganized facts that need to be processed or stored by a computer.

Data

How well did you know this?

Not at all

Perfectly

Can be displayed in rows, columns, relational databases.
Numbers, dates, String
Estimated 20% of enterprise data
Requires less storage.
Easier to manage and protect with legacy solutions.

Structured Data

How well did you know this?

Not at all

Perfectly

Cannot be displayed in rows, columns, relational databases.
Images,audio, video, word processing files, emails, spreadsheets
Estimated 80% of enterprise data
Requires more storage
More difficult to manage and protect with legacy solutions.

Unstructured Data

How well did you know this?

Not at all

Perfectly

Advantage: Quick insertions, very fast access if the index is known.
Disadvantage: Slow search, slow deletions, fixed size

Array

How well did you know this?

Not at all

Perfectly

Advantage: Dynamic size, faster deletion than array, quick insertion.
Disadvantage: Slow search

Linked List

How well did you know this?

Not at all

Perfectly

Advantage: Provide last-in, first out access
Disadvantage: Slow access to other items

Stack

How well did you know this?

Not at all

Perfectly

Advantage: Provide first in, first out access
Disadvantage:Slow Access to other items.

Queue

How well did you know this?

Not at all

Perfectly

Advantage: Quick search, insertion, and deletion ( if tree remains balanced)
Disadvantage: Deletion algorithm is complex

Binary Tree

How well did you know this?

Not at all

Perfectly

Advantage: Fast insertion, deletion, access to largest item.
Disadvantage: Slow access to other items.

Heap

How well did you know this?

Not at all

Perfectly

Advantage: Very fast access if key known, fast insertion.
Disadvantage: Slow deletion, access slow if key not known, inefficient memory usage.

Hash Table

How well did you know this?

Not at all

Perfectly

Advantage: Models real-world situations
Disadvantage: Some algorithms are slow and complex

Graph

How well did you know this?

Not at all

Perfectly

A step by step procedure on how to solve a problem.
Manipulate the data in the data structures in various ways.

Example : Step by step of how to cook a pancit canton.

Algorithm

How well did you know this?

Not at all

Perfectly

Enumerate the Main Data Structure Operations

Sort
Insert
Delete
Search

How well did you know this?

Not at all

Perfectly

ENUMERATE THE REAL APPLICATIONS OF DATA STRUCTURE

Real-world data storage
Operating Systems
Graph Modeling

How well did you know this?

Not at all

Perfectly

Personnel records, inventory records

Real-world data storage

How well did you know this?

Not at all

Perfectly

Stacks and Queues to manage processes and resources

Operating Systems

How well did you know this?

Not at all

Perfectly

Discovering network topologies, Social Network connections.

Graph Modeling

How well did you know this?

Not at all

Perfectly

A collection of related data and set of rules for organizing and accessing it.
An arrangement of data in a computer’s memory or disk.

Example: arrays, linked lists, queues, binary trees, hash tables.

Data Structures

How well did you know this?

Not at all

Perfectly

Manipulate the data in the data structures in various ways.

Algorithm

How well did you know this?

Not at all

Perfectly

Why is it important to learn about data structure?

Efficiency: Faster code, less memory use.
Problem-solving: Right tools for the job.
Better code: Easier to read, maintain, and debug.
Job market: Essential for interviews and careers.
Foundation: Building block for other CS concepts

How well did you know this?

Not at all

Perfectly

How will choosing which data structure to use help in creating efficient programs?

Time: Faster operations (search, insert, delete).
Space: Less memory consumption.
Flexibility: Adapt to changes easily.

How well did you know this?

Not at all

Perfectly

A structure consisting of a fixed number of components with each component of the same type.

Arrays

How well did you know this?

Not at all

Perfectly

Enumerate the Array Components

Name;
Data/ Component type;
Indices of first and last component

How well did you know this?

Not at all

Perfectly

Enumerate the Types of Arrays

- One- Dimensional Arrays - Multidimensional Array - Jagged Array

- Store a number of items with a pre-defined data type. - For practical purposes, so that the computer will know if it can fit inside the memory - All items are stored contiguous starting from 0 to the size of the array - Known as Single- Dimensional Arrays

One- Dimensional Arrays

- Known as rectangular array - An array with more than one dimension - The form of a multi-dimensional array is a matrix

Multidimensional Array

- Arrays of arrays - The elements of a jagged array are other arrays.

Jagged Array

What are Array Operations?

- Insert - Delete

A new item is always inserted in the first vacant cell in the array

Insert

The item to be deleted must first be found

Delete

What are the types of search?

- Linear / Sequential search - Binary search

- Your going to look of each cell after another - Looks at every single index value in the entire array - If there are duplicates, linear search works better when you want to find all matches. - If there are no duplicates, a binary search is better.

Linear / Sequential search

When will the sequential search end? What are the two scenarios?

- If the element is found - when the end of the array is reached

- The data is "halved" at each step of the execution. - Used in the age guessing game, “Higher or Lower” - in order the search to work, the array must be sorted first, before searching can happen. - work if the array is sorted first if it's an unsorted array the binary search will not work. - more faster compared to linear search

Binary Search

In Data Structure, how are we going to measure the time and space complexity of a particular algorithm, what unit?

We use the big (O) notation

Enumerate the Types of Data Structures

- Built-in Data Structures - User Defined Data Structures

Why is there’s no String in the Built-in Data Structures?

- Because String is **made up of characters.** The native data structure is characters and it just combined to create a string -String is an array of characters.

ENUMERATE THE CHARACTERISTICS OF A DATA STRUCTURE

- Linear - Non- Linear - Homogenous - Non - Homogenous - Static - Dynamic

The data items are arranged in a linear sequence. Example: Array

Linear

the data items are not in sequence. Example: Tree, Graph

Non-Linear

all the elements are of the same type. Example: Array

homogeneous

the elements may or may not be of the same type. Example: Structures

non-Homogeneous

those whose sizes and structures associated memory locations are fixed, at compile time. Example: Array

Static

those that expand or shrink depending upon the program need and its execution. Also, their associated memory locations change. Example: Linked List created using pointers

Dynamic

-Used for us to manipulate the user-defined data structures - is a finite set of instructions or logic, written in order, to accomplish a certain predefined task. - The _________ is not the complete code or program, it is just the core logic(solution) of a problem, which can be expressed either as an informal high-level description as pseudocode or using a flowchart.

Algorithm

Every Algorithm must satisfy the following properties?

1. Input 2. Output 3. Definiteness 4. Finiteness 5. Correctness

- There should be 0 (zero) or more inputs supplied externally to the algorithm. - Not required

1. Input

- There should be at least 1 output obtained. - required

Output

Every step of the algorithm should be clear and well defined.

Definiteness

The algorithm should have a finite number of steps.

Finiteness

Every step of the algorithm must generate the correct output

Correctness

**True or False** An algorithm is said to be efficient and fast if it takes less time to execute and consumes less memory space.

True

The performance of an algorithm is measured on the basis on the following properties:

-Space Complexity - Time Complexity

- The concept that is overlooked most of the time - Because the majority of us developers are thinking, "Hmm, I probably won't need to know that while I actually code!"

Complexity Analysis

- deals with comparing algorithms based on the number of computing resources that each algorithm uses. Usually, resources are time and memory - being able to make an informed decision about which algorithm is a winner in terms of making efficient use of resources (time or memory, depending upon use case).

Algorithm analysis

- Deals with the use of the memory space of a particular algorithm. For **instance, program instructions, variables execution.** - Whenever a solution to a problem is written some memory is required to complete it.

Space Complexity of Algorithms

Algorithm uses memory space for three reasons which is?

1. Instruction Space 2. Environmental Stack 3. Data Space

- Code or executable that needs to be stored in the machine - It's the amount of memory used to save the compiled version of instructions

1. Instruction Space

- Executable to run - Sometimes an algorithm (function) may be called inside another algorithm(function). In such a situation, the current variables are pushed onto the system stack, where they wait for further execution and then the call to the inside algorithm(function) is made - For example, If a function A() calls function B() inside it, then all the variables of the function A() will get stored on the system stack temporarily, while the function B() is called and executed inside the function A().

2. Environmental Stack

-Amount of space used by the variables and constants. - Can be modified

Data Space

Which one has the better approach? **Algorithm 1** Int getSquare(int n) { Int square; for (int i = 1; i < = n; 1++) { square = square + n; } return square; } **Algorithm 2** Int getSquare(int n) { return (n* n); }

Algo 2, because it just multiplies the n*n and it will return already

This calculating where we need to know the value of memory used by a different type of datatype variables, which generally varies for different operating systems, but the method for calculating the __________________ remains the same

Calculating the space complexity

What are the size of this? Bool, char, unsigned char, signed char

1 byte

What are the size of this? Short, unsigned short

2 byte

What are the size of this? Float, int , unsigned int, long, unsigned long

4 byte

What are the size of this? - Double, long double, long long

8 byte

- an algorithm signifies the **total times required by the program to run till its comparison** - Most commonly expressed using the big O notation. - Most commonly estimated by counting the numbers of **elementary steps performed by any algorithm to finish execution** -Elementary steps mean the basic steps of the particular algorithm

Time complexity

- the most common metric for calculating time complexity. - This removes all constant factors so that the running time can be estimated in relation to N. as N approaches infinity.

Big O notation

ENUMERATE THE TYPES OF TIME COMPLEXITY

Linear Time - O(n) Constant Time -O(1) Quadratic Time -O(n²)

N is depending on the input or the time it will take will depend on the input

Linear Time - O(n)

- Whatever the input is the time it takes for the algorithm to finish its functionality will remain constant. - Whatever the size of input will not matter

Constant Time -O(1)

The time it takes will be depending on the depending on the input squared

Quadratic Time -O(n²)