Data Structures: CSC 172

Procrastination is the grave in which opportunity is buried.

--- Dennis Kimbro.

Any fool can drown; that's the easy bit.

--- Pete Goss, solo sailor

Time and Place

2014:
172: 10:25-11:40 WF Gavett 202
172H: 10:25-11:40 WF LeChase 181

Grading Policies

Here are the 172 Assignment Guidelines and Grading Policies.

Academic Honesty:

Yogi says: "If you can't imitate him, don't copy him!"

172's design avoids the usual academic honesty issues by encouraging team effort. It's rare in that regard, so take maximum and guilt-free advantage of the cooperative atmosphere.

Formally, this course follows The University Policy on Academic Honesty .

Notes

  • Project and Laboratory exercises are due in Blackboard on the day and time indicated in Blackboard: any dates given in the tables below are approximate. Don't forget the late penalty.
  • Fall lab(s) and workshop(s) will be scheduled after classes start: Thus for lab work, workshops. and projects the T and R designations are approximate.
  • Visit Readings and Resources.
  • In the tables, MAW is Weiss, your printed textbook, KR is Kernighan-Ritchie the C text (available on line), FOCS is Fundamentals of Computer Science (FOCS) by Aho and Ullman, S is for Scheme (e.g. MIT or "other" or your choice). For readings, X.Y means "Chapter X, section Y". For self-tests, it's "Chapter X, exercise Y".

    Schedule

    (date on BB)--> -->
    Date Readings Lecture Self-Test Assignments
    W 9/03 MAW 1.1-1.3 TP Intro ODP , and CB Intro HTML MAW 1.5, 1.7, 1.8c, 1.11a(note misprint), 1.12 --
    F 9/05 MAW 1.4-1.6, FOCS 4.1-4.5 ) Generics PPT , and Oracle Generics Lesson Combx HTML MAW 1.13-1.15; FOCS 4.2.1, 4.2.2, 4.2.5, 4.3.1, 4.3.2, 4.4.1, 4.4.4a, 4.5.1, 4.5.2, 4.5.9 Lab: Java Review .
    W 9/10 MAW 2.*, Combinatorics, Running Time RunTime PPT, RunTime HTML, MAW 2.1, 2.7, 2.11, 2.12; FOCS 4.6.1, 4.6.2, 4.7.1, 4.7.2, 4.8.1a&b. Lab: Generics . Workshop: Induction, and FOCS 4.8.1c&d, 4.5.9 .
    F 9/12 MAW 2.*; KR 1.* Combinx. C in a lecture . KR 1. 1,1.15, 1.22 Lab: C intro .
    W 9/17 MAW 3.1-3.5; KR 2.* Java Linked Lists ODP , and Java Linked Lists PPT , and C Linked Lists ODP , and C Linked Lists PDF , and Lists HTML MAW 3.7, 3.9 Lab: JavaCollections . Workshop: Combx .
    F 9/19 MAW 3.4, - 3.6?; KR 3.* Lists II -- Lab: Linked Lists .
    W 9/24 MAW 3.6, 3.7; KR 4.*, 7.6 Stacks, Arith. Expr. ODP , and Stacks, Arith. Expr. PPT , and Stacks, Queues HTML , MAW 3.8, 3.10, 3.28; KR 4.4, 4.7 Lab: Dbl-lkd-Lists . Workshop: Recurring .
    F 9/26 MAW 4.1 - 4.3 Oview HTML , and Trees ODP , and Trees PPT , and BSTs PPT MAW 4.1 - 4.9 Lab: BST.
    W 10/1 MAW 4.4; KR 5.1-5.5 AVL ODP , AVL PPT , AVL HTML , C Pointers I , C Pointers II MAW 4.19, 4.21, 4.26 ???more; KR 5.1--5.3, 5.6 Lab: C Pointers . Workshop: Trees
    F 10/03 MAW 4.6-4.8; KR 5.6-5.12 Trav, B-trees, Sets, Map and AVL-II HTML , and B,theaded PPT , and C lists PPT MAW 4.31, 4.41, 4.51; KR 5.7, 5.9, 5.14, 5.20 Lab: C Ptrs to Ptrs .
    W 10/08 MAW 5.1-5.7, KR 6.1 --6.3 Hashing ODP and Hashing PPT and Hashing HTML MAW 5.1, 5.17 ; KR 6.1 Lab: C Ptrs to Fns . Workshop: work thru old tests.
    F 10/10 -- Slack -- Lab: C self-ref DS and Project Proposals Due Sat. .
    W 10/15 MAW 6.1-6.4, 6.9; KR 6.4-6.7 Heap and PQ ODP , and Heaps and PQ PPT, and Heaps HTML MAW 6.2, 6.3; KR 6.3, 6.4, 6.5 Lab: NONE. Workshop: Hashing
    F 10/17 All readings, old midterms MIDTERM IN CLASS -- Lab: Heaps
    W 10/22 MAW 7.1-7.5; KR 7.1-7.7 Simple Sorts ODP , Array Mergesort ODP, List Mergesort++ ODP , Merge Math ODP , and Merge in C ODP and Simple Sorts HTML Also SimpleSorts PPT , MergeSort PPT , MergeRecur PPT . MAW 7.1 -- 7.5; KR 7.1, 7.3-7.6, 7.9, 7.11-12. Lab: Sorts Workshop: Sorts
    F 10/24 MAW 7.6-7.9; Solving Recurrences, KR 7.8 QuickSort ODP, QuickSort PPT and LBSort ODT; LBSort PPT; Simple Sorts HTML and Further Sorts HTML MAW:7.15, 7.17, 7.20-21, 7.24, 7.30; Lab: More Sorts Revised Proposals Due Sat. .
    W 10/29 Back of the Envelope ; MAW 8.1-8.5 HashWs Ans Disjoint Sets ODP, Disjoint Sets PPT and Disjoint Sets HTML and MAW 8.1, 8.6 Lab: Union-Find Workshop: Back of the Envelope
    F 10/31 ?? MAW 8.6-8.7; KR Appendix B Slack, set math, sthg else? MAW 8.5, 8.7, 8.8 Lab: Scheme 1
    W 11/05 MAW 9.1 - 9.3.2 Graphs ODP -- Paths ODP and Graphs PPT -- Paths PPT and Graphs I HTML MAW 9.1, 9.3, 9.5 Lab: Graphs Intro Workshop: Back of the Envelope
    F 11/07 MAW 9.3.3- 9.5 ODPs: ShPath, Flow and PPTs: ShPath, Flow and Flow HTML MAW 9.11, 9.12, 9.15 Lab: Shortest Path I
    W 11/12 MAW 9.6, 9.7; S MIT 2-4 or equiv. 3 PPTS: P, NP ODP and 3 PPTS: P, NP PPT and ODPs: DFS , MWST and PPTs: DFS , MWST . Html: MST,DFS,NP HTML MAW 9.29-30, 9.39, 9.41, 9.54. 9.56 Lab: SP II: Dijkstra Workshop: Graphs I
    F 11/14 Huffman HTML Greedy -- Lab: Min. Spanning Tree
    W 11/19 MAW 10.1, S MIT 5-7 or equiv Progress Report Presentations MAW 10.3, 10.10 Lab: Scheme II and Workshop: Graphs, Huffman Project Progress Report Due Sat. .
    F 11/21 MAW 10.2 DivConq ODP and DivConq PPT and D&C HTML MAW 10.22, 20.24 Lab: DivConq
    W 11/26 MAW 10.3 DP ODP and DP PPT and DP HTML 10.28 Lab: Dyn Prog
    F 11/28 Recess: US Thksgvg, Red Planet Day Greedy Quiz Anss No Workshop, No Quiz
    W 12/03 MAW 10.3 or 10.4 DP II or Start Randomized 10.31, 10.35 Lab: Scheme Data Workshop: Dyn. Prog.
    F 12/05 MAW 10.4 Randomized Algs HTML and Skiplists ODP Skiplists PPT,plus Randomizing Algorithms ODP, 10.36 Lab: Lambda
    W 12/10 MAW 10.5 Backtrack ODP, Backtrack PPT and State-space search HTML 10.42, 10.43 Lab: state-space search Workshop: Graph Search
    M 12/15 1:30 -- 3:00 PM CSB 601 Final Project Presentations. .
    R 12/18 12:30 PM Final Exam CUMULATIVE FULL-LENGTH FINAL DEWEY 1-101 --
    S 12/20 -- -- Final Web Site Due Sat,, Also my.Project Report due (see BB).


    ---

    Last update: 8/8/2014: CB