Welcome to CS166! Two handouts available up front: course ● information and syllabus. Also available online! ● Today: ● Course overview. ● Why study data structures? ● The range minimum query problem. ● Course Staf Keith Schwarz ([email protected]) Anna Saplitski ([email protected]) Ilan Goodman ([email protected]) Kevin Gibbons ([email protected]) Luna Frank-Fischer ([email protected]) Course Staff Mailing List: [email protected] The Course Website http://cs166.stanford.edu Required Reading Introduction to ● Algorithms, Third Edition by Cormen, Leiserson, Rivest, and Stein. You'll want the third ● edition for this course. Available in the ● bookstore; several copies on hold at the Engineering Library. Prerequisites CS161 (Design and Analysis of Algorithms) ● We'll assume familiarity with asymptotic notation, ● correctness proofs, algorithmic strategies (e.g. divide-and-conquer, dynamic programming), classical algorithms, recurrence relations, universal hashing, etc. CS107 (Computer Organization and Systems) ● We'll assume comfort working from the command- ● line, designing and testing nontrivial programs, and manipulating bitwise representations of data. You should have some knowledge of the memory hierarchy. You should also know how to code in both high-level and low-level languages. Grading Policies 1/3 Assignments 1/3 Midterm 1/3 Final Project Midterm: Tuesday, May 24 Midterm: Tuesday, May 24 7PM – 10PM 7PM – 10PM Location TBA Location TBA Why Study Data Structures? Why Study Data Structures? Explore where theory meets practice. ● Many of the data structures we'll cover are used extensively in ● industry. In fact, some were invented there! Challenge your intuition for the limits of efficiency. ● You'd be amazed how many times we'll take a problem you're ● sure you know how to solve and then see how to solve it faster. See the beauty of theoretical computer science. ● We'll cover some amazingly clever theoretical techniques in the ● course of this class. You'll love them. Equip yourself to solve complex problems. ● Powerful data structures make excellent building blocks for ● solving seemingly dificult problems. Range Minimum Queries The RMQ Problem The Range Minimum Query problem ● (RMQ for short) is the following: Given an array A and two indices i ≤ j, what is the smallest element out of A[i], A[i + 1], …, A[j – 1], A[j]? 3311 4411 5599 2266 5533 5588 9977 9933