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 from the course text,
...
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 from 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,
[email protected]
•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,
[email protected]
•Office: DC 3591 (near front of room)
•Office hours: Monday 2:30-3:30 PM
•Joseph Haraldson,
[email protected]
•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:
[email protected]
•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
