|
|
|
|
|
|
|
|
|
Announcements
All annonucements will be on Piazza
About CSC180
This course serves as an introduction to computer programming and computer science. We will introduce the Python programming language. We will use Python to solve a variety of problems, and practice problem-solving techniques that are applicable to computational problems. We will discuss good practices in software engineering (designing and building large software systems). We will analyze the efficiency of algorithms, and discuss designing efficient algorithms. Various research areas in computer science (AI, software engineering research, the theory of computation, etc.) will be introduced throughout the term. No previous knowledge of programming or computer science is assumed.
Class tournaments
Pong Tournament: a Pong AI tournament will be held at the end of November, with the format outlined here. Prizes: .5 bonus point for qualifying (beating the Chaser by at least 150 points when playing to 1000), 2 points for third place, 3 points for second place, 4 points for winning, plus medals for teams placing 1st, 2nd, and 3rd. Deadline to enter: Nov. 25 on MarkUs, in teams of one or two.
Gomoku tournament: Teams of up to two people are allowed. To qualify for the tournament, you must win against a program that plays according to the algorithm outlined in Project 2. Two black stones and one white stone will be placed randomly on the board, and you play white. The format of the final tournament is TBD, but you are expected to play for either white or black. Prizes: .5 bonus point for qualifying, 2 points for third place, 3 points for second place, 4 points for winning, plus medals for the winning teams. Time control: your function will have 250ms to return a move. Your submission should be in this format.Deadline to enter: Dec. 2 on MarkUs, in teams of one or two.
Teaching team
Instructor: Michael Guerzhoy. Office: BA5244, Email: guerzhoy at cs.toronto.edu (please include CSC180 in the subject, and please ask questions on Piazza if they are relevant to everyone.)
Getting help
Michael's office hours: Monday 6-7, Tuesday 5-6, Wednesday 6-7, Thursday 7-8. Or email for an appointment. Or drop by to see if I'm in. Feel free to chat with me after lecture!)
Course forum on Piazza (Please sign up right away!)
Lectures
L0101: Monday 5-6 in SF1101, Wednesday 2-3 in BA1130, Thursday 3-4 in BA1130
L0102: Monday 4-5 in SF1101, Wednesday 4-5 in MB128, Thursday 11-12 in WB116
Labs
PRA0101: Tuesday 9-12 in SF1013 (9:30 in the first week)
PRA0102: Wednesday 9-12 in SF1013 (9:30 in the first week)
PRA0103: Friday 3-6 in SF1013
Software
We will be using the free Pyzo IDE to develop Python programs. Please download and install Pyzo right away.
Textbooks
CSC180 is not a standard course (because EngSci students are not standard students), and so we will not be following any one textbook. During the term, I will be recommending readings from:
Practical Programming (2nd edition): An Introduction to Computer Science Using Python 3 by Paul Gries, Jennifer Campbell, and Jason Montojo, 2013 (excellent explanations of basic topics). Available at the link as a pdf, and also available in the bookstore (look on the CSC108 shelf)
Think Python: How to Think Like a Computer Scientist by Allen B. Downey, 2014 (free on the web, the explanations can be somewhat terse)
Problem Solving with Algorithms and Data Structures Using Python by Brad Miller and David Ranum, 2014 (free on the web, I will be recommending readings during the second half of the course from this book)
Evaluation
The better of:5%: Weekly labsand
20%: Assignments
30%: A two-hour midterm
45%: A final exam
5%: Weekly labsYou must receive at least 40% on the final exam to pass the course.
20%: Assignments
20%: A two-hour midterm
55%: A final exam
Bonus marks may be available throughout the term.
Exam
2016 exam paper (reference sheet). Solutions + marking scheme.
2015 exam paper (reference sheet). Partial solution of the challenging problems. I encourage people to work on the problems in the beginning of the exam by themsleves. (Note that Q8 and Q9 were supposed to be very challenging -- exam grades were adjusted.)
2014 exam paper (reference sheet). Solutions and my favourite solution of Q7. Video solution of Q7.
Midterm
Midterm paper, solutions + notes on marking
Oct 31, 6:30pm-8:30pm, in EX200.
How to prepare: make sure that you understand (i.e., can write from scratch) all the labs (and Project I). Make sure you can explain and write from scratch the material from the lecture. Make sure you understand the memory model and global/local variables, and can predict the output in complicated cases.
2015 midterm paper. Reference sheet. Solutions: Part 1, Part 2 (contains optional advanced material).
2014 midterm and aid sheet. (Solutions). Note: in Q2d, True and False should switch places. Another solution is to go return not (a==b==c). Not covered yet: Q2(a), Q2(c), Q3(d), the bonus is difficult without more material.
2010 midterm. (Solutions; note that there is a small bug in the solutions to the last question and that the midterm was written in Python 2, which means that it uses print <things-to-print> instead of print(<things-to-print>).)
Projects
The projects will be submitted and graded using MarkUs. You should be able to login to MarkUs soon.
The assignments are to be done by each student or team alone. Any discussion of the assignments with other students should be about general issues only, and should not involve giving or receiving written, typed, or emailed notes. Please refer to François Pitt's Guidelines for Avoiding Plagiarism.
Project 1: handout, gamify.py (worth 4%, due on Oct.1116 at 10:59 PM). Video: How we'll be testing your program (test_gamify.py). Project 1 FAQ. Sample solution: gamify_soln.py. Marking scheme, gamify_cov.py.
Project 2: handout, gomoku.py (worth 8%, due on Nov.713 at 10:59 PM).
Project 3: handout, synonyms.py, test.txt (worth 8%, due on Nov.2829 at 10:59 PM). Autotester test cases.
Lab handouts
Week of Sept. 12: Welcome to Python. Video instructions for setting up Python 3. Text description: once you start Pyzo, click on "Shell Config", and enter /n/share/copy/csc180f/pyzo2015a/bin/python into the exe field
Week of Sept. 19: Functions and Local and Global Variables: Simulating a Pocket Calculator. Solutions.
Week of Sept. 26: Computation using loops. A hint for Problem 1. Solutions.
Week of Oct. 3: Multifile projects, lists, and loops. Solutions, test_calc.py.
Week of Oct. 10: Lists and loops, nested lists, and matrix multiplication. Solutions.
Week of Oct. 17: Tic-tac-toe (ttt.py). Solutions.
Week of Oct. 17: No lab assignment this week — catch up on previous labs and work on old midterms and CodingBat.
Week of Oct. 31: Gaussian Elimination; sample run. numpy.py. Solutions.
Week of Nov. 7: Dictionaries, Files, and Readability Scores. Solutions I, Solutions II -- Flesch-Kincaid
Week of Nov. 14: Dictionaries, Web Scraping, and Computational Linguistics. Solutions I, Solutions II: web-scraping
Nov. 30/Dec. 2/Dec. 6: def getEngsciAnswer(x): return getEngsciAnswer(x). EngsciAnswer (i.e., solutions). Video solutions: Iterative is_balanced(), implementing the iterative is_balanced() recursively (and tracing the solution). A genuinely recursive approach (tracing the genuinely recursive approach). A recursive str.find().
Lecture notes
Suggested readings for the next couple of lectures: Downey chapters 1-2 and/or Gries chapters 1-2. Note: you're only responsible for the material in lecture. However, some people learn best by reading, which is why I'm listing readings.
Sept. 12: Intro slides, Python expressions and variables, a very simple Python program, Conditionals: printing an absolute number, printing different messages depending on the number. Youtube videos on tracing: Part 1, Part 2, Part 3.
Sept. 13: Intro slides, part 2, the secret number magic trick + comments, more on writing conditional: the Jack Sparrow example (the YouTube clip), intro to the quadratic equation solver
Sept. 16: a note on printing multiple values, string literals in Python, ints and floats, more on finite precision, in the context of the quadratic equation solver. Optional aside for people who like irrational numbers: you cannot store most irrational numbers in computers: there is just not enough space to store an infinite number of digits. So what can you do? You can store a string like "pi", and hope that's interpreted in a sensible way. Of course, most irrational numbers aren't named! You can also store Python code that generates the irrational number in question to arbitrary precision (coming up in a few weeks: code to compute numbers like sqrt(2) and π). But note that there are uncountably many irrational numbers, but only countably many Python programs. That means that you still can't hope to represent almost any irrational numbers.
Suggested readings for the next couple of lectures: Gries ch. 3 and 5, Downey ch. 3-4, Downey 5.1-5.7, Downey 11.6 for global variables.
See these lecture notes on Booleans and if-statements and these lecture notes on locals/globals. Also see this tutorial.
Sept. 19: Functions; global and local variables. Multiple assignments and swapping variables. Just for fun: Happy Talk Like a Pirate Day! Also: The distinction between "parameters" and "arguments" is basically a waste of time (in my humble opinion), but here's an explanation. A lot of the time, the terms are used interchangeably.
Sept. 21: Variable naming conventions (just for fun, see also: PEP 8, the official Python style guide). Boolean functions and Boolean algebra (Just for fun, George Boole, who worked on Boolean Algebra). Fixing up the has_roots() example. Converting Booleans. We started summarizing passing information to and from functions. For completeness: Python operator precedence.
Sept. 22: Passing data to and from functions. Swapping variables, pt 2.
Challenge question: How to swap two variables without using multiple assignments and without defining an additional temporary variable? Hint: start with a = a + b. (Follow-up, requires advanced material: what if the variables are not integers?)
Suggested readings for the next couple of lectures: Downey 7.3-7.4 (Gries Chapter 9 uses some material that we haven't covered from Gries Chapter 8)
Sept. 26: Control flow using return statements. For-loops, and computing powers. While-loops and computing log10. Primality testing with for-loops. Videos: Computing log10 using while-loops, primality testing, tracing is_prime.
Just for fun, about computing exponents: how to compute b^x when x is not an integer? This is generally done by computing power series rather than repeatdly multiplying b by itself. See Lab#3 for an example of a computation of a sum of a power series.
Sept. 28: More assignment operators, integer division. Details on range(). More on for-loops and primality testing. Factorials and trailing zeros. Testing: calculator.py.
Swapping variables without temporary storage. (Advanced material on a generalization of this.)
Just for fun: the too-easy puzzle at the New York Times.
Challenge question: write a function that computes the number of trailing zeros in n! without having to multiply huge numbers.
Sept. 29: Computing PI with no calculus + random.random(). Infinite loops, while, break, and continue. input(), and a bit more about design. Video: Debugging Infinite Loops with Pyzo.
Just for fun: Q in lecture: can random.random() produce truly random numbers? A: Not really, but it can generate pseudorandom numbers. Aside: we don't really need random numbers at all to compute PI: we could generate points on a grid instead.
Suggested readings for the next couple of lectures: Gries Ch. 8-9, Downey Ch. 10.1-10.6, 10.8-10.13
Suggested exercises: Warmup-1, Warmup-2, Logic-1, Logic-2 on CodingBat.
Oct. 3: Academic Integrity in CSC180 (links: Guidelines for Avoiding Plagiarism, Academic Justice at The Varsity, full Academic Tribunal decisions). the if __name__ == '__main__' block (program.py, test_program.py.) Intro to lists.
Oct. 5: Heterogenous lists, insert, append, in, not in. while loops and input. Passwords example: using global variables to store state, parallel lists, testing. Slicing, slicing using loops.
Oct. 6: Extend, extend using loops, functions that modify lists and functions that return values. The missing k problem
Oct. 7 extra tutorial: code from the tutorial, for/while loops simple example
Challenge question hint: to compute the number of trailing 0's in n!, figure out the number of the factors of 5 that make up n!.
Challenge question: how to solve the The missing k problem without looking at any one value in the list more than once?
Suggested exercises: List-1 and List-2 on CodingBat.
Readings for material that is coming up: CSC180 lectures notes: the Python memory model.
Oct. 12: Happy Ada Lovelace Day (Ada Lovelace on wikipedia; the actual paper we discussed). More on indexing in lists. Counting trailing zeros in n!; the missing k problem.
Oct. 13: Yet more on the missing number problem. Nested loops; Nested loops and nested lists.
Oct. 13 office hours code: Review of return.
The CSC180 Pong Tournament (for bonus marks): details here. Oct. 17: Intro to mutability and aliasing; changing the contents of lists inside functions. Lecture on the board: see CSC180 lectures notes: the Python memory model. Video: mutable and immutable variables are treated the same way (Part 1, Part 2.)
Notetaker needed for Lec0102. Please volunteer!
Oct. 19: Lecture on the board. Memory model worksheet and solution. Video Exercise C solution.
Oct. 20: Creating objects in memory, Exercise C and the multiple local variable tables example, in Python Tutor; adding and extending lists. Intro to shallow and deep copying of lists.
Oct. 21 Extra Tutorial: write-up.
Suggested exercises (more challenging): Array-3 on Coding Bat Java (Note: you can't submit those problems since the autotester is for Java rather than Python, but you can still do them).
Suggested viewing: Making a deep copy of lists of lists and why our algorithm doesn't work for lists of lists of lists.
Suggested readings: Shallow vs. Deep Copy
Oct. 24: The elegant solution to the Missing Number problem (4PM section: see also here). AI for tic-tac-toe (see also the Lab#6 solutions). Deep Copy of lists of lists of ints; video: Deep and Shallow Copy, with Diagrams. Intro to strings.
Just for fun: distinguishing zero from the letter oh.
Suggested exercises: String-1 and String-2 on CodingBat. More advanced exercises: String-3 on CodingBat Java.
Oct. 26: Remembering arguments: the example with transmitting a random packet. Reversing strings; anagrams, and some str functions. The longest run example.
Just for fun: Error detection with Checksums; TCP/IP (the usual internet protocol) and checksums.
Challenge/Google interview question: solve the random packet problem without using a list of size N.
Oct. 27: Formatting strings, exec. Generating all passwords by programmatically generating a nested loop. Using continue to generate passwords of different lengths. A state variables example: n "a"s plus b. Don't iterate over lists while modifying them (more on this on Monday).
Optional: Drawing truss bridges using Turtle Graphics; drawing N-PSI using Turtle Graphics. Intro to Turtle Graphics.
Oct. 31: Iterating over lists while modifying them, Pt. 2. Selection sort.
Suggested readings: Midterm solutions. Gries ch. 11, Gries ch. 10. Or: Downey Ch. 11, Downey ch. 12, Downey ch. 14.
Nov. 2: Tuples. Intro to dictionaries. Intro to inverting dictionaries.
Just for fun: UofT endowment reports.
Nov. 3: Sparse matrices. Iterating over dictionaries and modifying them. Inverting dictionaries. Intro to reading files (versedog.txt.)
Just for fun: Reverse telephone directories.
Suggested readings: Computational complexity handout.
Nov. 7: A few optional notes on numerical stability. Optional notes on file encoding. More on files and text processing (losttime.txt, losttime_fr.txt). Intro to runtime complexity anlaysis.
Just for fun: The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!) by Joel Spolsky.
Nov. 9: More on runtime complexity; binary search (also see the readings for this week). Just for fun: Twenty Questions.
Nov. 10: (Binary Search review, on the board). Analyzing longest_run() for worst-case runtime complexity. Timing operations. Functions as objects. Plotting and empirically analyzing the runtime of functions.
Just for fun: Epoch time.
Just for fun: Note that if we ask 20 yes/no questions an eliminate half the possibilities every time, we can eliminate 1/(0.5**20) = 1,048,575 possibilities -- that's a lot of concepts that could be identified with 20 questions. If we are slightly less effective, and can only eliminate 30% of the possibilities every time, we're left with just 1/(0.7**20) = 1253 concepts.
Suggested readings: Computational complexity handout. The Analysis and Sorting and Searching chapters in Miller and Ranum.
Nov. 14: Intro to P3, on the board. Sets. dict.get() and dict.update(). The runtime complexity of Selection Sort.
Just for fun: to read more on babies learning word, see e.g. Paul Bloom, How Children Learn The Meanings of Words (The MIT Press, 2002). For more on distributional semantics, see here.
Just for fun: To sort midterms alphabetically with selection sort, we'd have to lay them all out in a row, and go over that row looking for the maximum. Assuming comparing each midterm to our current maximum takes half a second, the whole procedure would take about 0.5*250**2/2=15625 seconds, which is more than four hours.
Challenge/Google interview question: Eggs break when dropped from floor k, but not lower floors, of a 100-floor building. You have two eggs. How to find out k while minimizing the worst-case number of times that you need to drop eggs? (Note: if you have 9 eggs, you just want to do binary search. If you only have 1 egg, you have to drop it from floor 1, then floor 2, then floor 3, etc., since it might break.)
Nov. 16: Monte Carlo Integration and more NumPy (Note: you are not required to memorize NumPy syntax.) Just for fun: Monte Carlo Integration, Monte Carlo in the context of multi-dimensional integrals.
Complexity of Selection Sort: Take 2. Intro to Bubble Sort.
Nov. 17: Bubble Sort Continued + Complexity of Bubble Sort. Bozosort. Intro to Bucket/Counting Sort.
Upcoming readings: The Recursion chapter in Miller et al up to Visualizing Recursion. Ch. 6.5-6.7 from Downey.
Nov. 21: Complexity of Bucket Sort. Complexity is hard + enumerating all possible triples of numbers (just for fun: Fermat's Last Theorem). Intro to the complexity of arithmetic operations.
Just for fun: The Karatsuba algorithm and its history.
Challenge/Google interview question for Barack Obama
Readings: Ch. 3.1-3.2 of The Structure and Interpretation of Computer Programs (DeNero's Python version). (Also check out the original classic, perhaps over the break.)
Nov. 23: Complexity of multiplication 2. Intro to recursion and n!; computing fib(n) recursively; recursive is_even(n). Printing lists forward and backward recursively.
Video: Tracing fact(n) (on YouTube).
Just for fun: Happy Fibonacci day!
Challenge/interview question: implement integer division efficiently if you are only allowed to use addition, subtraction, and integer division by 2 as constant-time operations.
Nov. 24: Tracing functions that print lists recursively, tracing is_even(). AI for the game of Race to 21 using recursion (play21.py -- the full game). Summing lists recursively.
Just for fun: watch AlphaGo go a little crazy following Lee Sedol's divine move (and an explanation.) (See the wiki article for more information.)
Just for fun: XKCD's optimal Tic-Tac-Toe moves.
Nov. 28: Anything that you can do with a loop you can do with recursion (optional aside: named arguments.) Complexity of fact(n). Complexity of sum_list2().
Upcoming readings: MergeSort in Miller et al. and Insertion Sort in Miller et al.
Nov. 30: Complexity of exponentiation. Complexity of fib(n). Intro to MergeSort.
Just for fun: John von Neumann.
Dec. 1: Complexity of MergeSort (optional aside: we cannot do better than O(nlog(n)) if we only use comparisons). See also video (part 1), video (part 2), video (part 3). Insertion Sort. Recursive Deep Copy.
Just for fun: Timsort, Python's built-in sorting algorithm, is a blend of Merge Sort and Insertion Sort.
Solution to the Two Eggs Puzzle (but try to think of a proof.)
Dec. 5: print_all(): analysis and runtime complexity. Robotics option propaganda (just for fun): The Future of Computer Science (DeepMind's algorithm for automatically learning to play Atari Breakout, B. F. Skinner's pigeons playing Pong). (Briefly mentioned as an aside: B. F. Skinner's 'Superstition' in the Pigeon, and Wikipedia's writeup).
Also: a less serious take on automatically learning to play video games.
Dec. 7: Fast exponentiation. Recursive merge() and its complexity (video: recursive merge(), complexity analysis). Review of call trees of recursive functions.
Just for fun: Turing's and Goedel's results on what's possible and what's not possible. (Video: Halting Problem Intro, Halting Problem proof, Goedel's Incompleteness Theorem). (More on this, if you're interested: Gödel's Incompleteness Theorem (look for "As I said, once you have Turing's results"); Does Gödel Matter? by Jordan Ellenberg. Even more: Quantum Computing since Democritus by Scott Aaronson is available for free online via the UofT library.
Thanks for a great semester, and good luck on your exams!
MarkUs
All project submission will be done electronically, using the MarkUs system. You can log in to MarkUs using your UTORid.
For group projects, to submit as a group, one of you needs to "invite" the other to be partners, and then the other student needs to accept the invitation. To invite a partner, navigate to the appropriate Assignment page, find "Group Information", and click on "Invite". You will be prompted for the other student's UTORid; enter it. To accept an invitation, find "Group Information" on the Assignment page, find the invitation listed there, and click on "Join". Only one student must invite the other: if both students send an invitation, then neither of you will be able to accept the other's invitation. So make sure to agree beforehand on who will send the invitation! Also, remember that, when working in a group, only one person must submit solutions.
To submit your work, again navigate to the appropriate Exercise or Assignment page, then click on the "Submissions" tab near the top. Click "Add a New File" and either type a file name or use the "Browse" button to choose one. Then click "Submit". You can submit a new version of any file at any time (though the lateness penalty applies if you submit after the deadline) — look in the "Replace" column. For the purposes of determining the lateness penalty, the submission time is considered to be the time of your latest submission.
Once you have submitted, click on the file's name to check that you have submitted the correct version.
Policy on special consideration
Special consideration will be given in cases of documented and serious medical and personal cirumstances.
Policy on Academic Integrity
As a University of Toronto student, you are held to the highest standards of academic integrity. In particular, the assignments in this course are to be done by each student or team alone. Any discussion of the assignments with other students should be about general issues only, and should not involve giving or receiving written, typed, or emailed notes. You must not receive notes from another student, and you must not share your solutions with other students. Please refer to François Pitt's Guidelines for Avoiding Plagiarism. Failure to adhere to the Code of Behaviour on Academic Matters will be sanctioned. Please refer to the Academic Integrity at the University of Toronto website.
