Data Structures for Efficient Information Processing
This course on data structures covers essential concepts such as organizing data, runtime considerations, and the importance of choosing the right data structure for various operations. It emphasizes the need for strategic data organization to enhance efficiency and performance in modern applications. Dive into topics like abstract data types, data structure consideration, and the impact of problem sizes on runtime. Explore the trade-offs involved in sorting data and learn how different data structures like AVL trees and heaps impact operations like insert, lookup, and get-min. Additionally, find valuable links for further resources and stay up-to-date with course administrivia.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Introduction to Data Structures
Course Administrivia My office hours: Mon 11:30am-1:30pm, Wed 12:30- 1:30pm, Fri 11:30am-2:30pm, in this Zoom room. Exams: two midterms and a final. Exams are open-book, open-notes. Six assignments. Each assignment has a written component, due in one week, and a programming component, due in two weeks. Lectures will be recorded and posted on the website as soon as they are ready. Powerpoint slides will be posted on the website shortly before start of lecture. One-on-one meetings this week! Class should be interactive. Either raise your hand or write in chat to ask questions.
Some Helpful Links http://ee.usc.edu/~redekopp/csmodules.html Remedial modules http://ee.usc.edu/~redekopp/csmodules .html http://bytes.usc.edu/cs104/ Class website http://bytes.usc.edu/cs104/ http://ee.usc.edu/~redekopp/csmodules.html
Organizing Your Data Should you always sort your data? No. What are the tradeoffs? An Insert operation becomes more expensive (but a Lookup operation becomes less expensive) In a backup system, you are constantly adding new information, and you rarely (hopefully never) look up that information. How should you organize your data? What is the best data structure? The answer is, invariably, it depends. Otherwise, this class would be called Data Structure (singular), I d teach it to you today, and everyone would go home and get an A.
Data Structure Consideration
Data Structures Matter! Modern applications process vast amount of data Various data structures allow these operations to be completed with different time and storage requirements Data Structure Insert Lookup Get-Min (1) (n) (n) UnsortedList (log n) (log n) (log n) AVL Tree (log n) (n) (1) Heap
Importance of Runtime Problem Size Bit operations used n2 2n n = log n n n log n n! 3 x 10-11s 10-10s 3 x 10-10s 10-9s 10-8s 3 x 10-7s 10 4 x 1011 years 102 7 x 10-11s 10-9s 7 x 10-9s 10-7s * 103 10-10s 10-8s 10-7s 10-5s * * 104 1.3 x 10-10s 10-7s 10-6s 10-3s * * 105 1.7 x 10-10s 10-6s 2 x 10-5s 0.1 s * * 106 2 x 10-10s 10-5s 2 x 10-4s 10.2 s * *
Abstract Data Types Programming students tend to focus on the code and less on the data and its organization More seasoned programmers focus first on What data they have How it will be accessed How it should be organized An abstract data type describes what data is stored and what operations are to be performed A data structure is a specific way of storing the data implementing the operations Example ADT: List Data: items of the same type in a particular order Operations: insert, remove, get item at location, set item at location, find Example data structures implementing a List: Linked list, array, etc.
Our First ADT
Course Goals 01 02 03 Learn basic and advanced techniques for implementing data structures and analyzing their efficiency Learn how to identify the best data structure for your needs. Learn to utilize ADTs to specify the functionality of what you want to do. Will require mathematical analysis from CS 170
