Data Structures
General Course Information
Edirlei Soares de Lima
<edirlei.lima@universidadeeuropeia.pt>
Data Structures
•
Professor: Edirlei Soares de Lima
–
Education:
•
•
•
B.Sc. in Computer Science – UnC
M.Sc. in Computer Science – UFSM
Ph.D. in Computer Science – PUC-Rio
–
–
Teaching Experience: PUC-Rio, UNIRIO, UERJ, IADE-UE
Game Experience:
•
•
•
Game Engines: RPG Builder, 3D Game Builder;
Research Projects: most are related with Logtell (http://www.icad.puc-rio.br/~logtell/);
Games: Krimson (Best Game Award at SBGames 2010 – Indie Game Development
Festival), and several other prototype games.
–
More Information: https://edirlei.com/
What is a Data Structure?
•
A data structure defines how data is arranged in memory and
can be operated on by using various algorithms.
–
One of the most basic data structures used in general computer
programming is the array.
•
•
All data structures need algorithms to perform tasks and
manipulate data in memory.
Data structures are the foundation of many techniques used
in game programming and are essential to create specific
game mechanics in an efficient and effective way.
Example: Search in an Array
•
Problem:
Input: array a with n numbers and a number d to be
searched.
Output: i if the searched number is at v[i] or -1 if the
searched number is not in the array a;
Example: Search in an Array
•
The first algorithm: iterate over the array a, element by
element, checking if d is equal to one of the elements of a:
int SearchArray(int[] a, int d)
{
int i;
for (i = 0; i < a.Length; i++){
if (a[i] == d){
return i;
}
}
return -1;
}
Example: Search in an Array
•
Worst Case?
–
–
–
d is not in the array
In this case, n tests are necessary
T(n) = n → O(n) - Linear!
•
•
Best Case?
–
d is the first element
T(n) = O(1)
–
Algorithm complexity: when
analyzing an algorithm, we need
to consider the “Worst Case”,
the “Best Case” and the
Average Case?
–
n/2 tests
“Average Case”
–
T(n) = n/2 → O(n) - Linear!
Example: Search in an Array
•
What if the array is sorted?
–
We can improve the algorithm:
int SearchSortedArray(int[] a, int d)
{
int i;
for (i = 0; i < a.Length; i++)
{
if (a[i] == d)
return i;
else if (a[i] > d)
return -1;
}
return -1;
}
Example: Search in an Array
What is the complixity of the new algorithm?
Best Case:
•
•
–
T(n) = O(1)
An algorithm can have the same
complexity of another algorithm,
but it may be more or less efficient
than the other. Efficiency and
•
Worst Case:
–
complexity are different concepts.
T(n) = n → O(n) - Linear!
Example: Search in an Array
•
•
Can we improve the search algorithm?
–
Yes!
Binary search algorithm:
–
–
–
Compare d with the element that is in the middle of a;
if d is less than the middle element, search in the first half of the array;
if d is greater than the middle element, search in the second half of
the array;
–
–
if d is equal to the middle element, retorn its index;
Continue the procedure subdividing the select part of the array until
finding the searched element or reaching the end of the array.
Example: Search in an Array
int BinarySearchArray(int[] a, int d){
int begin = 0;
int end = a.Length - 1;
int middle;
while (begin <= end){
middle = (begin + end) / 2;
if (a[middle] > d)
end = middle - 1;
else if (a[middle] < d)
begin = middle + 1;
else
return middle;
}
return -1;
}
Example: Search in an Array
•
Worst Case: d is not in the array
–
–
–
2 tests are performed at every iteration;
At every iteration, the size of the search area is divided in half;
T(n) = O(log n)
Iteration
Size of the problem
1
2
n
n/2
n/4
n/8
…
3
4
…
log n
1
Algorithm Analysis – Complexity Types
Difference between O(n) and O(log n)
Input Size
O(n)
10 sec
1 min
O(log n)
3 sec
10
0
6
6 sec
6
00
600
6 400
592 000
46 080 000
4 608 000 000
10 min
1 hour
1 day
9 sec
3
12 sec
16 sec
21 sec
30 sec
36 sec
8
2
1 month
1 year
9
9
100 years
Data Structures
•
•
Games Development:
–
Explore the main concepts and applications of algorithms and data
structures used for game programming.
Learning Outcomes:
1
2
3
4
. Determine the complexity of algorithms;
. Implement common data structures used for game development;
. Implement and compare the performance of different algorithms;
. Apply algorithms and data structures in game programming.
Data Structures
•
Module Content:
1. Introduction to Data Structures and Algorithms
2. Data Structures:
a. Arrays
b. Linked Lists
c. Stacks
d. Queues
e. Hash Tables
f. Trees
g. Graphs
Method
•
Active and experiential learning:
–
–
–
Theoretical concepts;
Practical examples;
Implementation exercises;
•
•
Game framework: Unity 2021.x.x
Semester’s PBL team project:
–
Apply the studied algorithms and data structures in the implementation
of the semester’s project.
•
The game must use at least 3 different types of data structures.
•
All choices of data structures must be justified in a final report.
Evaluation
•
Continuous Assessment:
–
[70%] Intermediate assessment:
•
[40%] Individual exercises on the studied concepts;
•
[30%] Second intermediate delivery of the team project (game prototype)
with group discussion.
•
[30%] Practical exam on the concepts learned.
–
[30%] End of term assessment:
•
[100%] Final delivery of the team project (within the semester’s PBL team
project) with individual discussion + final report.
•
Final Assessment:
–
[100%] Practical exam on the concepts learned.
Evaluation
•
Project Deliveries:
–
1st delivery: game specification
•
No evaluation for Data Structures.
–
2nd delivery: working prototype
•
Basic algorithms and data structures + implementation progress + group
discussion.
–
3rd delivery: final version
•
Algorithms and data structures + overall game complexity and game
experience + individual discussion.
•
Requirements:
The game must use at least 3 different types of data structures (Arrays, Linked
Lists, Stacks, Queues, Hash Tables, Trees, or Graphs).
–
–
All choices of data structures must be justified in a final report.
Bibliography
•
•
•
•
Sherrod, A. (2007). Data Structures and Algorithms
for Game Developers. Charles River Media. ISBN:
978-1584504955
Penton, R. (2002). Data Structures for Game
Programmers. Muska & Lipman/Premier-Trade. ISBN:
978-1931841948
Cormen, T., Leiserson, C., Rivest, R., Stein, C. (2009).
Introduction to Algorithms, 3rd Edition, MIT Press.
ISBN: 978-0262033848
Hocking, J. (2018). Unity in Action: Multiplatform
Game Development in C# (2nd ed.). Shelter Island,
NY: Manning Publications. ISBN: 978-1617294969
Game Frameworks
•
•
Canvas: Data Structures
Course webpage:
–
http://edirlei.com/datastructures
•
Contact:
–
–
edirlei.slima@gmail.com