Lecture on Computer Science and Algorithms

Introduction

• Lecture focused on understanding algorithms and their efficiency.
• Emphasis on analyzing running time and efficiency of algorithms.

Key Concepts

• Running Time: Measure of how long an algorithm takes to execute.
• Big O Notation: Used to describe an upper bound on the running time of an algorithm. Examples: O(n), O(log n), O(1)
• Big Omega (Ω) Notation: Describes a lower bound on the running time of an algorithm.
• Big Theta (Θ) Notation: Used when an algorithm's upper and lower bounds are the same.
• Efficiency: Refers to both the speed of execution and resource use, like memory.

Algorithms

Linear Search

• Search method where you check each element one by one until you find the target or reach the end.
• Efficiency:
  • Worst-case: O(n)
  • Best-case: Ω(1)
• Implementation: Use loops to iterate through elements.

Binary Search

• More efficient than linear search but requires sorted data.
• Works by repeatedly dividing the dataset in half and eliminating the half that does not contain the target.
• Efficiency:
  • Worst-case: O(log n)
  • Best-case: Ω(1)

Pseudo Code for Searches

• Example of Linear Search Pseudo Code:
  • For each element in the array:
    • If element is the target, return true.
    • Else, at the end, return false.
• Example of Binary Search Pseudo Code:
  • Check middle element:
    • If equals target, return true.
    • If less, search left half.
    • If more, search right half.
    • If no elements left, return false.

Sorting Algorithms

• Selection Sort: Find the smallest element and place it at the beginning, repeat for each position.
• Efficiency: Not mentioned; focus was on demonstrating sorting conceptually.

Use of Data Structures

Arrays and Strings

• Arrays are contiguous memory locations used to store multiple values.
• Used for storing strings by defining an array of characters.

Custom Data Types

• Structs: Used in C to define new data types with multiple fields.
• Example: Define a person struct with fields for name and number.

Debugging

• Techniques to find and fix bugs in code.
• Use of printf, Debugger tools, and Rubber Duck Debugging.
• Debugger allows stepping through code to understand execution.

Conclusion

• Understanding how to measure algorithm efficiency is crucial.
• Recognizing when to use different search and sort techniques can optimize performance.