DATA STRUCTURES AND ALGORITHMS Flashcards
How are arrays declared in flow charts?
+———————+
| myArray |
| |
| [0] [1] [2] |
+———————+
Explain the rule of sums, products and transitivity in big O notation.
Rule of Sums: O(f(n)) + O(g(n)) = O(max( f(n), g(n)))
If f(n) and g(n) are the time complexities of different parts of a program then the total time complexity of that program can never be greter than the longer time complexity between f(n) and g(n).
Rule of products: O(f(n)) * O(g(n)) = O(O(f(n)) * O(g(n)))
if O(f(n)) and O(g(n)) are the time complexities of two parts of a program, and are multiplied one by the other, then the total time complexity of the program is not more than O(f(n)) multiplied by O(g(n))
Rule of transitivity: If O(f(n)) = O(g(n)), and O(g(n)) = O(h(n)) then O(h(n)) = O(f(n))
What are the types of control structures in programming?
If statements, switch statements, loops, break and continue statements
What are the differences between Algorithms and computer programs
Purpose: An algorithm is only a finite set of steps to solve a problem, while a computer program is those same steps writing in a programing language both to solve the problem and to be understood by the computer
Abstract: Algorithms are abstract concepts, that focus on logical solutions to problems, while a computer program is the concrete implementation of a solution of a problem in a programming language
Portability: Algorithms since they are conceptual, can be implemented in serveral deifferent l programing languages and scenarios, while computer programs are already implemented in programming language, hence are limited to certain devices and plartforms
Execution: Algrothms are logical steps yet to be executed, where as computer programs are already implemented steps to a solution that executes said steps
Acronym: PAPEr
What are post test and pre test loops?
In pre-test loop the condition is checked before running the loop body, in a post test loop, the body is ran before the condition is checked for the first time