Algorithms Design - Week 1: Introduction to Analysis of Algorithms

Course Information

• Course Title: Algorithms Design

• Code: CS 205

• Week: 1 - Introduction to Analysis of Algorithms

• Textbook: Introduction to Algorithms, 4th Edition (2022) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

• Note: This presentation is for academic use only at Pharos University in Alexandria.

Course Textbook and Auxiliary Books

• Main Textbook:

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and Clifford Stein, “Introduction to Algorithms”, 4th Ed., MIT Press, McGraw-Hill, 2022.

• Other Useful Auxiliary Books:

  • M. T. Goodrich, I. R. Tamassia, “Algorithm Design: Foundations, Analysis, and Internet Examples”, John Wiley & sons, 2001.

  • Anani Levitin, “Introduction to the Design and Analysis of Algorithms”, 3rd Ed., Prentice Hall, 2012.

Grading Policy

• Midterm Exam: 20%

• Final Exam: 40%

• Report/Presentation: 10%

• Quizzes: 10%

• Labs:

  • Interactive: 10%

  • Lab Exam: 10% (non-interactive)

Course Objectives

• Analyze algorithms that solve specific problems and characterize their time and space complexity.

• Analyze the expected running time of a randomized algorithm whose input probabilities are well defined.

• Design modifications to a given algorithm to suit a specified situation.

Course Description

The course aims to balance theory and practice, enhancing problem-solving skills for developing efficient software systems. It uses concrete examples to demonstrate algorithm techniques, including:

• Recurrences and amortized analysis

• Randomization

• Divide-and-conquer

• Dynamic programming

• Greedy methods

• String algorithms

• Geometric algorithms

• Number-theoretic algorithms

• Complexity classes

• NP-complete problems

• Approximation algorithms

Topics Covered

• Types of complexity

• Deterministic time and complexity analysis

• Basic probability theory problems and polynomial time reducibility

• Approximation and randomized algorithms

• Dynamic programming

• Greedy Algorithms

• Amortized analysis to characterize an algorithm’s time complexity.

• String algorithms, Geometric algorithms, Number-theoretic algorithms.

• Complexity classes.

• Approximation algorithms.

What is an Algorithm?

• Any well-defined computational procedure that takes values as input and produces values as output.

• It provides a step-by-step method for solving a computational problem.

• Algorithms are not dependent on a particular programming language, machine, system, or compiler.

• They are written in pseudo-code.

Algorithm: Input -> Output

Algorithm Properties

Formal Definition: An Algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms should satisfy the following properties:

1. INPUT: Zero or more quantities are externally supplied.

2. OUTPUT: At least one quantity is produced.

3. DEFINITENESS: Each instruction is clear and unambiguous.

4. FINITENESS: The algorithm terminates after a finite number of steps.

5. EFFECTIVENESS: Every instruction must be very basic so that it can be carried out, in principle, by a person using only pencil & paper.

Algorithm Principles

• Sequence:

  • One command at a time

  • Parallel and distributed computing

• Condition:

  • IF

  • CASE

• Loops:

  • FOR

  • WHILE

  • REPEAT

Analysis of Algorithms

• Analyzing an algorithm means predicting the resources the algorithm requires.

• Resources include memory, bandwidth, but most often, it is the computational time that we want to measure.

• By analyzing several candidate algorithms for a problem, we can identify the most efficient one.

• The basic elements of algorithm analysis include: Asymptotics, Summations, and Recurrences.

Types of Algorithm Complexity

• Time complexity:

  • How much time it takes to compute

  • Measured by a function $T(N)$

• Space complexity:

  • How much memory it takes to compute

  • Measured by a function $S(N)$

Time complexity

• $N$ = Size of the input

• $T(N)$ = Time complexity function

• Order of magnitude:

  • How rapidly $T(N)$ grows when $N$ grows

  • For example: $O(N)$, $O(log N)$, $O(N^2)$ and $O(2^N)$.

Time Complexity Examples

• Bubble sort $(N^2)$

• Quicksort $(N \cdot logN)$

• $log N$: sub-linear

• $2^N$: exponential

• $N^2$: quadratic

• $N$: linear

• $N^3$: cubic

Insertion Sort Algorithm

• First, we explain the Insertion sort.

• Next, we do the analysis of this algorithm.

• It takes as a parameter an array $A[1 … n]$ containing a sequence of length $n$ that is to be sorted.

• Example: INSERTION-SORT on the array: $A = [ 5, 2, 4, 6, 1, 3 ]$

Insertion Sort Example

• Array indices appear above the rectangles, and values stored in the array positions appear within the rectangles.

• (a)–(e) The iterations of the for loop.

• In each iteration, the black rectangle holds the key taken from $A[ j ]$, which is compared with the values in shaded rectangles to its left.

• Shaded arrows show array values moved one position to the right, and black arrows indicate where the key moves to.

• (f) The final sorted array.

Insertion Sort Code

InsertionSort(A, n) {
  for i = 2 to n {
    key = A[i]
    j = i - 1;
    while (j > 0) and (A[j] > key) {
      A[j+1] = A[j]
      j = j - 1
    }
    A[j+1] = key
  }
}

Insertion Sort Run Example

Example run of the Insertion Sort algorithm with array $A = [30, 10, 40, 20]$.

The algorithm iterates, inserting elements into the sorted portion of the array. The variables $i$, $j$, and $key$ track the progress.