| Lecture (date) | Summary | Assignments and Handouts |
|---|---|---|
| L1 (2017/01/11) |
Introduction to the course - administrative and topical. Theme of the course: abstraction versus efficiency. Illustrated on stack of double-precision floating-point numbers. |
Slides used in class |
| L2 (2017/01/18) |
Linear data structures: stacks and queues Preconditions as contracts between implementor and user of an ADT Array and linked-list implementations of stacks and queues |
Outline of lecture
Java code implementing Stack, Node, and Queue, as discussed in class |
| L3 (2017/01/23) |
Some example ADT design problems: Stacks enhanced with the minimum operation; priority queues Double-ended queues (Deques) Java specifics: The Comparable Interface |
Outline of lecture
The first programming assignment - due back by 9:05 am on Feb 1st (prior to the beginning of class on that date). |
| L4 (2017/01/25) |
Discussion of programming assignment Java: The Comparable interface Programming with lists (recursively) Practice problems: Exercises 3.11, 3.12, 3.24, and 3.36 of your text |
Outline of lecture |
| L5 (2017/01/30) |
Algorithm analysis: Introducing Big Oh Notation. Analysis of simple pieces of code
Read Sections 2.1 - 2.4.2 of your text. |
|
| L6 (2017/02/01) |
Running time analysis (continued). Further examples. Determining recurrences for the running time, illustrated on exponentiation and insertion sort.
Insertion sort is discussed in Section 7.2 of the text (pages 272-273). |
Java code of a recursive implementation of insertion sort Chapter 3 of this textbook has a nice introduction to Big-Oh notation and concepts. |
| L7 (2017/02/06) |
Recursive programming. Writing recurrences. Solutions to some common recurrences. Insertion sort, merge-sort, quick-sort, and binary search: algorithms and analysis. Merge-sort and quick-sort are discussed in Section 7.6 and 7.7 of your text. Binary search is discussed in pages 45-46 of your text. Some recurrences We should know |
Java code for recursive implementations of binary search and merge sort |
| L8 (2017/02/08) | In-class exam | |
| L9 (2017/02/13) |
Searching and sorting. Search in sorted/ unsorted arrays/ linked lists. Sorting algorithm attributes: running time, memory usage (in-place or not), stability. Lower bound on running time of comparison-based sorting Linear-time sorting: Counting (bucket) sort. |
The second programming assignment - due back by 9:05 am on Feb 20th. |
| L10 (2017/02/15) |
Linear-time sort: bucket (counting) sort and radix sort Introduction to (binary) trees. Representation of, and recursive programming on, binary trees. Linear-time sorting is discussed in Section 7.11 of the text. Tree terminology is discussed in pages 101-102, and implementation of binary trees in pages 107-108 of the text. Practice problems on sorting and searching: Exercises 7.44 and 7.45 are straight-forward; 7.42 and 7.43 less so. |
|
| L11 (2017/02/20) |
Array implementation of binary trees. Memory inefficient, except for complete binary trees Binary Heaps. structure and ordering properties. Implementing priority queues as binary heaps: example and code Read Chapters 6.1, 6.2, and 6.3.1-3 of the text. |
|
| L12 (2017/02/22) |
Heapsort: in-place implementation Some practice problems from the text Introduction to Dynamic Dictionaries Heapsort is discussed in Chapter 7.5 of the text |
The third programming assignment - due back by 5:00 pm on March 3rd. |
| L13 (2017/02/27) |
Binary trees. Recursive programming on binary trees Binary Search Tree (BST) implementation of dynamic dictionaries: examples and algorithms. Introduction to Balanced BSTs |
Java code for binary tree node and a main program that uses this. Practice problems: Download these and complete the recursive methods in the main program. |
| L14 (2017/03/01) |
Dynamic dictionaries implemented as binary search trees: implementation details Dynamic dictionaries in Java: Maps BST implementations are discussed in Chapter 4.3 of the text |
Java code for the Dynamic Dictionary Interface, the BST class, and the BST implementation of DD as discussed in class. |
| L15 (2017/03/06) | In-class exam | |
| L16 (2017/03/08) | Balanced BST's -- AVL trees. Inserting into AVL trees. Rebalancing: single rotations | |
| L17 (2017/03/20) |
AVL trees. Rebalancing -- single and double rotations The height of an AVL tree AVL trees are discussed in Chapter 4.4 of the text. |
|
| L18 (2017/03/22) |
Finishing up with AVL trees -- the remove operation Lazy delete Amortized analysis of ArrayList insert Introduction to Hash Tables |
The fourth programming assignment - due back by 5:00 pm on March 31st. |
| L19 (2017/03/27) | Hashing (Guest lecture by Calvin Deutschbein) | |
| L20 (2017/03/29) | Hashing with Calvin (continued) |
Calvin's cuckoo-hashing code that he discussed in class. |
| L21 (2017/04/03) |
Constant-time array initialization (Exercise 5.14 of the text) Introducing graphs: terminology and notation. Some example applications. Representation as adjacency matrices and adjacency lists Read Chapter 9.1 of the text
|
|
| L22 (2017/04/05) |
Topological sort for DAGs Graphs: Internal vs external representation of vertex names Read Chapter 9.2 of the text |
|
| L23 (2017/04/10) |
Review of hashing.
Read Chapter 5.1 - 5.5, and 5.7.2, of the text |
The fifth programming assignment - due back by 5:00 pm on April 18th. |
| L24 (2017/04/12) | In-class exam | |
| L25 (2017/04/17) |
Shortest-path problems on graphs: definition and basic properties All-pairs shortest paths: the Floyd Warshall algorithm Read pages 366-367, and Chapter 10.3.4 |
|
| L26 (2017/04/19) | Single-source shortest paths - the method of relaxations. Application to acyclic graphs, and to general graphs | |
| L27 (2017/04/24) |
Single source shortest paths - Dijkstra's algorithm
Class summary |
|
| L28 (2017/04/26) |
Make-up test(for eligible students) No class for the rest!! |