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:

• 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)

1. Introduction: elementary algorithm analysis, basic sorting algorithms, divide&conquer method (Cormen: Sections 1-4)
2. Sorting algorithms: HeapSort, QuickSort, sorting in linear time (Cormen: Sections 6-8)
3. Basic data structures: hash tables, binary search trees, maybe red-black trees (Cormen: Sections 10-13)
4. Further algorithmic techniques: dynamic programming, greedy algorithms (Cormen: Sections 15-16)
5. Graph algorithms: spanning tree, graph search, Dijkstra's algorithm (Cormen: Sections 22-24)
6. Basic number-theoretic algorithms and cryptography (Cormen: Section 31)