What is Computer Science?
Computer Science is the study of computation, algorithms, and information processing. At its core, computer science asks: "What can be computed, and how efficiently can we compute it?"
Algorithms: The Heart of Computing
What is an Algorithm?
An algorithm is a step-by-step procedure for solving a problem. Every program you write implements one or more algorithms.
Properties of Good Algorithms
A good algorithm must be:
- Correct: Produces the right output for all valid inputs
- Finite: Eventually terminates
- Definite: Each step is clearly defined
- Efficient: Uses resources (time, memory) wisely
Classic Algorithms
1. Searching Algorithms
Linear Search: Check each element one by one
python
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
Binary Search: Efficiently search sorted arrays
python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Comparison:
Array size: 1,000,000 elements
Linear Search: up to 1,000,000 comparisons
Binary Search: at most 20 comparisons
2. Sorting Algorithms
Bubble Sort: Simple but slow (O(n²))
python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
Quick Sort: Much more efficient (O(n log n))
python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
Data Structures: Organizing Information
Why Data Structures Matter
Choosing the right data structure can mean the difference between:
- A program that runs in seconds vs. hours
- Using megabytes vs. gigabytes of memory
- Code that's maintainable vs. a tangled mess
Fundamental Data Structures
1. Arrays
Advantages:
- ✅ Fast random access: O(1)
- ✅ Simple to use
Disadvantages:
- ❌ Fixed size (in many languages)
- ❌ Expensive insertion/deletion: O(n)
javascript
const numbers = [1, 2, 3, 4, 5];
console.log(numbers[2]); // O(1) access
numbers.push(6); // O(1) insert at end
2. Linked Lists
Definition: Nodes connected by pointers/references
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
Advantages:
- ✅ Dynamic size
- ✅ Efficient insertion/deletion: O(1) if position known
Disadvantages:
- ❌ No random access: O(n)
3. Stacks (LIFO)
Real-world analogy: Stack of plates
python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
# Browser history example
history = Stack()
history.push('google.com')
history.push('github.com')
print(history.pop()) # github.com (going back)
Use Cases:
- Function call stack
- Undo/redo functionality
- Depth-first search
4. Queues (FIFO)
Real-world analogy: Line at a store
python
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.popleft()
def is_empty(self):
return len(self.items) == 0
Use Cases:
- Task scheduling
- Breadth-first search
- Message queues
5. Hash Tables
Definition: Maps keys to values using a hash function
python
# Python dictionary (hash table)
student_grades = {
'Alice': 95,
'Bob': 87,
'Carol': 92
}
# O(1) average case operations
print(student_grades['Alice']) # 95
student_grades['David'] = 88 # Add new
Advantages:
- ✅ Fast lookup: O(1) average
- ✅ Fast insertion: O(1) average
6. Trees
Binary Search Tree (BST):
- Left child < parent
- Right child > parent
- Fast search: O(log n) average
python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def inorder_traversal(self, node):
if node:
self.inorder_traversal(node.left)
print(node.value, end=' ')
self.inorder_traversal(node.right)
Use Cases:
- File systems
- HTML DOM
- Expression parsing
Big O Notation: Measuring Efficiency
Common Time Complexities
O(1) Constant - Array access
O(log n) Logarithmic - Binary search
O(n) Linear - Linear search
O(n log n) Linearithmic - Merge sort
O(n²) Quadratic - Bubble sort
O(2ⁿ) Exponential - Fibonacci (naive)
Visual Comparison
Operations for different input sizes:
n=10 n=100 n=1000
O(1) 1 1 1
O(log n) 3 7 10
O(n) 10 100 1000
O(n²) 100 10000 1000000
Why Algorithms Matter
Problem: Find if a number exists in an array of 1,000,000 elements
python
# O(n) - up to 1,000,000 comparisons
def linear_search(arr, target):
for num in arr:
if num == target:
return True
return False
# O(log n) - at most 20 comparisons
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
Performance difference: 50,000x faster!
Recursion
What is Recursion?
A function that calls itself as part of its execution.
Factorial:
python
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120
Fibonacci with Memoization:
python
def fibonacci_dp(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_dp(n - 1, memo) + fibonacci_dp(n - 2, memo)
return memo[n]
print(fibonacci_dp(100)) # Calculates instantly!
Computational Thinking
The Four Pillars
- Decomposition: Break problems into smaller parts
- Pattern Recognition: Find similarities
- Abstraction: Focus on important details
- Algorithms: Design step-by-step solutions
Example: Planning a Trip
Decomposition:
- Book flights
- Reserve hotel
- Plan activities
Pattern Recognition:
- Previous trips to similar destinations
- Weather patterns
Abstraction:
- Focus on essentials (passport, tickets)
- Ignore details (exact shirt to pack)
Algorithm:
- Check passport expiration
- Search flights within budget
- Compare hotels
- Create packing list
Practical Applications
Real-World Examples
Google Search:
- Data Structure: Inverted index
- Algorithm: PageRank
- Challenge: Billions of pages, millisecond response
GPS Navigation:
- Data Structure: Graph
- Algorithm: Dijkstra's shortest path
- Challenge: Real-time traffic
Netflix Recommendations:
- Data Structure: Matrix
- Algorithm: Collaborative filtering
- Challenge: Scale to millions of users
Key Takeaways
- Choose the right tool: Array vs. Linked List depends on your needs
- Efficiency matters: O(n) vs O(log n) is huge for large inputs
- Trade-offs exist: Time vs. Space, Simplicity vs. Performance
- Practice is essential: Understanding isn't enough - implement!
- Think before coding: Plan your algorithm first
Resources
Online Platforms
- LeetCode: Practice problems
- HackerRank: Challenges
- Coursera: University courses
- Khan Academy: Beginner-friendly
Books
- "Introduction to Algorithms" (CLRS)
- "The Algorithm Design Manual"
- "Cracking the Coding Interview"
- "Grokking Algorithms"
Practice Problems
- Two Sum
- Reverse a string
- Valid palindrome
- Binary search
- Merge sorted lists
Conclusion
Computer Science fundamentals are the foundation of all software development. Whether you're building a web app, training an AI model, or designing a database, these concepts apply.
Remember:
- Algorithms solve problems efficiently
- Data structures organize information effectively
- Big O helps us compare solutions
- Practice turns theory into skill
Master these fundamentals, and you'll be prepared to tackle any programming challenge!
Sources:
- "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein
- Stanford CS106B Course Materials
- MIT OpenCourseWare
- Various computer science textbooks