CS 234 Lectures Slides S14

Document Content and Description Below

CS 234 Data Types and Structures Spring 2014 Instructor: Kevin Lanctot Slides based on notes and slides from Lori Case and J.P. Pretti with additions by Kevin Lanctot. Many diagrams are taken fr... om the course text, Data Structures and Algorithms Using Python by Rance D. Necaise Table of Contents Topic Slide 1. Course Overview 2 2. Python Review 21 3. Abstract Data Types 33 4. Python Lists 64 5. Analysis of Algorithms 72 6. Linked Lists 120 7. The Stack ADT 168 8. The Queue ADT 178 9. The Priority Queue ADT 191 Topic Slide 10. Binary Trees 201 11. Sorting 229 12. Searching and Hashing 282 13. Binary Search Trees 334 14. 2-3 Trees 373 15. B-Trees 406 16. Graphs 424 17. Final Exam Notes 478 CS234 Spring 2014 1 Welcome to CS 234! Topic 1 – Course Overview Four Questions • Who am I? Who are we? → Staff • Who are you? → Intended Audience • What are we doing? → Course Objectives • How will we do it? → Course Delivery References • More details in course syllabus available on Learn. CS234 Spring 2014 2 Instructor • Kevin Lanctot, klanctot@uwaterloo.ca •Office: DC 3136 DC 2555C •Office hours: Tue 2:30-3:30 PM • Things to know about me: I’m a talker not a typer. I only check my email once or twice a day. Last name is pronounced long-k toe, i.e. “long toe” with the “k” sound after long CS234 Spring 2014 3 Who are we? → Staff Instructional Assistants • William Saunders, wrsaunde@uwaterloo.ca •Office: DC 3591 (near front of room) •Office hours: Monday 2:30-3:30 PM •Joseph Haraldson, jharalds@uwaterloo.ca •Office: DC 2302 B •Office hours: Tuesday 3:30-4:30 PM • deal with MarkUs, answering questions about course material, issues around assignment marking CS234 Spring 2014 4 Who are we? → Staff Instructional Support Coordinator • Ahmed Hajyasien • email: ahajyasien@uwaterloo.ca •Office: DC 3115 • pick up assignments in his office, deals with cheating cases CS234 Spring 2014 5 Who are we? → Staff Who are you? Intended Audience •Interested in learning more about CS • Seeking to understand the source of potential improvements and efficiencies in programs • Have passed CS 116 or CS 136 • Required for CS minor • CS as a second teachable CS234 Spring 2014 6 What are we doing? Course Objectives • To study efficient algorithms and data structures in a language-independent setting. • To become familiar with a number of standard data structures and algorithm design approaches. • To gain additional experience in program design and implementation. • To appreciate the formal analysis of algorithms. • For example, consider the Jellybean Challenge... CS234 Spring 2014 7 What are we doing? Lessons Learned from Jellybean Challenge • Computers are currently very good as solving some problems and very poor at solving others. • What are we missing from the current state of the art? • How we store and access data is critical. i.e. Data Structures. • How we use computers solve to problems is critical. i.e. Design of Algorithms CS234 Spring 2014 8 What are we doing? Reality Check This course is concerned with efficiency. What other aspects of good program design are important? • use minimal resources (time, space) • easy to understand, maintain, reuse, extend • correct, robust, secure •modular •scalable • elegant (i.e. a simple solution to a difficult problem) CS234 Spring 2014 9 Course Delivery • Lectures will include slides (with some blank sections for discussions) some notes made on whiteboard technical demonstrations • Slides only contain key points must supplement slides with course text and notes taken in class •No labs or tutorials CS234 [Show More]

Last updated: 2 years ago

Preview 1 out of 479 pages