G-E2HZ7JKCY4

Course Outline: Analysis of Algorithms

Course Code: CS-251
Credit Hours: 3 (3+0)
Prerequisites: Data Structures

Course Learning Outcomes (CLOs)

  1. Explain the concepts of best, expected, and worst-case behavior of an algorithm.
  2. Identify the characteristics of data and/or other conditions or assumptions that lead to different algorithmic behaviors.
  3. Determine the time and space complexity of simple algorithms informally.
  4. Use Big O, Omega, and Theta notation to formally provide asymptotic upper bounds on time and space complexity.
  5. Apply algorithmic strategies (brute-force, greedy, divide-and-conquer, dynamic programming) to solve appropriate problems.
  6. Solve problems using graph algorithms, including single-source and all-pairs shortest paths, and at least one minimum spanning tree algorithm.
  7. Trace and/or implement a string-matching algorithm.

At the end of this course, students will be able to:

Course Contents

  • Week 1: Introduction to Algorithms and Mathematical Foundations
  • Week 2: Growth of Functions and Asymptotic Notations
  • Week 3: Recurrence Relations and Loop Invariants
  • Week 4: Divide-and-Conquer Techniques
    • Merge Sort and Quick Sort
    • Divide-and-conquer approach vs. iterative approaches
  • Week 5: Greedy Algorithms
    • Huffman coding and activity selection
    • Solving problems using greedy algorithms
  • Week 6: Dynamic Programming – Introduction
    • Introduction to dynamic programming
    • Memoization vs. tabulation
  • Week 7: Dynamic Programming – Applications
    • Longest Common Subsequence (LCS)
    • Knapsack problem using dynamic programming
  • Week 8: Midterm Exam Preparation and Review
    • Review of key concepts from Weeks 1-7
    • Solving sample problems from each topic
  • Week 9: Graph Algorithms – Basics
    • Graph representations: adjacency list, adjacency matrix
    • Graph traversal: BFS and DFS
  • Week 10: Graph Algorithms – Shortest Paths
    • Dijkstra’s algorithm and its applications
    • Solving shortest path problems
  • Week 11: Graph Algorithms – Minimum Spanning Trees
    • Kruskal’s and Prim’s algorithms
    • Solving minimum spanning tree problems
  • Week 12: String-Matching Algorithms
    • Knuth-Morris-Pratt (KMP) algorithm
    • String-matching applications
  • Week 13: Hashing and Search Trees
    • Hash functions and hash tables
    • Binary search trees and their operations
  • Week 14: Advanced Topics in Algorithm Design
    • Approximation algorithms (e.g., Traveling Salesman Problem)
    • Real-world problems suited for approximation algorithms
  • Week 15: Algorithm Complexity Classes
    • P, NP, NP-hard, and NP-complete problems
    • Classification and significance of NP-complete problems
  • Week 16: Final Project Presentation and Course Review
    • Final project presentations
    • Review of key topics through interactive Q&A

Teaching Methodology

  • Lectures: Conceptual explanations and discussions.
  • Written Assignments: Regular problem-solving and theoretical assignments.
  • Practical Labs: Hands-on programming and algorithm implementation.
  • Semester Project: A comprehensive project applying the concepts learned throughout the course.
  • Presentations: Students present their final projects, demonstrating their understanding and implementation of algorithms.

Text Book

Reference Materials

  • Algorithm Design (1st edition, 2013/2014) by Jon Kleinberg, Eva Tardos
  • Algorithms (4th edition, 2011) by Robert Sedgewick, Kevin Wayne

Detailed Weekly Breakdown with Activities and Assignments

Week 1: Introduction to Algorithms and Mathematical Foundations

  • Introduction to algorithms and their importance in computing
  • Functions: Definition, real-life examples, domain and range, arithmetic of functions, composite functions
  • Asymptotic notations: Big-O, Big-Ω, Big-Θ, little-o, little-ω
  • Classroom Activity:
    • Discuss real-world algorithmic problems.
    • Group Activity: List areas where algorithms are applied (e.g., healthcare, logistics, AI).
  • Assignment:
    • Write a 1-2 page essay on the role of algorithms in solving real-world problems.

