Slides

Low Level vs. High Level Programming Languages

• Machine Language: Only uses 0’s and 1’s.

• Assembly Language:

  • Difficult to read.

  • Longer development time.

  • Greater control of hardware.

  • Generally runs faster.

• System Languages: Used in system programming, closer to hardware.

• High Level Language:

  • Human-readable.

  • Quicker to program.

  • Abstracts hardware details.

Compiled vs. Interpreted Programming Languages

• Interpreted Languages:

  • Converted to machine language at runtime.

  • Requires an interpreter on the computer.

  • Must distribute code.

  • Generally slower.

• Compiled Languages:

  • Converted to machine language in advance.

  • Can be executed independently.

  • Code is hidden.

  • Generally faster.

What is an Algorithm?

• A set of specific steps to accomplish a task:

  • Must be clear, precise, and in order.

  • Does not require intelligence from the executor.

• Examples of Algorithms:

  • Recipe.

  • Assembly instructions.

  • Multiplication of large numbers.

• Typically:

  • Input: Receives information.

  • Output: Produces a result.

Maximum in a List of Numbers

• Blockly Code: MaximumInList.txt

• Operational Requirement:

  • Number of operations equals the number of elements in the list.

  • Adding an item increases comparisons by one.

  • Doubling items doubles the comparisons (Linear Algorithm).

Linear Search

• Method:

  • Check each item in the list to find the target value.

• Blockly Code: LinearSearch.txt

Binary Search

• Requirements:

  • List must be sorted.

• Ideal For:

  • Searching numbers in range (1 to 1000).

  • Finding names in a phonebook or sorted lists.

• Decision Tree Example:

  • Search = [1, 1000], n ≤ 500?

Binary Search Continued

• Divide the list in half until one item remains.

• Blockly Code: BinarySearch.txt

Linear Search vs. Binary Search

• Binary Search Operational Steps Example:

  • Low, mid, high approach to find a number.

• Comparison Requirements:

  • Linear Search: Best case 1, worst case N, average linear.

  • Binary Search: Relatively fewer comparisons even as list size increases.

Comparison of Operations

• Linear Search Comparisons:

  • Best Case: 1

  • Worst Case: N

  • Doubling items doubles the comparisons.

• Binary Search Comparisons:

  • For 2 items: 1 comparison

  • For 4 items: 2 comparisons

  • For 8 items: 3 comparisons

  • Doubling items increases by 1 comparison.

  • Binary Search is a Sublinear Algorithm.

Merge Sort

• Algorithm Explanation:

  • Use balance scale to sort canisters.

• Comparison Requirement:

  • To sort 2N items:

    • t(N) comparisons for each half and 2N for merging.

• Supralinear Algorithm.

Quicksort

• Algorithm Overview:

  • Use balance scale again for sorting.

• Comparison Requirement:

  • To sort 2N items:

    • N comparisons to split into left/right.

    • t(N) comparisons for each list.

Summary of Sorting Algorithms

• Time Complexity:

  • Bubble Sort: Quadratic

  • Insertion Sort: Quadratic

  • Selection Sort: Quadratic

  • Merge Sort: Supralinear

  • Quick Sort: Supralinear

Summary of Algorithms

• Time Complexity Overview:

  • Print First Number of a List: Constant

  • Maximum of a List: Linear

  • Linear Search: Linear

  • Binary Search: Sublinear

  • Simple Sorting: Quadratic