COMP 202 Midterm Review

In the Midterm

1. Binary numbers
2. Primitive Types: int, boolean, String, double
3. Type casting
4. Operations: +, -, *, /, ++, --, +=, -=, %
5. Boolean Logic: AND, OR, NOT (&&, ||, !)
6. Comparisons: >, >=, <, <=, ==, !=
7. Conditional Statements: if, else if, else
8. Loops: for and while
9. Arrays
10. Methods
11. Passing variables to methods: Primitive types, and reference types ( Arrays )
12. Sorting (not including merge sort)

NOT the Midterm

1. Complexity
2. Recursion
3. Merge sort

Binary

Interpreting decimal numbers:

Decimal numbers (base 10 numbers)

• Counting with digits -> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
• From right to left:
  • The 1nd digit is multiplied by 1 and added to the count
  • The 2nd digit is multiplied by 10 and added to the count
  • The 3rd digit is multiplied by 100 and added to the count
  • The 4rd digit is multiplied by 1000 and added to the count
  • The n-th digit is multiplied by 10^n-1 and added to the count

Interpreting binary numbers

Binary numbers (base 2 numbers)

• Counting with bits -> { 0, 1 }
• From right to left:
  • The 1nd digit is multiplied by 1 ( 2⁰ ) and added to the count
  • The 2nd digit is multiplied by 2 ( 2¹ ) and added to the count
  • The 3rd digit is multiplied by 4 ( 2² ) and added to the count
  • The 4rd digit is multiplied by 8 ( 2³ ) and added to the count
  • The n-th digit is multiplied by 2^n-1 and added to the count

This is how you convert from a binary string to a decimal string

Binary practice questions

• Convert 37 to binary
• Convert 1010111010 to decimal

Variables

Variable types and declaration

Primitive types: int, float, double, char, boolean

Literals (values): 27, 3.14159, 'r', true/false

A special type in Java: String

Declaring variables

To use variables in Java we need to declare them

TYPE variable_name;

TYPE variable_name = INITIAL_VALUE;

Operations with variables

Binary operations: variable_1 OPERATOR variable_2

• +, -, *, /, %

Unary operations:OPERATORvariable_1, variable_1OPERATOR

• ++, --

Assignments: variable_1 ASSIGNMENT_OPERATOR variable_2

• =, +=, -=, *= , /=, %=

Type Casting

Implicit (automatic) casting:

• Operations between int variables or values give an int result
• Operations between int and double variables or values give a double result
• The + operation between any primitive type and String give a String result

Type Casting

Explicit casting:

We can force our program to treat a number as having a different type

Variables practice questions

• What are the types of the following operations int n = 202; /* * What are the types of the following operations */ "hello comp " + n; n / 2.0; n / 2; "hello comp " + (n + 48);

Logical operations ( Boolean expressions, comparisons )

Boolean expressions

Boolean expressions are anything that can be evaluated to be true or false

The following are boolean expressions

• The true and false values
• Any boolean variable
• Any comparison between two variables ( yes/no answer translates to true/false values ) // for primitive types a == b; // if a and b have the same value this is true a != b; // if a and b have the same value this is false a >= b; // if a is greater or equal to b, this is true a < b; // if a is smaller than b, this is true // For strings a.equals(b); // true if both variables contain the same string
• Any combination of the previous three kinds of logical expressions, using AND (&&) and OR (||) operators A && B; // true only if both A and B are true, false in any other case A || B; // false only if both A and B are false.
• Any of the previous 4 kinds of logical expressions, using the NOT (!) operator at the beginning !A; // this takes the negation of A. if A if false, !A is true.

Boolean expressions practice questions

