# COMP 110/L - Introduction to Algorithms & Programming: A Comprehensive Summary
## 1. Introduction to Computer Science and Programming
This foundational module sets the stage for the course, introducing the fundamental concepts of
computer science, problem-solving, and the role of algorithms.
* **What is Computer Science?**
* The study of computation, information, and automation.
* It encompasses theory, design, development, and application of software and hardware.
* **Algorithms:**
* A step-by-step procedure for solving a problem or accomplishing a task.
* Characteristics of a good algorithm: finite, well-defined, and effective.
* Examples: a recipe for baking a cake, a set of instructions for assembling furniture.
* **Programming Languages:**
* **High-Level Languages:** Closer to human language and easier to read and write (e.g.,
Python, Java, C++).
* **Low-Level Languages:** Closer to machine code, providing more control over the
hardware (e.g., Assembly language).
* **Compilation and Interpretation:** The processes of translating high-level code into
machine-executable instructions.
* **The Software Development Lifecycle:**
* A process for planning, creating, testing, and deploying high-quality software.
* Stages: Requirement analysis, design, implementation, testing, and maintenance.
## 2. Fundamentals of Programming
This section delves into the basic building blocks of a program, focusing on how data is stored,
manipulated, and expressed.
### 2.1. Data Types and Variables
* **Variables:** Named storage locations that hold data. The value of a variable can change
during program execution.
* **Data Types:** Define the type of data a variable can hold. Common primitive data types
include:
* **Integer (`int`):** Whole numbers (e.g., 10, -5, 0).
* **Floating-Point (`float`, `double`):** Numbers with a decimal point (e.g., 3.14, -0.001).
* **Character (`char`):** A single letter, number, or symbol (e.g., 'a', '7', '$').
* **Boolean (`bool`):** Represents true or false values.
* **Declaration and Initialization:**
* **Declaration:** Specifying the name and data type of a variable.
* **Initialization:** Assigning an initial value to a variable at the time of declaration.
### 2.2. Operators
Operators are symbols that perform operations on variables and values.
* **Arithmetic Operators:** Used for mathematical calculations.
* `+` (Addition), `-` (Subtraction), `*` (Multiplication), `/` (Division), `%` (Modulus - remainder of
a division).
* **Assignment Operators:** Used to assign values to variables.
* `=` (Assignment), `+=` (Add and assign), `-=` (Subtract and assign), `*=` (Multiply and assign),
`/=` (Divide and assign).
* **Comparison Operators:** Used to compare two values, resulting in a boolean value.
* `==` (Equal to), `!=` (Not equal to), `>` (Greater than), `<` (Less than), `>=` (Greater than or
equal to), `<=` (Less than or equal to).
* **Logical Operators:** Used to combine conditional statements.
* `&&` (AND), `||` (OR), `!` (NOT).
### 2.3. Input and Output
* **Standard Input:** Reading data from the user (e.g., keyboard).
* **Standard Output:** Displaying data to the user (e.g., screen).
## 3. Control Flow
Control flow statements allow a program to execute different pieces of code based on certain
conditions or to repeat a block of code multiple times.
### 3.1. Conditional Statements
* **`if` Statement:** Executes a block of code if a specified condition is true.
* **`if-else` Statement:** Executes one block of code if the condition is true and another if it is
false.
* **`if-else if-else` Statement:** Allows for checking multiple conditions.
* **`switch` Statement:** A multi-way branch statement that compares the value of a variable to
a list of case values.
### 3.2. Loops
* **`for` Loop:** Executes a block of code a specified number of times. It consists of an
initialization, a condition, and an increment/decrement.
* **`while` Loop:** Repeats a block of code as long as a given condition is true.
* **`do-while` Loop:** Similar to a `while` loop, but the block of code is executed at least once
before the condition is checked.
* **Nested Loops:** A loop inside another loop.
## 4. Functions
Functions are blocks of organized, reusable code that are used to perform a single, related action.
* **Function Declaration and Definition:**
* **Return Type:** The data type of the value the function returns. `void` is used if the
function does not return a value.
* **Function Name:** A unique identifier for the function.
* **Parameters (Arguments):** Input values that are passed to the function.
* **Function Body:** The block of code that defines what the function does.
* **Function Call:** Invoking a function to execute its code.
* **Return Statement:** Used to return a value from a function.
* **Scope:**
* **Local Variables:** Declared inside a function and are only accessible within that function.
* **Global Variables:** Declared outside of any function and are accessible throughout the
program.
## 5. Arrays and Strings
Arrays and strings are fundamental data structures for storing collections of data.
### 5.1. Arrays
* A collection of elements of the same data type stored in contiguous memory locations.
* **Declaration and Initialization:** Creating an array of a specific size and data type.
* **Accessing Elements:** Using an index (starting from 0) to access individual elements.
* **Multidimensional Arrays:** Arrays of arrays, used to represent tables or grids of data.
### 5.2. Strings
* A sequence of characters.
* In many languages, strings are treated as arrays of characters.
* **Common String Operations:**
* Concatenation (joining strings).
* Finding the length of a string.
* Accessing individual characters.
* Substring extraction.
## 6. Introduction to Object-Oriented Programming (OOP)
OOP is a programming paradigm based on the concept of "objects," which can contain data and
code to manipulate that data.
* **Classes and Objects:**
* **Class:** A blueprint for creating objects. It defines the properties (attributes) and
behaviors (methods) that all objects of that class will have.
* **Object:** An instance of a class.
* **The Four Pillars of OOP:**
* **Encapsulation:** Bundling data and the methods that operate on that data within a single
unit (the class).
* **Abstraction:** Hiding the complex implementation details and showing only the essential
features of the object.
* **Inheritance:** A mechanism where a new class (subclass or derived class) inherits
properties and behaviors from an existing class (superclass or base class).
* **Polymorphism:** The ability of an object to take on many forms. It allows a single interface
to be used for a general class of actions.
## 7. Introduction to Data Structures
Data structures are ways of organizing and storing data in a computer so that it can be accessed
and modified efficiently.
* **Stack:**
* A linear data structure that follows the Last-In, First-Out (LIFO) principle.
* **Operations:** `push` (add an element to the top), `pop` (remove the top element), `peek`
(view the top element).
* **Queue:**
* A linear data structure that follows the First-In, First-Out (FIFO) principle.
* **Operations:** `enqueue` (add an element to the rear), `dequeue` (remove the front
element), `peek` (view the front element).
* **Linked List:**
* A linear data structure where elements are not stored at contiguous memory locations. The
elements are linked using pointers.
* **Types:** Singly linked list, doubly linked list, circular linked list.
* **Operations:** Insertion, deletion, traversal.
## 8. Algorithms
This section focuses on common algorithms for performing essential tasks like searching and
sorting.
### 8.1. Searching Algorithms
* **Linear Search:** A simple search algorithm that sequentially checks each element of a list
until a match is found or the whole list has been searched.
* **Binary Search:** An efficient algorithm for finding an item from a **sorted** list of items. It
works by repeatedly dividing in half the portion of the list that could contain the item.
### 8.2. Sorting Algorithms
* **Bubble Sort:** A simple sorting algorithm that repeatedly steps through the list, compares
adjacent elements and swaps them if they are in the wrong order.
* **Selection Sort:** An in-place comparison sorting algorithm that divides the input list into a
sorted and an unsorted sublist, and repeatedly moves the smallest (or largest) element from the
unsorted sublist to the sorted sublist.
* **Insertion Sort:** A simple sorting algorithm that builds the final sorted array one item at a
time.
* **Merge Sort:** A divide-and-conquer algorithm that divides the unsorted list into n sublists,
each containing one element, and then repeatedly merges sublists to produce new sorted
sublists until there is only one sublist remaining.
* **Quick Sort:** A highly efficient divide-and-conquer sorting algorithm. It works by selecting a
'pivot' element from the array and partitioning the other elements into two sub-arrays, according
to whether they are less than or greater than the pivot.
## 9. Introduction to Algorithm Analysis
Algorithm analysis is the determination of the amount of resources (such as time and memory)
necessary to execute an algorithm.
* **Time Complexity:** The amount of time an algorithm takes to run as a function of the length
of the input.
* **Space Complexity:** The amount of memory an algorithm needs to run as a function of the
length of the input.
* **Big O Notation:** A mathematical notation that describes the limiting behavior of a function
when the argument tends towards a particular value or infinity. It is used to classify algorithms
according to their running time or space requirements in the worst-case scenario.
* $O(1)$: Constant time
* $O(\log n)$: Logarithmic time
* $O(n)$: Linear time
* $O(n \log n)$: Linearithmic time
* $O(n^2)$: Quadratic time
* $O(2^n)$: Exponential time
## 10. Lab Component (COMP 110L)
The lab component of the course provides hands-on experience with the concepts learned in the
lectures.
* **Programming Assignments:** Implementing the algorithms and data structures discussed in
class.
* **Debugging:** Identifying and fixing errors in code.
* **Testing:** Writing and executing tests to ensure the correctness of the code.
* **Version Control:** Using systems like Git to manage and track changes to code.
* **Integrated Development Environments (IDEs):** Using tools like Visual Studio Code, Eclipse,
or IntelliJ IDEA for writing, compiling, and debugging code.
