Module content & resources                                                                                                                      2
                                                                                                                                                                          Learning objectives                                Materias                                           Reference text 
                                                                                                                                                                          •  Elementary data structures:                     Slides 
                                                                                                                                                                             arrays, stacks, queues, linked 
                                                                                                                                                                             lists 
                                       B16 Software Engineering                                                                                                           •  Binary Trees                                    Notes 
                                       Algorithms and Data Structures 1                                                                                                   •  Binary Search Trees                             •  PDF & HTML versions 
                                       Lecture 1 of 4: Recap on complexity, quasilinear and linear sort,                                                                  •  Heaps                                           •  Include optional content 
                                       elementary data structures (arrays, stacks, queues, linked lists) 
                                                                                                                                                                          •  Priority Queues                                 Examples 
                                       Dr Andrea Vedaldi                                                                                                                  •  Hashing                                         •  PDF & HTML versions 
                                       4 lectures, Hilary Term                                                                                                                                                                                                                                                 
                                                                                                                                                                          •  Locality Sensitive Hashing                      •  Include optional content 
                                       For lecture notes, tutorial sheets, and updates see                                                                                •  Graphs 
                                       http://www.robots.ox.ac.uk/~vedaldi/teach.html                                                                                                                                        Source code for the examples                       Introduction to Algorithms, 3rd 
                                                                                                                                                                          •  Shortest paths                                                                                     Edition. Cormen, Leiserson, 
                                                                                                                                                                                                                                                                                Rivest, Stein. McGraw-Hill, 1990.
                                                                                                                                                                                                                                                                                                                          4
                                       B16 Software Engineering                                                                                                                                        Problem                                                                   Algorithm 
                                       Algorithms and Data Structures 1                                                                                                          A problem is a description of the input data, the                           An algorithm is a description of computational 
                                       Lecture 1 of 4: Recap on complexity, quasilinear and linear sort,                                                                         output data, and the relationship between them.                              steps that generate the output data from the 
                                       elementary data structures (arrays, stacks, queues, linked lists)                                                                                                                                                           input data, thus solving the problem.
                                       Dr Andrea Vedaldi 
                                       4 lectures, Hilary Term 
                                       For lecture notes, tutorial sheets, and updates see 
                                       http://www.robots.ox.ac.uk/~vedaldi/teach.html
            Sorting problem [revision]                                                                                                                      5             Merge Sort [revision]                                                                                                                           6
            Problem definition                                                           Problem instance                                                                 MergeSort(A):                                                                Merge(B,C): 
            •  Input: A sequence A = (A ,A ,…,A                    )                     •  Input:      A=(5,4,3,2,1)                                                     1. If |A| = 1, return                                                        1. Let i ← 0 and j ← 0
                                                 0   1         n−1                                                                                                        2. Let i ← ⌊|A|/2⌋                                                           2. Reserve space for a sequence A of |B| + |C| 
            •  Output: The same sequence, but permuted so that                           •  Output:  A = (1,2,3,4,5)                                                      3. Let B ← (A ,…,A               )                                               elements
                                                                                                                                                                                             0         i−1                                             3. While i < |B| and j < |C|:
                                                                                                                                                                          4. Let C ← (A,…,A                  )
               A      ≤A for i=1,…,n−1                                                                                                                                                       i         |A|−1
                 i−1       i                                                                                                                                                                                                                               1. If B ≤ C:
                                                                                                                                                                          5. Call MergeSort(B)                                                                     i      j
                                                                                                                                                                                                                                                               1. Set A       ←B and i ← i+1
                                                                                                                                                                          6. Call MergeSort(C)                                                                            i+j       i
                                                                                                                                                                          7. Set A ← Merge(B,C)
                                                           2. Else:
                                                                                                                                                                                                                                                               1. Set A       ←C and j ← j+1
                                                                                                                                                                                                                                                                          i+j       j
                                                                                                                                                                                                                                                       4. While i < |B|:
                                                                                                                                                                                                                                                           1. Set A       ←B and i ← i+1
                                                                                                                                                                                                                                                                      i+j       i
                                                                                                                                                                                                                                                       5. While j < |C|:
                                                                                                                                                                                                                                                           1. Set A       ←C and j ← j+1
                                                                                                                                                                                                                                                                      i+j       j
                                                                                                                                                                                                                                                       6. Return A
            Merge Sort: example [revision]                                                                                                                  7             Complexity [revision]                                                                                                                           8
                                                                                                                                                                          We characterise the speed of an algorithm as follows:                        Worst-case complexity 
                                                                 divide                                                                       merge                       •  Let n be a parameter characterising the size of the                       f(n) is the largest possible number of steps to solve 
                    2    7    6    3   5    8    4    1                                            1    2    3   4    5    6    7    8                                       input 
                                                                                                                                                                          •  We study the number of steps f(n) that an                                 any problem instances of size n 
                                                                                                                                                                             algorithm requires to solve the problem                                   Average-case complexity 
                    2    7    6   3    5    8    4    1                                            2    3   6    7    1    4    5   8
                                                                                                                                                                                                                                                       f(n) is the average possible number of steps to solve 
                    2    7    6   3    5    8    4    1                                            2   7    3    6    5    8   1    4                                                                                                                  problem instances of size n  
                                                                                                                                                                                                                                                       This requires defining a probability distribution over 
                    2    7    6   3    5    8    4    1                                            2   7    6    3    5    8   4    1                                                                                                                  problem instances 
          Complexity [revision]                                                                                                 9          Merge Sort: work done [revision]                                                                                     10
          Big-O notation                                                 Big-Θ notation                                                                                                     n
          We say that f(n) is Big-O of g(n) iff there are constant       We say that f(n) if Big-Θ of g(n) iff it is                                                                                                          divide & merge    total work
          n ,a such that                                                                                                                               1 sequence of size 8                                                       1 × 8            8
           0                                                             simultaneously Big-O and Big-Ω of g(n)
          ∀n≥n :f(n) ≤ ag(n)                                                                                                                           2 sequences of size 4
                  0                                                                                                                                                                                                               2 × 4            8
          Big-Ω notation                                                                                                                                                                                             log2n
                                                                                                                                                       4 sequences of size 2                                                      4 × 2            8
          We say that f(n) is Big-Ω of g(n) iff there are constant 
          n ,a such that                                                                                                                               8 sequences of size 1
           0                                                                                                                                                                                                                      8 x 1            8
          ∀n≥n :f(n) ≥ ag(n) 
                  0
                                                                                                                                                                                        O(nlogn)
          Merge Sort: complexity [revision]                                                                                    11          How fast can you sort?                                                                                               12
          Recurrence relation                                            Solution of the recurrence relation                               A class of sorting algorithms                                  A counting argument 
          Merge Sort called on a sequence of length n = |A|:             The solution of of the recurrence equations is                    Algorithm ������(A) only accesses the input sequence A             There are n! possible permutations A of the sequence 
          • Calls itself recursively on sequences of size n/2                                                                              by observing the results of pairwise comparisons               (1,2, …,n) 
                                                                             f(n) = n(log n + 1)                                           A