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
4. Week 04: Divide-and-Conquer Algorithms
4.1. Searching in Arrays
4.2. Merge Sort
4.3. Quicksort and its Variations
4.4. Complexity of Divide-and-Conquer Algorithms
4.5. Generalising Comparison-Based Sorting
4.6. Exercises
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
»
4. Week 04: Divide-and-Conquer Algorithms
4. Week 04: Divide-and-Conquer Algorithms
ΒΆ
4.1. Searching in Arrays
4.1.1. Linear Search
4.1.2. Binary Search
4.1.3. Binary Search Invariant
4.1.4. The Main Idea of Divide-and-Conquer algorithms
4.2. Merge Sort
4.2.1. Merging two sorted arrays
4.2.2. Main sorting procedure and its invariants
4.3. Quicksort and its Variations
4.3.1. Partitioning an array
4.3.2. Partitioning in action
4.3.3. Sorting via partitioning
4.4. Complexity of Divide-and-Conquer Algorithms
4.4.1. Changing variable in recurrence relations
4.4.2. Complexity of Merge Sort
4.4.3. Complexity of Quicksort
4.4.4. The Master Theorem
4.5. Generalising Comparison-Based Sorting
4.5.1. Comparator as a parameter
4.5.2. A functor for sorting
4.6. Exercises
4.6.1. Exercise 1
4.6.2. Exercise 2
4.6.3. Exercise 3
4.6.4. Exercise 4
4.6.5. Exercise 5
4.6.6. Exercise 6
4.6.7. Exercise 7
4.6.8. Exercise 8
4.6.9. Exercise 9
4.6.10. Exercise 10