Data Structures and Algorithms

Course outline

1. Unit 1 · Week 1

   Algorithm analysis

   1. Measuring an algorithm's speed
   2. Data structures, algorithms and counting operations
   3. Growth rates: O(1), O(log n), O(n) and O(n²)
   4. Big O, Big Ω and Big Θ
   5. Best, worst and average case
2. Unit 2 · Weeks 1–2

   Arrays and searching

   1. Arrays: data in a row
   2. Declaring an array: memory, indexes and addresses
   3. Arrays and the cost of their operations
   4. Linear search
   5. Binary search
3. Unit 3 · Week 3

   Insertion sort and merge sort

   1. Putting data in order
   2. Insertion sort
   3. Merging two sorted halves
   4. Merge sort
4. Unit 4 · Week 4

   Quick sort

   1. Quick sort at a glance
   2. Partitioning around a pivot
   3. Sorting both sides recursively
   4. Quick sort performance and comparing sorts
5. Unit 5 · Week 5

   Linked lists

   1. Linked lists: data in a chain
   2. Creating a node and pointing head at it
   3. Singly linked lists
   4. Inserting in the middle and at the end
   5. Deleting a node
   6. Doubly and circular linked lists
6. Unit 6 · Week 6

   Searching and sorting linked lists

   1. Finding and ordering items in a list
   2. Searching a linked list
   3. Binary search on a list
   4. Sorting a linked list
   5. Merging two sorted lists
7. Unit 7 · Week 7

   Stacks

   1. Stacks: last in, first out
   2. The stack and its array implementation
   3. A linked-list stack and bracket matching
   4. Stacks in action: function calls and undo
8. Unit 8 · Week 8

   Polish notation

   1. Writing expressions without brackets
   2. Infix, prefix and postfix
   3. Converting infix to postfix with a stack
   4. Evaluating postfix (RPN)
   5. Evaluating prefix (Polish) expressions
9. Unit 9 · Week 9

   Queues

   1. Queues: first in, first out
   2. A queue in a plain array
   3. Queues and circular queues
   4. Deques and priority queues
   5. A queue from two stacks
10. Unit 10 · Week 10

    Search trees: BST, AVL and B-trees

    1. Search trees: keeping data sorted
    2. Binary search trees
    3. Deleting from a BST
    4. AVL trees and rotations
    5. AVL double rotations: LR and RL
    6. B-trees and B+ trees (overview)
11. Unit 11 · Week 11

    Tree traversals and topological sort

    1. Visiting every node of a tree
    2. Preorder, inorder, postorder and level order
    3. Level-order traversal with a queue
    4. Directed graphs, DAGs and in-degree
    5. Topological sort
12. Unit 12 · Week 12

    Binary heaps and heap sort

    1. Heaps: the largest on top
    2. Heap shape: a tree stored in an array
    3. Heap insert: sift up
    4. Binary heaps: insert and extract
    5. Build-heap: heapify from the bottom up
    6. Building a heap and heap sort
13. Unit 13 · Week 13

    Hash tables

    1. Hash tables: finding by key
    2. Hash functions: from key to bucket
    3. Hash functions and chaining
    4. Linear probing step by step
    5. Open addressing: linear and quadratic probing
    6. Searching and deleting with probing
14. Unit 14 · Week 14

    Graphs and graph traversal

    1. Graphs: things and their connections
    2. Representing a graph
    3. Breadth-first search (BFS)
    4. Depth-first search (DFS)
15. Unit 15 · Week 15

    Minimum spanning trees and shortest paths

    1. Cheapest networks and shortest routes
    2. Spanning trees: V − 1 edges, no cycle
    3. Kruskal's minimum spanning tree
    4. Relaxing an edge
    5. Dijkstra's shortest path