**Lectures**: Mon 10:00-11:40am & Web 10:00-11:40am, East Up Building (Dong Shang Yuan), Room 201

**Instructor**: Xiaotie Deng - SEIEE 3-428
Email: deng-xt@cs.sjtu.edu.cn

Office hours: by appointment via email or ask after class

**Teaching Assistant**:

Tong Yin - SEIEE 3-524, Email: yintong@sjtu.edu.cn, WeChat: ytong_94

Xiang Yan - SEIEE 3-329, Email: yxghost@sjtu,edu.cn, WeChat: xyanghost

Please submit your assignments (from the second one) in pdf(recommanded) or word to yintong@sjtu.edu.cn

- 50% coursework plus 50% final examination
- Coursework:
- 20% of your final scores come from 4 assignments
- 1st: Select and complete 5 assignments, 1% each, maximum 5%. Due: Oct. 11th.
- 2nd: Select and complete 5 assignments for 5% in total. Due: 23:59 pm, Oct. 25th. Note that from this time, all your assignments should be handed in through email!
- 3rd: The deadline for Assignment #3 is postponed to Nov. 29th.
- 4th: The deadline for Assignment #4 is Dec. 13th.

- 1 middle term test, maximum 20%
- Expert students assign problems, one for each, and email to TA Xiang Yan(yxghost@sjtu.edu.cn) before 23:59, Oct. 27th.
- These problem, may be modified a little, will be announced on Oct. 28th. See the problmes.
- Everyone choose and complete 5 from these problems, as the first part of the exam, and email them to TA Tong Yin (yintong@sjtu.edu.cn) before 9:59 am, Nov. 1st.
- On class of Web. (Nov. 1st), complete determined 2 problems, and 3 from these problems, as the second part of the exam. At the beginning of the class, prof. Deng will show a table on the screen, illustrating which problems everyone should do. After finishing the exam, hand your answers to prof. Deng.
- The problems and answers can be found here.
- Grading for the midterm exam is done. You can contact TA TONG YIN or XIANG YAN, either through WeChat or E-mail, to ask grade of yourself.

- Extra-ordinary work (For A+ work) maximum 10%
- One project leading to a publishable research paper
- Student expert self study: Script one lecture note and give a suitable exam question (not searchable from Internet) with a correct solution.

- 20% of your final scores come from 4 assignments
- Final Examination: Problems given out 24 hours before examination and each redoes it in class. Two parts separately marked and both counted in final examination evaluation.
- Part I. Choose and finish 5 of these problems and send your answers to TA Tong Yin (yintong@sjtu.edu.cn). Deadline: Dec. 17th 23:59.
- The final exam will take place at Dec 18th, 10:00 am to 12:00 am.

- Further information about middle term test, project and others will be resleased soon.

- Lecture 0: slides, lecture notes
- Lecture 1: slides
- Lecture 2: slides, lecture notes about median finding
- Lecture 3: slides, lecture notes about convex hull
- Lecture 4: slides, lecture notes about sketch and streaming algorithms, lecture notes about kolmogorov complexity, lecture notes about Misra Gries alg & Morris counting
- Lecture 5: slides, lecture notes about Algorithmic Lower Bound for Data of Fixed Distribution
- Lecture 6: slides, lecture notes from Hongyang, lecture notes from Zheng Min
- Lecture 7: slides
- Lecture 8: slides, lecture notes from Fang Pin, lecture notes from Xin Fan, lecture notes from Zhe Wang, related materials.
- Lecture 9: slides 1, slides 2,Lecture notes from Yao Deng
- Lecture 10: slides,lecture notes from Hao Zhou.
- Lecture 11: slides 1, slides 2,lecture notes from Hongxiao Bai, related materials.
- Lecture 15: Lecture notes from Zhenxing Gu.
- You could also refer to the course website of last year for more related materials. The password for those pdf is sjtu2016.

If you have any problem with this website, please contact yxghost@sjtu.edu.cn