Computer Algorithms

Course Information

  • Semester: 4th
  • Course Code: 07-0613-CA401
  • Credits: 03
  • Course Teacher: Md Habibul Basar Faruq
  • Email: mh.faruq06@gmail.com

Course Description

This course introduces the design, analysis, and implementation of algorithms. Students will learn fundamental algorithmic techniques such as divide-and-conquer, greedy strategies, dynamic programming, and graph algorithms. The course emphasizes efficiency analysis using Big-O notation and explores NP-completeness, approximation, and randomized algorithms.

Course Outcomes

Upon successful completion of this course, students will be able to:

  • Analyze the time and space complexity of algorithms using asymptotic notations
  • Design efficient algorithms using recursion, divide-and-conquer, greedy, and dynamic programming techniques
  • Apply graph algorithms for solving shortest path, spanning tree, and network flow problems
  • Understand NP-complete problems and approaches to handle intractable problems
  • Implement approximation and randomized algorithms for complex computational tasks

Weekly Topics

  • Week 1: Introduction to Algorithms & Complexity

    • What is an algorithm? Characteristics and analysis

    • Asymptotic notations (Big-O, Big-Ω, Big-Θ)

      Get the lecture

  • Week 2: Recursion and Recurrence Relations

    • Solving recurrence relations
    • Master theorem for divide-and-conquer

  • Week 3: Divide-and-Conquer Algorithms

    • Binary search, merge sort, quicksort
    • Analysis of recursive algorithms

  • Week 4: Advanced Sorting and Searching

    • Heap sort, counting sort, radix sort
    • Lower bounds for comparison-based sorting

  • Week 5: Greedy Algorithms

    • Greedy approach principles
    • Huffman coding, activity selection, minimum spanning trees (Kruskal, Prim)

  • Week 6: Dynamic Programming

    • Overlapping subproblems and optimal substructure
    • Examples: Matrix chain multiplication, longest common subsequence, knapsack

  • Week 7: Graph Algorithms I

    • BFS, DFS
    • Connected components, topological sorting

  • Week 8: Graph Algorithms II

    • Dijkstra’s algorithm, Bellman-Ford
    • Floyd-Warshall for all-pairs shortest paths

  • Week 9: Network Flow Algorithms

    • Ford-Fulkerson algorithm
    • Applications of max-flow

  • Week 10: String Matching Algorithms

    • Naive matching, KMP algorithm
    • Rabin-Karp hashing approach

  • Week 11: NP-Completeness and Reductions

    • P vs NP, NP-complete problems
    • Examples: SAT, Vertex Cover, Traveling Salesperson

  • Week 12: Approximation Algorithms

    • Approximation ratio
    • Approximation for NP-hard problems (e.g., TSP, vertex cover)

  • Week 13: Randomized Algorithms

    • Randomized quicksort, Monte Carlo and Las Vegas algorithms

  • Week 14: Advanced Topics

    • Parallel algorithms, streaming algorithms basics

  • Week 15: Course Review and Final Examination

Assessment Components

  • Assignments and Quizzes – 20%
  • Midterm Exam – 20%
  • Final Exam – 50%
  • Class Participation – 10%

Suggested Textbooks and References

  • Introduction to Algorithms – Cormen, Leiserson, Rivest, and Stein (CLRS) (Get the book)
  • Algorithms – Robert Sedgewick and Kevin Wayne
  • Algorithm Design – Jon Kleinberg and Éva Tardos
  • Online resources: MIT OCW 6.046J, Stanford CS161