# Topics

Topics | textbook |
CS3 |
Web links | ||
---|---|---|---|---|---|

21 Aug | M/1 | Introductions, Policies | |||

22 Aug | T/1 | Lab 1: Review and mastery | |||

23 Aug | W/1 | What is a data structure?, Design and specification | 1.1 | ||

25 Aug | F/1 | Object-oriented design, Classes and methods | 2.1-2.1.1.1 | ||

28 Aug | M/2 | .h files, Templates, UML | 2.2 | ||

29 Aug | T/2 | Lab 2: Classes | |||

30 Aug | W/2 | ||||

01 Sep | F/2 | ADTs, Lists | 1.2, 3.1 | ||

05 Sep | T/3 | Lab 3: Function design, Unit testing | |||

06 Sep | W/3 | Implementing an ADT | 3.2-3.2.1 | ||

08 Sep | F/3 | append, remove, Pointers, "Smart" pointers | 3.2.2 | Module 4 up through "Heap memory" | |

11 Sep | M/4 | ||||

12 Sep | T/4 | Lab 4: Pointers | |||

13 Sep | W/4 | Dynamic allocation | "Unique pointers" and "Dynamically allocated arrays" | ||

15 Sep | F/4 | Recursion, Fibonacci, Linked nodes | 7.1-7.2 | ||

18 Sep | M/5 | Linked list | 9.1 | ||

19 Sep | T/5 | Lab 5: Linked node methods | |||

20 Sep | W/5 | Linked list implementation (continued) | |||

22 Sep | F/5 | Recursive algorithms, Tower of Hanoi | 7.7 | ||

25 Sep | M/6 | Binary search, The call stack | |||

26 Sep | T/6 | Lab 6: Reading code, make, gdb, Backtracking | |||

27 Sep | W/6 | Recursive backtracking, Other uses of stacks | |||

29 Sep | F/6 | ||||

02 Oct | M/7 | Stacks and recursion, Array-based stack implementation, Exceptions | 6.1 | ||

03 Oct | T/7 | Lab 7: Using STL stacks | |||

04 Oct | W/7 | Review of allocation, references, and memory models | |||

09 Oct | M/8 | Classic ADTs, The "big picture" | |||

10 Oct | T/8 | Lab 8: Empirical efficiency | |||

11 Oct | W/8 | Algorithmic efficiency, Big-O notation | 4.2, 4.5 | ||

16 Oct | M/9 | Comparing implementations, Linked stacks, Array List, Linked List revisited | 6.2, 10.2 | ||

17 Oct | T/9 | Lab 9: Interfaces and multiple implementations | |||

18 Oct | W/9 | Inheritance part 1: type inheritance, is-a vs has-a, Quadratic sorts | Ch. 7 | ||

20 Oct | F/9 | Comparing algorithms, Faster sorts: mergesort | 8.9-8.10 | ||

23 Oct | M/10 | Mergesort cont'd | |||

24 Oct | T/10 | Lab 10: Overloading operators | |||

25 Oct | W/10 | Faster sorts: quicksort | 8.11 | ||

27 Oct | F/10 | Queues, Linked Queue | 9.1.1, 9.2 | ||

30 Oct | M/11 | Trees, Tree implementation | 11.1-11.3 | ||

31 Oct | T/11 | Lab 11: Linked trees | 16.1-16.2 | ||

01 Nov | W/11 | Traversals | |||

03 Nov | F/11 | Binary search trees | 11.4-11.4.2 | ||

06 Nov | M/12 | BST analysis, Balance, rotation | |||

07 Nov | T/12 | Lab 12: BST implementation | |||

08 Nov | W/12 | BST remove | 11.4.3 | ||

10 Nov | F/12 | BST remove, cont'd | |||

13 Nov | M/13 | Maps/Dictionaries, Hash tables | 6.4, 7.12, 10.1-10.4 | ||

15 Nov | W/13 | Heaps | 7.17 | ||

17 Nov | F/13 | Inheritance, is-a / has-a, Hierarchies | 2.1 | ||

20 Nov | M/14 | Model presentation and debrief | |||

21 Nov | T/14 | Lab: DT/Alg implementation | |||

27 Nov | M/15 | Presentation work day | |||

28 Nov | T/15 | Lab: DT/Alg implementation | |||

29 Nov | W/15 | Presentations | |||

01 Dec | F/15 | Presentations |