Skip to main content

Algorithms and Data Structures, Autumn 2009

Welcome to the course!

  • The teacher/lecturer for the course is Sergei Vorobyov. His office is in Ovastova. He can be contacted at sergeiv kurla setur dot fo.
  • The textbook for the course is: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press & McGraw-Hill Book Company, 2001. ISBN 0-262-03293-7 (MIT Press). ISBN 0-07-013151-1 (McGraw-Hill); see errata.
  • The course will take place twice a week, on Mondays and Thursdays, in Uttarastova, starting at 8:30, and will be organized as a series of 45-minute sessions with short 10 min breaks in between (plus a longer 30 min lunch break). During sessions we will switch between lectures and problem solving.
  • There will be a series of homework assignments.
  • The final exam is a four-hour long uninterrupted written problem solving session, with no interaction allowed.
  • Top 10 skills
  • Top 10 CIO courses


1. Monday, 24 August

  1. Algebra, Algorithms, Al Khwarizmi, Euclid. What are algorithms? Why they are important? (maybe more important than hardware). Problems and algorithms. Examples of algorithms and applications, Binary Search, Insertion Sort, Merge Sort (John von Neumann).  Incremental and Divide & Conquer algorithm design techniques. Analysis, best case, worst case, asymptotic behavior. Asymptotic notation. Solving the D & C recurrence for the Merge Sort using recursion trees, getting the O(n log n) bound. Summations, mathematical induction. Proving algorithms correct based on the invariants method. Constants and lower order terms can be ignored. Comparing algorithms on the basis of their asymptotic behavior.
  2. Roughly, we covered Ch. 1 & 2 of [CLRS], looked at a few exercises.
  3. Homework: read once again Ch. 1 & 2 of [CLRS],  think about all exercises and problems (especially 2.3-7*, p. 37). We'll cover them next time. Try to read ahead Ch 3, to get prepared for the next lecture. Install Java/Netbeans on your computer and refresh your memory by implementing a couple of algorithms we discussed.

Useful websites:

  1. mathworld.com
  2. Wollfram Alpha
  3. Top 500
  4. Wikipedia


2. Thursday, 27 August

  1. We tried to solve/discuss almost all exercises and problems from Ch 1, 2 and 3, and studied Ch 3 (Asymptotics and Growth of Functions).
  2. Efficient multiplication of numbers, polynomials (starting with linear polinomial multiplication using just 3 rather than 4 coefficient multiplications). Karatsuba's D & C O(n^1.59) algorithm (compared with the naive quadratic one). Bubble sort, simultaneous Min and Max makinmg 3/2n comparisons, their analyses.
  3. Problem 2.3-7 withstands, try it again
  4. Read Ch. 3 and try Ch 4 to be studied next time.


3. Monday, 31 August

  1. Asymptotic order of growth, reminder, the sum and multiplication rules, their proofs.
  2. Analyzing and comparing different solutions to the homework ex. 2.3-7 (bin search vs burning the candle from two ends)
  3. Repeating proofs by induction, examples.
  4. Ch 4 "Solving Recurrences": substitution, recursion trees, master method, with examples. Proving the simplified Master Theorem.
  5. Pb. 4.2 "Finding the missing number".
  6. Ch. 6 "HeapSort", explanation, analysis, sample runs, discussion of the algorithm. Application to Priority queues.
  7. Read Ch. 7 "QuickSort" to be studied next time.
  8. Solve Pbs. 4.3, 4.6, 4.7.


4. Thursday, 3 September

  1. Solved together Pbs 4-1, 4-3, 4-4, 4-6, 4-7
  2. Pb. 4-6.a remains for the next time
  3. Corrected (extended) the solution to 4-2 "Missing number" (discussed last time) for the case when n<>2^n-1.
  4. For Heapsort, solved all Ex. 6.1-*, 6.1-*, 6.3-*.
  5. Discussed recursive vs iterative implementations of factorial, Binary search, Max-Heapify, Tail recursion in general, replacement by iteration
  6. Try iterative implementations (rather than recursive) implementations for MergeSort, Quicksort. 
  7. Started Ch. 7 "Quicksort", discussed straghtforward and sophisticated Partition, worst-case and average case for Quicksort.


5. Monday, 7 September

  1. Solved Ex. 6.4-*, Ex. 6.5-*, Pb. 6.1 about Heaps and Priority Queues.
  2. Problems 6.2, 6.3 remain as homework
  3. Pb. 4.6.a "Why Diogenes cannot determine a good chip if these are in minority?"
  4. Reversed Polish Notation, computing with a stack
  5. Ch. 7 "Quicksort" (continued)
  6. Implementing recursive procedure calls using a stack (promised in Session 4)
  7. Optimizing quicksort by selecting the smaller partition to be sorted first, eliminating the second recursive call by a loop (tail recursion), homework.
  8. Analysis of randomized quicksort, probability of comparing z_i to z_j, expected number of comparisons, linearity of expectation
  9. Ex 7.1-*, 7.3-2, 7.4-1, 7.4-2, 7.4-3, 7.4-4


