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 copy-past 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 - 2-3, Red-Black and B Trees
tl;dr: Today we extended our discussion on balanced binary search trees. We had seen AVL-trees before. We examined 2-3 trees, red-black trees and an overview of b-trees.
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 Zig-Zig, Zig-Zag 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 rotate-left and rotate-right 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 log-n 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 none-comparison 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, Big-O Notation.
tl;dr: GCD naive and efficient algorithm. Big-O 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