|
| Coding standards | |
| Introduction to Linux |
|
|
|
| 1. | [M. August 19] |
| Syllabus | |
| Lecture 1A Who should study computer science? | |
| Lecture 1B Course philosophy | |
| Lecture 1C Large software and programming principles | |
| Lecture 1D Standards | |
| Lecture 1E Things not to use in C++ | |
| 2. | [W. August 21] |
| Lecture 2A Programming languages | |
| Lecture 2B Compilers | |
| Lecture 2C Two major standards | |
| Lecture 2D Introduction to Linux and the local machines | |
| Lecture 2E Logging into Xlogin | |
| Lecture 2F Getting things done on Xlogin | |
| Lecture 2G Summary | |
| Linux reference | |
| Assignment 0 assigned | |
|
|
|
| 3. | [Th. August 22] |
| Lecture 3A Programming language syntax | |
| Lecture 3B Values | |
| Lecture 3C Types | |
| Lecture 3D Expressions | |
| Lecture 3E Statements | |
| Lecture 3F Compound statements | |
| 4. | [F. August 23] |
| Lecture 4A Variables | |
| Lecture 4B Assignment statements | |
| Lecture 4C Variable Initialization | |
| Lecture 4D Abbreviations for assignment statements | |
| Lecture 4E Assignments are expressions | |
| Lecture 4F Compound statements and scope | |
| 5. | [M. August 26] |
| Lecture 5A Hand simulation | |
| Lecture 5B Some uses of variables | |
| Lecture 5C Named constants | |
| Lecture 5D Type checking | |
| 6. | [W. August 28] |
| Lecture 6A Functions | |
| Lecture 6B Function libraries | |
| Lecture 6C Standard input and standard output | |
| Lecture 6D Writing to the standard output | |
| Lecture 6E Reading from the standard input | |
| Lecture 6F Summary | |
| 7. | [Th. August 29] |
| Lecture 7A Defining functions | |
| Lecture 7B Calling your functions | |
| Lecture 7C Side effects, pure functions and void functions | |
| Lecture 7D Return statements | |
| Lecture 7E What Are Functions Good for? | |
| Lecture 7F Parameters | |
| 8. | [F. August 30] |
| Lecture 8A The main function | |
| Lecture 8B The order of function definitions | |
| Lecture 8C Boolean expressions | |
| Lecture 8D Mental model of boolean expressions | |
| Lecture 8E Booleans are values | |
| Lecture 8F Booleans are actually integers | |
| [M. September 2] | |
| Holiday | |
| 9. | [W. September 4] |
| Lecture 9A Making decisions | |
| Lecture 9B Making decisions in expressions | |
| Lecture 9C Pitfalls with if-statements | |
| Lecture 9D Standards for if-statements | |
| Lecture 9E Repetition | |
| Lecture 9F While-loops | |
| Lecture 9G Summary | |
| Assignment 0 due | |
| Assignment 1 assigned | |
| 10. | [Th. September 5] |
| Lecture 10A Checking loops | |
| Lecture 10B Planning while-loops | |
| Lecture 10C Loop invariants | |
| Lecture 10D Pitfalls with loops | |
| Lecture 10E Summary | |
| [F. September 6] | |
|
Exam 1 Lectures |
|
| 11. | [M. September 9] |
| Lecture 11A For-loops | |
| Lecture 11B Additional features of for-loops | |
| Lecture 11C Planning for-loops | |
| Lecture 11D Breaking out of a loop | |
| Lecture 11E Standards for loops | |
| Lecture 11F Summary | |
|
|
|
| 12. | [W. September 11] |
| Lecture 12A Mental model of functions 1: What does the function accomplish? | |
| Lecture 12B Function contracts | |
| Lecture 12C Choosing function, parameter and variable names | |
| Assignment 1 due | |
| Assignment 2 assigned | |
| 13. | [Th. September 12] |
| Lecture 13A Scan algorithms | |
| Lecture 13B Filtered scans | |
| Lecture 13C Elementary arrays | |
| Lecture 13D Summary | |
| 14. | [F. September 13] |
| Lecture 14A Scan algorithms on arrays | |
| Lecture 14B Search algorithms | |
| Lecture 14C More on search algorithms | |
| Lecture 14D Summary | |
| 15. | [M. September 16] |
| Lecture 15A Mental model of functions 2: how function calls are performed by the Computer | |
| Lecture 15B Recursion | |
| Lecture 15C Detailed hand simulation of a recursive function | |
| Lecture 15D Summary | |
| 16. | [W. September 18] |
| Lecture 16A Understanding recursion | |
| Lecture 16B Computing powers | |
| Lecture 16C Making sure that a recursive function stops | |
| Lecture 16D Summary | |
| 17. | [Th. September 19] |
| Lecture 17A Recursive scan algorithms | |
| Lecture 17B Recursive search algorithms | |
| Lecture 17C Tail recursion | |
| Lecture 17D Summary | |
| 18. | [F. September 20] |
| Lecture 18A Duplicated recursive calls | |
| Lecture 18B Detecting, diagnosing and fixing errors | |
| Lecture 18C Testing | |
| Assignment 2 due | |
| Assignment 3 assigned | |
| 19. | [M. September 23] |
| Lecture 19A Localizing errors and successive refinement | |
| Lecture 19B Using a debugger | |
| Lecture 19C Tracing | |
|
|
|
| 20. | [W. September 25] |
| Lecture 20A The memory, memory addresses and pointers | |
| Lecture 20B Pointer operations | |
| Lecture 20C Hand simulation with pointers | |
| Lecture 20D Const pointers | |
| Lecture 20E Summary | |
| 21. | [Th. September 26] |
| Lecture 21A Areas of memory | |
| Lecture 21B Allocating and deallocating memory in the heap | |
| Lecture 21C Ownership of memory and memory faults | |
| Lecture 21D Dangling pointers | |
| Lecture 21E Finding and fixing memory faults | |
| Lecture 21F Memory leaks | |
| Lecture 21G Summary | |
| [F. September 27] | |
|
Exam 2 Lectures |
|
| 22. | [M. September 30] |
| Lecture 22A Arrays | |
| Lecture 22B Creating arrays | |
| Lecture 22C Deleting arrays | |
| Lecture 22D Chunks are not automatically copied | |
| Lecture 22E Pointer arithmetic | |
| Lecture 22F Array bounds | |
| Lecture 22G Summary | |
| 23. | [W. October 2] |
| Lecture 23A Passing arrays to functions | |
| Lecture 23B Const arrays | |
| Lecture 23C Logical and physical size | |
| Lecture 23D Example | |
| Lecture 23E Returning an array from a function | |
| [Th. October 3] | |
| Assignment 3 due | |
| Assignment 4 assigned | |
| Assignment 4 | |
| 24. | [F. October 4] |
| Lecture 24A Physical parameter passing modes | |
| Lecture 24B Logical parameter passing modes | |
| Lecture 24C Reallocating an array (optional) | |
| Lecture 24D Summary | |
| [M. October 7 – Tu. October 8] | |
| Fall break | |
| 25. | [W. October 9] |
| Lecture 25A Type definitions | |
| Lecture 25B Modules | |
| Lecture 25C Linkage | |
| Lecture 25D Summary | |
| 26. | [Th. October 10] |
| Lecture 26A Null-terminated strings | |
| Lecture 26B Standard operations on null-terminated strings | |
| Lecture 26C Algorithms on null-terminated strings | |
| Lecture 26D Reading and writing characters and strings | |
| Lecture 26E Summary | |
| 27. | [F. October 11] |
| Lecture 27A Structures | |
| Lecture 27B Creating structured values | |
| Lecture 27C Referring to fields in structures | |
| Lecture 27D Constructors | |
| Lecture 27E More on constructors | |
| Lecture 27F Summary | |
| 28. | [M. October 14] |
| Lecture 28A Copying structures | |
| Lecture 28B Arrays of structures and compound selectors | |
| Lecture 28C Naming and documentating structures | |
| Lecture 28D Passing structures to functions | |
| Lecture 28E Forward and recursive structure type definitions | |
| Lecture 28F Summary | |
| [W. October 16] | |
| Assignment 4 due | |
| Assignment 5 assigned | |
| Assignment 5 | |
|
|
|
| 29. | [Th. October 17] |
| Lecture 29A Abstract data types | |
| Lecture 29B Conceptual Lists | |
| Lecture 29C Linked lists | |
| Lecture 29D Implementation of linked lists | |
| Lecture 29E Summary | |
| [F. October 18] | |
|
Exam 3 Lectures
|
|
| 30. | [M. October 21] |
| Lecture 30A Equations about lists | |
| Lecture 30B Using equations to derive algorithms | |
| Lecture 30C Another example using equations | |
| Lecture 30D Summary and Another Example | |
| 31. | [W. October 23] |
| Lecture 31A Example: produce a modified list | |
| Lecture 31B Example: select the even members of a list | |
| Lecture 31C Example: is one list a prefix of another? | |
| 32. | [Th. October 24] |
| Lecture 32A Looping over linked lists | |
| Lecture 32B Example: sum of the numbers in a list | |
| Lecture 32C Example: reversing a list | |
| Lecture 32D Summary and Caution | |
| 33. | [F. October 25] |
| Lecture 33A Destructive functions on linked lists | |
| Lecture 33B Example: Sort a linked list | |
| Lecture 33C Example: Remove a value from a linked list | |
| Lecture 33D Example: Modify the items in a linked list | |
| Lecture 33E Memory sharing | |
| Lecture 33F Summary | |
| [M. October 28] | |
| Assignment 5 due | |
| Assignment 6 assigned | |
| Assignment 6 | |
| 34. | [W. October 30] |
| Lecture 34A Elementary analysis of algorithms | |
| Lecture 34B Logarithms | |
| Lecture 34C Common functions | |
| Lecture 34D Examples algorithms | |
| Lecture 34E Linear and binary search | |
| Lecture 34F Profilers (optional) | |
| Lecture 34G Summary | |
| 35. | [Th. October 31] |
| Lecture 35A FIFO queues | |
| Lecture 35B Linked implementation of FIFO queues | |
| Lecture 35C Array implementation of FIFO queues | |
| 36. | [F. November 1] |
| Lecture 36A Binary Trees | |
| Lecture 36B Trees in C++ | |
| Lecture 36C Nondestructive functions on trees | |
| Lecture 36D Summary | |
| 37. | [M. November 4] |
| Lecture 37A Traversing trees | |
| Lecture 37B Destructive functions on trees | |
| Lecture 37C Summary | |
| [W. November 6] | |
| Assignment 6 due | |
| Assignment 7 assigned | |
| Assignment 7 | |
| 38. | [Th. November 7] |
| Lecture 38A Binary search trees | |
| Lecture 38B Lookup and insertion | |
| Lecture 38C Removing the smallest value from a binary search tree | |
| Lecture 38D Summary | |
| [F. November 8] | |
|
Exam 4 Lectures
|
|
| 39. | [M. November 11] |
| Lecture 39A Deletion from a binary search tree | |
| Lecture 39B Height-balanced binary search trees | |
| Lecture 39C Summary | |
| 40. | [W. November 13] |
| Lecture 40A Doing rotations to keep a binary search tree height-balanced | |
| Lecture 40B Getting the height of a node and full implementation | |
| Lecture 40C Review of how to do rotations | |
| 41. | [Th. November 14] |
| Lecture 41A Tables | |
| Lecture 41B Hash functions | |
| Lecture 41C Hash tables | |
| Lecture 41D Summary | |
| 42. | [F. November 15] |
| Lecture 42A Heaps and priority queues | |
| Lecture 42B Representing a heap as an array | |
| Lecture 42C The priority queue type | |
| Lecture 42D Inserting into a heap | |
| Lecture 42E Removal from a heap | |
| Lecture 42F The cost of heap operations | |
| Lecture 42G Summary | |
| 43. | [M. November 18] |
| Lecture 43A Sorting a linked list using Insertion Sort | |
| Lecture 43B The cost of Insertion Sort | |
| Lecture 43C Merge Sort | |
| Lecture 43D Analysis of Merge Sort | |
| Lecture 43E Implementation of Merge Sort for linked lists | |
| Lecture 43F Summary and Optimality of Merge Sort | |
| 44. | [W. November 20] |
| Lecture 44A Heap Sort | |
| Lecture 44B Building an Initial Heap | |
| Lecture 44C Sorting using heaps | |
| Lecture 44D Analysis of Heap Sort | |
| Lecture 44E Summary | |
| [Th. November 21] | |
| Assignment 7 due | |
| Review | |
| [F. November 22] | |
|
Exam 5 Lectures
|
|
| [M. November 25] | |
| Review | |
| [W. November 27 – F. November 29] | |
| Thanksgiving break | |
| [M. December 2] | |
| Review | |
| [F. December 6] | |
| Final exam for section 001: 11:00–1:30 | |
| [W. December 11] | |
| Final exam for section 002: 2:00–4:30 | |