CSE 2207 : Algorithms

Conducted CSE 2207 Spring 2023 and CSE 2208 Fall 2022, Spring 2023, Fall 2023 with Mr. Md. Khairul Hasan.

Syllabus for CSE 2207 and it’s corresponding sessional course CSE 2208:

1. Algorithmic Complexity Analysis:

   • Understanding how the efficiency of an algorithm scales with input size.
   • Analyzing time and space complexity.
   • Big O notation and other complexity measures.

2. Design Methods for Efficient Algorithms:

   • Divide and Conquer:
     • Breaking down a problem into smaller subproblems and solving them independently.
     • Examples: Merge sort, quicksort.
   • Greedy Method:
     • Making locally optimal choices at each step to achieve a global optimum.
     • Examples: Huffman coding, Dijkstra’s algorithm.
   • Dynamic Programming:
     • Solving problems by breaking them into overlapping subproblems and storing intermediate results.
     • Examples: Fibonacci sequence, shortest path problems.
   • Backtracking:
     • Exploring all possible solutions by trying different options and undoing choices when necessary.
     • Examples: N-queens problem, Sudoku.
   • Branch and Bound:
     • Systematically exploring the solution space by pruning branches that cannot lead to an optimal solution.
     • Examples: Traveling salesman problem, 0/1 knapsack.
   • Polynomial Evaluation:
     • Efficiently evaluating polynomials using techniques like Horner’s method.
   • Lower Bound Theory:
     • Determining the minimum resources (time or space) required to solve a problem.
   • Intractable Problems:
     • Problems for which no efficient algorithm exists (NP-hard, NP-complete).