Introduction to Algorithms
In this session I first introduce the problem of “Stable Matching” and then we discuss the Gale-Shapley algorithm, proof of its consistency and a pseudocode as the implementation. Later I introduce a few problems as a motivation for the rest of these sessions and discuss the possibilities and applications. These problems are: Interval Scheduling, Weighted Interval Scheduling, Bipartite Matching, Independent Set and Competitive Facility Location.
Presented by: Ali Abolhassanzadeh Mahani, Physics Undergraduate Student, Sharif University of Technology
Resources: Kleinberg — Chapter 1
Basics of Algorithm Analysis
In this session we talked about Asymptotic Notations, Worst Cases, etc., we also discussed polynomial time as a definition of “Efficiency”. Then, we implemented the “Stable Matching” problem using lists and arrays in Python and analyzed the Gale-Shapley Algorithm.
Presented by: Negin Bagheri, Physics Undergraduate Student, Sharif University of Technology
Resources: Kleinberg — Chapter 2, CLRS — Growth of Functions (pp 43 — 64)
Breadth First Search and Depth First Search (Graph Algorithms)
This time we take a look at graphs. Here we discussed the definitions of graphs, metrics and distance in Computer Science. Then, we talked about the two most famous algorithms in Graph Theory, BFS and DFS algorithms. We also reviewed some of their implementations and talked about their possible applications.
Presented by: Ali Abolhassanzadeh Mahani, Physics Undergraduate Student, Sharif University of Technology
Resource: Kleinberg — Chapter 3, CLRS — Chapter 22 (Elementary Graph Algorithms)
Data Structures in C++ and Python and Memory Consumption
Here we talked about different kinds of data structures and how each can help us in different algorithms. We introduce implementations of these data structures in C++ and Python and cover the basics of Memory Manipulation.
Presented by: Mohammad Javad Sajjadi, Computer Science Undergraduate Student, Sharif University of Technology
Resources: CLRS — Chapters 10 and 12 (Elementary Data Structures and Binary Search Trees)