Meaning of “referencing” and “dereferencing”

Referencing means taking the address of an existing variable (using &) to set a pointer variable. In order to be valid, a pointer has to be set to the address of a variable of the same type as the pointer, without the asterisk:

int  c1;
int* p1;
c1 = 5;
p1 = &c1;
//p1 references c1

Dereferencing a pointer means using the *operator (asterisk character) to access the value stored at a pointer. NOTE: The value stored at the address of the pointer must be a value of the same type as the type of variable the pointer "points" to. e.g. *p = *p +1; Note: & is the reference operator and can be read as “address of”.* is the dereference operator and can be read as “value pointed by”.

Search an element in a sorted and rotated array

#include <stdio.h>

int searchElementInRotatedArray(int arr[], int start, int end, int key) {
    while(start < end) {
        int mid = (start + end) / 2;
        if(arr[mid] == key) {
            return 1;
        }
        if(arr[start] <= arr[mid]) {
            if((key >= arr[start]) && (key <= arr[mid])) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        } else {
            if((key >= arr[mid]) && (key <= arr[end])) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return 0;
}

int main() {
    int len, num;
    printf("Enter Length of Array: ");
    scanf("%d", &len);
    int arr[len];
    printf("Enter Elements of Array: ");
    for(int loop = 0; loop < len; loop++) {
        scanf("%d ", &arr[loop]);
    }
    printf("Enter Element to Search: ");
    scanf("%d", &num);
    (searchElementInRotatedArray(arr, 0, len, num))?printf("Key Found\n"):printf("Key Not Found\n");
    return 0;
}

Solution Using Temporary Array

Input arr[] = [10, 12, 23, 40, 53, 36, 78], d = 2, n =7
1) Store d elements in a temp array
   temp[] = [10, 12]
2) Shift rest of the arr[]
   arr[] = [23, 40, 53, 36, 78, 36, 78]
3) Store back the d elements
   arr[] = [23, 40, 53, 36, 78, 10, 12]

Time complexity O(n)
Auxiliary Space: O(d)

Implementation:

#include <stdio.h>

int main() {
    long num, rot;
    scanf("%ld %ld", &num, &rot);
    unsigned long arr[num];
    unsigned temp[rot];
    for(long loop = 0; loop < num; loop++) {
        scanf("%lu", &arr[loop]);
    }
    for(long loop = 0; loop < rot; loop++) {
        temp[loop] = arr[loop];
    }
    for(long loop = rot; loop < num; loop++) {
        arr[loop - rot] = arr[loop];
    }
    long index = 0;
    for(long loop = (num - rot); loop < num; loop++) {
        arr[loop] = temp[index++];
    }
    for(long loop = 0; loop < num; loop++) {
        printf("%lu ", arr[loop]);
    }
    return 0;
}

Compare two linked lists

int CompareLists(Node *headA, Node *headB)
{
    while((headA != NULL) && (headB != NULL)) {
        if(headA->data != headB->data) {
            break;
        }
        headA = headA->next;
        headB = headB->next;
    }
    if((headA == NULL) && (headB == NULL)) {
        return 1;
    } else {
        return 0;
    }
}

Reverse a Linked-List

void ReversePrint(Node *head)
{
    Node *prev = NULL, *curr = head, *next;
    if(head != NULL) {
        while(curr != NULL) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
        while(prev != NULL) {
            printf("%d\n", prev->data);
            prev = prev->next;
        }  
    }
}

What are P, NP, NP-complete, and NP-hard?

Problems in class P can be solved with algorithms that run in polynomial time.

Say you have an algorithm that finds the smallest integer in an array.  One way to do this is by iterating over all the integers of the array and keeping track of the smallest number you've seen up to that point.  Every time you look at an element, you compare it to the current minimum, and if it's smaller, you update the minimum.

How long does this take?  Let's say there are n elements in the array.  For every element the algorithm has to perform a constant number of operations.  Therefore we can say that the algorithm runs in O(n) time, or that the runtime is a linear function of how many elements are in the array.*  So this algorithm runs in linear time.

You can also have algorithms that run in quadratic time (O(n^2)), exponential time (O(2^n)), or even logarithmic time (O(log n)).  Binary search (on a balanced tree) runs in logarithmic time because the height of the binary search tree is a logarithmic function of the number of elements in the tree.

If the running time is some polynomial function of the size of the input**, for instance if the algorithm runs in linear time or quadratic time or cubic time, then we say the algorithm runs in polynomial time and the problem it solves is in class P.

NP

Now there are a lot of programs that don't (necessarily) run in polynomial time on a regular computer, but do run in polynomial time on a nondeterministic Turing machine.  These programs solve problems in NP, which stands for nondeterministic polynomial time.  A nondeterministic Turing machine can do everything a regular computer can and more.***  This means all problems in P are also in NP.

An equivalent way to define NP is by pointing to the problems that can be verified in polynomial time.  This means there is not necessarily a polynomial-time way to find a solution, but once you have a solution it only takes polynomial time to verify that it is correct.

Some people think P = NP, which means any problem that can be verified in polynomial time can also be solved in polynomial time and vice versa.  If they could prove this, it would revolutionize computer science because people would be able to construct faster algorithms for a lot of important problems. 

Ex: Subset Sum, 0-1 knapsack etc.
 
NP-hard

