Difference between revisions of "CISC220 F2023"

From class_wiki
Jump to: navigation, search
(Schedule)
(Schedule)
Line 209: Line 209:
 
|<!--[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Project1 Project #1]-->
 
|<!--[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Project1 Project #1]-->
 
|-
 
|-
|
+
|10
 
|Sep. 28
 
|Sep. 28
 
|Trees
 
|Trees
Line 223: Line 223:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
|style="background:rgb(102, 204, 255)"|10
+
|style="background:rgb(102, 204, 255)"|11
 
|Oct. 3
 
|Oct. 3
 
|Algorithm analysis
 
|Algorithm analysis
Line 230: Line 230:
 
|
 
|
 
|-
 
|-
|11
+
|12
 
|Oct. 5
 
|Oct. 5
 
|Balanced binary trees
 
|Balanced binary trees
Line 244: Line 244:
 
|style="background:rgb(245, 222, 179)"|<!--[http://nameless.cis.udel.edu/class_data/220_f2014/solutions_lab5.png Lab #5 solutions to 2.11.7, 2.11.8, and 2.11.10]-->
 
|style="background:rgb(245, 222, 179)"|<!--[http://nameless.cis.udel.edu/class_data/220_f2014/solutions_lab5.png Lab #5 solutions to 2.11.7, 2.11.8, and 2.11.10]-->
 
|-
 
|-
|style="background:rgb(102, 204, 255)"|12
+
|style="background:rgb(102, 204, 255)"|13
 
|Oct. 10
 
|Oct. 10
 
|
 
|
Line 251: Line 251:
 
|
 
|
 
|-
 
|-
|13
+
|14
 
|Oct. 12
 
|Oct. 12
 
|Balanced binary trees
 
|Balanced binary trees
Line 265: Line 265:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
|style="background:rgb(102, 204, 255)"|14
+
|style="background:rgb(102, 204, 255)"|15
 
|Oct. 17
 
|Oct. 17
 
|Midterm review
 
|Midterm review
Line 274: Line 274:
  
 
|-
 
|-
|15
+
|16
 
|Oct. 19
 
|Oct. 19
 
|MIDTERM
 
|MIDTERM
Line 288: Line 288:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
|style="background:rgb(102, 204, 255)"|16
+
|style="background:rgb(102, 204, 255)"|17
 
|Oct. 24<br>
 
|Oct. 24<br>
 
|Priority queues  
 
|Priority queues  
Line 295: Line 295:
 
|[https://drive.google.com/file/d/1xjRvqCxN_CH-xOlaofwY6A4O0D38_es7/view?usp=sharing STL PQ example]
 
|[https://drive.google.com/file/d/1xjRvqCxN_CH-xOlaofwY6A4O0D38_es7/view?usp=sharing STL PQ example]
 
|-
 
|-
|17
+
|18
 
|Oct. 26
 
|Oct. 26
 
|Priority queues
 
|Priority queues
Line 309: Line 309:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
|style="background:rgb(102, 204, 255)"|18
+
|style="background:rgb(102, 204, 255)"|19
 
|Oct. 31
 
|Oct. 31
 
|Disjoint sets
 
|Disjoint sets
Line 318: Line 318:
 
|
 
|
 
|-
 
|-
|19
+
|20
 
|Nov. 2
 
|Nov. 2
 
|Disjoint sets
 
|Disjoint sets
Line 332: Line 332:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
|style="background:rgb(102, 204, 255)"|20
+
|style="background:rgb(102, 204, 255)"|21
 
|Nov. 7
 
|Nov. 7
 
|Compression
 
|Compression
Line 339: Line 339:
 
|
 
|
 
|-
 
|-
|21
+
|22
 
|Nov. 9
 
|Nov. 9
 
|Finish compression; maps
 
|Finish compression; maps
Line 353: Line 353:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
|style="background:rgb(102, 204, 255)"|22
+
|style="background:rgb(102, 204, 255)"|23
 
|Nov. 14<br>''Withdraw deadline Nov. 13''
 
|Nov. 14<br>''Withdraw deadline Nov. 13''
 
|Hashing
 
|Hashing
Line 360: Line 360:
 
|
 
|
 
|-
 
|-
|23
+
|24
 
|Nov. 16
 
|Nov. 16
 
|Hashing
 
|Hashing

Revision as of 17:03, 28 August 2023

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.

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 (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: 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.

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. Where no such permission is granted or nothing is said, the default assumption is for you to do everything with your own human brain. If and when you use an AI tool (with permission), 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 AI-generated code, and a README file with all such citations should be included with any homework submission. AI or search tool usage during any in-class quizzes 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
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 Recursion Drozdek 5-5.5, 5.9
Sep.21/Sep. 22 LAB #4
9 Sep. 26 Trees Terminology; representation in general case; pre- and post-order traversals; binary trees Drozdek 6-6.2, 6.4-6.4.2
10 Sep. 28 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. 29 LAB #5
11 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
12 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
13 Oct. 10
14 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
15 Oct. 17 Midterm review Midterm review slides

Post-C++ lecture notes

2010 midterm (ignore questions 2 and 6)
16 Oct. 19 MIDTERM
Oct. 19/Oct. 20 NO LAB THIS WEEK
17 Oct. 24
Priority queues ADT, heap implementation Drozdek 4.3, 4.6, 6.9 STL PQ example
18 Oct. 26 Priority queues Finish heap details
Oct. 26/Oct. 27 NO LAB THIS WEEK
19 Oct. 31 Disjoint sets Union-find algorithm Drozdek 8.4.1

Wikipedia entry, UW slides (first 5 pages of PDF)
Optional: Princeton slides

20 Nov. 2 Disjoint sets Smart union, path compression, maze generation application
Nov. 2/Nov. 3 LAB #8
21 Nov. 7 Compression Huffman coding, tries Drozdek 11-11.2 (skip 11.2.1)
22 Nov. 9 Finish compression; maps Drozdek, 7.1.10 STL map example
Nov. 9/Nov. 10 LAB #9
23 Nov. 14
Withdraw deadline Nov. 13
Hashing Hash function, probing (linear, quadratic, double hashing), chaining Drozdek 10-10.2.2
24 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???