CS171: Introduction to Computer Science II:
Introduction to Data
Structures and Algorithms
Fall 2008
Time and Place: Tue-Thu, 1:00pm-2:15pm,
Math &
Science Center W302
Lecture and Assignment Schedule (Tentative!
Still changing and will continue to change throughout the semester)
Note: The readings are from either
Goodrich & Tamassia's Java book (G&T) or from Kernighan & Ritchie's C
book (K&R)
|
Date |
Lecture topics |
Readings |
Handouts, Lecture Notes, Files |
| Aug 28 | Introduction, course overview and logistics, Java review |
G&T Chapter 1 and 2.1-2.2 (CS170 review) |
Course information and syllabus
[pdf] Lecture [ pdf ] Homework 1 |
| Sep 2 | Java programming cont'd; development and debugging in Eclipse | G&T 2.3, 2.4 | Lecture slides [pdf] |
| Sep 4 | Java objects, linked lists | G&T 3.1-3.3 |
Annotated lecture slides [pdf
] inclass code: /home/cs171000/inclass/sep-4/
Homework 2 assigned
UPDATED |
| Sep 9 | Introduction to algorithm analysis: Experiments, big-Oh notation; Justification techniques | G&T 4.1, 4.2 |
Annotated lecture slides [ pdf ] inclass code: /home/cs171000/inclass/sep-9/ |
| Sep 11 | Algorithm analysis cont'd: Recurrences | G&T 4.3 | Annotated lecture slides [ pdf ] |
| Sep 16 | Recursion; Analyzing recursive algorithms | G&T Section 3.5; G&T Chapter 4+ | Annotated lecture slides [ pdf ]Homework 3: Loops.java |
| Sep 18 | Solving recurences | G&T Chapter 4 |
Annotated lecture slides [ pdf ] Prof. Cheung notes: [ part 1] [ part 2] |
| Sep 23 | Basic sorts + Mergesort | G&T 11.1 | Lecture
notes Homework 4 assigned, due Tue 9/30, 11pm |
| Sep 25 | Quicksort + analysis; sorting lower bound | G&T 11.2-3 | Lecture notes |
| Sep 29 | MONDAY, 9am: Midterm review | ||
| Sep 30 | No class | ||
| Oct 2 | Midterm 1 | ||
| Oct 7 | Midterm postmortem: hw3 go over | ||
| Oct 9 | No class | ||
| Oct 10 | make-up lecture
hw4 go over Introduction to C; memory organization |
K&R Chapter 1 (Tutorial introduction to C); K&R Chapters 2, 4, and Sections 5.1-5.6 | Lecture
notes Homework 5 assigned, due Tue 10/21, 11pm |
| Oct 14 | No class (Fall Break) | ||
| Oct 16 | C; memory organization, memory allocation |
G&T Chapter 14 K&R sections 6.1-6.5 |
Lecture notes |
| Oct 21 | No class | ||
| Oct 23 | Finish up C stuff: putting it all together, debugging. Begin: abstract Data Types in Java; Stack and Queue ADTs, | G&T Chapter 5.1-2 |
Lecture notes Homework 6 |
| Fri, Oct 24 |
make-up lecture (3pm, W304: implementation issues (lists, iterators); Java collections |
G&T 5.1, Chapter 6 | Lecture notes |
| Oct 28 | Trees: representation, properties, traversal | G&T Sections 7.1-2 |
Lecture notes Homework 7 assigned, due Wed, 11/5 |
| Oct 30 | Instructor away | ||
| Nov 4 | Binary trees, traversal, Maps & Dictionaires | G&T 7.3, G&T 9.1 | Lecture notes |
| Nov 6 | Binary search trees | 10.1-10.2 |
Lecture notes Homework 8 |
| Nov 11 | Hashing | G&T 9.2 | Lecture notes |
| Nov 13 | Catch-up, Midterm review |
Lecture notes Homework 9 (due - Nov 19) |
|
| Nov 18 | Midterm 2 | ||
| Nov 20 | Graph representation, traversal | G&T Sections 13.1-13.3 | Homework 10 |
| Nov 25 | Basic Java UI/visualization/Events | ||
| Dec 2 | Directed and weighted graphs; Shortest paths/Dijkstra's algorithm; Priority Queue |
G&T 13.4; 13.5, 13.6; |
Homework 11 |
| Dec 4 | Priority queue ADT and Heap data structure | G&T 8.1-8.3 | |
| Dec 9 | Other graph properties: Search, Small world networks | Homework 12 | |
| TBD | Final Review | ||
| Dec 12 | Final |