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.