Scribd
Upload
33 views

Ders1 - Basic Concepts For Data Structures

Basic Concepts for data structures

Uploaded by

mcsurmeli39
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
33 views

Ders1 - Basic Concepts For Data Structures

Basic Concepts for data structures

Uploaded by

mcsurmeli39
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 31

BBS 516

VERİ YAPILARI VE
ALGORİTMALARI
• Dr. Öğretim Üyesi Adnan Özsoy

• adnan.ozsoy@hacettepe.edu.tr

• Office : 114

• Ders: 18.15 – D9

• 18.30?
About the course
• This course will help students understand the basic data
structures such as matrices, stacks, queues, linked lists,
etc.
References

• Veri Yapıları ve Algoritmalar, Rıfat Çölkesen, Papatya Bilim, 2002

• Data structures and algorithms in Java, MT Goodrich, R Tamassia, MH


Goldwasser - 2014

• Fundamentals of Data Structures in C. Ellis Horowitz and Sartaj


Sahni, 1993.

• Data Structures and Algorithm Analysis in C++. Mark Allen Weiss.

• Problem Solving and Program Design in C, 7th Edition. Jeri Hanly


and Elliot Koffman, Pearson, 2013
Communication

• The course web page will be updated regularly throughout


the semester with lecture notes, programming
assignments, announcements and important deadlines.

• https://piazza.com/hacettepe.edu.tr/spring2020/bbs516
Notlandırma
• Ara Sınav : 30%
• Final : 40%
• Proje : 30% - 3 proje
Policies
• Work groups
• You must work alone on all assignments stated unless otherwise

• Submission
• Assignments due at 23:59 (no extensions!)

• Lateness penalties
• No late submission
• Only have one time 2 day late submission
Cheating
• What is cheating?
• Sharing code: by copying, retyping, looking at, or supplying a file
• Coaching: helping your friend to write a programming assignment, line by line
• Copying code from previous course or from elsewhere on WWW

• What is NOT cheating?


• Explaining how to use systems or tools
• Helping others with high-level design issues
Cheating
• Penalty for cheating:
• Removal from course with failing grade

• Detection of cheating:
• We do check: Our tools for doing this are much better than most
cheaters think!
Ders Programı:

Hatfa Konu
Feb.24 Giriş
Mar.02 Algoritma Analizi
Mar.09 Dizinler
Mar.16 Yığın ve Sıralar
Mar.23 Sıralama 1
Mar.30 Sıralama 2
Apr.06 SINAV
Apr.13 İfadeler
Apr.20 Bağlı Listeler 1
Apr.27 Bağlı Listeler 2
May.04 Arama Algoritmaları
May.11 Ağaç
May.18 Tries
May.25 HOLIDAY
TBD FINAL
BASIC CONCEPTS
FOR DATA STRUCTURES
Data StructuresàData StructurING

How do we organize information so that we can find,


update, add, and delete portions of it efficiently?
Data Structure Example Applications

• How does Google quickly find web pages that contain a


search term?

• What’s the fastest way to broadcast a message to a network of


computers?

• How can a subsequence of DNA be quickly found within the


genome?

• How does your operating system track which memory (disk or


RAM) is free?

• In the game Half-Life, how can the computer determine which


parts of the scene are visible?
Suppose You’re Google Maps…
• You want to store data about cities (location, elevation,
population)…

What kind of operations should your data structure(s) support?


Operations to support the following scenario…
Finding addresses on map?
• Lookup city by name...

Mobile user?
• Find nearest point to me...

Car GPS system?


• Calculate shortest-path
between cities…
• Show cities within a given
window…

Political revolution?
• Insert, delete, rename cities
How will you count user views on YouTube?
• Lets write a userViewCount() function
int userViewCount (int current_count)
{
int new_count;
new_count =current_count + 1;
return new_count;
}

Will this implementation


work all the time?
How will you count user views on YouTube?
%99.9 times yes.
How will you count user views on YouTube?

YouTube's counter
previously used a 32-bit
integer

YouTube said the video - its


most watched ever - has
been viewed more than
2,147,483,647 times.

It has now changed the


maximum view limit to
9,223,372,036,854,775,808,
http://www.bbc.com/news/world-asia-
30288542
or more than nine quintillion.

http://www.economist.com/blogs/economist-
explains/2014/12/economist-explains-6
How bad can it be?
• June 4, 1996
• Ariane 5 rocket launched by the European Space Agency
• After a decade of development costing $7 Billion
(~21 Billion in Turkish Liras, just for comparison Istanbul’s
third bridge cost estimates are 4.5 Billion TL)
• Exploded just 40 seconds after its lift-off
• The destroyed rocket and its cargo were valued at $500
million
• Reason?
How bad can it be?
• Reason?
• Inertial reference system error: specifically a 64 bit
floating point number relating to the horizontal velocity of
the rocket with respect to the platform was converted to a
16 bit signed integer.
• The number was larger than 32,767, the largest integer
storable in a 16 bit signed integer, and thus the
conversion failed.
• $500 Million rocket/cargo
• Time and effort
Floating Point Representation
Floating Point Representation
28

Goals

“I will, in fact, claim that the difference between a bad


programmer and a good one is whether he considers his
code or his data structures more important. Bad
programmers worry about the code. Good programmers
worry about data structures and their relationships.”
Linus Torvalds, 2006
Data Structures
A data structure is a way to
store and organize data in
computer, so that it can be
used efficiently.

Some of the more commonly


used data structures include
lists, arrays, stacks, queues,
heaps, trees, and graphs. Binary Tree
Why So Many Data Structures?
• Ideal data structure:
• “fast”, “elegant”, memory efficient

• Generates tensions:
• time vs. space
• performance vs. elegance
• generality vs. simplicity
• one operation’s performance vs. another’s

The study of data structures is the study of


tradeoffs. That’s why we have so many of
them!
• Dr. Öğretim Üyesi Adnan Özsoy

• adnan.ozsoy@hacettepe.edu.tr

• Office : 114

• Ders: 18.15 – D9

• 18.30?

• https://piazza.com/hacettepe.edu.tr/spring2020/bbs516

You might also like