Week 2: Growth of Functions and Asymptotic Notations

  • Time and space complexity analysis
  • Sorting algorithm analysis
  • Loop invariants and recurrence relations
  • Classroom Activity:
    • Solve examples of Big-O, Big-Ω, and Big-Θ notations.
    • Pair Activity: Analyze the time complexity of Bubble Sort.
  • Assignment:
    • Determine the time complexity of given pseudocode using Big-O notation.

Week 3: Recurrence Relations and Loop Invariants

  • Solving recurrence relations using the Master Theorem
  • Analyzing algorithm behavior through loop invariants
  • Classroom Activity:
    • Solve recurrence relations using the Master Theorem.
    • Discuss loop invariants with practical examples.
  • Assignment:
    • Solve 3 problems involving recurrence relations and prove the correctness of a loop using loop invariants.

Week 4: Divide-and-Conquer Techniques

  • Classroom Activity:
    • Walkthrough Merge Sort and Quick Sort.
    • Compare divide-and-conquer with iterative approaches.
  • Assignment:
    • Implement Merge Sort and analyze its time complexity.

Week 5: Greedy Algorithms

  • Classroom Activity:
    • Solve the activity selection problem using a greedy approach.
    • Discuss Huffman coding.
  • Assignment:
    • Implement the activity selection problem and explain the difference between greedy and divide-and-conquer approaches.

Week 6: Dynamic Programming – Introduction

  • Classroom Activity:
    • Discuss the Fibonacci sequence and dynamic programming techniques.
    • Explain memoization vs. tabulation.
  • Assignment:
    • Write a program to compute Fibonacci numbers using dynamic programming.

Week 7: Dynamic Programming – Applications

  • Classroom Activity:
    • Solve the Longest Common Subsequence (LCS) problem.
    • Group Activity: Identify problems suitable for dynamic programming.
  • Assignment:
    • Implement LCS and solve a knapsack problem using dynamic programming.

Week 8: Midterm Exam Preparation and Review

  • Classroom Activity:
    • Review key concepts from Weeks 1-7 through a quiz and group discussions.
    • Solve sample problems from each topic.
  • Assignment:
    • Create a personal study guide summarizing all covered topics.

Week 9: Graph Algorithms – Basics

  • Classroom Activity:
    • Discuss graph representations and graph traversal algorithms.
    • Solve BFS and DFS problems.
  • Assignment:
    • Implement BFS and DFS for a given graph and analyze the time complexity.

Week 10: Graph Algorithms – Shortest Paths

  • Classroom Activity:
    • Explain Dijkstra’s algorithm with a practical example.
    • Solve a shortest path problem using Dijkstra’s algorithm.
  • Assignment:
    • Implement Dijkstra’s algorithm and test it with a weighted graph.

Week 11: Graph Algorithms – Minimum Spanning Trees

  • Classroom Activity:
    • Compare Kruskal’s and Prim’s algorithms.
    • Solve a minimum spanning tree problem.
  • Assignment:
    • Implement Kruskal’s algorithm and analyze the differences between Kruskal’s and Prim’s approaches.

Week 12: String-Matching Algorithms

  • Classroom Activity:
    • Discuss the Knuth-Morris-Pratt (KMP) algorithm.
    • Solve a string-matching problem using KMP.
  • Assignment:
    • Implement the KMP algorithm and test it with sample text and pattern inputs.

Week 13: Hashing and Search Trees

  • Classroom Activity:
    • Explain hash functions and demonstrate hash tables.
    • Discuss binary search trees and their operations.
  • Assignment:
    • Implement a hash table with chaining and traverse a binary search tree.

Week 14: Advanced Topics in Algorithm Design

  • Classroom Activity:
    • Discuss approximation algorithms (e.g., Traveling Salesman Problem).
    • Brainstorm real-world problems suited for approximation algorithms.
  • Assignment:
    • Solve the TSP using an approximation algorithm and write a report on the trade-offs.

Week 15: Algorithm Complexity Classes

  • Classroom Activity:
    • Discuss P, NP, NP-hard, and NP-complete problems.
    • Solve a sample problem and classify its complexity.
  • Assignment:
    • Research and present a real-world NP-complete problem and its significance.

Week 16: Final Project Presentation and Course Review

  • Classroom Activity:
    • Students present their final projects, demonstrating their understanding and implementation of algorithms.
    • Review key topics through an interactive Q&A.
  • Assignment:
    • Submit a final project report, detailing the algorithmic techniques used and results achieved.
Scroll to Top