6. Thursday, 10 September

  1. Solved together Pb. 6.2 (analysis of d-ary heaps), 6.3 (Young tableaux)
  2. Solved Ex 7.4-5, 7.4-6.
  3. Found an unsurmountable problem with Hoare's partitioning (Pb. 7.1), homework for the next time.
  4. Solved Stooge sort (Pb. 7.3)
  5. Discussed Pb. 7.4 (stack depth for quicksort)
  6. Solved Pb. 7.6 (Fuzzy sorting of intervals)
  7. Ch 8.1 "Sorting in linear time", proving the lower bound for comparison-based sorting.


7. Monday, 14 September

  1. We corrected Hoare partitioning (Pb 7.1), using while loops
  2. Reconsidered Fuzzy sorting of intervals
  3. Proved O(n) expected running time for fuzzy sorting of intevals, when all of them intersect (pb 7.6 b)
  4. Lower bound for comparison-based sorting, count sort, radix sort (ch 8).
  5. Solved Ex 8.1-*, 8.2-*, 8.3-1-4
  6. Solved Pb. 8-2, 8-3, 8-4


8. Thursday, 17 September

  1. Solved Pb. 8.5 a-d (Average sorting)
  2. Bucket sort, ch 8.4
  3. All exercises and remaining problems in ch 8
  4. Medians and order statistics (ch 9), selection in randomized and deterministic linear time
  5. Solved Ex. 9.2-1, 9.2-3, 9.2-4
  6. Solved Ex. 9.3-1, 9.3-3, 9.3-5, 9.3-6, 9.3-8, 9.3-9, Pb 9-1, 9.2 a, b
  7. Homework: Ex 9.3-7, Pb. 9.2 c, Ex 9.1-1


9. Monday, 21 September

  1. Homework discussion, Ex 9.3-7, 9.1-1, Pb 9-2 c
  2. Ch 10 "Elementary data structures"
  3. Solved almost all exercises, Pb 10-1, 10-2
  4. Homework: solve the remaining ones, especially Ex 10.3-4, 10.3-5, 10.4-4, 10.4-5, 10.4-6


10. Thursday, 24 September

  1. Solved Ex 10.3-4, 10.3-5, 10.4-3, 10.4-4. 10.4-5 left as a homework
  2. Ch. 11 "Hash tables"
  3. 11.1 Direct adress tables, solved Ex 11.1.1, 11.1-2, 11.1-3. Ex 11.1-4 homework 
  4. 11.2 Hash Tables, solved all Ex 11.2-*
  5. 11.3 Hash functions, md5sum, solved 11.3-1
  6. 11.4 Open addressing, Ex. 11.4-1
  7. Ch 12 Binary search trees, Sect 12.1, 12.2, solved all Ex 12.1-*, 12.2-1, 12.2-2. 12.2-3
  8. Homework: Ex 12.2-4, 12.2-5, 12.2-6, 12.2-7, 12.2-8, 12.2-9
  9. See Errata for CLRS.
  10. The textbook for the Communications & ICT course has been selected and approved (B. A. Forouzan, Data Communications and Networking), see the details on the appropriate web page


11. Monday, 28 September

  1. Finished Ch 12 Binary search trees, insertions and deletions, done almost all exercises, Pbs. 12.1 & 12.2
  2. Homework: Ex. 12.2-8, 12.3-5
  3. Studied Ch 13 Red-Black trees, properties, rotations, insertions, solved almost all exercises, started deletions 
  4. Homework: Ex. 13.4-*
  5. Introduced TREAPS (Pb 13-4)


12. Thursday, 1 October

  1. Solved Ex 12.3-5
  2. Finished Red-black trees, deletions (treaps remain for the next time), exercises
  3. Starting Ch 15 "Dynamic programming", 15.1 Assembly line problem
  4. 0/1 Knapsack, Optimal money exchange, Game of matches, Cutting the log, all solved by Dynamic programming
  5. Homework: read Ch 15, finish cutting the log


13. Monday, 5 October

  1. Ch 15 DP continued: Optimal matrix chain multiplication, Longest common subsequence, the Floyd-Warshall's algorithm (Ch 25.2)
  2. Cutting the log problem discussed
  3. Longest increasing subsequence
  4. Maximally convivial XMas party problem
  5. Greedy algorithms: Fractional knapsack, Dijkstra's algorithm (Ch. 24.3)
  6. Problems, exercises
  7. Trial exam problems distributed


14. Thursday, 8 October

  1. Discussed and solved all the problems from the trial exam above
  2. Discussed longest ascending subsequence
  3. Recommended reading


Friday, 23 October - Final Exam

  1. 4 hours written exam
  2. Consists of a series of problems
  3. Books are allowed
  4. Interaction is not allowed