Intro. to Data Structures & Algorithms

Pacman is an arcade game developed by Namanco in 1980.
Scan the QR code to the right or visit the link below it to
play the game. This next link will give you some inter-
esting facts about the game:
Throughout this course we will cover many different data
structures and algorithms. As we cover these algorithms,
a series of 3 projects will guide you in implementing the
algorithms to construct a working game of Pacman. The
rst project will focus on C++ revision and cover the
development of functions to help render images on the
screen and animate the characters.

As we cover different structures, you’ll be required to implement and integrate them into the
game. By the time the course is complete, you should have a fully working version of Pacman that
includes intelligence to control the ghosts.
You are encouraged to add to the game and make it your own. If you ever nd that you have too
much free time, I recommend going through SDL Tutorials by Lazy Foo (http://lazyfoo.
). They will give you better insight to the structure of 2D
graphics programming in SDL and will give you an architecture in which you can start creating
your own game.
While the primary outcome of the course is a thorough knowledge of Data Structures and
Algorithms, you will nd that strong programming skills will assist you throughout your career
in CS. Programming is as much of an art as it is a science. Remember that the only good way to
become a good programmer is to practice. So think of interesting ways to extend your game and
try add them in! Maybe try write your own game of Tetris!

Background & Tools
Git & BitBucket
When working in teams or on large projects you are usually required to use a version control sys-
tem so that everyone knows what version of the code you are editing. These systems then help
you keep track of why a change was made to the code (Commit Message), as well as who made
it (Author). They help you keep track of different changes to the code and if you’re working on
multiple features at the same time, it can be helpful to work on each feature in its own independent
Git is a version control system that allows you to track different versions of your code while
programming. Git was developed by Linus Torvalds (the same person who started Linux) and is
used by millions of programmers around the world and depending on who you listen to between
30%1 and 70%2 of professional programmers use it. We will be using basic the basic functionality
of Git in this course.
BitBucket and GitHub are online hosting environments for Git. BitBucket will give you a free,
unlimited subscription if you register your Wits email with them. This gives you access to private
repositories for your school work. I strongly suggest making use of this.
Git is a command line tool, but there are are plenty of very good and free graphical front ends.
I recommend SmartGIT, which is free for non-commercial use, QGit or Git-Gui.
1. Go to and sign up for a free account. Either signup using
your Wits email address, or signup with your own address and then add your Wits to your
prole under Manage Account — Email Addresses.
(a) Select a “Personal Account”
(b) Follow the process to prove that you’re not a robot.
(c) Conrm your email address by clicking on the link in the email that was sent to you.
2. Once you’ve added and veried your Wits email address visit the BitBucket Academic Li-
cense Page3 to convert your account to an unlimited academic license.

Leave a Reply

Your email address will not be published. Required fields are marked *