Algorithms & Architecture I

Home| Course

Schedule

Since this course is supposed to help you for your projects, you are highly encouraged to ask for specific subjects you want to learn about, as long as they are in the scope of this course :). Concerning the solutions to the exercises: You are supposed to find them and I will help you during the exercise sessions. Only some solutions will be provided on this web page.

Lecture 1 : Introduction, Growth of Functions

Abstract: Basic introduction to algorithm design, correctness of algorithms, analysis of algorithms, and asymptotic behaviours. Note: I will come back to chapter 2 when I treat sorting to avoid being redundant.

Reading: Chapters 1 and 3.

Material: lecture slides.

Exercises: pdf.

Suggested solutions: pdf.

Lecture 2 : Representing and Manipulating Numbers

Abstract: Binary representation of integers and floats, implementation of basic operations (in processors), basic arithmetics on integers and some applications, limits of the representation (integers and floats), and optimization issues.

Reading: A chapter related to binary representation in any reasonable architecture book. The choosen course book for architecture, or one of the additional listed books is fine. Ask at the library or borrow one from me.

Material: Slides pdf.

Exercises: Exercises of lecture 1: We make the deal that you try exercises of section 4 and then you check if you understand the solution of section 5. Don't cheat. Then you do these exercises on numbers: pdf.

Lecture 3 : Recurrences

Abstract: Introduction to recurrences and some techniques to solve them such as the substitution method, the recursion tree method, and the master method.

Reading: Chapter 4 and read again section 3.2.

Material: slides.

Exercises: Finish the exercises on numbers from last time.

Solution: Suggested solution to the RGB exercise rgb.c.

Lecture 4 : Probabilistic Analysis and Randomized Algorithms

Abstract: Introduction to counting, probabilities, and randomized algorithms.

Reading: Chapter 5 and appendices A and C.

Material: slides.

Exercises: (on recurrences, previous lecture)

• Substitution Method: exercises 4.1-1 and 4.1-2.
• Recursion Tree Method: exercise 4.2-1.
• Master Method: Try the master method on problems 4-1 and 4-4. Only try the method for the cases where it works. Choose one case and derive the recursion tree to find the solution when the method does not work, if you have time.

Solution: suggested solution.

Lecture 5 : Extra Material, Sorting

Abstract: Some extra material on computing polynomials and sorting algorithms (bubble sort, selection sort, insertion sort, merge sort, quicksort).

Reading: Chapters 2 and 7.

Material: polynomials and sorting slides.

Exercises:

• Probability Basics (Appendix C): exercises C.2-2, C.2-5, and C.3-3.
• Hiring Problem: exercises 5.2-1.
• Randomized Algorithms: exercise 5.3-2.

Lecture 6 : Extra Material, Sorting

Abstract: Heapsort, powering numbers, and Fibonacci revisited.

Reading: Chapter 6.

Material: powering numbers and sorting (cont.) slides.

Exercises (many but short and simple):

• Insertion Sort: exercises 2.1-1, 2.1-2, and 2.1-3.
• Quick Sort: exercises 7.1-1, 7.1-2 (this exercise shows a weakness of quicksort, but the same applies if the input array is already sorted or is reversed-sorted; check it), 7.1-3, 7.2-2, 7.2-3, and 7.4-5.
• Implementation: Implement the different sorting functions in sort-exercise.c.

Solution: suggested solution for 7.2-b.

Lecture 7 : Sorting in Linear Time, Data Structures

Abstract: Previous sorting algorithms were comparison sorts, here we study other kinds of sorts (counting, radix, and bucket sorts), and basic dynamic data structures such as stacks, queues, and linked lists.

Reading: Chapters 8 and 10.

Material: sorting in linear time and data structures slides.

Exercises:

• Heap Sort: exercises 6.1-1, 6.1-2, 6.1-3, 6.1-4, 6.1-6, 6.1-5, 6.2-1, 6.2-3, 6.2-5 (and use it in the implementation), 6.3-1, 6.3-2, 6.4-1, and 6.4-3.
• Implementation: Complete the previous implementation exercise.

Lecture 8 : Extra Material, Hashing and Hash Tables

Abstract: Introduction to hash functions and hash tables. The problem is to store or retrieve data in a dictionary data structure implemented efficiently as a hash table. Presentation of suggested solutions to the implementation of the different sorting algorithms. Extra material: the linux scheduling algorithm in O(1).

Reading: Chapter 11.

Material: hashing and hash tables and linux O(1) scheduler slides.

Exercises:

• Sorting in Linear Time: exercises 8.1-1, 8.1-2, 8.2-1, 8.2-3, 8.2-4, and 8.4-2.
• Stacks and Queues: exercises 10.1-1, 10.1-2, and 10.1-3.
• Linked Lists: exercises 10.2-2 (pseudo code only), 10.2-3 (pseudo code only), and 10.2-4.
• Rooted Trees: exercises 10.4-2 and 10.4-4 (pseudo code only).
• Implementation: Implements stacks and queues by filling the empty functions in stack-queue-exos.c. Note: you have to take care of overflow and underflow.

Solution: suggestion for 8.1-2.
Suggested implementations for the

• different sorting algorithms sort-solution.c,
• stacks and queues stack-queue-sol.c.

Lecture 9 : Binary Search Trees, Red-Black Trees

Abstract: Introduction to binary search trees that can be used as dictionary or priority queues, and a particular search tree structure (red-black tree) that has the property to keep the tree balanced. Also extra material on searching/exploring state-spaces.

Reading: Chapters 12 and 13. Sections 22.1, 22.2, 22.3 for those interesting in searching. Wikipedia on red-black trees.

Material: (general) searching/exploring, binary search, binary search trees, and red-black trees slides.

Exercises:

• Direct-access Tables: exercises 11.1-1 and 11.1-2.
• Hash Tables: exercise 11.2-1.

Lecture 10 : Red-Black Trees, String Matching, Solutions to Implementation Exercises.

Abstract: Extra material on findind shortest paths, string matching, finish red-black trees, presentation of solutions for the previous implementation exercises (if time left).

Reading: Wikipedia page on string searching and Chapter 32.

Material: Previous slides on red-black trees, shortest-paths slides, and string matching slides.

Exercises:

• Binary Search Trees: exercises 12.1-2, 12.1-3 (find the elegant solution that uses no stack), 12.1-5 (give a simple but convincing argument), 12.2-3, 12.3-3, and 12.3-4.
• Red-black Trees: exercises 13.1-2, 13.1-6, 13.1-7, 13.2-1, 13.2-3, 13.3-1, 13.3-3, and 13.3-6.