After a few months’ delay, we can finally start again with a new syllabus. The main resources of our course will be the 6.006 MIT course (Introduction to Algorithms) and our text book will be CLRS Introduction to Algorithms. The sessions will be held on Fridays at 3 P.M in the physics association’s skyroom class. Every session, students study three of the course lectures, work on the assignments and gather around to discuss their problems and noteworthy points of the course. Every student is encouraged to select a project as their final goal so that as we dive deeper into the course, we can struggle with our programs and learn new things.
We have a repository for the student projects. Link can be found here.
Suggested Text Editors
Session 1 (Lectures 1 — 3 and ProblemSet 1)
Date: August 21
Session Review: The students had worked on topics such as Peak Finding, Document Distance, Merge and Insertion sorts, and had analysed various algorithms for these problems. One of the major problems for the students was the fact that some of the codes were written in Python version 2. Now there are two ways to run the code: 1. run it with python2 and 2. first convert the code to version 3 using 2to3 command and then run it with version 3.
Note: The 2to3 command is not perfect and you might need to make some changes manually.
Some of the students had problems regarding Merge sort and Insertion sort that were answered.
For the next session, students will go through lectures 4 — 6 and PSet 2.
Session 2 (Lectures 4 — 6 and ProblemSet 2)
Date: August 28
Session Review: In this session we talked about AVL Trees and Binary Search Trees. The students didn’t have many problems with the basics of trees, so we focused on implementations in Python and C++. These implementations are available in our Github repository. (Linked below)
For the next session, students will go through lectures 7 — 8. It was decided that we study 2 lectures per session.
Session 3 (Lectures 7 — 8 and ProblemSet 2)
Date: September 4
Session Review: In this session, we tried to dive into implementation and code for a bit. Ali Abolhassanzadeh Mahani had implemented the Counting Sort algorithm with O(n) runtime with a profiler, while Saleh Shamloo had implemented a benchmark for some Sorting algorithms in C++ that followed the Comparison Computation Model. We compared His Quick Sort Algorithm with O(n log n) runtime with Ali’s algorithm which was written in Python. It took the counting sort algorithm an input of size 107 to beat the Quick Sort algorithm. This is were asymptotic notation shows itself and it also shows the power of low level languages like C++. Besides this contest, some students had problems regarding Radix Sort that were answered by Ali. (You can view our codes in our Github repository.)
For the next session, students will go through lectures 9 — 10 and review PSet 3.
Session 4 (Lectures 9 — 10 and ProblemSet 3)
Date: September 11
Session Review: This time, we went over the basics of hashing. Students had some questions regarding Open Addressing that were answered by Ermia Etemadi. We talked a little about Cryptographic Hashing and then we changed the topic to Modular Inverse calculation. There are various algorithms for it but two are of O(log n) runtime with n being the size of the prime number. The first the famous Extended Euclidean Algorithm and the second is an algorithm that uses Fast Power to calculate powers of a number. We went over their implementations in Python and C++.
For the next session, students will go through lectures 11 — 12 (Unit 4). After that, the sessions will be 1 lecture at a time since the Fall semester is starting.