## ICS 353: Design And Analysis Of Algorithms

Course Information

Class/Laboratory Schedule:

Three 50-minute lectures per week. No lab (3-0-3)

Designation:   Required Course

Prerequisites

Prerequisite(s) by Topic:

• Basic Algorithmic Analysis
• Fundamental Data Structures and Algorithms
• Recursion
• Proof Techniques
• Basic of Counting

Prerequisite Courses:

Catalog Description:

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.

Textbook(s):

M. Alsuwaiyel, Algorithms, Design Techniques and Analysis, World Scientific, 1999.
Reference(s) and Other Material:
N/A

Course Outcomes:

• 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.

Topics Covered:

• 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.​