Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Data Structures and Algorithms

Adapted from Brett Hannan
by

Jon Weisz

on 20 January 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Data Structures and Algorithms

DS
+
ALG
“(computer science) the organization of data (and its storage allocations in a computer)”
Data Structure
“The way data is encoded by a computer. Data structure is not usually the concern of the user.”
Data Struture
www.uni-due.de/CP/key_terms.htm
wordnetweb.princeton.edu/perl/webwn
“a way to store and organize data in order to facilitate access and modifications”
Data Structure
highered.mcgraw-hill.com/sites/0070131511/student_view0/glossary_b-d.html
“A logical relationship among data elements that is designed to support specific data manipulation functions"
Data Structure
www.vertaasis.com/glossary.php
"a precise rule (or set of rules) specifying how to solve some problem"
Algorithm
wordnetweb.princeton.edu/perl/webwn
“A precise step-by-step plan for a computational procedure that begins with an input value and yields an output value in a finite number of steps”
Algorithm
en.wiktionary.org/wiki/algorithm
“In mathematics, computer science, and related subjects, an algorithm is an effective method for solving a problem expressed as a finite sequence of instructions.”
Algorithm
en.wikipedia.org/wiki/Algorithm
*
*
Effective Method
Always gives a right answer (rather than a wrong answer or none)
Is expressed as a finite sequence of finite instructions
Always finishes executing after a finite number of steps
Works for all instances from the class of problems
Example: iTunes database
String target = “Careless Whisper”;
if (song001.title.equals(target)...
else if (song002.title.equals(target)...
else if (song003.title.equals(target)...
else if (song004.title.equals(target)...
else if (song005.title.equals(target)...
else if (song006.title.equals(target)...
else if (song007.title.equals(target)...
else if (song008.title.equals(target)...
...


What operations might we want to perform?
What arrangement(s) will allow us to do so?

Consider the painfully simplistic case where we have no data structures other than individual objects...

String target = “Careless Whisper";

for (int i=0; i<size; i++)
if (song[i].equals(target)
...



With arrays
With only individual objects
What difference would it make if the array was sorted v. unsorted?


Other considerations
a[0] = new Song("All of Me");
a[1] = new Song("Break Free");
a[2] = new Song("Chandelier");
a[3] = new Song("Dirt");
a[4] = new Song("Fancy");
a[5] = new Song("Girls chase Boys");
a[6] = new Song("Happy");
a[7] = new Song("I Don't Dance");
a[8] = new Song("Maps");
a[9] = new Song("Rude");
a[10] = new Song("Shake it Off");
a[11] = new Song("Timber");
Ordered Array
a[0] = new Song("Happy");
a[1] = new Song("Chandelier");
a[2] = new Song("Shake it Off");
a[3] = new Song("Timber");
a[4] = new Song("All of Me");
a[5] = new Song("Maps");
a[6] = new Song("Girls chase Boys");
a[7] = new Song("Dirt");
a[8] = new Song("I Don't Dance");
a[9] = new Song("Break Free");
a[10] = new Song("Rude");
a[11] = new Song("Fancy");
Unordered Array
x
x
x
x
x
x
x
o
o
o
x
x
x
x
x
x
x
x
x
x
o
o
x
o
x
o
x
o
x
x
x
x
x
x
x
x
o
o
x
o
x
o
x
o
x
x
4
*
3
2
*
3*3 Game Board
9! = 9*8*7*6*5*4*3*2*1
= 362,880
Search approach to Tic-Tac
Goal?
Path to goal?
Search technique?
Feasibility?
5*5 Square has 25! possible sequences
25! = 1.55E+25
= 15,511,210,043,331,000,000,000,000

For comparison, the age of the universe in seconds is estimated to be 4.35E+17 seconds...
11*11 gameboard
121! = 8.09E+200

Compare: lower bound estimate for the future age of the universe at its heat death is 1.0E+100

Write answers to the following questions to the best of your ability. Be as thorough and accurate as possible, while remaining concise.

What is a data structure?
Give examples.
What is an algorithm?
Give examples.
Why do we study data structures and algorithms together?

Why the + ?
First - can you recall our definition for "data structure"?
The data structure chosen determines what algorithms we can carry out
COMS W3137 Lecture 1
What Kind of Relationships?
Data Structure

Physical Properties
Color
Shape
Position
Velocity

Organizational Properties
Groups
Schedules
Orderings
A generic set of tools for organizing what we know, and how we know it.
Datastructures
Tools
A generic set of tools for answering questions about what we know.
Algorithms
A specific set of tools for implementing things more efficiently.
Instrumentation
IDE
Spend more time programming, less time coding
Automatic code completion
Online syntax checking
Automatic simple error correction
IntelliJ IDEA
Eclipse
Revision Control Systems
Tool for versioning files
Checkpoint your work
Easy backups to the cloud.
Get in to good habits early
Use Github
Full transcript