CS341 Algorithms Analysis Lecture 1

Course Information

• Course Title: Algorithms Analysis and Design
• Course Code: CS341
• Lecturer: Dr. Ahmed Hamza
• Lecture Number: 1

Solving Problems (1)

• Problem Solving Steps:
  • Clearly define the problem
  • Think of possible solutions
  • Select the best solution based on prevailing circumstances
  • Apply the chosen solution
  • If the solution works, proceed; otherwise, return to step 2

Solving Problems (2)

• Common approach:
  • Solve a problem for a particular case
  • Solve for another case
  • Solve for more cases
  • Look for patterns and emerge trends
  • Develop a general solution (algorithm)

Algorithm Definition

• Algorithm:
  • A step-by-step method to solve a problem within a finite time.
  • General form, a well-defined computational procedure that takes input to produce output.
  • Input (X) → Algorithm (F: X → Y) → Output (Y = F(X))

Algorithm Examples

• Examples:
  • Repairing a lamp
  • A cooking recipe
  • Calling a friend on the phone
  • Rules to play a game
  • Directions for driving from A to B
  • A car repair manual
  • Human Brain Project
  • Internet & Communication Links (Graph)
  • Matrix Multiplication

Why Study Algorithms? (1)

• Impact:
  • Web search, packet routing, distributed file sharing (Internet)
  • Human genome project, protein folding (Biology)
  • Circuit layout, file system, compilers (Computers)
  • Movies, video games, virtual reality (Computer graphics)
  • Cell phones, e-commerce, voting machines (Security)
  • MP3, JPG, DivX, HDTV, face recognition (Multimedia)
  • Recommendations, news feeds, advertisements (Social networks)
  • N-body simulation, particle collision simulation (Physics)
  • Large discrete structures

Why Study Algorithms? (2)

• Benefits:
  • Proving algorithm termination for real-time problems
  • Identifying the best/fastest solution without coding multiple options
  • Recognizing problems that don't have practical algorithms.

Why Study Algorithms? (3)

• Reasons:
  • Programmers need to develop working solutions
  • Clients want problems solved efficiently
  • Students will potentially play various roles.
  • Theorists want to understand the problem
  • Avoid performance bugs (primary practical reason)

Why Study Algorithms? (4)

• Challenges:
  • Assessing the capability of a program to handle large inputs
  • Understanding program slowness
  • Recognizing memory issues

Algorithm vs. Program

• Program:

  • An instance/concrete representation of an algorithm in a programming language.
  • Set of instructions to solve a problem

• Algorithm:

  • A sequence of instructions describing how to perform a task

One Problem, Many Algorithms (1)

• Problem statement:

  • Defines the desired input-output relationship in general terms.
  • Doesn't need to specify all valid outputs for all inputs.
  • Uses a verifiable property of correct outputs.

• Example for Specific case (small input):

  • Checking for students who share a birthday in a classroom

• Example for general case (arbitrarily large input):

  • Checking for whether a pair of students with same birthday exists in a class of randomly selected students

• Pigeonhole Principle: If there are more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon.

One Problem, Many Algorithms (2)

• Algorithm:

  • Describes a computational procedure that maps the input to a single deterministic output.
  • Solves the problem when it returns the correct output for any specific input.

• Problem Example:

  • Sorting sequence of numbers into non-decreasing order

• Solution Algorithms:

  • Merge sort, quick sort, heap sort

Problem Instances

• Problem Instance: An input sequence
• Many problems have infinite instances
• Computer limitations require limiting possible instances (number and size

Problem-Algorithm Example

• Problem:

  • To find two students who share the same birthday and year

• Algorithm:

  1. Create an empty record for names and birthdays.
  2. Interview each student.
     • If a birthday already exists in the record, return the pair.
     • Otherwise, add the student's name and birthday to the record.
  3. Return "No such pair" if no matching birthday is found.

Properties of Algorithms

• Properties:
  • Ordered sequence of precise steps.
  • Finite well-defined instructions.
  • Unambiguous execution sequence.
  • Correctness.
  • Termination

Syntax & Semantics

• Algorithm correctness:

  • Semantics: Correct conceptual representation in the algorithm. (The soul)
  • Syntax: Correct implementation/representation of the algorithm (The body).

• Warning:

  • Syntactically correct, but semantically incorrect codes

• Easier to check syntax than semantics

Algorithm Summary

• Problem Statement: Relationship between input and output
• Algorithm: Procedure to achieve the relationship
• Definition: Steps for transforming input to output
• Instance: Needed input for solving
• Correct Algorithm: Works correctly (halts with correct output) for all inputs.

The End

Dive into the fundamentals of problem-solving in algorithms with this quiz based on the first lecture of CS341. Explore the step-by-step methods that define algorithms and learn how to identify and implement solutions effectively. Enhance your understanding of common approaches and algorithm definitions through practical examples.