I.
Terminology
Basic Concepts and Notation
Programming – a problem solving process.
Problem domain - Focuses on input (raw data), output (processed data), and tasks like sorting.
• Raw data – set of numbers in the original order.
• Processed data – sorted numbers
Machine domain - Includes storage (bits in memory) and processing (performing operations).
• Storage medium – consist of serially arranged bits that are addressable as a unit.
• Processing unit – allow us to perform basic operation.
Solution domain - links the problem and machine domains.
Data type – kind of data that variables can assume in a programming language and for which operations are
automatically provided.
Abstract data type (ADT) – mathematical model with defined operations. In Java it can be expressed with an
interface.
Data structure – The implementation of ADT in terms of the data types or other data structures.
• In Java – it can be expressed with a class.
Algorithm – Finite set of instructions which, if followed, will accomplish a task.
• Finiteness – an algorithm must terminate after a finite number of steps.
• Definiteness – ensured if every step of an algorithm is precisely defined.
• Input – domain of the algorithm which could be zero or more quantities.
• Output – set of one or more resulting quantities; also called the range of the algorithm.
• Effectiveness – ensured if all the operations in the algorithm are sufficiently basic that they can, in
principle, be done exactly and in finite time by a person using paper and pen.
Addressing Methods
• Computed Addressing Method – used to access the elements of a structure in pre – allocated space.
• Link Addressing Method – used to manipulate dynamic structures where the size and shape are not
known beforehand or changes at runtime.
• Memory Pool or avail list – source of the nodes from which linked structures are built.
Mathematical Functions
• Floor of x (└x┘) – greatest integer less than or equal to x.
• Ceiling of x (┌x┐) – smallest integer greater than or equal to x.
• Modulo – remainder operator. (mod)
Complexity of Algorithm
• Space utilization – amount of memory required to store the data.
• Time efficiency – amount of time required to process the data.
o Execution time – amount of time spent in executing instructions of a given algorithm.
• The Big-Oh Notation (O-Notation) – how the time or space needed by an algorithm grows as the size of
the input increases.
o T(n) grows at a rate proportional to n and thus T(n) is said to have “order of magnitude n”
denoted by the O – notation as T(n) = O (n).
Arrays
Arrays - objects that help us organize large amounts of information.
- An ordered list of values.
- stores multiple values of the same type (the element type).
Bounds Checking
- Once an array is created, it has a fixed size.
- An index used in an array reference must specify a valid element. (0 to N – 1).
Arrays as Parameter
- entire array can be passed as a parameter to a method.
- the reference to the array is passed, making the formal and actual parameters aliases of each other.
- changing an array element within the method changes the original.
- array element can be passed to a method as well, and follows the parameter passing rules of that
element's type.
Arrays of Object
- elements of an array can be object references.
- It does NOT create the String objects themselves.
- Each object stored in an array must be instantiated separately.
Array elements - the values held in an array.
Array declaration – names the array and specifies the type of its element.
Initializer list – used to instantiate and initialize array in one step.
- values are delimited by braces and separated by commas.
- the size of the array is determined by the number of items in the initializer list.
Linked List
Linked list – is a collection of components, called nodes. Every node (except the last node) contains the address
of the next node.
o Singly – linked list
o Doubly – linked list
Info – stores relevant information.
Link/next – stores the address.
Recursion
Recursion – a definition in terms of itself.
In Algorithm
- Natural approach to some problems.
- Recursive Algorithm – uses itself to solve one or more smaller identical problems
In Java
- Recursive methods implement recursive algorithms
- Recursive method – includes a call to itself
◼ A recursive method must have a least one base, or stopping case.
A base case does not execute a recursive call --- stops the recursion.
Each successive call to itself must be the “smaller version of itself”.
Decomposition (N – 1) – ability to break down a problem into smaller/simpler components that can be easily
implemented and tested. (smaller identical problem)
Composition (* N) – complex structure is built using simpler data structures. (answers in a smaller problem
forming an answer to a larger problem)
Base/stopping case (1!) – the condition that allows the algorithm to stop recursing.
Fibonacci numbers – Nth Fibonacci number is the sum of the previous two Fibonacci numbers.
0, 1, 1, 2, 3, 5, 8, 13…
Complexity Time Ascending Order
1.) O(1)
2.) O(log₂ log₂ n)
3.) O(log₂ n)
4.) O(n)
5.) O(n log₂ n)
6.) O(n₂ᶺ2)
7.) O(nᶺ2 log₂ n)
8.) O(nᶾ)
9.) O(2ᶺn)
10.) O(nᶺn)
Execution time and Time complexity
void black(int a[][], int b, int c){ line of code time executed
for(int x=1; i<=c; I++) 2 n+1
for(int y=1; y<=c; y++) 3 n+1
a[x][y] = b[x][y]; 4 n
for(int x=1; i<=c; x++) 5 n+1
for(int y=1; y<=c; y++) 6 n+1
for(int z=1; z<=c; z++) 7 n+1
if( a[x][y] = 0) a[x][y] = a[x][z] & a[z][y]; 8 n
n+1 (2nᶺ3+5nᶺ2+4n+2)( 2nᶺ2 + 3n + 1)
n+1 =2nᶺ3+7nᶺ2+7n+n
n the time complexity is T(n) = O(nᶾ)
2nᶺ2 + 3n + 1
n+1
n+1
n+1
n
2nᶺ3+5nᶺ2+4n+2 – whole loop