• What is the value of c after executing this code? int a = 3; int b = 2; boolean c = !( a > b);
• What is the value of d after executing this code? int a = 3; int b = 2; boolean c = false; boolean d = ( (a>b) && !c ) || ( c && !( a > b);

Conditional statements

Using boolean expressions to conditionally execute code

• The if statement if ( BOOLEAN_EXPRESSION){ // this will be executed only if BOOLEAN_EXPRESSION is true int a = 10; // the variable a exists only within the enclosing curly braces } // a does not exist here
• The else statement if ( BOOLEAN_EXPRESSION){ // this will be executed only if BOOLEAN_EXPRESSION is true int a = 10; // the variable a exists only within the enclosing curly braces } else { // this will be executed only if BOOLEAN_EXPRESSION is false int b = 10; } // neither a or b exist here
• The else if statement if ( BOOLEAN_EXPRESSION_1){ // this will be executed only if BOOLEAN_EXPRESSION_1 is true int a = 10; // the variable a exists only within the enclosing curly braces } else if ( BOOLEAN_EXPRESSION_2 ) { // this will be executed only if BOOLEAN_EXPRESSION_1 is false // and BOOLEAN_EXPRESSION_2 is true int b = 10; } else { // this will be executed only if BOOLEAN_EXPRESSION_1 is false // and BOOLEAN_EXPRESSION_2 is false int c = 10; } // neither a, b, or c exist here

Practice questions

In the following code,

what will be the value of result if

• SOME_VALUE = 4?
• How about if SOME_VALUE = 9?
• And if SOME_VALUE = 11?

Loops

The while loop

This works like an if statement

• While CONDITION is true, execute the code insidde the curly braces
• When CONDITION is false, continue with SOME_OTHER_CODE

The for loop

The condition variables initialized in the first part only exist within the curly braces

1. start with INITIALIZE_INDEX.
2. evaluate if CONDITION_ON_INDEX is true
   • if true, DO_SOMETHING; CHANGE_VALUE_OF_INDEX; and go back to step 2
   • if false, continue with SOME_OTHER_CODE

Loops practice questions

• Which numbers will be printed by the following code? int counter = 1; int pow = 1 while ( counter < 10 ){ System.out.println(pow); pow *= 2; counter++; }
• What is the value of c after executing this code? int c = 0; for ( int x = 0; x < 5; x++){ for ( int y = 0; y < 5; y++){ c = c + 2; } } System.out.println(c);
• Will the following code work? for ( int x = 0; x < 5; x++){ System.out.println(x); } System.out.println(x);
• Write a program that uses two loops to prints a square (Assignment 2 Warm up question 3)

Arrays

Declaring Arrays

Breaking down the declaration of an Array - 1

int: the type of the array

[]: this variable is an array

days_per_month: the variable name

{31,28,31,30,31,30,31,31,30 31,30,31}: The content of the array

Breaking down the declaration of an Array - 2

int: the type of the array

[]: this variable is an array

days_per_month: the variable name

new int: Allocating memory on the computer for this array

[12]: The length of the array (number of elements)

Accesing Arrays

Strings as Arrays

Arrays practice questions

• Write the code to reverse the elements of the test_array int[] test_array = {1,2,3,4,5,6}; for ( int i = 0 ; i < SOME_VALUE; i++){ REVERSE_ELEMENTS; } // test_array should be equal to { 5, 4, 3, 2, 1} here
• Write the code to print every character of the string, replacing every 'e' with an 'a' String name = "September"; for ( int j = 0; j < SOME_VALUE; j++){ // PRINT A CHARACTER } // the previous code should have printed Saptambar System.out.println(c);

Methods

Creating methods

Methods that do not return a value

Methods that return a value

Using methods

Passing primitive types to a method

You CANNOT change the value of a primitive type parameter inside a method

Passing reference types to a method

You CAN change the value of a reference type parameter inside a method (e.g. you can modify an array inside a method)

Methods practice question

• Write a method that takes an array as an input, and reverses its contents in place. Hints: This method should not return anything ( a void method).
• Write a method that takes an array and an integer n as an input. It should return the sum of the first n elements of the array.

Sorting and search

Linear Search

 
Given an array of N items, and a target to search
For every position i in the array {
    if the item as position i is our target{
       Finish! We found our target!
    }
}

Binary Search

 
Given an array A of N items, and a target to search
Let start = 0, end = N-1
while target not found{
    Set mid = (start + end)/2
    if A[mid] is our target{
       Finish! We found our target!
    }
    else{
        if A[mid] < target{
            set start = mid + 1
        }
        else if A[mid] > target{
            set end = mid - 1
        }
    }
}

Bubble sort!

 
Start with an unsorted array A with N items

while the array is unsorted{

    For every position between 1 and N {

        if A[i] and A[i-1] are 
        not in the correct order{

           Swap A[i] and A[i-1]

        }

    }

}

Insertion sort!

 
Start with an unsorted array A with N items

For every pos between 1 and N-1 {
    
    Let j = pos 
    Let ITEM = A[pos]
    
    While j > 0 
    and ITEM is smaller than A[j -1] {

        Set A[j] = A[j-1]
        Decrease j by 1

    }

    Set A[j] = ITEM
}

Sorting and Search practice questions

• DO ASSIGNMENT 3!!!!!!!!!!!!!!