- Course Duration: 14 sessions + 1 offline bonus session
- Instructor: Soroush Sahraei
- Mentor: Erfan Mirshams
- Language: C++
- Basic C++ knowledge (or at least being active enough to self-study)
- Basic knowledge of recursion
- Konkour-level Graph theory knowledge
In this course, students will learn:
- Basic time and memory complexity analysis using informal definitions
- How to work with online judges
- Algorithmic thinking
- Commonly-used sorting techniques
- How to participate in programming contests
- Using recursion to generate non-trivial sequences
- Binary search
- Prefix sums and their different variations
- Working with various STL data structures
- Implementing queues, stacks and vectors by themselves, albeit not clean on an industrial scale
- Basic methods to store graphs
- Basic graph traversal algorithms (BFS and DFS)
- Topic: Simple Algorithmic Tasks
- Description: A 1.5 hour contest hosted on Quera, featuring 6 simple tasks that require no prior knowledge of CP yet tickle the minds of contestants.
- Topic: Introduction
- Description: Introduction to the course, explaining why learning DSA is beneficial in both academic and industrial fields. Some fun and interesting theoretical tasks will be presented if there's extra time left.
- Homework: Two or three theoretical puzzles that will be discussed in the next session.
- Topic: Introduction to online judges + A brief intro to STL data structures
- Description: Talking about online judges and how to work with them, also telling students to join the necessary groups. After a short introduction to STL DS, a few simple DS tasks will be given to students to think about and will be solved in class.
- Homework: Beginner-level DS tasks in quera.
- Topic: Time Complexity
- Description: Giving students a grasp of how complexity analysis works. Due to the complex nature of the topic, formal definitions such as the α and θ notations will not be discussed.
- Homework: Five brute-force tasks in Quera (which need non-trivial optimizations regarding TC) plus additional TC calculation tasks.
- Topic: Sorting Algorithms
- Description: Famous sorting algorithms will be presented, students will be asked to implement a sorting algorithm of their choice (except for bubble sort) and use it to solve a simple task in Quera. We'll also use our learnings from the previous session to analyze the complexity of some sorting algorithms.
- Homework: Students will be asked to implement an A)O(n^2) B)O(n*log(n)) C)O(n) sorting algorithm, judging will be done via Quera. Video tutorials on sets and maps along with some related tasks will also be given to students.
- Topic: Complete Search with Recursion
- Description: We'll start by trying to find a way to generate all subsets with bit masks, we'll also talk about recursively generating all possible permutations and hopefully solve a few tasks.
- Homework: Video tutorials will be prepared on backtracking (possibly including some special cases of DFS), students are to watch these videos and solve their respective tasks on Quera.
- Topic: A 1.5 hour long contest (probably teams of two)(with prizes)
- Description: Students will be asked to participate in a 1.5 hour long contest in Quera. The contest itself will be similar to Atcoder beginner contests. The rest of the session will be used to talk about contest strategy.
- Homework: Video tutorials will be prepared for every task in the contest, students have to watch them and implement every task.
- Topic: Greedy algorithms and how to utilize them with sorting to solve tasks
- Description: This session will mostly be dedicated to students after a brief description, students will be given multiple tasks to solve in order to sharpen their intuition. The student who solves the most tasks will be rewarded.
- Homework: None, students will be given time to catch up on their previous tasks.
- Topic: Binary Search
- Description: Students will be given a simple task after learning the basic idea of binary search.
We'll also review sets and introduce
lower_bound
andupper_bound
functions. - Homework: Students will be given some simple binary search tasks, they'll also be asked to
implement
lower_bound
andupper_bound
functions for sorted vectors.
- Topic: Prefix Sums
- Description: We'll discuss prefix sums and solve the classic "maximum subarray sum" problem we'll also discuss 2D prefix sums and use the rest of the session to revise the previous topics.
- Homework: A few tasks utilizing partial sums will be uploaded to Quera.
- Topic: Storing Graphs, DFS, Stack
- Description: We'll talk about ways to store graphs, then we'll introduce the DFS algorithm so make understanding it simpler, we'll talk a little bit about stacks. We'll also implement this during the class.
- Homework: Related tasks will be uploaded to Quera along with video tutorials for further understanding.
- Topic: BFS, Queue, Shortest Paths in weightless graphs
- Description: We'll discuss how BFS works and implement it using queues. A few related tasks will also be given to students.
- Homework: Related tasks will be uploaded to Quera along with video tutorials for further understanding.
- Topic: Dynamic Programming
- Description: We'll extend some of our ideas from session 9 and solve some introductory tasks.
- Homework: Some tasks from Atcoder DP contest will be given to students (probably translated).
- Topic: Memoization, Top-down Dp, Buttom-up dp, more tricks
- Description: Since DP is a vast topic, we'll cover even more classic examples of it. We'll also introduce memoization and solve some recursive/backtracking tasks using some of our ideas from session 5.
- Homework: More classic tasks will be given to students.
- Topic: A 2-hour-long contest (probably teams of two)(with prizes)
- Description: A contest held on Quera featuring various tasks for students to utilize their learnings from the past sessions.
- Description: This session will be prerecorded and offline, I'll be discussing some techniques that utilize stacks, queues and doubly ended queues (deque). These techniques include but are not limited to the "Nearest Smaller Element", "Sliding Window Minimum" and related problems.
- Automata theory by INOI
- Graph theory by INOI
- Introduction to
- C++ by INOI
- Algorithms by INOI
- Combinatorics by INOI
- Competitive Programmer’s Handbook
- AN INTRODUCTION TO THE USA COMPUTING OLYMPIAD
- Principles of Algorithmic Problem-Solving
- Since the course is presented in both traditional and online manners, absentees can view the recorded files of the online class.
- Academic dishonesty includes, but is not limited to, plagiarism, cheating on exams or assignments, falsifying data, submitting work completed by someone else, and collaborating on assignments without permission.
- On first offense, violators will be warned against their action.
- On second offense, violators will be refrained from participating in the next upcoming contest.
- On their third offense, violators will be suspended from the course.
- Extra tasks (harder/easier) will be available for students throughout the course.