Design and analysis of algorithms

[Usr6]

Lectures

• Introduction and Course Overview
  
• Analysis of Classical Algorithms
  
• Analysis of Some Sorting Algorithms
  
• Order of Growth
  
• Asymptotic Analysis: Part I
  
• Asymptotic Analysis: Part II
  
• Algorithmic Analysis
  
• Worst and Average Case Analysis
  
• Amortized Analysis
  
• Mathematical Preliminaries
  
• Summations
  
• Recurrence Relations
  
• Data Structures: Linked Lists and Graphs
  
• Data Structures: Trees
  
• Data Structures: Heaps
  
• Data Structures: Disjoint Sets and Union/Find Algorithms
  
• Data Structures: Complexity Analysis of Union/Find Algorithms
  
• Induction: General Introduction
  
• Induction: Integer Exponentiation and Polynomial Evaluation
  
• Induction: The Problem of Generating Permutations
  
• Induction: Finding the majority element
  
• Divide and Conquer: Introduction
  
• Divide and Conquer: Top-Down Merge Sort
  
• Divide and Conquer: The Selection Problem
  
• Divide and Conquer: QuickSort
  
• Divide and Conquer: Multiplication of Large Integers and Matrix Multiplication
  
• Divide and Conquer: Strassen's Algorithm
  
• Dynamic Programming: Introduction
  
• Dynamic Programming: The Longest Common Subsequence Problem
  
• Dynamic Programming: Matrix Chain Multiplication
  
• Dynamic Programming: All Pairs Shortest Path Problem and the Knapsack Problem
  
• The Greedy Approach: Introduction
  
• The Greedy Approach: Single Source Shortest Path Problem
  
• The Greedy Approach: Minimum Spanning Trees (Kruskal's Algorithm)
  
• The Greedy Approach: Minimum Spanning Trees (Prim's Algorithm)
  
• The Greedy Approach: File Compression
  
• Graph Traversal: Depth First Search
  
• Graph Traversal: Applications of Depth First Search
  
• Graph Traversal: Breadth First Search
  
• NP-Completeness: Part I
  
• NP-Completeness: Part II
  

ICS-353 Online Course