Untitled Quiz

Course Information

• Course: CS341 Algorithms Analysis and Design
• Lecture: 2
• Instructor: Dr. Ahmed Hamza

Algorithm Recap

• Problem Statement: Defines the input/output relationship
• Algorithm: A procedure achieving the relationship
• Definition: A sequence of steps to transform input into output
• Instance: The input needed for computing the solution
• Correct Algorithm: For every input, it halts with the correct output

Brief History of Algorithms

• The study began with mathematicians seeking a general algorithm for each problem type
• Named after Abu Abdullah Muhammad ibn Musa al-Khwarizmi, a 9th-century Persian mathematician
• Dar al-Hikma (House of Wisdom) translated and published scientific and philosophical works, including Greek texts

Al-Khwarizmi's Golden Principles

• Principle 1: Break down complex problems into smaller sub-problems.
• Principle 2: Organize sub-problems to be solved independently.
• Principle 3: Solve sub-problems in a specific order.
• Principle 4: Combine sub-problem solutions to yield the original problem's solution.

Algorithmic Successes (Discrete Fourier Transform)

• Breaks down a waveform into periodic components
• Applications include DVD, JPEG, MRI, and astrophysics.
• Brute force: N² steps
• FFT algorithm: N log N steps, enabling new technologies
• Developed by Friedrich Gauss (1805)

Algorithmic Successes (N-body Simulation)

• Simulates gravitational interactions between N bodies
• Brute force: N² steps
• Barnes-Hut algorithm: N log N steps, enabling new research
• Developed by Andrew Appel (PU '81)

Why Algorithms are Useful

• Re-usable solutions to recurring problems.
• Following instructions precisely solves problems without additional thinking.
• All problem-solving knowledge is directly within the algorithm.

Why Write Algorithms Down

• Future re-use without needing to rediscover the solution
• Modification and Improvement
• Easy explanation to others

Why Analyze Algorithms

• Proving algorithms complete within a given time frame
• Identifying the fastest solution to a problem without coding and testing different algorithms
• Knowing problem complexity classes and avoiding wasted time on problems impossible on practical devices

But Computers Are So Fast These Days

• Computational demands in many problems remain
• Speed and efficiency remain necessary

Algorithms Must be Analyzed

• Classify problems and algorithms by complexity
• Predict performance and comparison of algorithms for parameter tuning
• Enhance understanding and improve implementations and algorithms

Importance of Analyzing Algorithms (1)

• Limiting various algorithms for a problem
• Understanding the relationship between problem size and running time.
• Learning about algorithm's running time without coding.
• Evaluating techniques to write efficient code and identifying bottlenecks to optimization

Importance of Analyzing Algorithms (2)

• Array-based list retrieve operation takes at most one operation, while a linked-list-based list retrieve operation takes at most N operations.
• Insert/delete are easier on linked list implementations.
• ADT implementation selection should consider frequency of operations.
• Efficiency consideration is optional for small problem sizes.
• Tradeoffs are to be considered between algorithms, time requirements and memory requirements.

What do we Analyze about Algorithms

• Algorithm behaviour and improvement
• Correctness: Matching of input/output to algorithm requirements?
• Amount of Work: Basic operations for the task
• Amount of Space: Memory usage
• Simplicity: Clear to understand.
• Verification/ Implementation
• Optimality: Is there a better solution and/or more efficient way?