CS 101 – Introduction to Computer Science
Lecture Notes: Algorithms, Complexity, and Computational Thinking
I. What Is Computer Science?
Computer Science is not simply programming. Programming is a tool, while CS is the
study of:
- Computation
- Information
- Algorithms
- Ef ciency
- Abstraction
Core questions:
- What problems can be solved by computers?
- How ef ciently can they be solved?
- How should solutions be represented?
II. Algorithms
An algorithm is a nite, precise sequence of steps for solving a problem.
Key characteristics:
1. Input: Accepts zero or more inputs.
2. Output: Produces at least one result.
3. De niteness: Each step is precisely de ned.
4. Finiteness: Terminates after a nite number of steps.
fi
fi
fi
fi
fi
fi
5. Effectiveness: Each step is computationally feasible.
Algorithms are independent of programming languages.
III. Example Algorithms
A. Finding the Maximum Element in an Array
- Initialize max = rst element
- Iterate through array
- Update max when a larger element is found
- Return max
B. Linear Search
- Check each element sequentially
- Runtime grows linearly with input size
C. Binary Search
- Requires sorted input
- Repeatedly divides search space in half
- Much faster for large datasets
IV. Pseudocode
Pseudocode allows us to describe algorithms without language-speci c syntax.
Focuses on logic rather than implementation details.
Example:
fi
fi
FOR i FROM 1 TO n
IF A[i] > max THEN
max ← A[i]
V. Algorithmic Ef ciency
Ef ciency matters because:
- Computers have nite resources
- Data sizes grow rapidly
- Poor algorithms scale badly
VI. Time Complexity
Time complexity describes how runtime grows with input size n.
Common classes:
- O(1): Constant time
- O(log n): Logarithmic
- O(n): Linear
- O(n log n): Divide-and-conquer algorithms
- O(n^2): Quadratic
- O(2^n): Exponential
We usually analyze worst-case behavior.
VII. Big-O Notation Rules
- Ignore constants
fi
fi
fi
- Ignore lower-order terms
- Focus on growth rate
VIII. Space Complexity
Measures memory usage relative to input size.
Important for large datasets and embedded systems.
IX. Data Structures Overview
Common data structures:
- Arrays
- Linked lists
- Stacks
- Queues
- Hash tables
- Trees
- Graphs
Choice of data structure strongly affects performance.
X. Abstraction
Abstraction hides unnecessary details.
Examples:
- Functions
- Classes
- APIs
- Data types
Abstraction allows humans to manage complexity.
XI. Computational Thinking
Involves:
- Decomposition
- Pattern recognition
- Abstraction
- Algorithm design
These skills apply beyond programming.
XII. Limitations of Computation
Some problems are:
- Intractable (too slow)
- Undecidable (cannot be solved at all)
Example: Halting Problem.
XIII. Summary
Computer Science is about solving problems ef ciently using well-de ned processes.
Understanding algorithms and complexity is foundational to all advanced CS topics.
CS 101 – Introduction to Computer Science
Lecture Notes: Algorithms, Complexity, and Computational Thinking
fi
fi
I. What Is Computer Science?
Computer Science is not simply programming. Programming is a tool, while CS is the study of:
- Computation
- Information
- Algorithms
- Ef ciency
- Abstraction
Core questions:
- What problems can be solved by computers?
- How ef ciently can they be solved?
- How should solutions be represented?
II. Algorithms
An algorithm is a nite, precise sequence of steps for solving a problem.
Key characteristics:
1. Input: Accepts zero or more inputs.
2. Output: Produces at least one result.
3. De niteness: Each step is precisely de ned.
4. Finiteness: Terminates after a nite number of steps.
5. Effectiveness: Each step is computationally feasible.
Algorithms are independent of programming languages.
fi
fi
fi
fi
fi
fi
III. Example Algorithms
A. Finding the Maximum Element in an Array
- Initialize max = rst element
- Iterate through array
- Update max when a larger element is found
- Return max
B. Linear Search
- Check each element sequentially
- Runtime grows linearly with input size
C. Binary Search
- Requires sorted input
- Repeatedly divides search space in half
- Much faster for large datasets
IV. Pseudocode
Pseudocode allows us to describe algorithms without language-speci c syntax.
Focuses on logic rather than implementation details.
Example:
FOR i FROM 1 TO n
IF A[i] > max THEN
max ← A[i]
fi
fi
V. Algorithmic Ef ciency
Ef ciency matters because:
- Computers have nite resources
- Data sizes grow rapidly
- Poor algorithms scale badly
VI. Time Complexity
Time complexity describes how runtime grows with input size n.
Common classes:
- O(1): Constant time
- O(log n): Logarithmic
- O(n): Linear
- O(n log n): Divide-and-conquer algorithms
- O(n^2): Quadratic
- O(2^n): Exponential
We usually analyze worst-case behavior.
VII. Big-O Notation Rules
- Ignore constants
- Ignore lower-order terms
- Focus on growth rate
fi
fi
fi
VIII. Space Complexity
Measures memory usage relative to input size.
Important for large datasets and embedded systems.
IX. Data Structures Overview
Common data structures:
- Arrays
- Linked lists
- Stacks
- Queues
- Hash tables
- Trees
- Graphs
Choice of data structure strongly affects performance.
X. Abstraction
Abstraction hides unnecessary details.
Examples:
- Functions
- Classes
- APIs
- Data types
Abstraction allows humans to manage complexity.
XI. Computational Thinking
Involves:
- Decomposition
- Pattern recognition
- Abstraction
- Algorithm design
These skills apply beyond programming.
XII. Limitations of Computation
Some problems are:
- Intractable (too slow)
- Undecidable (cannot be solved at all)
Example: Halting Problem.
XIII. Summary
Computer Science is about solving problems ef ciently using well-de ned processes.
Understanding algorithms and complexity is foundational to all advanced CS topics.
fi
fi