Transcript Data Structures 1

Instructor: Dr. Sahar Shabanah
Fall 2010
Lectures
 ST, 9:30 pm-11:00 pm
 Text book:
 M. T. Goodrich and R. Tamassia, “Data Structures and Algorithms in
Java”, 4th Edition, 2005, Wiley, ISBN: 978-0471738848
 Lecture slides will be posted on the course page before each
lecture.
 Read thru the lecture notes and the assigned readings before
class.
 Be prepared to ask questions.
 Class website:
http://groups.yahoo.com/group/CPCS204_F10/
Grading
 20% Lab & Assignments
 20% Mid-Term Exam
 20% Final Project
 40% Final exam
Course Content
 Object Oriented Design
 Arrays & Linked Lists
 Analysis tools
 Stacks & Queues
 Lists
 Trees
 Heaps
 Maps & Tables
 Sorting & Searching Algorithms
Data Structures
 A data structure in computer science is a way of
storing data to be used efficiently.
 A data structure is a representation of a finite data
set [2].
 Data Structures examples are Array, List, Linked
list, Doubly linked list, Stack, Queue, Hash table,
Graph, Heap, Tree, Binary Search tree, Red-Black
tree, etc
Data Structure Basic Operations
 Queries operations
 get information about the data structure.
 Search (data structure, key):

searches for a given key in a data structure.
 Sort (data structure):

sorts elements of a data structure.
 Minimum(datastructure):

finds the element with the minimum value in a data
structure.
Data Structure Basic Operations
 Maximum (data structure):
 finds the element with the maximum value in a data
structure.
 Successor (data structure, element):
 finds the element that succeeds the given element in a
data structure.
 Predecessor (data structure, element):

finds the element that precedes the given element in a
data structure.
Data Structures Basic Operations
 Modifying operations:
 Change the status of a data structure.
 Insert (data structure, element):


inserts an element into a data structure.
Delete (data structure, element):
 deletes an element from a data structure.
Algorithms
 An algorithm is a sequence of
computational steps that transform the
input into the output .
 Algorithms can be classified according to
the problem-solving approach that they use
or the problems that they solve.
Algorithms with similar problemsolving approach
 Recursive Algorithms: convert the problem into
sub-problems, then solve each one using
recursion.
 Backtracking Algorithms: return a solution if
found or recur through the problem with every
possible choice until solution or failure is reached.
 Brute Force Algorithms: try all possibilities until a
satisfactory solution is found.
Algorithms with similar problemsolving approach
 Divide and Conquer Algorithms: divide the problem
into smaller sub-problems of the same type, and solve
these sub-problems recursively, then combine the
solutions to the sub-problems into a solution to the
original problem.
 Dynamic Programming Algorithms: find the best
solution of multiple exist solutions. Examples are
Knapsack and Activity Selection Problem. Brute Force
Algorithms: try all possibilities until a satisfactory
solution is found.
Algorithms with similar problemsolving approach
 Greedy Algorithms: get the best solution at the
moment, without regard for future consequences. By
choosing a local optimum at each step, it will end up at
a global optimum. Examples are Prim’s and Dijkstra’s
algorithms.
 Branch and Bound Algorithms: a tree of sub-problems
is formed.
 Randomized Algorithms: use a random number at
least once during the computation to make a decision.
Algorithms solve similar problems
 Sorting Algorithms: Bubble Sort, Selection Sort,
Insertion Sort, Shell Sort, Merge Sort, Heap Sort,
Quick Sort, Bucket Sort, etc.
 Linear-Time Sorting: Counting Sort, Radix Sort,
Bucket Sort, etc.
 Graph Algorithms: Breadth First Search (Bfs), Depth
First Search (Dfs), Topological Sort, Strongly
Connected Components, Generic Minimum Spanning
Tree, Kruskal’S, Prim’S, Sin- gle Source Shortest Path,
Dijkstra’S, etc.
Algorithms solve similar problems
 Searching Algorithms:
 List Search: Linear Search, Binary Search, etc.
 Tree Search: Breadth First Search, Depth First Search,
etc.
 Informed Search: Best-First Search, A*, etc.
 String Matching: Naïve String Matching, Knuth-
Morris-Pratt, Boyer-Moore, etc.
Java Programming Basics
 Base Types:
 Objects
 Enum Types
 Methods
 Expressions
 Control flow
 Arrays
 Simple Input and Output
Object-Oriented Design
 Intro
 Inheritance
 Polymorphism
 Exceptions
 Interfaces and abstract Classes
 Casting
 Generics