Lectures
Final Lecture notes can be found here (last update: 5/22/2020)
For students who have signed up to take notes, they should create an account with overleaf.com. Please note you need a VPN connection to log onto Overleaf. Then log onto this url and select “Open as Template”. Once the template is opened, make sure “XeLaTeX” is selected as the compiler in the menu and that it compiles correctly. Then start by opening the session.tex file, updating the Subject, Author, Date, … fields and start creating notes. Notes should be taken in Farsi. Please note that the Overleaf editor is not the easiest editor to work with when typing Farsi and English. Keeping different languages on seperate lines helps. You can select the “Rich Text” editor or just copypast the text into your local editor and then paste it back when you are done editing and ready to compile. Alrternatively you can download MikTeX and TeXStudio and edit it on your local box. Once you are done, rename your project to IUST_DS98_SessionX (replace X by session number) and share it with my email (first name, at gmail). Please let me know if you have any questions.
Alternatively, you can download the latex template from here and upload it to overleaf or use TeXStudio (or other LaTeX editor/compilers) intead.

Session 30  23, RedBlack and B Trees
tl;dr: Today we extended our discussion on balanced binary search trees. We had seen AVLtrees before. We examined 23 trees, redblack trees and an overview of btrees.
Note Taker: خانم زهرا صالحی

Session 29  Toplogical Sort  SCCs
tl;dr: Today we explained the toplogical sort algorithm in DAGs. Next, we defined Strongly Connected Components in directed graphs and developed an efficient algorithm to find them. We also talked about a recent advance in graph theory <a href=en.wikipedia.org/wiki/Hedetniemi%27s_conjecture>Hedetniemi's conjecture</a>.
Note Taker: آقای مصطفی مسعودی و یاسین عسکریان

Session 27  Graph Connectivity, DFS, Connected Components, DAGs
Note Taker: آقای رضا علیدوست و خانم ملیکا احمدی

Session 25  SplayTree + Graph
tl;dr: We started today's session with Splay trees. We demonstrated how it's used, its benefits and how it is done through ZigZig, ZigZag and Zig operations. Next, we talked about graphs, their applications and their representation.
Note Taker: آقای محمد حسین حسینپور

Session 24  Binary Search Trees 2
tl;dr: Today we introduced AVL trees and updated the Insert and Delete operations to maintain the AVL property. Next, we introduced efficient Split and Merge operations for AVL trees. Finally, we introduced an example where we can use split and merge operations to solve it efficiently, in addition to compute order statistics in BSTs.
Note Taker: آقای هژار آزیز

Session 23  Binary Search Trees
tl;dr: We started off by explaining what a binary search tree is, whey we need it and how to perform basic operations. Next, we analyzed computational complexity of basic operations. We concluded with the need to maintain a balanced tree. We introduced the rotateleft and rotateright operations. Next session we will will introduce the AVL tree.
Note Taker: خانم فاطمه امیدی

Session 22  Hash Tables
tl;dr: We first reviewed hash tables. Next we discussed what a good hash function looks like. We deomonstrated collision rate of different hash functions (the code is attached). We also discussed how one could use flaws of a hash function for a Denial of Service attack. We introduced what a Universal Family hash function is and introduced a university family hash function for integers and strings. Finally, we demonstrated the Rabin Karp algorithm for string matching using the string hash function introduced earlier to match a pattern of size P against a text of size T in O(P+T) time.
Note Taker: آقای مجتبی نافذ

Session 20  Hash Tables
tl;dr: We started the session by discussion some academic dishonesties for programming assignments A2, A5, A6 and A7. The request is for students who have not honored the academic honor code to drop the course. We then reviewed HashTables and finally demonstrated uses of hash functions and their effect on hash table performance in .NET. We also reviewed the .NET implementation of hash functions of String, Int and Double.
Note Taker: خانم نگار زینالعابدین

Session 19  Disjoint Sets  Continued + Hash Tables
tl;dr: First we discussed the path compression heuristic for disjoint sets. Next we explained hash tables.
Note Taker: آقای آرمین غلامپور

