CS5350 Advanced Algorithms

This course provides a review of mathematical techniques for analysis of computer algorithms, techniques for design of efficient algorithms, description and analysis of both well-established and recently developed algorithms.

The objective of this course is for students to become aware of the appropriateness of algorithms as solutions to given problems, of their efficiency, and to be able to discuss and justify solving techniques. Students will be able to implement algorithms adapted to the problems at hand. They will know how to communicate to team members the features of a given problem along with the solution they propose with its justification.

The syllabus can be found here.

Assignment 1: In any reasonable programming language write the following functions

• A fold function that takes an array (list) and its size in argument, as well as a seed and a function and that folds the array with the function, starting with the seed. The fold function needs to be recursive. You must then instantiate the fold function to make it a sum function, a product function, a minimum and a maximum function.
• A k-minimum function that returns the k minimal values (the minimum, the second but minimum value, etc.) of an array (list) of n elements. The function can be recursive but does not need to be recursive. You should make the function optimal in terms of complexity, for varying values of k and n.
• A merge sort function.
• A multiplication function that takes an array a of n positive or zero integer digits, an array b of n positive or zero integer digits, representing integers in any unknown radix beta greater or equal to 2 in argument, as well as a multiplication and an addition function for two integer digits in that base returning two digits representing their product resp. sum, in argument and that returns an array c of 2n digits representing the product of a and b. The function can be recursive but does not need to. A C prototype could be:

  void multiply_schoolbook(uint32_t *c, const uint32_t *a, const uint32_t *b, size_t n, void (*mul)(uint32_t *h, uint32_t *l, uint32_t a, uint32_t b), void (*add)(uint32_t *h, uint32_t *l, uint32_t a, uint32_t b));

  Your function needs to work in any radix beta. Its complexity can be O(n^2).
• A multiplication function that takes an array a of n positive or zero integer digits, an array b of n positive or zero integer digits, representing integers in any unknown radix beta greater or equal to 2 in argument, as well as a multiplication, an addition, a subtraction function for two integer digits in that base returning two digits representing their product resp. sum or difference, and a comparison function, returning -1, 0 or 1 depending on the relation between two digits, in argument and that returns an array c of 2n digits representing the product of a and b. The function can be recursive but does not need to. A C prototype could be:

  void multiply_faster(uint32_t *c, const uint32_t *a, const uint32_t *b, size_t n, void (*mul)(uint32_t *h, uint32_t *l, uint32_t a, uint32_t b), void (*add)(uint32_t *h, uint32_t *l, uint32_t a, uint32_t b), void (*sub)(uint32_t *h, uint32_t *l, uint32_t a, uint32_t b), int (*cmp)(uint32_t a, uint32_t b));

  Your function needs to work in any radix beta. Its complexity needs to be O(n^(log2(3))). You should base your function on the techniques discussed here.

Assignment 2 is described in this PDF document. The assignment is due October 2nd, 2023, 05:59MDT. It must be submitted by email to advancedalgorithms@christoph-lauter.org.

Assignment 4 is described in this PDF document. The assignment is based on code and data found here. The assignment is due October 30th, 2023, 05:59MDT. It must be submitted by email to advancedalgorithms@christoph-lauter.org.

Assignment 5 is consists in implementing and testing all functions required for Red-Black Binary Search Trees as stubbed out in the boilerplate section of this archive file. Student can find inspiration by looking at the code for classical (unbalanced) binary search trees, as programmed in class, and provided in the code section of the archive file. Students should test the different functions for correctness thoroughly, which includes testing the red-black properties that make the tree balanced. Students must include a description of their testing strategy, with a comparison of classical and red-black binary search trees, in their submissions (as a text or PDF file). The assignment is due November 5th, 2023, 02:59MST. It must be submitted by email to advancedalgorithms@christoph-lauter.org.

The final exam was on strings and edit lists. A solution for the programming part can be found here.

Copyright (C) 2023 Christoph Lauter