Design And Analysis Of Algorithms (CCOM5050)

Latest Course Syllabus-ABET Style () (PDF)

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