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 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_F2023
TA	??, E-mail: ??, office hours: ?? in Smith 102A (??)
Schedule	Lectures: Tuesdays and Thursdays 11:10 am to 12:30 pm in GORE 219 Labs: Thursdays 2:20 to 3:15 pm in CLB 046 and Fridays 3:00 to 3:55 pm in ISE 202. In the schedule below note that there is NOT a lab every week
Grading	50% Labs (5% each). These are problem sets/smaller programming exercises which are assigned in lab most weeks and due by midnight the night before the next lab. All written answers must be in PDF form. Attendance at labs is expected--this is your chance to ask questions face to face and get started early on the assignment 10% Open-ended programming project. Subject to a few constraints, you will be free to implement and apply a data structure and/or algorithm of your choosing. 20% Midterm 20% Final (essentially a midterm for the second half of the course) 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 4th edition: Amazon $10+ used, $33 paperback 4th edition: Google Play e-book $40 rental, $70 purchase Code examples from the book can be downloaded here
AI policy	something something about ChatGPT, Copilot, etc.

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
2023-2024 UD academic calendar

#	Date	Topic	Notes	Readings	Links
1	Aug. 29	Introduction	Big four topics on data structures and algorithms: abstraction, implementation, analysis, and applications	Drozdek 1.1-1.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
	Aug. 31/Sep. 1	LAB #1
3	Sep. 5	C++ review	ADTs, classes, destructors, constructors, assignments	Drozdek 1.4 (skip 1.4.5) cplusplus.com tutorial: Classes I & II, Special Members	cplusplus_2a.tar
4	Sep. 7	C++ review	Function & class templates, STL	Drozdek 1.7-1.8 cplusplus.com tutorial: Classes II, 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 4-4.1
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 doubly-linked lists for stacks and queues	Drozdek 3-3.2, 3.7, 3.8, 4.2, 4.4, 4.5	sll_stack
8	Sep. 21	Trees	Terminology; representation in general case; pre- and post-order traversals; binary trees	Drozdek 6-6.2, 6.4-6.4.2
	Sep.21/Sep. 22	LAB #4
9	Sep. 26	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. 28
	Sep.28/Sep. 29	LAB #5
10	Oct. 3	Algorithm analysis	Big-O notation and common complexity classes; analyzing code to obtain big-O estimates	Drozdek 2-2.3, 2.5-2.6, 2.7
11	Oct. 5	Balanced binary trees	AVL trees: definition, balance notation, rotations	Drozdek 6.7-6.7.2 (skip 6.7.1)	Rotation applet
	Oct. 5/Oct. 6	LAB #6
12	Oct. 10
13	Oct. 12	Balanced binary trees	AVL trees: applying rotations to restore balance property	Drozdek 6.7-6.7.2 (skip 6.7.1)
	Oct. 12/Oct. 13	LAB #7
14	Oct. 17	Midterm review		Midterm review slides Post-C++ lecture notes	2010 midterm (ignore questions 2 and 6)
15	Oct. 19	MIDTERM
	Oct. 19/Oct. 20	NO LAB THIS WEEK
16	Oct. 24	Priority queues	ADT, heap implementation	Drozdek 4.3, 4.6, 6.9	STL PQ example
17	Oct. 26	Priority queues	Finish heap details
	Oct. 26/Oct. 27	NO LAB THIS WEEK
18	Oct. 31	Disjoint sets	Union-find algorithm	Drozdek 8.4.1 Wikipedia entry, UW slides (first 5 pages of PDF) Optional: Princeton slides
19	Nov. 2	Disjoint sets	Smart union, path compression, maze generation application
	Nov. 2/Nov. 3	LAB #8
20	Nov. 7	Compression	Huffman coding, tries	Drozdek 11-11.2 (skip 11.2.1)
21	Nov. 9	Finish compression; maps		Drozdek, 7.1.10	STL map example
	Nov. 9/Nov. 10	LAB #9
22	Nov. 14 Withdraw deadline Nov. 13	Hashing	Hash function, probing (linear, quadratic, double hashing), chaining	Drozdek 10-10.2.2
23	Nov. 16	Hashing	Deletions; applications to file integrity verification, password storage	Drozdek 10.3 Illustrated Guide to Cryptographic Hashes	Project assigned
	Nov. 16/Nov. 17	NO IN-PERSON LAB THIS WEEK -- BUT LAB #10 ASSIGNED
	Nov. 21	NO LECTURE TODAY Thanksgiving
	Nov. 24	NO LAB THIS WEEK
	Nov. 23	NO LECTURE TODAY Thanksgiving
24	Nov. 28	Graphs	Terminology, applications, representations: adjacency matrix, adjacency lists	Drozdek 8-8.1	slides
25	Nov. 30	Graphs	Traversals: depth-first, breadth-first	Drozdek 8.2, 8.3 (stop after Dijkstra's) Optional: Path-finding tutorial (stop at "Heuristic search")	slides
	Nov. 30/Dec. 1	NO LAB THIS WEEK
26	Dec. 5	Graphs	Shortest path: Dijkstra's algorithm
27	Dec. 7	Sorting (abbreviated)	Insertion sort, mergesort	Drozdek 9.1.1, 9.3.4 Optional: Sorting algorithms animated
	Dec. 7/Dec. 8	NO LAB THIS WEEK
28		Final review on YouTube		Final review slides Post-midterm lecture notes	recording (with solutions to 2010 final linked below) 2010 final (ignore Q4 and Q5, but see Q2 on 2010 midterm)
	Dec. 12 -- this is past the end of classes	Final project demos			Project due
	Dec. 13-17	FINAL EXAM	Time and location???