|
Resources |
Staff Contact Information |
||
Instructor
Teaching Fellows:
|
|||
Lecture Schedule |
|||
|
Lecture |
Date |
Lecture Topic |
Lecture Slides, Readings, and Code Examples |
Homeworks, Labs, and Tests |
|
1 |
M 7/6 |
Overview of Course & Course Policies; Motivational Lecture: Two algorithms for searching an array---algorithm, implementation, analysis, and experiments. |
Lecture Slides: PDF |
HW 1: HTML Part A Solution: HTML |
2 |
T 7/7 | Java continued: Types, operators, and expressions. Java arrays |
Lecture Slides: PDF |
|
|
3 |
W 7/8 | Java expressions and operators concluded Java Statements: Conditionals: if/then, if/then/else Loops: while, for |
Lecture Slides: PDF |
|
| 4 | Th 7/9 | Breaking a Java program into separate classes and separate files; more on scope (public vs private); static vs non-static members. Creating and using (dynamic) objects; object-oriented design. Lab: Testing and debugging
|
Java V: PDF Summary of Java Program Structures: PDF |
HW 02: PDF Part A Solution: HTML |
| 5 | M 7/13 | Fields vs local variables and scope
Program Structure; The keyword |
Lecture: PDF
|
|
| 6 | T 7/14 | Creating and Using Objects; public vs private; Object-Oriented Programming; Abstract data types |
Lecture: PDF | Lab One: HTML |
| 7 | W 7/15
|
Object-Oriented Programming Concluded; Stacks, Queues, and Priority Queues as Abstract Data Types; Reference types: Basic Principles of References/Pointers; String type as a reference type Array resizing
|
Lecture: PDF Stack Example Code: JAVA |
|
| 8 | Th 7/16 | Queues implemented as Ring Buffers Deques and Priority Queues; |
Lecture: PDF |
HW 03: ZIP Part A Solution: HTML |
| 9 | M 7/20 | Analyzing the Time Complexity of Algorithms; Introduction to Sorting; Iterative Sorting Algorithms: Selection Sort |
Lecture Slides: PDF | |
| 10 | T 7/21 | Conclusions on Iterative Sorting: Complexity of Insertion Sort; Recursive Sorting Methods and their Complexity: Mergesort; Conclusions on sorting algorithms and complexity | Lecture Slides: PDF |
|
| 11 | W 7/22 | Introduction to Linked Lists; Stacks and Queues using Linked Lists; | Lecture Slides: PDF | |
| 12 | Th 7/23 | Iterative algorithms on Linked Lists |
Notes on Iteration and Linked Lists: HTML |
HW 04 Directory: DIR Part A Solution: HTML |
| 13 | M 7/27 | Iterative LL Algorithms concluded; Recursion and LLs Lab: Java Iterators |
Notes on Recursion and Linked Lists: HTML |
|
| 14 | T 7/28 | Recursion on LLs concluded |
|
Lab 03: HTML |
| 15 | W 7/29 | More list structures: doubly-linked lists, multilists, nested lists. |
|
|
| 16 | Th 7/30 | Binary Search Trees: Basic properties of BSTs, Basic algorithms |
|
HW 05: ZIP
Part A Solution: HTML Solution to Index.java: JAVA |
| 17 | M 8/3 | Algorithms on Binary Trees; Recursive tree traversals; Iterative tree traversals using an explicit stack |
Binary Tree Code: HTML | |
| 18 | T 8/4 | 2-3 Trees; B-Trees and external data structures | Lecture: PDF | Lab 04: PDF |
| 19 | W 8/5 | Heap Data Structure for Priority Queues; Heapsort | Reading: HTML
Max Heap Code Example: JAVA Lecture Notes: PDF |
|
| 19 | Th 8/6 | The (nearly) Perfect Data Structure; Perfect Hashing, Hash Functions; Hash Tables with Separate Chaining | Readings: Basic, Separate Chaining Another basic reading: Basic2 How to Build a Hash Table in Five Minutes or Less: HTML. Separate Chaining Example Code: JAVA. Lecture Notes: PDF |
HW 06: HTML |
| 20 | M 8/10 | Open Addressing; Linear Probing; Double hashing; |
Reading: Open Addressing
Example Code: JAVA |
|
| 21 | T 8/11 |
Resizing a hash table in linear time; Hash Tables concluded; Bloom Filters: Probabalistic Data Structures |
Readings: Dynamic Resizing
Example Code: JAVA Data Structure Comparison Code: ZIP |
|
| 22 | W 8/12 | Review Session |
Example Final Exam: PDF
Example Final Exam Solutions: PDF Exam Directory: DIR |
|
| Th 8/13 | Final Exam |
Final Exam (Word): DOCX Final Exam (PDF): PDF |