Monday | Tuesday | Wednesday | Thursday | Friday |
1/14 Lecture 0: Introduction | 1/15 | 1/16 Lecture 1: Standard types and basic operations | 1/17 | 1/18 Lecture 2: Standard types, basic operations and branching |
What is computer science? - Computational problems - main questions of computer science - programming in the context of CS - course procedures Introductory information on how to get started with this class (includes instructions on how to sign up for Zybook) Carefully read the course syllabus (Home and Policies tabs on the class webpage) Review slides on Canvas Sign up for Zybook and complete the exercises in ch. 1 and ch. 2 before the end of Tuesday 1/15 | Program elements (literals, expressions, operators, operands, keywords) - Program flow and keeping track of program state - order of operations - variables - data types, their operations, and conversion in Python - program flow Download and install Python 3.7.2 on your computer before the lab (any Python 3 version works for our purpose) Refresh browser with Zybook, complete exercises in ch. 3.1-3.3 before the end of Thursday 1/17 | Lab 0 assigned (ch. 4) Python interpreter and programming in IDLE - Hello world program and producing user output - Reading user’s input - basic conversion to int and string - Pythontutor - coding style (docstrings, comments, whitespaces) - errors Reminder: Bring laptop to each lab | Program elements (literals, expressions, operators, operands, keywords) - Program flow and keeping track of program state - order of operations - Variables - Data types, their operations, and conversion in Python - program flow - Conditional statements - Nested Ifs Refresh browser with Zybook, complete exercises in ch. 3.4-3.6 before the end of Tuesday 1/22 | |
1/21 | 1/22 | 1/23 Lecture 3: Sequence types (lists and strings), mutability, booleans | 1/24 | 1/25 Lecture 4: Conditional iteration, booleans, sentinel value |
Martin Luther King Day | Strings, lists and standard operations - breaking program into pieces - visualizing program result Refresh browser with Zybook, complete exercises in ch. 5 (Sequence types) before the end of Thursday 1/24 Lab 0 due | Lab 1 assigned (ch. 6) | Iteration - sentinel value - infinite loop - input validation loop - accumulation of result Zybook (refresh): ch. 7 (conditional iteration) before the end of Sunday 1/27 | |
1/28 Lecture 5: Counting iteration | 1/29 | 1/30 Lecture 6: More iteration | 1/31 | 2/1 Lecture 7: Modular program design: Functions |
Iterative program execution - Iterating over sequences - range function - Index-based and element-based iteration - accumulator variables Study notes, slides and code examples on Canvas, Zybook chapters to prepare for Quiz 0. Zybook: ch. 8 (counting iteration) before the end of Tuesday 1/29 | Loops practice quiz - Looping over lists - nested loops - problem solving using loops (factorial, gradeAverage, list element replacement, minimum) Study notes, slides and code examples on Canvas, Zybook chapters, and use study guide to prepare for Quiz 0. Zybook: ch. 9 (more iteration) before the end of Thursday 1/31 Lab 1 due | Lab 2 assigned (ch. 10) Quiz 0 | Functions intro - reasons for functions - variable scope(visibility) - return vs. print - built-in Python functions - modular program design Zybook: ch. 11 (functions) before the end of Sunday 2/3 | |
2/4 Lecture 8: More function concepts (scope) | 2/5 | 2/6 Lecture 9: Files | 2/7 | 2/8 Lecture 10: Debugging, files, memory, testing |
Functions calling functions - function composition - program flow with functions - examples - modules Zybook: ch. 12 (more functions) before the end of Tuesday 2/5 | File input - File output - readlines vs read - vowels program Zybook: ch. 13 (files) and study vowels program before the end of Thursday 2/7 Lab 2 due | Lab 3 assigned (ch. 14) Quiz 0 review - function example (weather evaluation) | Debugging -, files - variables in memory (mutable variables (ints, strings) vs. immutable variables (lists)) - functions and function contracts - generating good test coverage - automated testing with doctest | |
2/11 Lecture 11: Testing, memory, dictionaries | 2/12 | 2/13 Lecture 12: Binary numbers | 2/14 | 2/15 Lecture 13: Boolean operations |
Key/value data - dictionaries- examples Zybook: ch. 15 (dictionaries) before the end of Tuesday 2/12 | Binary numbers and their meaning - conversion between binary and decimal - ASCII table - binary representation of numbers, text, images, audio, video Zybook: ch 40.5 (lists) and ch. 16 (binary data) before the end of Thursday 2/14 Lab 3 due | Lab 4 assigned (ch. 17) Quiz 1 | Operations on binary numbers - Defining functions using truth tables Zybook: ch. 18 (Truth table) before the end of Sunday 2/17 | |
2/18 Lecture 14: Minterm expansion | 2/19 | 2/20 Lecture 15: Abstraction, Full adder | 2/21 | 2/22 Lecture 16: Storing data , von Neumann architecture |
From function definition to formula to circuit (minterm expansion principle) Zybook: ch. 19 (Minterm expansion) before the end of Tuesday 2/19 | Abstraction -Building a full adder Zybook: ch. 20 (Adder) and slides, before the end of Thursday 2/21 Lab 4 due | Lab 5 assigned (ch. 21) | How data is stored von Neumann architecture Zybook: ch. 22 (Memory) and slides, before the end of Sunday 2/24 | |
2/25 Lecture 17: Fetch-execute cycle | 2/26 | 2/27 Lecture 18: How to reason about program’s efficiency | 2/28 | 3/1 Lecture 19: Asymptotic analysis |
Moore’s law - von Neumann bottleneck - fetch execute-cycle - machine language and assembly language Zybook: ch. 23 (Machine language) and slides, before the end of Tuesday 2/26 | Analyzing program’s efficiency using worst-case asymptotic analysis - relative function’s growth rate discussion and exercises Prepare for the Midterm exam, use Study Guide Lab 5 due | No new lab assignment, prepare for the Midterm Exam Quiz 2 | Big Oh analysis Asymptotic analysis: formal definition, rules of asymptotic analysis, examples Prepare for the Midterm exam, use Study Guide | |
3/4 | 3/5 | 3/6 | 3/7 | 3/8 |
Lundi Gras Spring Break |
Mardi Gras Spring Break | Spring Break | Spring Break | Spring Break |
3/11 Lecture 20: Search algorithms | 3/12 | 3/13 Lecture 21: Introduction to recursion; recursive binary search | 3/14 | 3/15 Lecture 22: Sorting algorithms, selection sort, merge sort |
Search algorithms - Linear search strategy, code, running time analysis - Binary search strategy, code, running time analysis - Divide and conquer problem-solving approach Before the end of Tuesday 3/12: - Zybook ch: 24 (Big Oh) - Zybook ch: 25 (Searching) - Read notes on Canvas (chapter on searching) Prepare for the Midterm exam, use Study Guide | Recursive binary search - introduction to recursive problem solving - factorial Prepare for the Midterm exam, use Study Guide | Midterm exam Pencil-and-paper based, closed-books / closed-notes / zero technology. Standard test questions (multiple-choice, true/false, fill-in-the-blanks, short text answer, etc) and writing small programs. See the study guide on the course webpage for more info. One double-sided letter-size helper sheet is allowed. Anything course-related can be placed on this sheet. | Selection sort mechanics - minimum selection -Swapping - Selection sort code - Merge sort development
- Zybook ch: 26 (Intro to Recursion) - Read recursion_reading.pdf on Canvas (only pages 509 - 515) - Run class code in Python Tutor | |
3/18 Lecture 23: Recursive problem solving, sorting | 3/19 | 3/20 Lecture 24: Merge sort, recursion practice | 3/21 | 3/22 Lecture 25: More recursion practice |
Recursive problem solving: sumn(), myLen() Sorting (selection sort review) Before the end of Tuesday 3/19: - Zybook ch: 27 (Sorting) - Run class code in Python Tutor. | Merge sort development Sorting (finished)- merge sort - merge and merge sort analysis vowels() Before the end of Thursday 3/21: - Zybook ch: 28 (Creating recursive solutions) - Read recursion_reading.pdf on Canvas (only pages 516 - 519) - Review notes on Canvas. - Run class code in Python Tutor | Lab 6 assigned (ch. 29) Practice Recursion | powerOfTwo(), min_cutoff(), mymax() - allcaps() - reverse() - morevowels() Function tracing Before the end of Sunday 3/24: - Review all recursion material (incl. Canvas reading). - Run all recursive code in Python Tutor and understand its operation. | |
3/25 Lecture 26: Introduction to OOP | 3/26 | 3/27 Lecture 27: Overloading | 3/28 | 3/29 Lecture 28: OOP practice |
Object-oriented approach - Date class and its operations; constructor, methods, __str__, self Zybook ch: 31 (Intro to OOP) before the end of Tuesday 3/26 | Objects are mutable, overloading of operators, Rational class and its operations Zybook ch: 32 (OOP continued) before the end of Thursday 3/28 Lab 6 due | Lab 7 assigned (ch. 33) Quiz 3 | Rational class and its operations (cont), Coin exercise Before the end of Sunday 3/31: - Download and run Coin and Coin_value from Canvas, run them in Python Tutor or Thonny and observe which objects are created and how they are passed to functions. - Review notes on OOP and attend TA help hours if OOP is still scary. | |
4/1 Lecture 29: Linked structures: list | 4/2 | 4/3 Lecture 30: Operations on linked structures | 4/4 | 4/5 Lecture 31: More operations on linked lists |
Motivation (list play) - running time of Python list operations - Creating linked node class - creating simple linked structure Before the end of Tuesday 4/2: - Study Node code very well. |
| Standard linked list operations and their efficiency Zybook ch. 34 (singly linked list) before the end of Friday 4/5 Lab 7 due
| Lab 8 assigned (ch. 35) | Linked-list operations and their efficiency Zybook ch. 36 (doubly linked list) before the end of Sunday 4/7 |
4/8 Lecture 32: Linked lists finished. Binary search trees
| 4/9 | 4/10 Lecture 33: Recursive tree traversal | 4/11 | 4/12 Lecture 34: Binary search tree (BST) implementation |
Linked lists: remove. Before the end of Tuesday 4/9: - Hw: Prepare presentation on traversal algorithm | Extra credit Zybook: ch. 41-49 (Modules, Strings and Lists, More Programming, Stacks and Queues, Internet and Web, Privacy and Security, Operating Systems, Exceptions, Inheritance). You pick and choose which chapters to do, or (ideally) all the chapters. Extra credit Zybook is due by the end of Tuesday 4/30 | Binary tree traversal algorithms (preorder, postorder, inorder) Lab 8 due | Lab 9 assigned (ch. 37) Quiz 4 | Implementation of binary search tree operations - finding a node, traversal - Computing the sum of nodes in a BST Problem solving with linked structures Zybook (refresh) ch. 38 (trees) before the end of Sunday 4/14 |
4/15 Lecture 35: Graphs and networks | 4/16
| 4/17 | 4/18 Lab 12: Binary search trees; graphs and networks | 4/19 |
Linked structures summary - Intro to graphs, history of Internet, graph problems, analysing graphs - graph representation
Zybook ch.39 (graphs) before the end of Thursday 4/18 | Finish graphs Class NP and the meaning of P vs NP question Before the end of Tuesday 4/23: Review slides and reading on Canvas. Lab 9 due | Lab 10 assigned (ch. 40) Graphs and networks practice | Easter | |
4/22 | 4/23 | 4/24 Lecture 37: Limits of computation: uncomputable problems | 4/25 | 4/26 Lecture 38: Models of computation: Finite state machines |
Easter | Class NP and the meaning of P vs NP question - current status - Implication of resolution The status of P vs NP question Proof by contradiction - halting problem - proof of impossibility Before the end of Thursday 4/25: Review slides on Canvas. | Quiz 5 Exam review | Definition of FSM - examples - practical use Before the end of Sunday 4/28: Review slides on Canvas. | |
4/29 Lecture 39: Models of Computation: Turing Machines. Summary of the course. | 4/30 | 5/1 | 5/2 | 5/3 |
Turing and his role in modern computing - Turing machine - examples - Turing test and Turing equivalence Review slides and reading on Canvas. Lab 10 due | Extra credit Zybook due Bonus labs due | Study day | Study day | |
5/6 Final Exam | 5/2 | |||
The exam is paper-based, closed-books / closed-notes / zero technology. It contains standard test questions (multiple-choice, true/false, fill-in-the-blanks, short text answer, etc) and writing small programs on paper. See the study guide on the course webpage for more information. One double-sided letter-size helper sheet is allowed. Anything course-related can be placed on this sheet. |
Final Exam Date: The final exam is on Monday, May 6, 1:00pm - 3:00pm in ST 302. |