Cmpt 120 Assignment 4-6

Introduction to Computing Science and Programming I

Credits: 3

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

Text:
How to Think Like a Computer Scientist - Learning with Python, Allen Downey, Jeffrey Elkner, Chris Meyers, Green Tea Press,
http://www.openbookproject.net/thinkcs/python/english2e/
http://greenteapress.com/thinkpython/html/
CMPT 120 Study Guide, Greg Baker, SFU, 2010:http://www.cs.sfu.ca/CC/120/ggbaker/guide/guide

Recommended References:
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


Course Description:

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.


Course Outline:

WeekTopic
Week 1
  • Computer system introduction
  • Learn how to convert integers to binary and vice versa.
  • Learn and practice how to use two’s complement notation for representing negative integers.
  • Practice using the interactive Python interpreter.
  • Learn and practice how to use basic data types.
  • Learn how to declare variables.
  • Learn and practice how to use assignment statements.
  • Operators and order of operations
Week 2
  • Learn and practice how to use library modules.
  • Learn and practice how to write functions
  • Type conversion and type coercion
  • Parameters and arguments
  • Variable scope
  • Learn and practice how to write pseudocode for Python functions.
Week 3
  • Learn how to use if - else statements.
  • Nested if statements
  • Recursion and recursive functions
  • Learn how to design and use functions that return numbers or strings.
Week 4
  • Learn how to design and use loops.
  • Compare for loop and while loop
  • Learn and practice how to use Boolean expressions.
  • Nested loop
Week 5
  • Compound data type
  • String slicing and string comparison
  • Looping and counting with string
  • List introduced
  • List slicing
  • String and list comparison
  • Mutability of string and list
Week 6
  • Tuple
  • Mutability of tuple
  • Tuples and list comparison
  • Dictionaries
  • Dictionaries used in sparse matrices
Week 7
  • Mid-term review
  • See more examples and exercises.
  • Mid-term
Week 8
  • Learn and practice how to read text files
  • Write to text files
  • Pickling
  • Learn and practice how to use throw and catch exceptions.
Week 9
  • Learn and practice how to design and use basic searching and sorting algorithms.
  • Use O-notation to describe the running time of simple algorithms.
  • Classes and objects introduced
  • Object-oriented programming features
Week 10
  • Class attributes
  • __str__ method and initialization method
  • Method overloading
  • Inheritance
Week 11
  • Card game analysis
  • Data structure
  • Linked lists
  • Lists and recursion
  • Lists as collection
Week 12
  • Abstract data types
  • Stack ADT
  • Implement stacks with Python lists
  • Queue ADT
  • Improved linked queue
Week 13
  • Overall course review.
  • More practice exercises and exam preparation.

Evaluation:

Labs10%
Assignments20%
Mid-term Exams30%
Final Exam40%

Software Download:

Python can be downloaded from official web site: http://www.python.org/download/


Instructors:

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.

  1. 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 .

  2. 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 .

  3. 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.

Implementing

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.]

0 thoughts on “Cmpt 120 Assignment 4-6

Leave a Reply

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