YSC2229: Introductory Data Structures and Algorithms
1. Course Syllabus
2. Software Prerequisites
3. OCaml Style Guide
1. Week 01: Introduction
2. Week 02: Working with Arrays
3. Week 03: Complexity of Algorithms and Order Notation
3.1. Generating Arrays
3.2. Complexity of Algorithms
3.3. Order Notation
3.4. Sums of Series and Complexities of Loops
3.5. Complexity of Simple Recursive Algorithms
3.6. Exercises
4. Week 04: Divide-and-Conquer Algorithms
5. Week 05: Binary Heaps and Priority Queues
6. Week 06: Abstract Data Types
7. Midterm Project: Memory Allocation and Reclamation
8. Week 07: Hashing-Based Data Structures
9. Week 08: Searching in Strings
10. Week 09: Backtracking and Dynamic Programming
11. Week 10: Data Encoding and Compression
12. Week 11: Binary Search Trees
13. Week 12: Graph Algorithms
14. Week 13: Elements of Computational Geometry
15. Final Project: Vroomba Programming
YSC2229: Introductory Data Structures and Algorithms
Docs
»
3. Week 03: Complexity of Algorithms and Order Notation
3. Week 03: Complexity of Algorithms and Order Notation
ΒΆ
3.1. Generating Arrays
3.1.1. Simple random generators
3.1.2. Measuring execution time
3.1.3. Randomised array generation and testing
3.2. Complexity of Algorithms
3.3. Order Notation
3.3.1. Big O-notation
3.3.2. Properties of Big O-notation
3.3.3. Little o-notation
3.3.4. Proofs using O-notation
3.3.5. Hierarchy of algorithm complexities
3.3.6. Complexity of sequential composition
3.4. Sums of Series and Complexities of Loops
3.4.1. Arithmetic series
3.4.2. Geometric series
3.4.3. Estimating a sum by an integral
3.4.4. Big O and function composition
3.4.5. Complexity of algorithms with loops
3.5. Complexity of Simple Recursive Algorithms
3.5.1. Complexity of computing the factorial
3.5.2. Method of differences
3.5.3. Recurrence relations
3.5.4. First-order recurrence relations
3.5.5. Inhomogeneous recurrence relations
3.6. Exercises
3.6.1. Exercise 1: Realistic Complexity of Laplace Expansion
3.6.2. Exercise 2
3.6.3. Exercise 3