CSE221: Algorithm Analysis & Design

Taught CSE221: Algorithm Analysis & Design during Summer 2026. This course addresses the study of efficient algorithms, their theoretical analyses, and effective algorithm design paradigms for complex computational problem-solving.

Pre-requisite: CSE220
Semester Taught: Summer 2026
Institution: BRAC University, Department of Computer Science and Engineering

Course Description

This course addresses the study of efficient algorithms, their analyses, and effective algorithm design techniques. Standard algorithm design strategies, such as Divide and Conquer, Greedy methods, Dynamic Programming, Backtracking, basic search and traversal techniques, Graph algorithms, elementary parallel algorithms, algebraic simplification and transformations, lower bound theory, and NP-hard / NP-complete problems are discussed in detail.

Examples of data structures and algorithms studied include Heaps, Hashing, Graph algorithms (shortest paths, depth-first and breadth-first search, network flow, computational geometry, minimum spanning trees), integer arithmetic (GCD, primality), polynomial and matrix calculations, advanced sorting, performance bounds, asymptotic analysis, worst-case and average-case behaviors, and correctness.

Course Objectives

• Introduce students to time and space complexity of algorithms (asymptotic analysis).
• Teach students different sorting and searching methods and provide clear criteria for evaluating their comparative efficiency.
• Familiarize students with diverse problem-solving paradigms (divide and conquer, greedy strategies, dynamic programming, backtracking, and graph algorithms).

Course Topics & Outline

• Asymptotic Analysis & Foundations: Big-O, Big-Omega, Big-Theta notations, recurrence relations, and the Master Theorem.
• Divide and Conquer Paradigm: Merge Sort, Quick Sort, selection algorithms, and recurrence solving.
• Graph Search & Traversals: Graph representations (adjacency matrix and list), Breadth-First Search (BFS), Depth-First Search (DFS), topological sort, and bipartite graphs.
• Shortest Path Algorithms: Single-source and all-pairs shortest paths (Dijkstra’s algorithm, Bellman-Ford, Floyd-Warshall).
• Minimum Spanning Trees (MST): Greedy strategy for MSTs, Kruskal’s algorithm (Disjoint Set Union) and Prim’s algorithm.
• Greedy Method: Optimal substructure, greedy-choice property, activity selection, fractional knapsack, and Huffman coding.
• Dynamic Programming: Principles of optimality, memoization vs. tabulation, longest common subsequence (LCS), 0/1 knapsack, matrix chain multiplication, and coin change.
• Backtracking: State-space trees, N-Queens problem, subset sum, and graph coloring.
• Network Flow & Geometry: Introduction to maximum flow (Ford-Fulkerson) and basic computational geometry.
• Complexity & Intractability: Polynomial time, P vs. NP, NP-completeness reductions, and lower bound theory.

Course Outcomes (COs)

• CO1: Demonstrate knowledge, understanding, and ability to identify usage of classical algorithms.
• CO2: Analyze or compare accuracy, efficiency, and complexity (time, space) of algorithms.
• CO3: Apply suitable problem-solving approaches such as sorting, searching, divide and conquer, graph theory, greedy, and dynamic programming to propose solutions to unseen or real-world problems.
• CO4: Convert algorithms into executable computer programs using preferred programming languages.

Textbooks & Reference Materials

1. Introduction to Algorithms, Charles E. Leiserson, Clifford Stein, Ronald L. Rivest, and Thomas H. Cormen, 3rd Edition, The MIT Press, ISBN: 9780262033848.
2. Algorithm Design, Jon Kleinberg and Éva Tardos, 1st Edition, Pearson, ISBN-13: 978-0321295354.
3. Algorithms, Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, 1st Edition, McGraw-Hill, ISBN: 9780073523408.
4. Algorithms Illuminated, Tim Roughgarden, 1st Edition, Soundlikecoding, ISBN: 9780999282984.
5. Lecture notes, departmental slides, and algorithm visualizations via VisuAlgo.