Back to courses index

SWEB450: Analysis of Algorithms

Description:Asymptotic analysis of upper and average complexity bounds; Identifying differences among best, average, and worst case behaviors; Big oh, little oh, omega, and theta notation; Standard complexity classes; Empirical measurements of performance; Time and space tradeoffs in algorithms; Using recurrence relations to analyze recursive algorithms; Algorithmic strategies including brute-force, greedy, divide-and-conquer, backtracking, branch-and-bound, heuristics and pattern matching; Introduction to P and NP. (Prerequisite: ITBP319)
Credit Hours.:3
Text Book: Anany Levitin, Introduction to The Design and Analysis of Algorithms, second edition, Pearson International Edition, ISBN 0-321-36413-9
Coordinator: Boumediene Belkhouche
Topics Outline:
  1. Review of proof techniques (SO: a)
  2. Basic algorithmic analysis: Asymptotic analysis of upper and average complexity bounds; best, average, and worst case behaviors; big-O, little-o, ?, and ? notation; standard complexity classes; empirical measurements of performance; time and space tradeoffs in algorithms; (SO: a, b, c)
  3. Recurrence relations to analyze recursive algorithms (SO: a, b, m)
  4. Fundamental algorithmic strategies: Brute-force; greedy; divide-and-conquer; backtracking; branch-and-bound; heuristics; pattern matching and string/text algorithms; numerical approximation (SO: a, b, c, n, i, j)
  5. Fundamental data structures: Implementation strategies for graphs and trees; performance issues for data structures (SO: b, c, g, i, j, k)
  6. Graph and tree algorithms: Depth- and breadth-first traversals; shortest-path algorithms (Dijkstra?s and Floyd?s algorithms); transitive closure (Floyd?s algorithm); minimum spanning tree (Prim?s and Kruskal?s algorithms); topological sort (SO: b, c, g, i, j, k)
  7. Machines and Computability (SO: a)
Outcomes:
  1. Identify the different algorithmic analysis notations.
  2. Determine the time and space complexity of algorithms.
  3. Apply recurrence relations to estimate the time complexity of algorithms
  4. Apply various algorithmic strategies to solve problems.
  5. Differentiate Non-Polynominal algorithm completeness.
Mapping of Topics Outline to Outcomes
 1 2 3 4 5 6 7
1      
2   
3   
4    
5       
Pre-requisiteITBP319: Data Structures
Volume of the Course that Contributes to CIT Students Outcomes(SOs)
Move the mouse over the Students Outcome number to view the Students Outcome text
a b c d e f g h i j k l m n
28% 15% 7% 2% 0% 0%2% 0% 12% 7% 7% 2% 7% 5%
Show Details