|
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 | |