CISC220 F2023
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 Email: cer@cis.udel.edu Office: Smith 446 Office hours: Wednesdays, 24 pm in Smith 211 
URL 
http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023 
TAs 

Schedule  
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 Canvasemail 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 email of your intention to use them before the deadline. 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 = 90100, B = 8090, C = 7080, 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 (at least not new). Suggested sources:
Code examples from the book can be downloaded here 
Collaboration and AI policy  Students can discuss problems with one another in general terms, but must work independently on all assignments except when pairs or teams are permitted. This also applies to online and printed resources, including search engine results and discussion forums: you may consult them as references (as long as you cite them), but the words (i.e., code) 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.
On certain assignments where the instructions explicitly grant permission, students may use generative AI tools such as OpenAI's ChatGPT, GitHub's Copilot, Meta's Code Llama, etc. for code creation, modification, and/or bugfinding. Where no such permission is granted or nothing is said, the default assumption is that all code written originally came from and was fixed by your own human brain. Furthermore, if and when you use an AI tool for any permitted purpose, it MUST be acknowledged with a citation along the lines of these guidelines (i.e., specific tool, date, prompt or prompts used, as well as any other useful context). Such citations should be added as comments to any code files which contain AIgenerated code, and a README file with all such citations should be included with any homework submission. AI tools are generally acceptable for tutorial or explanatory purposes while working on programming assignments or labs, or when studying for quizzes/exams. However, AI or search tool usage during any inclass quiz or exam is prohibited. 
Schedule
Note: The blue squares in the "#" column below indicate Tuesdays. Tan rows are lab days (Thursdays/Fridays). All lectures (except YouTube posts) should be available on UDCapture
20232024 UD academic calendar
#  Date  Topic  Notes  Readings  Links 

1  Aug. 29  Introduction  Big four topics in data structures and algorithms: abstraction, implementation, analysis, and applications  Drozdek 1.11.3 

2  Aug. 31  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 
Basic C++ exercises with tutorial 
Aug. 31/Sep. 1  LAB #1  
3  Sep. 5  C++ review  ADTs, classes, destructors, constructors, assignments  Drozdek 1.4 (skip 1.4.5) 
cplusplus_2a.tar Simple C++ class creation exercises with solutions 
4  Sep. 7  C++ review  Function & class templates, STL  Drozdek 1.71.8 cplusplus.com tutorial: Classes II (class templates section in particular), STL reference 
template_test, anythingcell 
Sep. 7/Sep. 8  LAB #2  
5  Sep. 12 Register/add deadline 
Stacks  ADT (including STL) and applications, including stacks for postfix expression evaluation  Drozdek 44.1 codestepbystep practice site (registration required) 
stl_test 
6  Sep. 14  Stacks and queues  Implementing stacks with linear arrays; queue ADT, applications, and linear array implementation  Drozdek 4.1, 4.2  array_stack, array_queue 
Sep.14/Sep. 15  LAB #3  
7  Sep. 19  Queues, deques, and lists  Circular arrays for queues, singly and doublylinked lists for stacks and queues  Drozdek 33.2, 3.7, 3.8, 4.2, 4.4, 4.5  
8  Sep. 21  Trees  Terminology; representation in general case; pre and postorder traversals; binary trees; recursion  Drozdek 66.2, 6.46.4.2  More than you ever wanted to know about computing factorials 
Sep.21/Sep. 22  LAB #4  
9  Sep. 26  Trees  Binary trees for arithmetic expressions; inorder traversals; binary search trees  Drozdek 6.3, 6.56.6 (skip 6.6.1), 6.12 (expression trees)  
10  Sep. 28  Trees  Deletions, findMin(), findMax() in binary search trees; lab #5  
Sep.28/Sep. 29  LAB #5  
11  Oct. 3  Algorithm analysis  BigO notation and common complexity classes; analyzing code to obtain bigO estimates  Drozdek 22.3, 2.52.6, 2.7  
Oct. 5  NO LECTURE TODAY Instructor at meeting 

Oct. 5/Oct. 6  LAB #6  
12  Oct. 10  Balanced binary trees  AVL trees: definition, balance notation, rotations  Drozdek 6.76.7.2 (skip 6.7.1)  Rotation applet 
13  Oct. 12  Balanced binary trees, priority queues (PQ)  AVL trees: applying rotations to restore balance property; PQ ADT, comparison of implementation efficiencies  Drozdek 6.76.7.2 (skip 6.7.1); 4.3, 4.6 (PQs)  STL PQ example 
Oct. 12/Oct. 13  NO LAB THIS WEEK  
14  Oct. 17  Heap implementation of priority queues (NOT on midterm  see midterm review material in Links column) 
Heap implementation details, complexity analysis  Drozdek 6.9  Midterm review slides 2010 midterm (ignore questions 2 and 6), UDCapture going over 2010 exam 
15  Oct. 19  MIDTERM  
Oct. 19/Oct. 20  NO LAB THIS WEEK  
16  Oct. 24 
Disjoint sets  Equivalence relations, classes; unionfind algorithm 
Wikipedia entry, UW slides (first 5 pages of PDF) 

17  Oct. 26  Disjoint sets  Smart union, path compression, maze generation application  
Oct. 26/Oct. 27  LAB #7  
18  Oct. 31  Compression  Huffman coding, tries  Drozdek 1111.2 (skip 11.2.1)  
19  Nov. 2  Finish compression; maps  Drozdek, 7.1.10  STL map example  
Nov. 2/Nov. 3  LAB #8  
20  Nov. 7  Graphs  Terminology, applications, representations: adjacency matrix, adjacency lists/sets  Drozdek 88.1  
21  Nov. 9  Graphs  Traversals: depthfirst, breadthfirst  Drozdek 8.2, 8.3 (stop after Dijkstra's) Optional: Pathfinding tutorial (stop at "Heuristic search") 
BFS pseudocode 
Nov. 9/Nov. 10  LAB #9  
22  Nov. 14 Withdraw deadline Nov. 13 
Graphs  Dijkstra's shortest path algorithm, Kruskal's minimum spanning tree algorithm  Project assigned  
Nov. 16  NO LECTURE TODAY Instructor away 

Nov. 16/Nov. 17  NO LAB THIS WEEK  
Nov. 21  NO LECTURE TODAY Thanksgiving break 

Nov. 23  NO LECTURE TODAY Thanksgiving break 

Nov. 23/Nov. 24  NO LAB THIS WEEK Thanksgiving break 

23  Nov. 28  Hashing  Hash function, probing (linear, quadratic, double hashing), chaining  Drozdek 1010.2.2 Why choose a prime for hash table size? 

24  Nov. 30  Hashing  Deletions; applications to file integrity verification, password storage  Drozdek 10.3 Illustrated Guide to Cryptographic Hashes 

Nov. 30/Dec. 1  LAB #10  
25  Dec. 5  Sorting  Insertion sort, mergesort  Drozdek 9.1.1, 9.3.4 Optional: Sorting algorithms animated 

26  Dec. 7  Sorting  Actually less sorting  
Dec. 7/Dec. 8  NO LAB THIS WEEK  
Final review on YouTube  Final review slides Review recording  start at 4:17 (with solutions to 2010 final linked below) 2010 final (ignore Q4 and Q5, but see Q2 on 2010 midterm)  
Dec. 1112  Final project demos  Project due  
Dec. 14 11:30 am  1:30 pm 
FINAL EXAM  Gore 219 (this room!) 