CCPS 109, Computer Science I
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CCPS 109, Computer Science I
2021
The fi rst part introduces the core Python language and its central standard library modules, in principle sufficient to solve all problems in the graded labs. Interactive exercises available at the CodingBat Python training site drill in the syntax of Python until students reach the stage where the language works with them as aid for solving problems.
1. Python as a scriptable calculator
2. Functions that make decisions
3. Sequence types string, list and tuple
4. Sequence iteration
Having unleashed the students to work on the graded labs of the course, the second part of this course introduces higher-level techniques to express computations, and showcases non-trivial examples of interesting problems where the power of Python shines.
5. General repetition
6. Educational example programs
7. Lazy sequences
8. Recursion
Part Three: Python In The Real World
At this point, the students should be hard at work completing their lab problems to reach a higher course grade. This third part is therefore more relaxed, exploratory and theoretical in nature. It introduces powerful mechanisms that make Python even more expressive, along with some important and universal ideas of computer science that are independent of any particular programming language. These ideas will then be expanded further in the course CCPS 209 Computer Science II and beyond.
9. String processing
10. Numerical computation with numpy
11. Classes and objects
12. Spillover of interesting examples that were skipped earlier
The public GitHub repository ikokkari/PythonExamples always contains the latest versions of lecture notes (as PDF files) and all example programs (as Python scripts) used in this course.
The software needed to do everything in this course is free to download and use. Students can either (1) download and install the free PyCharm interactive development environment to write, run and test their programs on their computers, or (2) create themselves a free account to the cloud-based repl.it programming environment, and import the course repositories into their "repls" to work on. The second alternative is recommended especially for low power computers.
The fi rst four modules of this course use the problems offered in the free CodingBat Python online programming environment to drill in the basics of the core Python language. These simple yet excellent and educational problems on that site allow beginning students to quickly pinpoint what their functions are doing right and wrong, and what issues still remain to fix. When combined with another excellent online utility of Python Tutor that allows these functions to be animated and stepped through forwards and backwards, their educational powers mutually reinforce each other.
After acquiring proficiency with the language with these two free training sites so that the students can start applying this knowledge in solving problems with the language as their ally instead of the opponent, the lab problems in fifth module onwards have been chosen from the problem collection "109 Python Problems for CCPS 109". The public GitHub repository ikokkari/PythonProblems always contains the latest versions of the automated tester script and the necessary data files.
The course grade is based solely on how many lab problems from the collection "109 Python Problems for CCPS 109" the student successfully solves. Nothing else can affect the course grade in either direction. These labs will be submitted all at once, at the same time at the end of the course. The functions written in these labs should be written inside the Python source file labs109.py for the automated tester script tester109.py to find and evaluate.
The course grade granted at the end of the course is computed with the following formula. To earn the passing grade of 50% (D minus), the student must successfully complete ten labs. After that, every additional lab that they complete adds one more point to their course grade. Therefore to get the highest possible course grade of 90% (A plus), the student has to complete fifty lab problems out of the 109+ problems offered.
Students are expected to create the solutions to these problems as their own individual work. However, they are allowed to look for advice and guidance by searching any and all existing material in online articles and programming forums such as Stack Overflow. (Whatever problem you have in coding, thousands of others have had that exact same problem before, the more so the more universal and general that particular issue happens to be.) However, until the grades
for this course have been tallied, students are not allowed to post any new questions concerning these lab problems anywhere.
As long as no code is being copied via direct copy-paste or going through the eyes, brains and fi ngers of the student so that this discussion stays at the level of ideas, students may freely discuss these problems with anybody both inside and outside this course, with no fear of any repercussions from such activity. After all, this is how all learning works. Except for the things that you happen to discover by yourself, all knowledge comes from somebody else. Whether that somebody is your formal instructor or some other person has no epistemological consequences on that.
Finally, should some students get stuck with some problem that they have given their honest effort to but somehow can't seem to set it right and eliminate the bugs (and this will eventually happen to everyone regardless of their skill level, since everyone has mental blind spots somewhere), it is acceptable to occasionally, but not as a general rule, to show the code to somebody for a second pair of eyeballs that will hopefully spot something that the original student missed.
That other person may also be the instructor of the course, as long as this does not become a regular habit and the student gives the impression of having fi rst given the problem a good college try. The best way to do this is most likely by email, as old-fashioned as that form of media might seem to us now. In case of some difficult corner case bug that was not caught and revealed by the fi rst 300 recorded test cases for that problem but shows up only as a checksum discrepancy, the instructor can put the discrepancy function inside the tester109.py script to good use and run both functions for all test cases, and find out exactly where the student function and the instructor's private model solution disagree. Such happenstances have historically revealed genuine bugs in the instructor's private model solutions, although these get ever more rare as the course material matures. (But some bugs will always be lurking, no matter how strenuously we try to stomp them down!)
Module 1: Python as a scriptable calculator
Python 3 is a modern programming language whose core syntax is simple enough to learn in five modules, and yet behind this simple syntax lies an entire universe of tremendous power. This module shows you how to set up this system to start your exploration of programming and computer science by fi rst using Python as a scriptable calculator that can operate on not just numbers, but on characters and text.
1. Launching the Python interactive environment either locally or on the cloud.
2. Entering arithmetic expressions inside the Python REPL.
3. Defining names that are associated with values, and using these names inside later expressions.
4. Basic operations of integer arithmetic, with a suggestion to avoid floating point numbers in your work if possible.
5. Importing new functions from the standard library modules and using them in your computations.
6. Representing text as string literals in Python.
7. Composing complex text strings from simpler pieces with the f-string mechanism.
After this module, students can launch the Python interactive environment either on their local computer (PyCharm) or on the cloud (repl.it). They know how to evaluate arbitrary arithmetic expressions in the REPL window, and how integer arithmetic operators work in Python. They can create names that remember values that were assigned to them, and use these names in later expressions to refer to results that were calculated earlier. They can open, edit, save and execute scripts in some Python IDE, and can make these scripts print results for the user to see. They can define text literals as ordinary and f-strings in Python. They can import new functions and data types from the standard library into their scripts, and know where to go in the official Python documentation to learn how to use these functions in their code.
1. "Python Lecture Notes", Module 1.
2. GitHub repository ikokkari/PythonExamples: first.py
3. YouTube playlist "CCPS 109 Computer Science I, Python" videos: "Python 1-1: Overview", "Python 1-2: And God created integers", "Python 1-3: Give me a name instead of a number", "Python 1-4: Executable text".
The purpose of this fi rst module is to get acquainted with the Python Interactive Development Environment (IDE) in which the Python programs are created and executed. Instead of an old- school installation straight from the source www.python.org, students who choose to work locally on their own computers can download and install the PyCharm IDE to do their work there. Alternatively, students may choose to work on a cloud-based Python environment repl.it that can be accessed anywhere via a web browser. All examples, exercises and lab problems in this course can be successfully completed in either environment.
Option 1 (PyCharm): Download and install the free edition of PyCharm. While installing, you might as well use the waiting time to also download the repositories ikokkari/PythonExamples and ikokkari/PythonProblems as zip archives (use the green Code button of the GitHub interface), and unzip these archives into folders PythonExamples and PythonProblems into wherever you usually store your data files.
In the “File->Open” menu of PyCharm, navigate to your directory PythonExamples and open the entire directory at once as a PyCharm project. Wait for PyCharm to populate the project menu with the example programs and files. Double click on a the file first.py to open it in editor. Use to drop-down menu of the editor window to Run the script.
In the “Tools” menu, click “Python or Debug console” to open a REPL window in which you can enter Python commands interactively. You can also play around with the PyCharm features to edit, run and analyze example scripts.
Option 2 (repl.it on the cloud) : Create yourself a free account on the site repl.it under which your files will be stored under. Click the black "import repo" button on the top right corner, enter the URL https://github.com/ikokkari/PythonExamples into the dialog box and click "Import from GitHub". You should now see a Python 3 "repl" named PythonExamples under your account that contains all the example programs from this course. Do the same for the URL https://github.com/ikokkari/PythonProblems to import the automated testing environment for the lab problems for this course. Then go to your PythonExamples repl and press the green "Run" button to execute the script first.py.
When this fi rst script asks you to enter your name and age, give it something so that the script can proceed. To make the "Run" button execute some other script, you have to edit the second line of the file .replit to read run="python3 scriptname.py" where you should replace scriptname with the actual name of the script that you want to run.
During the fi rst five modules, this course uses the excellent CodingBat Python interactive training site. This site contains lots of small programming problems whose purpose is to drill in
the core Python language that we learn during the fi rst five modules. From the sixth module onwards, we move on to apply this knowledge to solve problems from the collection "109 Python Problems for CCPS 109".
Every CodingBat problem is solved as a script that defines exactly one function. Since we will be writing functions next module onwards, this module is devoted to setting up the programming environment (either PyCharm or repl.it) and learning to use the CodingBat interactive coding environment. Create yourself a free account at CodingBat so that it will remember your solved problems and the solutions that are works in progress. Then, in the collection "String-1", go to the problem hello_name. The editor pane already contains the signature of the function that you should always keep exactly as it was given, since otherwise the automated testers. Under the function signature, type one line of text (please don't just copy-paste from here)
return 'Hello' + name + '! '
indented two spaces to denote that this statement is inside the function hello_name that is being defined in this script. Once you have done this, press the "Go" for CodingBat to grade your function by giving it a bunch of test cases and verifying that your function returns the
correct result for each. You should see something resembling the screenshot below :
Next to your editor pane, CodingBat shows a table with all the test cases in the "Expected" column, with the individual results from your function in the "Run" column. The green box means that your function returned what it was supposed to return for the test case in that row. If your function had returned anything other than the expected result, that row would then have a red
box at the end to show you the existence of a bug in your code. (Don't worry, you will write your fi rst bug soon enough to see plenty of red!)
One caveat of using CodingBat, at least the moment of writing this, is that the server uses Python 2 internally, so the nice things of Python 3 that we learn in this course do not work in these scripts. For example, trying to implement hello_name using an f-string will only result in a syntax error. Another caveat is that many problems have been adapted from the Java version of the site, and the terminology has not been edited to correspond to Python. For example, whenever you see something referred to as an "array", just mentally substitute the word "list" in its place.
Module 2: Functions that make decisions
The simple two-way decision is the foundation of all computation from which all other computational operations are built from bottom up, all the way down to the logic gates of the computer processor up to the highest levels of abstraction inside Python. The existence of forks in the road that the execution of a program has to choose between makes it possible for the outcome to be different for different inputs given to that program, instead of every computation leading to Rome regardless of these inputs.
1. Defining your own functions that compute and return a result that depends on the function arguments.
2. Purpose of whitespace to indicate nesting of statements inside a Python script.
3. Two-way decisions to branch the execution of a script into two mutually exclusive branches based on the truth value of some condition.
4. Equality and order comparisons in Python.
5. Building up larger decision trees from two-way decisions via nesting and laddering.
6. Expressing more complex conditions with logical connectives.
After this module, students are able to fi rst define functions in their scripts, and then call these functions properly later in the code using different argument values. They understand the difference between the function printing the result versus returning it. They can explain the connection of the whitespace indentation that starts a Python statement and the nesting of that statement inside the Python script. They can make their functions perform simple two-way if- else statements, and combine these two-way decisions into more complex decision trees by nesting them and creating if-else ladders. They recognize the core logical connectives and, or and not, and can explain how the truth value of a complex condition built with these is determined by the truth values of its subconditions.
1. "Python Lecture Notes", Module 2.
2. GitHub repository ikokkari/PythonExamples: conditions.py timedemo.py
3. YouTube playlist "CCPS 109 Computer Science I, Python" videos: "Python 2-1: Verb every word to me", "Python 2-2: Forks on the road", "Python 2-3: The Galton board of reality", "Python 2-4: A Skinner box for humans, localized entirely within your computer", "Python 2-5: Once in a century".
Study the example script timedemo as an example of how to do computations with calendar dates and times with the datetime module in the standard library. Use this knowledge to adapt the script to find out what day in the future you will be exactly twice as old as you are today. (Compute how many days you have been alive so far, and then add that many days to the current date.) Then, find out which day of the week you were born in.
Since the humble two-way decision is the fundamental building block of all computations, having this operation at our disposal allows us, in principle if not always in practice, to solve any computational problem as a Python function... provided that the problem has an upper limit to how large its input can be, so that we can encode all possibilities into a decision tree implicitly executed by the statements of the function. This is especially the case when the arguments given to the function are truth values so that each argument is either True or False, with no third alternative.
The problems in the CodingBat Python sections Warmup-1, Logic-1 and Logic-2 will have you write functions that cover all possible situations of their argument values with a small handful of decisions properly nested and laddered. Your task for this module is to solve at least ten problems of your choice from these three sections. This ought to drill the Python syntax (including that annoying redundant colon after every condition, and that == and = are different things, as are also // and /) into your fingertips, while at the same time your mind gets accustomed to the task of breaking down a complex decision into a decision tree made of simple two-way decisions.
When comparing your solutions to those of other students, remember that whenever you come up with one way to organize a decision tree, there always would have been many other result- equivalent ways to do so.
Module 3: Sequence types string, list and tuple
There are only so many interesting questions that we can ask about a single integer or other scalar value. However, in the current era of terabytes, even everyday computers that not only the five richest kings of Europe but also us commoners and other normos can afford to own, can process sequences that consist of millions, even billions, of such scalar values of data. Sequences allow our Python programs to aggregate scalar values together under a single name, and the powerful polymorphic functions and operators on sequences can handle all types of sequences in a uniform fashion.
1. Embedding special characters inside string literals with escape sequences.
2. The slicing operator for Python sequences, as demonstrated by slicing pieces from existing text strings.
3. Strings as immutable sequences of Unicode characters.
4. The structurally flexible and heterogeneous lists in Python.
5. Constructing new list objects from existing sequences with list comprehensions.
After this module, students know how to make up text string literals that can contain arbitrary Unicode characters. They can slice and dice text strings forwards and backwards with the slicing operator [] of Python. Their ability to represent data has expanded from scalar values into sequences of arbitrary values as Python lists. Students can take an existing list and transform it into a new list with list comprehensions.
1. "Python Lecture Notes", Module 3.
2. GitHub repository ikokkari/PythonExamples: listdemo.py stringdemo.py comprehensions.py tuples.py
3. YouTube playlist "CCPS 109 Computer Science I, Python" videos: "Python 3-1: It slices, it dices, and so much more!", "Python 3-2: Pretty objects all in a row", "Python 3-3: All sequences eager and lazy", "Python 3-4: Definition of terse"
When a function that is more complex than a couple of lines does not return the answers you expect, it is often convenient to be able to step through the execution to see exactly what is
going on in each step. We shall later learn how to use such debuggers built in PyCharm and repl.it, but until then, students should check out the excellent Python Tutor for this purpose. Copy-paste one of the functions that you have written earlier into the editor pane on that page, followed by a line in which you call that function for some argument values. To see a step-by- step animation of the function execution, press the button "Visualize execution" to take you to the screen where you can step through your execution both forward and backward. You can see exactly the values associated with each name at each step during this execution, which will be useful in finding out the exact spot where the computation does something unexpected for some failing test case.
To practice handling sequences of data and learn to understand how these sequences can be freely sliced into smaller pieces and concatenated into larger pieces, CodingBat sections Warmup-2, String-1 and List-1 contain a host of excellent problems ready to be solved with the Python language learned in this module. Your task is again is to drill in the language syntax into your fingertips while your mind adapts to think about entire sequences of data of unlimited length instead of mere individual scalar values. Therefore, this module you should again complete at least ten, but preferably more, problems chosen from these three sections.
In computing, we are accustomed to the idea that duplication of bytes by the billions is essentially free. The same principle also applies inside the computer program. Once you have discovered a way to solve some problem for one element, you can place this solution inside some repetition control structure that then solves it for the entire sequence of such elements. This module introduces the basic for-loop control structure to do this very thing.
Many problems can be expressed in, or at least converted to the form of some small local operation being repeatedly performed for the elements of some cleverly chosen existing sequence. Especially when asked to do something five times, the computer program does the exact same thing as a human who keeps a running count going "one, two, three, four, five", thereby unknowingly iterating through a simple arithmetic progression that turns out to be isomorphic to the actual problem that exists outside the mind of that particular human. That, and the computer program usually starts counting up from zero because that turns out to be mathematically convenient. However, a computer can count up to a billion much faster than us humans, even though just like us, it does not need to remember all the numbers that it has previously processed, but only the number that it is currently at.
1. Iterating through the elements of an arbitrary sequence with the same for-loop.
2. Lazy sequences that produce their elements one at the time on command.
3. The extremely memory-efficient range sequences for the commonly needed arithmetic progressions of integers.
4. Files as sequences of lines, each line a sequence of characters.
5. Tuples are compact immutable sequences of a handful of elements.
6. Sets and dictionaries to remember what the function has seen and done.
After this module, students can write for-loops to iterate through the elements of the given sequence, and have the body of the for-loop perform the same computation for each element. This computation can involve updating the local state of the function such as tallying up the sum or the maximum of the elements seen so far. They know how to represent arithmetic progressions as range objects, and understand why such a range requires far less memory to store compared to an eager list that contains its elements explicitly. They know the difference between mutable lists and immutable tuples, and which operations are possible based on that. Students can create a fresh new set and use it to store the values encountered during the
function execution, and can explain why asking a set whether it currently contains some element is much faster than asking the same question from a list.
2022-06-21