**Credits:** 3

**Students should take this course at:** 3rd Year - 2nd Semester
**Pre-requisite:**
Data Structures (CCOM3034), Discrete Mathematics (CCOM3020) and Calculus 2 (MATE3152)

Description

In this course general and advanced techniques for the design and analysis of algorithms are discussed. Topics included: mathematical induction, asymptotic notation, worst-case analysis, recurrence relations and their closed form solutions, sorting and search algorithms, randomized algorithms, parallel algorithms, proof of correctness, advanced design techniques, advanced data structures, graph algorithms, np-completeness.

Content

Summations

Mathematical Induction

Set, Functions and Relations

Roles of Algorithms

Introduction to the Design of Algorithms: Divide–and–Conquer

Growth of Functions

Recurrences

Heapsort

Quicksort

Sorting in Linear Time

Elementary Data Structures

Hash Tables

Binary Search Trees

Red–Black Trees

Elementary Graph Algorithms

Minimum Spanning Trees

Single–Source Shortest Paths

All–Pairs Shortest Path

Matrix Operations

NP–Completeness

Objectives

Understand asymptotic notation, its properties and use in measuring algorithm behavior

Determine asymptotic expressions for the worst-case execution time and space requirements of algorithms and data structures

Understand the process of proving algorithm correctness and provide proofs for classical algorithms studied in the course and similar ones

Understand the importance of a data structure in providing efficient algorithms to solve a particular problem

Know the different strategies that are known to be useful in finding efficient algorithms to solve problems and to be able to apply them

Be able to establish comparisons among different solutions and deciding circumstances when one may be better

Understand the concepts of parallel algorithms and the influence of the different parallel computer architectures

Understand the concepts of computational complexity and its use in categorizing problems in terms of their computational requirements, and to know about different techniques to cope with hard problems

Be able to use mathematical language and do elementary proofs

Create algorithms to solve problems