What does NP-hard mean?  A lot of times you can solve a problem by reducing it to a different problem.  I can reduce Problem B to Problem A if, given a solution to Problem A, I can easily construct a solution to Problem B.  (In this case, "easily" means "in polynomial time.")

If a problem is NP-hard, this means I can reduce any problem in NP to that problem.  This means if I can solve that problem, I can easily solve any problem in NP.  If we could solve an NP-hard problem in polynomial time, this would prove P = NP.





Ex: Travelling Salesman, Subset Sum etc.
 
NP-complete

A problem is NP-complete if the problem is both

• NP-hard, and
• in NP.

Note: The interesting observation here is that, we are still unable to find a single problem that is NP, but not NP-Hard.

Sequence Control

1. Sequence control

Sequence control : the control of the order of execution of the operations both primitive and user defined.
Implicit: determined by the order of the statements in the source program
or by the built-in execution model
Explicit: the programmer uses statements to change the order of execution
(e.g. uses If statement)

1. Levels of sequence control

Expressions: computing expressions using precedence rules and parentheses.
Statements: sequential execution, conditional and iteration statements.
Declarative programming: an execution model that does not depend on the order
of the statements in the source program.
Subprograms: transfer control from one program to another.

1. Sequencing with expressions

The issue: given a set of operations and an expression involving these operations,
what is the sequence of performing the operations?
How is the sequence defined, and how is it represented?
An operation is defined in terms of an operator and operands.
The number of operands determines the arity of the operator.
Basic sequence-control mechanism: functional compositionGiven an operation with its operands, the operands may be:

• Constants

• Data objects

• Other operations

Example 1: 3 * (var1 + 5)

operation - multiplication, operator: *, arity - 2

operand 1: constant (3)

operand 2: operation addition

operand1: data object (var1)

operand 2: constant (5)

Functional compositions imposes a tree structure on the expression,
where we have one main operation, decomposable into an operator and operands.
In a parenthesized expression the main operation is clearly indicated.
However we may have expressions without parentheses.
Example 2: 3* var1 +5
Question: is the example equivalent to the above one?
Example 3: 3 + var1 +5
Question: is this equivalent to (3 + var1) + 5, or to 3 + (var1 + 5) ?
In order to answer the questions we need to know:

• Operator's precedence

• Operator's associativity

Precedence concerns the order of applying operations, associativity deals with the order of operations of same precedence.
Precedence and associativity are defined when the language is defined - within the semantic rules for expressions.
3. 1. Arithmetic operations / expressionsIn arithmetic expressions the standard precedence and associativity of operations
are applied to obtain the tree structure of the expression.
Linear representation of the expression tree:

• Prefix notation

• Postfix notation

• Infix notation

Prefix and postfix notations are parentheses-free.
There are algorithms to evaluate prefix and postfix expressions and algorithms to convert an infix expression into prefix/postfix notation, according to the operators' precedence and associativity.
3. 2. Other expressionsLanguages may have some specific operations, e.g. for processing arrays and vectors, built-in or user defined. Precedence and associativity still need to be defined - explicitly in the language definition or implicitly in the language implementation.
3. 3. Execution-time representation of expressions

• Machine code sequence

• Tree structures - software simulation

• Prefix or postfix form - requires stack, executed by an interpreter.

3. 4. Evaluation of tree representationEager evaluation - evaluate all operands before applying operators.
Lazy evaluation - first evaluate all operands and then apply operations
Problems:

• Side effects - some operations may change operands of other operations.

• Error conditions - may depend on the evaluation strategy (eager or lazy evaluation)

• Boolean expressions - results may differ depending on the evaluation strategy.

1. Statement level sequence control

4. 1. Forms of statement-level control

• Composition – Statements are executed in the order they appear on the page.

• Alternation – Two sequences form alternatives so one sequence or the other 

• sequence is executed but not both. (conditionals)

• Iteration – A sequence of statements that are executed repeatedly.

• Explicit Sequence Control

goto Xif Y goto X – transfer control to the statement labeled X if Y is true.
break4. 2. Structured programming design

1. Hierarchical design of program structures

1. Representation of hierarchical design directly in the program text 

1. using "structured" control statements.

1. The textual sequence corresponds to the execution sequence

1. Use of single-purpose groups of statements

4. 3. "Structured" control statements

1. Compound statements

Typical syntax:
begin

statement1;

statement2;

...

end;

Execute each statement in sequence.
Sometimes (e.g., C) { ... } used instead of begin ... end

1. Conditional statements

if expression then statement1 else statement2
if expression then statement1
If we need to make a choice among many alternatives
nested if statements
case statements
Example :
case Tag is

when 0 => begin

statement0

  end;

when 1 => begin

statement1

  end;

when 2 => begin

statement2

  end;

when others => begin

statement3

   end;

end case
Implementation: jump and branch machine instructions, jump table implementation for case statements (see fig. 8.7)

1. Iteration statements

Simple repetition (for loop) Specify a count of the number of times to execute a loop:
Examples:
perform statement K times;
for I=1 to 10 do statement;
for(I=0;  I<10;  I++) statement;
Repetition while condition holds
while expression do statement; - Evaluate expression and if true execute statement. then repeat process.
repeat statement until expression; - Execute statement and then evaluate expression. Quit if expression is true.
C++ for loop functionally is equivalent to repetition while condition holds
by T. Pratt and M. ZelkowitzProblems with structured sequence control:Multiple exit loops
Exceptional conditions
Do-while-do structure