Algorithms and Data StructuresInstructors:Bob SedgewickKevin WayneComputer Science 226Fall 2007Copyright © 2007 by Robert Sedgewick and Kevin Wayne.outlinewhy study algorithms?usual suspectscourseworkresources (web)resources (books)2Course Overview3COS 226 course overviewWhat is COS 226?•Intermediate-level survey course.•Programming and problem solving with applications.•Algorithm: method for solving a problem.•Data structure: method to store information.Topic Data Structures and Algorithmsdata types stack, queue, list, union-find, priority queuesorting quicksort, mergesort, heapsort, radix sortssearching hash table, BST, red-black tree, B-treegraphs BFS, DFS, Prim, Kruskal, Dijkstrastrings KMP, Rabin-Karp, TST, Huffman, LZWgeometry Graham scan, k-d tree, Voronoi diagram4Why study algorithms?Their impact is broad and far-reachingInternet. 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. CD player, DVD, MP3, JPG, DivX, HDTV.Transportation. Airline crew scheduling, map routing.Physics. N-body simulation, particle collision simulation.…Old roots, new opportunitiesStudy of algorithms dates at least to EuclidSome important algorithms were discovered by undergraduates!5Why study algorithms?300 BC1920s1940s1950s1960s1970s1980s1990s2000s6Why study algorithms?To be able solve problems that could not otherwise be addressedExample: Network connectivity [stay tuned]7Why study algorithms?For intellectual stimulationThey may unlock the secrets of life and of the universe.Computational models are replacing mathematical modelsin scientific enquiry8Why study algorithms?20th century science(formula based)21st century science(algorithm based)for (double t = 0.0; true; t = t + dt) for (int i = 0; i < N; i++) { bodies[i].resetForce(); for (int j = 0; j < N; j++) if (i != j) bodies[i].addForce(bodies[j]); }E = mc2F = maF = Gm1m2r2h22m2+ V (r) (r) = E (r)For fun and profit9Why study algorithms?•Their impact is broad and far-reaching•Old roots, new opportunities•To be able to solve problems that could not otherwise be addressed•For intellectual stimulation•They may unlock the secrets of life and of the universe•For fun and profit10Why study algorithms?11The Usual SuspectsLectures: Bob Sedgewick•TTh 11-12:20, Bowen 222•Office hours T 3-5 at Cafe Viv in FristCourse management (everything else): Kevin WaynePrecepts: Kevin Wayne•Thursdays.1: 12:30 Friend 1102: 3:30 Friend 109•Discuss programming assignments, exercises, lecture material.•First precept meets Thursday 9/20•Kevin’s office hours TBANeed a precept time? Need to change precepts?•email Donna O’Leary (CS ugrad coordinator) [email protected] course web page for up-to-date info12Coursework and Grading7-8 programming assignments. 45%•Due 11:55pm, starting Monday 9/24.•Available via course website.Weekly written exercises. 15%•Due at beginning of Wednesday lecture, starting 9/24.•Available via course website.Exams.•Closed-book with cheatsheet.•Midterm. 15%•Final. 25%Staff discretion. Adjust borderline cases.•Participation in lecture and precepts•Everyone needs to meet us both at office hours!Challenge for the bored. Determine importance of 45-15-15-25 weightsFinalMidtermProgramsHWCourse content. http://www.princeton.edu/~cos226•syllabus•exercises•lecture slides•programming assignments (description, code, test data, checklists)Course administration. https://moodle.cs.princeton.edu/course/view.php?id=24•programming assignment submission.•grades.Booksites. http://www.cs.princeton.edu/IntroCShttp://www.cs.princeton.edu/IntroAlgsDS•brief summary of content.•code.•links to web content.13Resources (web)Algorithms in Java, 3rd edition•Parts 1-4. [sorting, searching]•Part 5. [graph algorithms]Introduction to Programming in Java•basic programming model•elementary AofA and data structuresAlgorithms in Pascal(!)/C/C++, 2nd edition•strings•elementary geometric algorithmsAlgorithms, 4th edition (in preparation)Resources
View Full Document
Unlocking...