ICS 353: Design And Analysis Of Algorithms

​

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
Course Level: 
 Undergraduate
Prerequisites
Prerequisite(s) by Topic: 
  • Basic Algorithmic Analysis
  • Fundamental Data Structures and Algorithms
  • Recursion
  • Proof Techniques
  • Basic of Counting
Prerequisite Courses: 
ICS 202: Data Structures
ICS 253: Discrete Structures I
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.​