Introduction to Computing Science and Programming I
Length of Course: 14 weeks
Classroom Hours per Week: 4 hours lecture, 1 hour lab
Corequisites: Pre Calculus 12 or a university mathematics course, English 097
How to Think Like a Computer Scientist - Learning with Python, Allen Downey, Jeffrey Elkner, Chris Meyers, Green Tea Press,
CMPT 120 Study Guide, Greg Baker, SFU, 2010:http://www.cs.sfu.ca/CC/120/ggbaker/guide/guide
Python Programming for the Absolute Beginner, 3rd Edition, Michael Dawson, Course Technology PTR, 2010
Invitation to Computer Science, Third Edition: Java Version, G. Michael Schneider and Judith Gersting , Course Technology, 2006
This course is an introduction to computing science and program design, suitable for students with little or no programming background. Students will learn fundamental concepts and terminology of computing science, acquire introductory skills for programming in a high-level language, and be introduced to the diverse fields and applications of computing science.
Python can be downloaded from official web site: http://www.python.org/download/
Ken Chan, B.Sc. (Simon Fraser), M.S.E.E. (Wayne)
William Cheng, B.Sc., M.Sc. (Cal. State)
Yvonne Yang, B.Sc. (Hunan), Ph.D. (Paris)
Transferability: see www.bctransferguide.ca
This site applies only to CMPT 120 D1 (Burnaby) in Summer 2011. See the other instructors' pages for other sections.
- In a file , write a recursive version of the function. Your function should be:
You can assume that and that . Under those conditions, your function should always return the same list as .
- In a file , write a recursive version of the selection sort algorithm. Your function should be:
The recursive step should be to get the smallest item from into . Once this is done, you can recursively sort the list from to .
- In a file , write a recursive function that takes an unsigned binary value (as a string like ) and converts it to an integer (37 in the example).
This can be done recursively for any length binary string. In the example (), notice that the first 5 characters of the string () convert to the integer 18, and the last character () becomes 1. Therefore, the whole string converts to 37 = 2×18 + 1.
So, you should first convert the first n-1 bits to a decimal value, double it, and add the last bit.
One common component of video games is or . These are people or other entities in games that aren't controlled by the players. These range from the ghosts in Pac-Man to computer-controlled teammates in modern first-person shooters. (The term “NPC” is often reserved for non-opponents, but I'm using to refer to any computer-controlled entity in the game.)
NPCs seem to always receive the same criticism: they're stupid. Even Yahtzee thinks so (caution: he has quite the pottymouth). Most NPCs are prone to things like standing stupidly in a corner, and being generally useless. Basically, things don't seem to have progressed much since Pac-Man.
So, we're going to see what we can do about the problem. Working on a game like Halo 3 seems like a bit much, so we're going to start on the other end of the spectrum, with a Pac-Man-inspired game.
Your job in this assignment is to control the ghosts in a Pac-Man-like game. The game is quite different than the original Pac-Man. We will call our game .
For this assignment, your job is to create an algorithm and program to control the ghosts. Name your program .
Both CMPTman and the ghosts move around a grid of squares. CMPTman is trying to collect all of the dots; the ghosts are trying to catch CMPTman. Our game will eliminate many of the complications of Pac-Man: there will be no power pellets (so no eating ghosts), no bonus items, and no “lives” to lose (when CMPTman hits a ghost, the game is over). This is what the game will look like when played:
Our game will be turn-based instead of an action game. In the game, CMPTman will make two moves, and then each of the ghosts will take one.
You don't have to draw the board or worry about the gameplay: the provided module will do that for you. Your job is to design and implement an algorithm that will control the ghosts. The provided library will take care of CMPTman's moves. You simply have to provide the direction for each ghost to move for each turn.
The fundamental job of the ghosts is simple: get CMPTman!
Doing this “well” is quite hard and you aren't expected create a “perfect” solution (whatever that means). Start by getting the ghosts moving toward CMPTman and work up from there. Note that multiple ghosts can occupy the same square: they don't have to worry about running into each other.
A module “” has been provided: you'll have to download the file. Save this file in the same directory as your program and you should be able to import it.
A collection of hints has been provided.
Your code should be easy to read and understand.
When you submit, include a text file that describes what your code is doing. You can use this to give whatever kind of description you think is appropriate for the markers. This will be a chance to describe anything you think is clever, or that we might not notice. You could also describe known problems (like “the ghosts always gets stuck if…”).
When you're done, create a ZIP file containing the and files you created for this assignment and submit it with the submission server. Don't submit the cmptman module.
[Thanks to Deborah Lee for procrastinating by making nicer icons for the game.]