WEEK 2 Foundations of Algorithm Analysis

Algorithms and their Applications

Course Overview

  • Course Code: CS2004 (2024-2025)
  • Instructor: Dr. Mahir Arzoky
  • Relevant Concept: Foundations of Algorithm Analysis

Laboratory Sessions

  • Number of Sessions: Two per week
  • Schedule:
    • Laboratory 1: Mondays 11:00 to 13:00
    • Laboratory 2: Mondays 13:00 to 15:00
  • Location: In-person only at TOWA 407
  • Other Notes:
    • Stick to your own laboratory session
    • Intro and demonstrations at the beginning of each session

Laboratory Worksheets

  • Worksheet 1: Java Programming Environment (2024-2025)
  • Worksheet 2: Simple Algorithms (2024-2025)

Knowledge Resources

  • Knowledge Bank Folder: Contains essential materials for the module, programming, mathematics, and CodeRunner Assessment. Updates will be provided throughout the module.

Java Programming Tutorials

  • Tutorials Overview: Cover basic programming concepts, important for upcoming modules:
    • Tutorial 1: Eclipse (Starts 22 Sep)
    • Tutorial 2: Classes and Objects (Starts 22 Sep)
    • Tutorial 3: Variables (Starts 22 Sep)
    • Tutorial 4: Control Statements (Starts 22 Sep)
    • Tutorial 5: Arrays and ArrayLists (Starts 22 Sep)
    • Tutorial 6: Main Methods (Starts 22 Sep)
    • Tutorial 7: Java String Class (Starts 22 Sep)
    • Tutorial 8: Recursion (Starts 22 Sep)

Mathematical Foundation

  • Importance in Computer Science: Mathematics is fundamental for designing and analyzing algorithms; it underpins computational complexity which helps understand efficiency:
    • Key Concepts:
    • Discrete mathematics
    • Logic
    • Probability
    • Graph theory

Course Content

Analysis and Implementation of Algorithms
  • Focus: On analysis, implementation, and development of complex algorithms.
  • Topics Covered:
    • Basics of algorithms and computation
    • Key concepts: Running time, Pseudo-Code, Counting primitive operations
Comparing Algorithms
  • Criteria: Efficiency of algorithms measured by:
    • Time taken
    • Resources consumed
  • Types of Running Time:
    • Best case
    • Worst case
    • Average case

Running Time of Algorithms

  • Variation in Running Time: Increases with input size, impacts performance:
    • Best Case: Rarely informative
    • Worst Case: Focus is primarily on this for real-time applications.

Experimental Studies

  • Procedure: Implement the algorithm and measure performance:
    • Vary input sizes and compositions with a method like System.currentTimeMillis() to measure actual running time.
  • Limitations: Results may be indicative of performance on some but not all inputs. Consistent hardware and software environments are required for valid comparisons.

Asymptotic Analysis

  • Definition: A high-level performance evaluation based on input size rather than practical implementation.
  • Big-Oh Notation: Used to denote the upper limit of an algorithm's running time.

Pseudo-Code Basics

  • Introduction: A blend of programming language and written text used to outline algorithms.
  • Structure:
    • Input/Output definitions
    • Line numbering
    • Control flows: If-Then-Else, While loops, For-each loops

Examples of Pseudo-Code

  • Algorithm Examples: Demonstrating common structures:
    1. UselessAlgorithm: Incrementing an integer.
    2. Sign: Determines the sign of a number.
    3. Sum: Sums all integers from 1 to n.
    4. ArrayMax: Finds maximum in a 1-D array and then in a 2-D array.

Primitive Operations

  • Definition: Basic computations identifiable in Pseudo-Code such as evaluating expressions, variable assignments, and array indexing.
  • Counting Operations Example: Evaluating lines of Pseudo-Code to infer algorithm performance:
    • Estimate total operations as a function of input size (n).

Counting Primitive Operations

  • Determine the maximum number of operations executed based on input size:
    • Example: For finding maximum in a 2-D array, total operations can be represented as T(n,m).

Next Steps in Course

  • Upcoming Topics: Detailed analysis of Time Complexity, Big-O, T(n), and practical implementation of algorithms in labs.
  • Mathematical Requirements: Understanding is essential for success in laboratory exercises and future concepts.