ECE345 — Algorithms and Data Structures

Course focuses on the design and analysis of algorithms and data structures. Traditionally a pre-requisite to do anything in software engineering. Follows ECE244 — Programming Fundamentals and ECE297 — Software Design and Communication.

We used the Introduction to Algorithms textbook by Cormen, Leiserson, Rivest, and Stein (CLRS).

Concepts covered

• Discrete mathematics
  • Logarithms and exponents
  • Fibonacci numbers
  • Summation
    • Sequence and series (arithmetic, geometric, infinite geometric)
    • Telescoping
  • Combinatorics
    • Rule of sums, rule of products
    • Combinations, permutations
    • Binomial theorem
    • Combinatorial argument
  • Proofs
    • Proof by induction
    • Proof by contradiction
• Algorithmic analysis
  • Asymptotic notation (big-O, big-Ω, big-Θ)
    • Time complexity
    • Space complexity
  • Best case, worst case, average/expected case
  • Deterministic, probabilistic algorithms
    • Monte Carlo algorithm
    • Las Vegas algorithm