Sign In
 

 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: 


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