A warm welcome to CS101!

As the past students said: CS101 is one of the most organized and useful courses at SIST. We do wish you a wonderful learning journey at CS101!!! Of course, this result does not come for free. We have been continuously improving the course in the past several years. Every year, we improve a bit according to the previous year's feedback. So let's briefly share with you what we will have this semester to make sure that you all are ready to have a great achievement. *NEW* for this semester: This year's essential improvement is that we will spend a significant effort for the first time to prepare short videos and blogs/posts (both in Chinese) for each week's lectures. The videos are summaries of key concepts (should be around 5mins for each concept). The posts are used to explain more complex things, including solutions for homework and some extra hints for your study. They will be shared via WeChat channel (视频号) and WeChat public account (公众号). The purpose is to help you master the knowledge after lectures more efficiently and friendly. However, they are not substitutes for the lectures, so you still need to attend the lectures.  To better achieve the above purpose, we will also record the professors' lectures in the class. In most cases, only the professors are in the recordings, sometimes the students may appear in the recordings when the professors interact with the students. However, if a clip where students’ faces appear on the screen is used for our short videos or other purposes, we will ask the involved students’ permission before using it. Do let us know if you have any concerns. The contents: The course consists of four large sections in terms of structures and the related algorithms: 1) List structures and sorting (divide and conquer); 2) Trees and traversal/update (Binary Search Tree); 3) Graphs and traversal/spanning-tree/shortest path (greedy); 4) Dynamic programming and advanced algorithm design (NP and NPC). The difficulty is well-balanced and becomes a bit more challenging towards the end of the course. However, if you keep following the lectures, you will not feel the difference. So don't think you can skip the earlier part because you have known some of the structures since high school (most likely, you know the name but nothing else). Homework/Discussion/Quiz sessions (in charge by TAs): The sessions after the lecture are equally important as attending lectures. Therefore, we try to make them well-coped to give you the most efficient learning experience. 1) Homework: we have weekly homework released before the lectures, so you know what you need to answer before you attend the lectures (you probably finish the homework during the lectures). 2) Discussion/Quiz: we have one quiz and discussion session every week since week 3, which covers the lectures from the last week only. Since you have attended the lectures and finished the homework the previous week, it is the right time to check whether you have mastered the knowledge. If not, you will have the chance to master it during the quiz session. Each session lasts one hour: 30mins to do the quiz and 30mins to discuss the answers. Our great TAs conduct the quiz sessions in smaller groups (about 45 students each) in the evenings (exact time and grouping will follow up). The TAs are the best students who are capable of helping you in many ways. So do approach them when you need them. Programming tasks: This course is not a programming course, but we will practice your programming skills to do four programming tasks related to the four sections of the lectures. This is to help you understand the structures/algorithms better and keep pushing your programming skills. Lastly, DO NOT copy: In the end, this is all about transferring knowledge to you! There is no shortcut, so don't just take someone's results as yours! If you have difficulties, we (the professors and TAs) are all here for help, so don't be shy to ask "stupid" questions (especially during the lectures). If you have any questions/suggestions, please let us know. Have a great learning journey!!! Dengji, Yuyao, Xin and Hao

Course Schedule


Week

Date

Content

1

9/05 Mon

Introduction (Slide, Post)

1

9/07 Wed

Elementary Data Structures: Array and Lists (Slide, Post)

2

9/12 Mon

Mid-Autumn Festival

2

9/14 Wed

Stack and Queue (Slide1, Slide2, Post, HW1)

3

9/19 Mon

Big O/Theta/Omega (Slide, Post, HW2)

3

9/21 Wed

Hash Table (Slide, Post)

4

9/26 Mon

Sorting: Insertion, Bubble (Slide, HW3)

4

9/28 Wed

Sorting: Merge (Slide, Post)

5

10/03 10/05 Mon Wed

National Day

5

10/08 Sat

Sorting: Quick (Slide, Post)

6

10/10 Mon

Divide and Conquer (Slide, HW4)

6

10/12 Wed

Trees: Introduction, DFS, BFS (Slide)

7

10/17 Mon

Binary Trees (Slide, HW5)

7

10/19 Wed

Heap and Heap Sort (Slide)

8

10/24 Mon

Binary Search Tree + Huffman Coding (Slide1, Slide2, HW6)

8

10/26 Wed

Balanced Binary Search Trees: AVL (Slide)

9

10/31 Mon

Red-Black Tree + Disjoint sets 1 (Slide)

9

11/02 Wed

Middle Term Exam

10

11/07 Mon

Disjoint sets 2 + Graphs: Introduction, Traversal (Slide1, Slide2, HW7)

10

11/09 Wed

Graphs: Traversal (Slide)

11

11/14 Mon

Minimum Spanning Trees (Slide, HW8)

11

11/16 Wed

Greedy (Slide)

12

11/21 Mon

Topological Sorts (Slide, HW9)

12

11/23 Wed

Shortest Path Algorithm: Dijkstra (Slide)

13

11/28 Mon

A* (Slide)

13

11/30 Wed

Floyd-Warshall Algorithm (Slide)

14

12/05 Mon

Dynamic Programming (Slide)

14

12/07 Wed

Knapsack Problem (Slide)

15

12/12 Mon

Reductions (Slide)

15

12/14 Wed

P+NP

16

12/19 Mon

NPC

16

12/21 Wed

Review

Posts


Wechat Posts

Wechat Videos

Please follow our WeChat channel to watch the videos, the QRcode is attached at the end.

(2022/09/07)欢迎走进算法与数据结构

(2022/09/19)储存结构的动态增长策略

(2022/09/19)数组和链表的异同

(2022/10/09)单调栈&单调队列(上)

(2022/10/09)单调栈&单调队列(下)

(2022/10/09)渐进符号

(2022/10/09)排序算法运行下界

(2022/10/16)std::sort设计思想

(2022/10/16)分治及两个经典的应用

(2022/10/16)平面最近点对

(2022/10/23)用堆维护中位数

(2022/11/23)详解Huffman编码

(2022/11/23)Median of medians上

(2022/11/23)Median of medians中

(2022/11/23)Median of medians下

(2022/12/02)常见的二叉搜索树的平衡策略

(2022/12/02)数组和二叉搜索树在存储数据上有什么区别?

(2022/12/02)数组和二叉搜索树在存储数据上有什么区别?

(2022/12/07)Floyd Warshall Algorithm回顾

(2022/12/07)动态规划

Resources


Slides

Homeworks

Quiz

General Resources

Other Resources