| David Stanovský // firstname.secondname@gmail.com |
|
| ALGORITHMS & DATA STRUCTURES @ KBTU |
Aim:
- principles of algorithm design (divide&conquer, greedy algorithms, detph/breadth searching, ...)
- elementary algorithm analysis (correctness, time and space complexity)
- smart algorithms for concrete problems (sorting, graphs algorithms, maybe number theory and cryptography)
Literature:
- Cormen, Leiserson, Rivest, Stein: Introduction to algorithms
- Dasgupta, Papadimitriou, Vazirani: Algorithms
Program:
| date | topic | recommended reading | homework | software project |
| 24.08. | Introduction to algorithm analysis | Dasgupta: Chapter 0 (pp. 11-17), Cormen: Chapter 1 (pp. 5-15) | ||
| Big-O Notation | Cormen: Chapter 3.1 (pp. 43-53) | I suggest to read the chapter at home, in exchange for the missing lectures. | ||
| 14.09. | InsertSort and MergeSort | Cormen: Chapter 2 (pp. 16-42) | ||
| 21.09. | Analysis of Divide&Conquer algorithms | Cormen: Chapter 4 (pp. 65-82, 93-97) | 1. Consider the algorithm described in [Cormen: exercise 2.3-4 (p. 39)]. Write a pseudo-code, write a recurrence for the running time and solve the recurrence. (Note: Master Theorem does not apply here.) 2. Solve [Cormen: exercise 4.5-2 (p. 97)]. Deadline: 28.09. 8:00 | Solve [Cormen: exercise 4.1-3 (p. 74)]. Deadline: 01.10. 20:00 |
| 28.09. | Master theorem revisited. Fast integer multiplication. Memory management in sorting, MergeSort revisited. Max-heaps. |
Cormen: Section 4.4 (88-92), Dasgupta: Sections 2.1 and 2.2 (51-55). Cormen: Section 2.3.1 revisited (30-34) Cormen: Section 6.1 (151-154). |
1. Solve [Dasgupta, exercise 2.12 (p. 81)]. 2. Solve [Dasgupta: exercise 2.23 part (a) (p. 82)]. Use the hint, it means, split the problem in halves to obtain an O(n log n) algorithm. (You can also think about part (b), but do not have to write the solution.) Deadline: 05.10. 8:00 | |
| 05.10. | HeapSort. QuickSort. | Cormen: Sections 6.1-6.4, 7.1-7.3 | 1. Look at Figures 6.2, 6.3 and 6.4 and solve Exercises 6.2-1, 6.3-1 and 6.4-1 (in Cormen). 2. Solve [Cormen, Exercise 7.2-3]: What does QuickSort do with the array (n,n-1,n-2,...,2,1)? Show it need Theta(n^2) operations to sort it! Deadline: 12.10. 8:00 |
1. Choose ONE of the following sorting algorithms: MergeSort, HeapSort, QuickSort, and implement it. 2. Find N such that your implementation sorts a random array of N numbers in about 1 second. 3. Plot the graph showing the running times for a) a random array of size n, b) sorted array of size n, c) reverse sorted array of size n where n runs through N, 2N, 3N, ..., 10N. Send me the code and the graph! Guidlines for a report. Deadline: 15.10. 20:00 |
| 12.10. | Midterm exam. Lower bound on the complexity of comparison sorts. CountingSort and RadixSort. |
Cormen: Sections 8.1-8.3 More on sorting can be found on wikipedia, or here |
1. Look at Figures 8.2 and 8.3 and solve Exercises 8.2-1 and 8.3-1 (in Cormen). 2. Solve [Cormen, Problem 8.3a, p. 206]. Deadline: 19.10. 8:00 | |
| 19.10. | Stacks and queues. Linked lists. Trees. | Cormen: Sections 10.1-10.4 | 1.Solve [Cormen, Exercise 10.3-5]. 2.Solve [Cormen, Exercise 10.4-1]. 3.Solve [Cormen, Exercise 10.4-4]. Deadline: 26.10. 8:00 | |
| 26.10. | Hash tables, hash functions. | Cormen: Sections 11.1-11.3 | 1.Solve [Cormen, Exercise 11.3-4]. 2.Read [Dasgupta, Section 1.5, pp. 42-45]. Modify the idea of the hash functions h_a described in the book, to hash people's names (you can assume that all names have at most 10 characters). Write down an explicit formula for a hash function you are using, and tell me the hash value of your name. Deadline: 2.11. 8:00 | |
| 2.11. | Binary search trees. | Cormen: Sections 12.1-12.3 | 1.Solve [Cormen, Exercise 12.1-1]. 2.Solve [Cormen, Exercise 12.2-1] (explain why!). 3.Solve [Cormen, Exercise 12.2-3]. Deadline: 9.11. 8:00 |
Implement building of a binary search tree from a random sequence of N integers, using N calls of the INSERT function.
Represent binary trees using four arrays (parent, key, leftchild, rightchild). Report on: 1. The running time for building the search tree. Use N,2N,...,20N (20 values), with N such that the running time is about 1 second. 2. The height of the tree. Use the same values of N, calculate the heigt and plot the values. Deadline: 11.11. 11:11 |
| 9.11. | Red-black trees (motivation and idea). Dynamic programming: Rod Cut and Matrix-chain Multiplication problems. |
Cormen: Sections 13.1 and 15.1-15.2 | 1.Solve [Cormen, Exercise 15.1-3]. Write two algorithms, using the bottom-up method and the top-down method. 2.Look at Figure 15.5 and Solve [Cormen, Exercise 15.2-1] in a similar way. Deadline: 16.11. 8:00 | |
| 16.11. | Greedy algorithms: Activity selection, Huffman codes. | Cormen: Sections 16.1-16.3 |
1. Write an algorithm for finding the longest palindrome subsequence using the BOTTOM-UP dynamic programming method. 2. Solve [Cormen, Exercise 16.1-4]. 3. Solve [Cormen, Exercise 16.3-3]. Deadline: 23.11. 8:00 | |
| 23.11. | Graph representation, breadth-first and depth-first search. Application: topological sort, Dijkstra's algorithm. | Cormen: Sections 22.1-22.4 Dijkstra's algorithm on wikipedia |
1. Consider the graph at the top of this page. Apply the topological sort algorithm we had at the lecture and show its output. Explain what you are doing. Assume that the lists v.adj (adjacency lists) are sorted. 2. Consider this graph. Apply Dijkstra's algorithm and show its output. Explain what you are doing. 3. Write an algorithm that, given an undirected graph, decides whether it contains a cycle. It shall run in time proportional to |V| (not proportional to |E|, this is too slow!). Deadline: 30.11. 8:00 | |
| 30.11. | Endterm exam. Review of dynamic programming and greedy algorithms. |
Final grade:
- 30% first part of the semester: 15% test, 15% homeworks
- 30% second part of the semester: 15% test, 15% homeworks
- 40% final exam
Homeworks
Homeworks will be assigned every week, usually on Tuesdays (here and by email). Homeworks are
due on Monday 8:00 at the class. Submit all solutions on a separate sheet of paper,
written in English (or both in English AND Russian, if you feel to have troubles to express yourself in
English). I will try to grade and comment on the solutions in the afternoon lesson.
Cooperation in small groups is encouraged, but you have to write your own solution (see
below). Late submissions will not be considered, except for documented medical reasons.
Do not cheat! In any form. I hate it. A lot.
The most frequent form is copying solutions from other students. If I find solutions that are
obviously copied, everybody will obtain zero points, no matter who was the source. Applies to both
homeworks and class work. I am not silly. If you do cheap tricks while copying (for example, replacing
variable names), it is still just a copy. If you find a solution on-line and copy it, I will very likely find
it too.
How to write solutions
I encourage you to talk about the homework assignments with each other, or with me. It is fine if you
solve a problem in a small group. But then, when you finally understand how to solve the problem,
you have write the solution on your own.
I actually suggest the following scheme for homeworks. You look at the assignment a few days
ahead. If you cannot solve a problem, you ask a friend. If he/she cannot solve it, you try together. If it
does not work, ask more students. If you are still failing, ask me.
Every answer has to be supported by an argument. If you use a non-trivial rule or theorem, you
have to refer to this rule or theorem. No problem you will be given requires to search for a nontrivial
theory outside the book we use.
Software projects:
Occasionally, you will be given a software project. Your solution shall be in any clone of C or C++. Solutions shall be submitted to my email. Submission is accepted only upon receiving a confirmation from me.
Send me a source code, accompanied by a text answering any given questions. Tell me, under which compiler you tested your code.
Syllabus: (not all topics will be covered: in the last three parts, we have to make a choice)
- Introduction: elementary algorithm analysis, basic sorting algorithms, divide&conquer method (Cormen: Sections 1-4)
- Sorting algorithms: HeapSort, QuickSort, sorting in linear time (Cormen: Sections 6-8)
- Basic data structures: hash tables, binary search trees, maybe red-black trees (Cormen: Sections 10-13)
- Further algorithmic techniques: dynamic programming, greedy algorithms (Cormen: Sections 15-16)
- Graph algorithms: spanning tree, graph search, Dijkstra's algorithm (Cormen: Sections 22-24)
- Basic number-theoretic algorithms and cryptography (Cormen: Section 31)