CISC220 F2021
Course information
| Description | CISC 220 -- Data Structures (Honors) Comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation. Topics include recursion, stacks, queues, lists, heaps, hash tables, search trees, sorting, and graphs. |
| Requirements | This is a course for undergraduates who have obstained a grade of C- or better in CISC 181, and have taken or are currently taking CISC 210 and MATH 241. |
| Instructor | Christopher Rasmussen E-mail: cer@cis.udel.edu Office: Smith 446 Office hours: Wednesdays, 2:30-4:30 pm |
| URL |
Full: http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021 |
| TA |
Emma Adelmann, E-mail: eadel@udel.edu, office hours: 5-6 pm on Mondays, 1-2 pm on Thursdays in Smith 102A |
| Schedule | Lectures are Tuesdays and Thursdays 9:30 am to 10:45 am in ISE 305, all labs are Wednesdays 4:40 pm to 5:30 pm in Smith 040 (basement). In the schedule below note that there is NOT a lab every week |
| Grading |
Your labs and programming projects are due by midnight of the deadline day (with a small grace period afterward). All should be submitted directly to Canvas--e-mail submissions will not be accepted. A late homework is a 0 without a valid prior excuse. To give you a little flexibility, you have 6 "late days" to use over the semester to extend the deadline by one day each without penalty. No more than two late days may be used per assignment. Late days will automatically be subtracted, but as a courtesy please notify the instructor and TA in an e-mail of your intention to use them before the deadline. Students can discuss problems with one another in general terms, but must work independently on all assignments. This also applies to online and printed resources: you may consult them as references (as long as you cite them), but the words you turn in must be yours alone. Any quoting must be clear and appropriately cited. The University's policies on academic dishonesty are set forth in the student code of conduct here. For the overall course grade, a preliminary absolute mark will be assigned to each student based on the percentage of the total possible points they earn according to the standard formula: A = 90-100, B = 80-90, C = 70-80, etc., with +'s and -'s given for the upper and lower third of each range, respectively. Based on the distribution of preliminary grades for all students (i.e., "the curve"), the instructor may increase these grades monotonically to calculate final grades. This means that your final grade can't be lower than your preliminary grade, and your final grade won't be higher than that of anyone who had a higher preliminary grade. I will try to keep you informed about your standing throughout the semester. If you have any questions about grading or expectations at any time, please feel free to ask me. |
| Textbook |
Data Structures and Algorithms in C++ (4th ed.), Adam Drozdek. It is NOT at the textbook store, don't look for it there
Code examples from the book can be downloaded here |
| University Covid policy | Student learning can only occur when students and their instructors feel safe, respected, and supported by each other. To ensure that our learning environment is as safe as possible, and in
keeping with CDC guidelines to slow the transmission of COVID-19 and the University of Delaware’s Return to Campus Guidelines (Health and Safety Section), we will adhere to the practice of wearing face masks and cleaning your seat and desk area at the beginning of class. This means that you:
As necessary, the University may announce modifications to these practices. In that event, these guidelines will be updated to reflect those modifications. |
Schedule
Note: The blue squares in the "#" column below indicate Tuesdays. Tan rows are lab days (Wednesdays). All lectures (except YouTube posts) should be available on UDCapture
2021-2022 UD academic calendar
| # | Date | Topic | Notes | Readings | Links |
|---|---|---|---|---|---|
| 1 | Aug. 31 | Introduction | Big four topics on data structures and algorithms: abstraction, implementation, analysis, and applications | Drozdek 1.1-1.3 |
|
| Sep. 1 | LAB #1 | ||||
| 2 | Sep. 2 | C++ review | C++ basics: differences with C, arrays, I/O, random numbers, new/delete, static vs. dynamic memory allocation | C vs. C++ C++ for Java programmers cheat sheets: [1], [2] cplusplus.com tutorial: Basics, Program Structure, Compound Data Types |
|
| 3 | Sep. 7 | C++ review | ADTs, classes, destructors, constructors, assignments | Drozdek 1.4 (skip 1.4.5) |
cplusplus_2a.tar |
| Sep. 8 | LAB #2 | ||||
| 4 | Sep. 9 | C++ review | Function & class templates, STL | Drozdek 1.7-1.8 |
template_test, anythingcell |
| 5 | Sep. 14 Register/add deadline |
Stacks | ADT (including STL) and applications, including stacks for postfix expression evaluation | Drozdek 4-4.1 | |
| Sep. 15 | LAB #3 | ||||
| 6 | Sep. 16 | Stacks and queues | Implementing stacks with linear arrays; queue ADT, applications, and linear array implementation | Drozdek 4.1, 4.2 | array_stack, array_queue |
| 7 | Sep. 21 | Queues, deques, and lists | Circular arrays for queues, singly- and doubly-linked lists for stacks and queues | Drozdek 3-3.2, 3.7, 3.8, 4.2, 4.4, 4.5 | sll_stack |
| Sep. 22 | LAB #4 | ||||
| 8 | Sep. 23 | Trees | Terminology; representation in general case; pre- and post-order traversals; binary trees | Drozdek 6-6.2, 6.4-6.4.2 | |
| 9 | Sep. 28 | LECTURE ON YOUTUBE Trees |
Binary trees for arithmetic expressions; in-order traversals; binary search trees | Drozdek 6.3, 6.5-6.6 (skip 6.6.1), 6.12 (expression trees) | |
| Sep. 29 | NO IN-PERSON LAB THIS WEEK -- LAB #5 ASSIGNED | ||||
| Sep. 30 | NO LECTURE TODAY Instructor away |
||||
| 10 | Oct. 5 | Algorithm analysis | Big-O notation and common complexity classes | Drozdek 2-2.3, 2.5-2.6 | |
| Oct. 6 | LAB #6 | ||||
| 11 | Oct. 7 | Finish algorithm analysis | Analyzing code to obtain big-O estimates | Drozdek 2.7 | |
| 12 | Oct. 12 | Balanced binary trees | AVL trees | Drozdek 6.7-6.7.2 (skip 6.7.1) | Rotation applet |
| Oct. 13 | LAB #7 | ||||
| 13 | Oct. 14 | Balanced binary trees | AVL trees | Drozdek 6.7-6.7.2 (skip 6.7.1) | |
| 14 | Oct. 19 | Midterm review | |||
| Oct. 20 | NO LAB THIS WEEK | ||||
| 15 | Oct. 21 | MIDTERM | |||
| 16 | Oct. 26 Withdraw deadline |
Priority queues | ADT, heap implementation | Drozdek 4.3, 4.6, 6.9 | |
| Oct. 27 | NO LAB THIS WEEK | ||||
| 17 | Oct. 28 | Priority queues | Finish heap details | ||
| 18 | Nov. 2 | Disjoint sets | Union-find algorithm | Drozdek 8.4.1 Wikipedia entry, UW slides (first 5 pages of PDF) |
|
| Nov. 3 | LAB #8 | ||||
| 19 | Nov. 4 | Disjoint sets | Smart union, path compression, maze generation application | ||
| 20 | Nov. 9 | Tries | Drozdek, 7.2 | ||
| Nov. 10 | LAB #9 | ||||
| 21 | Nov. 11 | Compression | Huffman coding | Drozdek 11-11.2 (skip 11.2.1) | |
| 22 | Nov. 16 | Hashing | Hash function, probing (linear, quadratic, double hashing), chaining | Drozdek 10-10.2.2 | |
| Nov. 17 | LAB #10 | ||||
| 23 | Nov. 18 | Hashing | Deletions; applications to file integrity verification, password storage | Drozdek 10.3 Illustrated Guide to Cryptographic Hashes |
|
| Nov. 23 | NO LECTURE TODAY Thanksgiving |
||||
| Nov. 24 | NO LAB THIS WEEK | ||||
| Nov. 25 | NO LECTURE TODAY Thanksgiving |
||||
| 24 | Nov. 30 | Graphs | Terminology, applications, representations: adjacency matrix, adjacency lists; minimum spanning tree with union-find | Drozdek 8-8.1, 8.5 (Kruskal's only) | |
| Dec. 1 | NO LAB THIS WEEK | ||||
| 25 | Dec. 2 | Graphs | Traversals: depth-first, breadth-first; shortest path: Dijkstra's algorithm | Drozdek 8.2, 8.3 (stop after Dijkstra's) Optional: Path-finding tutorial (stop at "Heuristic search") |
|
| 26 | Dec. 7 | Sorting | Selection/insertion sorts, start mergesort | Drozdek 9-9.1.2, 9.3.2 | |
| Dec. 8 | NO LAB THIS WEEK | ||||
| 27 | Dec. 9 | Sorting | Mergesort, quicksort | Drozdek 9.3.3, 9.3.4 Optional: Sorting algorithms animated |
Project due |
| 28 | Final review on YouTube | ||||
| Dec. 13-18 | FINAL EXAM | Time and place TBD |
