Greedy Strategy and Dynamic Programming Algorithms
Module 2: Greedy Strategy
1. Huffman Coding (Data Compression)
Definition: A greedy algorithm used for lossless data compression. It assigns variable-length codes to characters based on their frequency.
Working Principle:
- Count the frequency of each character.
- Place characters in a priority queue (Min-Heap) based on frequency.
- Pick two nodes with the lowest frequencies and create a new internal node with the sum of their frequencies.
- Repeat until only one node (the root) remains.
- Assign ‘0’ to the left
AI, ML, and DL: Core Concepts and Relationships
AI, ML, and DL: Core Concepts
Correlation: AI, ML, and DL
Artificial Intelligence (AI), Machine Learning (ML), and Deep Learning (DL) are interconnected fields, each building upon the other, but they are not synonymous. AI is the broader concept of machines being able to carry out tasks in a way that we would consider “intelligent.” ML is a subset of AI that focuses on the development of algorithms that allow computers to learn from and make predictions or decisions based on data. DL is a subfield
Read MoreAI, Machine Learning, and Deep Learning: Core Concepts
The Relationship Between AI, ML, and DL
The correlation between these three fields is best understood as a hierarchical relationship where each is a sub-field of the previous one:
- Artificial Intelligence (AI): The broad field of creating systems capable of performing tasks that typically require human intelligence (e.g., reasoning and problem-solving).
- Machine Learning (ML): A subset of AI that focuses on the use of algorithms and statistical models to allow computers to learn from data without being
Python Data Science Reference: Pandas, NumPy, and Files
Python String and List Operations
Use s[start(in):stop(ex):step] for slicing. For string methods in Pandas, ensure you use .str.(strfunction).
s.upper()#Ps.lower()#ss.title()#Pys.find("P")#0s.replace("old", "new", "count")s.strip()s.startswith()s.endswith()s.split(sep, maxsplit)s.join(parts)s.count(sub, start, end)
List Methods and Comprehensions
l.append(x)l.clear()l.copy()l.count(x)l.sort()l.insert(1, "a")l.pop(x)l.remove(x)
List Comprehensions:
l = [expression for item in iterable]l = [expression
Algorithm Analysis and Complexity: A Comprehensive Reference
Asymptotic Notations
1. Big-O Notation (Upper Bound)
Definition: Big-O gives the maximum growth rate of a function, representing the worst-case complexity.
- Formula: f(n) = O(g(n)) where 0 ≤ f(n) < c · g(n) for all n ≥ n₀
- Meaning: Function f(n) does not grow faster than g(n).
- Example: 3n² + 5n + 2 = O(n²)
2. Big-Omega Notation (Lower Bound)
Definition: Big-Omega gives the minimum growth rate, representing the best-case complexity.
- Formula: f(n) = Ω(g(n)) where 0 ≤ c · g(n) ≤ f(n) for all
Artificial Intelligence Search Algorithms and CSP Methods
Search Problem Components
- State Space: All possible configurations.
- Initial State: Starting configuration.
- Successor Function: Allowed transitions between states.
- Goal Test: Checks if the state satisfies the objective.
- Cost Function (Optional): Cost per action.
- Heuristic Function (Optional): Estimate to direct search.
- Solution: Sequence of actions from initial to goal state.
- State Space Graph: Vertices are states, edges are transitions.
- Search Tree: Tree of paths explored by the algorithm.
- Node: Data structure