Session 18  Disjoint Sets
tl;dr: We started the session by addressing internet disconectivity issues. Next, we analyzed the Heapify/BuildHeap algorithm and its applications. We then moved to disjoint sets and discussed a naive algorithm as well as an efficient algorithm with the union by rank huristic. Next session we will discuss the path compression technique and then move onto hash tables.
Note Taker: آقای امید میرزاجانی

Session 17  Priority Queue and MaxHeap
tl;dr: First, we looked at the C++ STL priority_queue class and then the heapq module in python to see how one would use a priority queue. We then discussed how one might implement it. Next, we looked at the Binary MaxHeap implementation and how it can guarantee logn computational complexity for Insert and ExtractMax. Finally, we discussed how we can use a MaxHeap to implement HeapSort.
Note Taker: آقای حسن صبور

Session 16  Dynamic Arrays and Amortized Analysis
tl;dr: We looked at the dynamic array implementations in the .NET library as well as the C++ STL library. We also explained two techniques for amortized analysis.
Note Taker: آقای هادی شیخی

Session 15  Basic Data Structures  Stack, Queue and Tree
tl;dr: Today we discussed Stack, Queue and Trees and how they may be used. We also looked at their .NET implementation.
Note Taker: آقای صدرا خاموشی

Session 14  Basic Data Structures  Linked Lists
tl;dr: We spent the entire lecture on linked lists. After explaining what a linked list is, we demonstrated how it is implemented in C. Next, we demonstrated how it is implemented in C# while explaining the difference between value types and reference types. Finally, we explained how linked lists are used for memory management in the operating system.
Note Taker: آقای محمد مصطفی رستمخانی

Session 13  Basic Data Structures  Arrays
tl;dr: We started the lecture by answering questions about the maximum arithmetic problem. We then moved onto the Basic Data Structures section of our syllabus. We demonstrated how pointer arithmetic is used to access array elements in O(1). We also discussed the order of insert/delete to the beginning, middle and end of the array.
Note Taker: خانم غزل زمانینژاد

Session 12  Dynamic Programming  Continued
tl;dr: We continued our discussion on dynamic programming with the knapsack prblem with and without repitition. We then examined the maximum arithmatic problem. This finishes the introduction to algorithms part of our course. Next, session we will start with basic data structures.
Note Taker: آقای سهند نظرزاده

Session 11  Dynamic Programming  Edit Distance
tl;dr: We continued our discussion on dynamic programming with the minimum edit distance problem. We first motivated the problem with an example from biology and also from natural language processing. We then went on to explain the details of how the algorithm works.
Note Taker: آقای سهند نظرزاده

Session 8  Tail Recursion + Dynamic Programming
tl;dr: We started by examining the tail recursion techniqure which I did not explain well last session. Next, we explained the concept of dynamic programming with first the fibonacci series and then with the Money Change problem. We will continue our discussion on dynamic programming next week.
Note Taker: آقای سهراب نمازی

Session 7  Divide and Conqure  Continued 2
tl;dr: We started by proving a lower bound on comparison based sorts. Next we introduced stable sort and why it is important for nonecomparison based sorts like Ordinal sort. Finally we introduced QuickSort and analyzed its run time in addition to introducing a few optimizations to it.
Note Taker: خانم پریسا علایی

Session 6  Divide and Conqure  Continued
tl;dr: Divide and Conqure: We spent more time on polynomial multiplication, then moved onto the master theorem and finished with merge sort.
Note Taker: خانم ملیکا نوبختیان


Session 4  Greedy Algorithms.
tl;dr: Greedy Algorithms. Reading: CLRS Chapter IV  Section 16
Note Taker: خانم زهرا حسینی

Session 3  GCD, BigO Notation.
tl;dr: GCD naive and efficient algorithm. BigO notation. Reading: CLRS Chapter I  Sections 2.2, 2.3, 3.1, 3.2
Note Taker: آقای محمد امید قسوری

Session 2  Course overview  What is an algorithm?
tl;dr: Course Overview. What is an algorithm? Reading: CLRS Chapter I  Sections 1.1 and 1.2
Note Taker: آقای میلاد اسفندیاری

Session 1  Introduction, DevOps, Git, Assignment 1
tl;dr: First Session. Introduction, Syllabus, Assignment 1