CISC-121*Introduction to Computer ScienceWinter 2013 |
Image by Alatryste, used under Creative Commons Licence |
Announcements
| Date | Subject | Text |
| 13-4-24 | Quiz 2 | Solutions |
Return to top
Personnel
| Instructor |
Dr. Robin W. Dawes |
 |
| Goodwin
537 |
||
| dawes AT cs
DOT queensu
DOT ca |
||
| http://sites.cs.queensu.ca/dawes/ |
||
| 533-6061 (but
e-mail is a much
better idea) |
||
| Office Hours:
24/7, by appointment |
| TAs |
Name |
Email |
Office
Hours |
Picture |
| Khalid Elgazzar |
elgazzar AT cs DOT queensu DOT ca |
 |
||
| Susanne Morrill |
8sm49 AT queensu DOT ca |
 |
||
Return to top
Course Information
| Calendar
Description |
Introduction to design and analysis of algorithms. Control structures: recursion, backtracking, exits. Data structures: structures, sequences, linked lists and references, binary search trees. Elementary searching and sorting. Introduction to assertions and loop invariants. Introduction to order-of-magnitude complexity. Introduction to numerical computation. Documentation, testing and debugging. |
| Text |
Think Python, by Allen B. Downey (free online version) |
| Syllabus |
Principles of good programming
Fundamentals of procedural programming Recursion Complexity analysis Linear structures Heirarchical structures Searching and sorting Numerical computation and errors Classes and object-oriented programming |
| Marking
Scheme |
2 quizzes @ 15%
1 final exam @ 50% 4 marked lab assignments @ 5% You must pass the final exam to pass the course. There will be no make-up quizzes for missed quizzes. In case of a quiz missed for medical or emergency reasons, an alternative marking scheme may be available. Students with special needs are responsible for contacting the instructor at least a week before each quiz. Please see the Queen's Disability Services page for students for more information. |
Return to top
Schedule
| Class
Schedule Labs |
Tuesday 9:30
- 10:20 Thursday 8:30 - 9:20 Friday 10:30 - 11:20 |
All
class meetings are in Dupuis 217 All labs are in Jeffery 157 |
|
| Assignment and Quiz Schedule |
Date |
Location |
Material |
| Quiz 1 |
February 5, 2013 | ||
| Quiz 2 | March 12, 2013 | ||
| Assignment 1 |
|||
| Assignment 2 |
|||
| Assignment 3 |
|||
| Assignment 4 | |||
Return to top
Course Plan and Record
Course Plan and Record
| Tuesday, January 8 Plan: Intro and Review Notes: History of Computing |
Thursday, January 10 Plan: Intro and Review Notes: Sequence, Selection, Repetition Demo Code: if statements and loops |
Friday, January 11 Plan: Intro and Review Notes: Repetition, Repetition, Repetition ... Demo Code: Collatz Conjecture |
| Tuesday, January 15 Plan: Fundamentals of Programming Notes: Functions |
Thursday, January 17 Plan: "go to, go to; you have known what you should not " Notes: Structured Programming Demo Code: Hammurabi in BASIC Hammurabi in bad Python |
Friday, January 18 Plan: Concision in style, precision in thought, decision in life. Notes: Programming Style Demo Code: Hammurabi in bad Python, using EasyGui |
| Tuesday, January
22 Plan: Top Down Programming Exercise Notes: Guessing Game |
Thursday, January 24 Plan: Lists Notes: Aliasing and Slices |
Friday, January 25 Plan: More Lists Notes: List functions Demo Code: List stuff |
| Tuesday, January 29 Plan: Local and Global Variables |
Thursday, January 31 Plan: Dictionaries Notes: Global and local variables, and dictionaries |
Friday, February 1 Plan: Recursion Demo Code: Recursive Functions |
| Tuesday, February 5 Plan: Binary Search Notes: Recursion and Binary Search Demo Code: Binary Search |
Thursday, February 7 Plan: Notes: More Recursion - Clever Multiplication |
Friday, February 8 Plan: Quiz 1 |
| Tuesday, February 12 Plan: |
Thursday, February 14 Plan: |
Friday, February 15 Plan: Introduction to Objects Notes: Creating Objects |
| *** Reading Week *** | ||
| Tuesday, February 26 Plan: |
Thursday, February
28 Plan: |
Friday, March 1 Plan: More Objects Notes for Week 7: More about objects Demo Code: Date.py Book.py program that uses Book and Date |
| Tuesday, March 5 Plan: Complexity |
Thursday, March 7 Plan: Complexity |
Friday, March 8 Plan: Complexity Notes for Week 8: Complexity Demo Code: growth of functions |
| Tuesday, March 12 Plan: Guest Lecture |
Thursday, March 14 Plan: Guest Lecture Notes for Week 9: Computer Arithmetic |
Friday, March 15 Plan: Quiz 2 |
| Tuesday, March 19 Plan: Complexity of Recursive Functions |
Thursday, March 21 Plan: continued |
Friday, March 22 Plan: continued Notes for Week 10: Complexity of Recursive Functions |
| Tuesday, March 26 Plan: |
Thursday, March
28 Plan: |
Friday, March 29 Plan: Good Friday |
| Tuesday, April 2 Plan: Linked Lists Notes for Week 11 and part of Week 12: Linked Lists Demo Code: Linked Lists |
Thursday, April 4 Plan: |
Friday, April 5 Plan: |
Return to top
Return to top
Labs
| Week |
Lab
Instructions |
Solutions |
| 1: Jan 7 - 11 |
no lab | |
| 2: Jan 14 - 18 |
Working with the Collatz Conjecture Collatz Extensions |
My solution |
| 3: Jan 21 - 25 |
Improving the Hammurabi Game | My solution |
| 4: Jan 28 - Feb 1 |
Social Networks Provided Code: Social_Network.py |
My solution |
| 5: Feb 4 - 8 |
Recommendation Machines Provided Code: Recommendation Starting Point.py |
My solution |
| 6: Feb 11 - 15 | Week 5 Lab continued | |
| *** Reading Week *** | ||
| 7: Feb 25 - Mar 1 |
Ancient Egyptian Fractions | My solutions: Solution 1 (slow) Solution 2 (faster) |
| 8: Mar 4 - 8 |
Image Manipulation Provided Code: Starting Point Provided Images (zipped file) |
My solution |
| 9: Mar 11 - 15 |
Week 8 Lab continued | |
| 10: Mar 18 - 22 |
no lab |
|
| 11: Mar 25 - 29 |
Your choice: Steganography or Trees Provided Code: Starting code for Steganography Starting code for Trees Provided Images (zipped file) Provided Text Samples (zipped file) |
My Steganography Solution My Trees Solution |
| 12: Apr 1 - 5 | ||
Return to top
Practice Problems
| Text
Section |
Exercises |
|
1.8 |
1.2 |
| 2.12 | 2.3 |
| 3.6 | 3.1, 3.2 |
| 3.15 |
3.3 (use column 50
rather than 70 if you prefer) 3.4 3.5 (think about how to generalize this to print any size grid) |
Return to top
Recommended Readings
| Source |
Section |
Read Before ... |
Comments |
| Learning (Your First Job) |
All |
January 11 |
Essential reading for all students |
| Computer Science For Fun | Any | whenever | purely recreational |
| Think Python (TP) | Chapter 1 | should be no surprises here | |
| TP | Chapter 2 | easy peasy | |
| TP | Chapter 3 | getting a bit more interesting | |
| TP | Chapter 5 | starting the good stuff | |
| TP | Chapter 15 | ||
| TP | Chapter 10 | ||
Return to top
Sample Tests
| Quiz 1 | Sample Quiz 1 - this is from a previous year. The material covered this year is slightly different - for example we have not yet covered strings - but the general format and style of the questions is a good indicator of what you can expect on Friday's quiz. |
| Quiz 2 | Sample Quiz 2 - once again, the material covered in the year this quiz was given was slightly different from what we have covered this year. Our test will naturally be based on what we have covered. |
| Final |
Return to top
Academic Integrity in CISC 121
Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).
Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1 on the Arts and Science website) and from the instructor of this course.
Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification, and are antithetical to the development of an academic community at Queen's. Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.
In CISC 121, academic integrity means that the work you hand in as your own (quizzes, final exam and assignments) really is your own. You may ask other people for general help in the course -- by which I mean general explanations and help with practice problems that are not being handed in. You may talk in general terms with other students about marked assignments, as in discussing strategies ("how are you handling the case where the list is empty?") or requirements ("are we supposed to print out all the data or just the average?"). You may not share code or even pseudo-code with anyone else.
I do allow you to work in pairs on assignments, in which case you are obviously allowed to work closely with your partner. To avoid possible misunderstandings, only one of you should hand in the assignment and the assignment should clearly identify both students who contributed to it.
The preceding text on academic integrity was written by Prof. Margaret Lamb and is used here with her permission.
Return to top
Essential Software to Download and Install
Python 2.7 can be downloaded from www.python.org Choose your download format - probably "Windows x86 MSI installer". Save the file and run it. Follow the instructions.
Installing SciTE
Python program files can be edited and run with a number of different tools. I like SciTE, which can be downloaded from http://opensource.ebswift.com/SciTEInstaller/ The download links are at the bottom of the page. You probably want SciTE 2.28 (x86).
There is one nasty bit of stuff you need to do in order to run your Python programs from within SciTE on a Windows machine: You need to modify your computer's "Path" variable to include the location where you installed Python (by default, this will be C:\Python27). Here are the steps for doing this in Windows 7:
1. On the Start Menu, right-click on "Computer", and choose "Properties". Click on "Advanced system settings". Click on "Environment Variables..."
2. Scroll down in the "System variables" window until you see the "Path" variable. Double-click on it.
3. BE VERY VERY CAREFUL
4. In the "Variable value" box, click once (not twice!) and use your arrow keys to move to the end of the string (the cursor will stop moving).
5. Enter the following at the very end of the line: ;C:\Python27
(If for some reason you installed Python in a different directory, use the location you chose here.)
6. Check that line carefully, then check it again. There is a semicolon before the C and a colon after it.
7. Check it again. You do NOT want to mess up your Path variable.
8. If you are sure you have it right, click on OK, and OK your way back out to the Properties window, which you can now close.
Installing EasyGui and Pypng
Here are links to two Python packages that we will be using this term. If you are planning to work on your own computer, you will need to install these. The following instructions describe how to install EasyGui under Windows, but the process is exactly the same for both packages - just substitute "pypng" for "easygui" where needed.
1. Download: click on the link, open or save the file (saving to your desktop is fine, since you don't need to keep these files after installation)
2. Open the file - it is actually a compressed directory.
3. Extract the contents to a new directory on your desktop (give it a name like "temp")
Now the messy bit
4. From the Start Menu, type "Command prompt" in the "search programs and files" box. Start a Command Prompt process.
5. Navigate to the directory you just created. This should need a single command: "chdir desktop\temp"
6. Enter the command "python setup.py install"
7. Observe the output in the Command Prompt window. If it shows no errors, sit back and smile proudly. Good job!
8. On the other hand, if you see something like "error <blahblahblah> Permission denied", then you will have to do the final step by hand.
8.1. Close the Command Prompt Window. It's no longer of any use.
8.2. Open the "temp" directory on your desktop. It will contain a "build" directory. Open it. It will contain a "lib" directory. Open it.
8.3. On the Start menu, open "Computer", then "C:", then "Python27", then "Lib", then "site-packages"
8.4. Drag the file "easygui.py" from the window you opened in 8.2, into the window you opened in 8.3
8.5. If a pop-up window appears telling you you need administrator permission, click "Continue". You're done!
9. Optional clean-up: delete the file that you downloaded in Step 1. Delete the directory you created in Step 3.
| EasyGui | A free, easy-to-use graphical user interface | easygui_v0.95.zip |
| Pypng | A free, easy-to-use png image handling package | pypng-0.0.12.zip |
Return to top
557 Goodwin Hall
Queen's University
Kingston, Ontario, Canada
K7L 2N8
Phone: (613) 533-6050
Fax: (613) 533-6513
