Algorithms Xiaojuan Cai cxj@sjtu.edu.cn Fall semester 2016

Course Overview Why study Algorithms Outline of the course Course Polices 12/8/2018 Xiaojuan Cai

What is Algorithm? The word ‘algorithm’ is derived from the name of Roman numerals, Arabic numeral, invented in India, but the most influential medium of transmission turned out to be a textbook, written in Arabic in the ninth century by Al Khwarizmi who lied in Baghdad. He laid out the basic methods for adding, multipl and dividing numbers. http://en.wikipedia.org/wiki/File:Abu_Abdullah_Muhammad_bin_Musa_al-Khwarizmi_edit.png Muḥammad ibn Mūsā al-Khwārizmī (780?-850?) a Muslim mathematician whose works introduced Arabic numerals and algebraic concepts to Western mathematics. (American Heritage Dictionary) 12/8/2018 Xiaojuan Cai

What is Algorithm? An algorithm is a procedure that consists of a finite set of instructions which, given an input from some set of possible inputs, enables us to obtain an output through a systematic execution of the instructions that terminates in a finite number of steps. 12/8/2018 Xiaojuan Cai

An example Problem: Sorting Input: A sequence of n numbers <a1, a2, …, an>. Output: A permutation (reordering) <a1’, a2’, …, an’>. of the input sequence such that a1’≤ a2’ ≤ … ≤ an’ An algorithm describes a specific computational procedure for achieving the input/output relationship. An instance of a problem consists of the input needed to compute a solution to the problem. An algorithm is said to be correct if, for every input instance, it halts with the correct output. 12/8/2018 Xiaojuan Cai

Why study Algorithms? What kind of problems are solved by algorithms? The Human Genome Project Internet: routing, searching engine Electronic commerce: public-key cryptography Manufacturing: resource-allocating Map, navigation Similarity of DNA sequences Convex hull … HGP has made great progress toward the goals of identifying all the 100,000 genes in human DNA, determining the sequences of the 3 billion chemical base pairs that make up human DNA, storing this information in databases, and developing tools for data analysis 12/8/2018 Xiaojuan Cai

“Computer Science is the study of algorithms.” Why study Algorithms? 1. Their impact is broad and far-reaching. Internet, Biology, Computers, Computer graphics, Security, Multimedia, Physics ...... Internet. Web search, packet routing, distributed file sharing, ... Biology. Human genome project, protein folding, ...Computers. Circuit layout, file system, compilers, ...Computer graphics. Movies, video games, virtual reality, ...Security. Cell phones, e-commerce, voting machines, ...Multimedia. MP3, JPG, DivX, HDTV, face recognition, ...Social networks. Recommendations, news feeds, advertisements, ...Physics. N-body simulation, particle collision simula “Computer Science is the study of algorithms.” -- Donald E. Knuth 12/8/2018 Xiaojuan Cai

“ Algorithms + Data Structures = Programs. ” Why study Algorithms? 2. to become a proficient programmer “ Algorithms + Data Structures = Programs. ” -- Niklaus Wirth The Art of Computer programming. After producing the third volume of his series in 1976, he expressed such frustration with the nascent state of the then newly-developed electronic publishing tools (especially those that provided input to phototypesetters) that he took time out to work on typesetting and created the TeX and METAFONT tools Niklaus Wirth: Algo W, Euler, Pascal, Modula, Oberon “Bad programmers worry about the code. Good programmers worry about data structures and their relationships. ” -- Linus Torvalds 12/8/2018 Xiaojuan Cai

Why study Algorithms? 3. For intellectual stimulation, be a wise person “有人天生喜欢“遍历”，踏遍千山万水，遍享万种风情...... 有人一生“贪婪”，眼界不宽，及时行乐； 有人注定适用“穷搜”，辛辛苦苦勤勤恳恳一辈子，付出很多，收获有限； 有人善用“时空权衡”，用最少的时间办最多的事情，的确精明； 有人会“分治”，再多的难题也能迎刃而解； 有人常“回溯”，错的太多，后悔太多； 有的人压根没有算法，于是盲目生活，盲目做事，最后所获无几；……” --- 邹恒明 《算法之道》 12/8/2018 Xiaojuan Cai

4. For profit 12/8/2018 Xiaojuan Cai

Why study anything else? Why study Algorithms? Why study anything else? 1. Their impact is broad and far-reaching. 2. to become a proficient programmer. 3. For intellectual stimulation, be a wise person 4. For profit 5. Old roots, new opportunities. 6.They may unlock the secrets of life and of the universe. ...... (Source from “Algorithms” by R. Sedgewick and K. Wayne) 12/8/2018 Xiaojuan Cai

Where are we? Why study Algorithms Outline of the course Course Polices 12/8/2018 Xiaojuan Cai

References 1. Algorithms: Design Techniques and Analysis, M.H. Alsuwaiyel 2. Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein 3. Algorithms, S, Dasgupta, C. Papadimitriou, U. Vazirani 4. Algorithms, 4th edition, R. Sedgewick, K. Wayne 12/8/2018 Xiaojuan Cai

Course Overview 12/8/2018 Xiaojuan Cai

Course goals To become proficient in the application of fundamental algorithm design techniques To gain familiarity with the main theoretical tools used in the analysis of algorithms To study and analyze different algorithms for many of “standard” algorithmic problems To introduce students to some of the prominent subfields of algorithmic study in which they may wish to pursue further study 12/8/2018 Xiaojuan Cai

Where are we? Why study Algorithms Outline of the course Course Polices 12/8/2018 Xiaojuan Cai

Grading Policy Homework 25% Programming assignment 15% Final exam 60% Distributed on course website after every lecture Submit every Tuesday Programming assignment 15% LeetCode (http://leetcode.com) Final exam 60% 12/8/2018 Xiaojuan Cai

TAs Homepage: http://basics.sjtu.edu.cn/~xiaojuan/algo16/ TAs  Chunmiao Li (李春淼), lichunmiao@sjtu.edu.cn Ruoyu Wang (王若愚), babyfish92@163.com Homepage: http://basics.sjtu.edu.cn/~xiaojuan/algo16/ 12/8/2018 Xiaojuan Cai

More on LeetCode Submission: Due on every Saturday night: 23:59 One student will be selected (randomly) to be report your solution （in 5 minutes） on Tuesday. 12/8/2018 Xiaojuan Cai

Teaching techniques One-minute paper Group teaching Final score = score + 3 (bonus) 12/8/2018 Xiaojuan Cai

Voices from senior students 算法是用来娱乐身心、课余刷题、公司面试、学会使用编程思想来看待各种问题的课程 用心学算法，很有意思的，这是程序员的内力修为，别太在意考试面试 坚持到期末 算法无论从哪个次元来看都是程序员的基础。 好好听课，不然会对自己失去信心。 这是我在软院上过最有意思最有收获的一门课。 算法很重要，但更重要的是思想。或许将来我们不会用到今天学习的算法，但是某个算法的思想会帮我们解决很多实际问题。 大神们请低调，给学渣们活路啊！ 还是从被窝里爬起来吧，对找工作还是很重要滴 … 12/8/2018 Xiaojuan Cai

Enjoy! 12/8/2018 Xiaojuan Cai