Extending a Game Application Using Data Structures and Algorithms

Extending Game Using DSA

Examination

Algorithms for structure operations; insert, remove, retrieval
Algorithms for structure navigation; search and sort
Algorithm types: iterative and recursive
Relationship between ADTs and computing fundamentals (e.g. Stack, Queue)
Use of Big O notation to specify time complexity for simple algorithms
Debug / Profiling tools for Internal State Examination.
Debug / Profiling tools for algorithmic execution analysis (e.g. Frame Analysis)
Memory Management: Pointers, References, Heap, Stack. 
STL and Boost: algorithms, iterators, and containers.
Introduction to Parallel Programming
- Goals of parallelism (e.g., throughput) versus concurrency (e.g., controlling access to shared resources)
- Parallelism, communication, and coordination
- Programming constructs for coordinating multiple simultaneous computations
- Need for synchronization
- Data races (simultaneous read/write or write/write of shared state)
- Higher-level races (interleavings violating program intention, undesired non-determinism)
- Lack of liveness/progress (deadlock, starvation)
- Game Specific Structures: 
- Scene Graphs 
- BSP/Quad Tree/kd-tree/OctTree
- Frustums. 
- Linear Data Managers and Object Aliasing
- Broadphase Collision Containers
- Component-Based Game Objects.
- Buffers and Queues – CPU vs GPU Representation.
- BitSets and Enumerations
- Enumerated Dictionaries. 
- Pipelines and Caches
- Type Semantics, SISD vs SIMD Access Traits. 
- Review of physical memory and memory management hardware
Data Oriented Programming vs. Object Programming solutions for Data Structure Representation. 
Brute Force/Greedy/Divide and Conquer
C&#43;&#43; Templates
C&#43;&#43; Class and Pointer Memory Layouts
C&#43;&#43; Specific Optimisation Strategies.
Sequential vs. parallel processing
Parallel programming vs. concurrent programming
Request parallelism vs. Task parallelism
Abstract Data Types and common implementation strategies:
- Linear ADTs:
- Lists (Arrays, Linked Lists)
- Stacks, Queues
- Non-Linear ADTs:
- Trees, Binary Trees, BSTs
- Maps (ListMaps, BSTMaps, HashMaps)
- Graphs
- Undirected
- Directed
- Weighted
- Graph Theory Fundamentals (Nodes, Edges etc).

Data Structures and Algorithms for Games - 5107COMP

Data Structures and Algorithms for Games

Construct user-defined ADTs in C++ and utilise the Boost/STL APIs in order to store data related to both game mechanics and game engine architecture.

Develop software that utilises appropriate algorithms and data structures to satisfy a technical game design specification.

Appraise a range of fundamental data structures and their operations.

Evaluate Sequential vs Parallel Algorithm Strategies and their relationship to CPU / GPU architectures.

Apply appropriate data structures in order to solve specific sub problems related to game and game engine development.

Analyse and differentiate fundamental algorithms’ (such as insert, remove, search, sort) time and space complexity characteristics as applied to a range of ADT implementations.