Three 50-minute lectures per week. No lab (3-0-3)
Designation: Required Course
Course Level: Undergraduate
Prerequisite(s) by Topic:
- Basic Algorithmic Analysis
- Fundamental Data Structures and Algorithms
- Proof Techniques
- Basic of Counting
Algorithms and Problem Solving Basic Algorithmic Analysis; Advanced Algorithmic Analysis; Advanced Data Structures Algorithms Strategies & Analysis of Fundamental Computing Algorithms; Basic Computability; The Complexity Classes P and NP.
M. Alsuwaiyel, Algorithms, Design Techniques and Analysis, World Scientific, 1999.
Reference(s) and Other Material:
- After completion of this course, the student shall be able to:
- Analyze the complexity of a given algorithm.
- Apply classical sorting, searching, optimization and graph algorithms.
- Compare, contrast, and choose appropriate algorithmic design techniques to present an algorithm that solves a given problem.
- Able to explain NP-Completeness and deal with NP-complete problems.
- Basic Concepts in Algorithmic Analysis
- Heaps and Disjoint-Sets Data Structures
- Solving Recurrence Relations: Expanding the recurrence, Change of Variable, and the Master Theorem.
- Divide and Conquer: Recursive Algorithms for Sorting, selection, Multiplication of Large Numbers and Matrices, Closest Pair Problem.
- The Greedy Approach: Fractional Knapsack, Activity Selection, Money Change, Longest Common Subsequence, Matrix-Chain Multiplication, all-Pair Shortest Paths.
- NP-Complete Problems.