ITEC33 (Ma'am Pamintuan) Flashcards
is a systematic way to organize data in order to use it efficiently.
Data Structure
represents the set of operations that a data structure supports.
Interface
provides the list of supported operations, type of parameters they can accept and return type of these operations.
Interface
provides the internal representation of a data structure.
Implementation
provides the definition of the algorithms used in the operations of the data structure.
Implementation
Data structure implementation should implement its interface correctly.
Correctness
Running time or the execution time of operations of data structure must be as small as possible.
Time Complexity
Memory usage of a data structure operation should be as little as possible.
Space Complexity
Consider an inventory of 1 million(106) items of a store. If the application is to search an item, it has to search an item in 1 million(106) items every time slowing down the search. As data grows, search will become slower.
Data Search
although being very high, falls limited if the data grows to billion records.
Processor Speed
As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data.
Multiple Requests
This is the scenario where a particular data structure operation takes maximum time it can take. If an operation’s worst case time is ƒ(n) then this operation will not take more than ƒ(n) time, where ƒ(n) represents function of n.
Worst Case
This is the scenario depicting the average execution time of an operation of a data structure. If an operation takes ƒ(n) time in execution, then m operations will take mƒ(n) time.
Average Case
This is the scenario depicting the least possible execution time of an operation of a data structure. If an operation takes ƒ(n) time in execution, then the actual operation may take time as the random number which would be maximum as ƒ(n).
Best Case
are values or set of values.
Data
refers to single unit of values.
Data item
Data items that are divided into sub items
Group Items.
Data items that cannot be divided
Elementary Items.
An entity is that which contains certain attributes or properties, which may be assigned values.
Attribute and Entity
Entities of similar attributes form an entity set.
Entity Set
is a single elementary unit of information representing an attribute of an entity.
Field
is a collection of field values of a given entity.
Record
is a collection of records of the entities in a given entity set.
File
a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output.
Algortihm
Algorithms form the basis of computer programming and are used to solve problems ranging from simple sorting and searching to complex tasks such as artificial intelligence and machine learning.
Computer Science
Algorithms are used to solve mathematical problems, such as finding the optimal solution to a system of linear equations or finding the shortest path in a graph.
Mathematics
Algorithms are used to optimize and make decisions in fields such as transportation, logistics, and resource allocation.
Operations Research
Algorithms are the foundation of artificial intelligence and machine learning, and are used to develop intelligent systems that can perform tasks such as image recognition, natural language processing, and decision-making.
Artificial Intelligence
Algorithms are used to analyze, process, and extract insights from large amounts of data in fields such as marketing, finance, and healthcare.
Data Science
are necessary for solving complex problems efficiently and effectively.
Algortihm
Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning.
Unambiguous
It is the simplest approach to a problem. A brute force algorithm is the first approach that comes to finding when we see a problem.
Brute Force Algorithm
is based on recursion. In this case, a problem is broken into several sub-parts and called the same
Recursive Algorithm
builds the solution by searching among all possible solutions. Using this algorithm, we keep on building the solution following criteria. Whenever a solution fails we trace back to the failure point build on the next solution and continue this process till we find the solution or all possible solutions are looked after.
Backtracking Algorithm
are the ones that are used for searching elements or groups of elements from a particular data structure. They can be of different types based on their approach or the data structure in which the element should be found.
Searching Algorithm
Sorting is arranging a group of data in a particular manner according to the requirement
-are used to sort groups of data in an increasing or decreasing manner.
Sorting Algorithm
work similarly to the searching algorithm. But they contain an index with a key ID. In hashing, a key is assigned to specific data.
Hashing Algorithm
This algorithm breaks a problem into sub-problems, solves a single sub-problem, and merges the solutions to get the final solution.
Divide and Conquer Algorithm
In this type of algorithm, the solution is built part by part. The solution for the next part is built based on the immediate benefit of the next part. The one solution that gives the most benefit will be chosen as the solution for the next part.
Greedy Algorithm
This algorithm uses the concept of using the already found solution to avoid repetitive calculation of the same part of the problem. It divides the problem into smaller overlapping subproblems and solves them.
Dynamic Programming Algorithm
we use a random number so it gives immediate benefit. The random number helps in deciding the expected outcome.
Randomized Algorithm
This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.
A Priori Analysis
This is an empirical analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.
A PosterioriAnalysis
Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.
Time Factor
Space is measured by counting the maximum memory space required by the algorithm.
Space Factor
to specify a block of C++ code to be executed if a condition is true.
if statement
to specify a block of code to be executed if the condition is false
else statement
to specify a new condition if the first condition is false.
else if statement
to select one of many code blocks to be executed.
switch statement
loops through a block of code as long as a specified condition is true
While loop
is a variant of the while loop. This loop will execute the code block once, before checking if the condition is true, then it will repeat the loop as long as the condition is true.
Do/While Loop
When you know exactly how many times you want to loop through a block of code
For loop
is a header file library that lets us work with input and output objects, such as cout. Header files add functionality to C++ programs.
include <iostream></iostream>
means that we can use names for objects and variables from the standard library.
using namespace std
This is called a function. Any code inside its curly brackets {} will be executed.
int main()
is an object used together with the insertion operator («) to output/print text. cin»_space; store/input a value(uses extraction operator)
cout
ends the main function.
return0
represents the amount of time required by the algorithm to run to completion.
Time Complexity
represents the amount of memory space required by the algorithm in its life cycle.
Space Complexity
that is a space required to store certain data and variables, that are independent of the size of the problem.
fixed part
is a space required by variables, whose size depends on the size of the problem.
variable part
refers to defining the mathematical boundation /framing of its run-time performance.
Asymptotic analysis
refers to computing the running time of any operation in mathematical units of computation.
Asymptotic analysis
is the formal way to express the upper bound of an algorithm’s running time. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete.
O(n) or Big Oh notation
is the formal way to express both the lower bound and the upper bound of an algorithm’s running time.
Theta Notation, or θ(n)
is the formal way to express the lower bound of an algorithm’s running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.
Omega Notation, or Ω(n)
An algorithm is designed to achieve optimum solution for a given problem.
-the closest solution that seems to provide an optimum solution is chosen.
Greedy Algorithm
the problem in hand, is divided into smaller sub-problems and then each problem is solved independently.
Divide and conquer approach
smallest possible sub-problem (fractions) are solved.
atomic
is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems.
-But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.
Dynamic Programming
is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used.
Dynamic Programming
allows us to execute a statement or group of statements multiple times
loop statement
In this type of loop, the test condition is tested before entering the loop body.
Entry Controlled loops
In this type of loop the test condition is tested or evaluated at the end of the loop body. Therefore, the loop body will execute at least once, irrespective of whether the test condition is true or false.
Exit Controlled Loops
is a sequence of data structures, which are connected together via links.
linked list
Each link of a linked list can store a data called an element.
Link
Each link of a linked list contains a link to the next link
Next
contains the connection link to the first link called First.
LinkedList
Item navigation is forward only.
Simple Linked List
Items can be navigated forward and backward.
Doubly Linked List
Last item contains link of the first element as next and the first element has a link to the last element as previous
Circular Linked List
