Difference between revisions of "CISC220 F2024"
(→Schedule) |
(→Schedule) |
||
Line 106: | Line 106: | ||
''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 | ''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 | ||
<br> | <br> | ||
− | [https://www1.udel.edu/registrar/cal/calendars/ | + | [https://www1.udel.edu/registrar/cal/calendars/2024-2025.pdf 2024-2025 UD academic calendar] |
<br><br> | <br><br> | ||
Line 141: | Line 141: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|3 | |style="background:rgb(102, 204, 255)"|3 | ||
− | |Sep. | + | |Sep. 3 |
|C++ review | |C++ review | ||
|ADTs, classes, destructors, constructors, assignments | |ADTs, classes, destructors, constructors, assignments | ||
Line 149: | Line 149: | ||
|- | |- | ||
|4 | |4 | ||
− | |Sep. | + | |Sep. 5 |
|C++ review | |C++ review | ||
|Function & class templates, STL | |Function & class templates, STL | ||
Line 164: | Line 164: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|5 | |style="background:rgb(102, 204, 255)"|5 | ||
− | |Sep. | + | |Sep. 10<br> |
''Register/add deadline''<br> | ''Register/add deadline''<br> | ||
|Stacks | |Stacks | ||
Line 172: | Line 172: | ||
|- | |- | ||
|6 | |6 | ||
− | |Sep. | + | |Sep. 12 |
|Stacks and queues | |Stacks and queues | ||
|Implementing stacks with linear arrays; queue ADT, applications, and linear array implementation | |Implementing stacks with linear arrays; queue ADT, applications, and linear array implementation | ||
Line 186: | Line 186: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|7 | |style="background:rgb(102, 204, 255)"|7 | ||
− | |Sep. | + | |Sep. 17 |
|Queues, deques, and lists | |Queues, deques, and lists | ||
|Circular arrays for queues, singly- and doubly-linked lists for stacks and queues | |Circular arrays for queues, singly- and doubly-linked lists for stacks and queues | ||
Line 193: | Line 193: | ||
|- | |- | ||
|8 | |8 | ||
− | |Sep. | + | |Sep. 19 |
|Trees | |Trees | ||
|Terminology; representation in general case; pre- and post-order traversals; binary trees; recursion | |Terminology; representation in general case; pre- and post-order traversals; binary trees; recursion | ||
Line 207: | Line 207: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|9 | |style="background:rgb(102, 204, 255)"|9 | ||
− | |Sep. | + | |Sep. 24 |
|Trees | |Trees | ||
|Binary trees for arithmetic expressions; in-order traversals; binary search trees | |Binary trees for arithmetic expressions; in-order traversals; binary search trees | ||
Line 214: | Line 214: | ||
|- | |- | ||
|10 | |10 | ||
− | |Sep. | + | |Sep. 26 |
|Trees | |Trees | ||
|Deletions, findMin(), findMax() in binary search trees; lab #5 | |Deletions, findMin(), findMax() in binary search trees; lab #5 | ||
Line 228: | Line 228: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|11 | |style="background:rgb(102, 204, 255)"|11 | ||
− | |Oct. | + | |Oct. 1 |
|Algorithm analysis | |Algorithm analysis | ||
|Big-O notation and common complexity classes; analyzing code to obtain big-O estimates | |Big-O notation and common complexity classes; analyzing code to obtain big-O estimates | ||
Line 235: | Line 235: | ||
|- | |- | ||
| | | | ||
− | |Oct. | + | |Oct. 3 |
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Instructor at meeting'' | |style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Instructor at meeting'' | ||
| | | | ||
Line 249: | Line 249: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|12 | |style="background:rgb(102, 204, 255)"|12 | ||
− | |Oct. | + | |Oct. 8 |
|Balanced binary trees | |Balanced binary trees | ||
|AVL trees: definition, balance notation, rotations | |AVL trees: definition, balance notation, rotations | ||
Line 256: | Line 256: | ||
|- | |- | ||
|13 | |13 | ||
− | |Oct. | + | |Oct. 10 |
|Balanced binary trees, priority queues (PQ) | |Balanced binary trees, priority queues (PQ) | ||
|AVL trees: applying rotations to restore balance property; PQ ADT, comparison of implementation efficiencies | |AVL trees: applying rotations to restore balance property; PQ ADT, comparison of implementation efficiencies | ||
Line 270: | Line 270: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|14 | |style="background:rgb(102, 204, 255)"|14 | ||
− | |Oct. | + | |Oct. 15 |
|Heap implementation of priority queues<br> (NOT on midterm -- see midterm review material in Links column) | |Heap implementation of priority queues<br> (NOT on midterm -- see midterm review material in Links column) | ||
|Heap implementation details, complexity analysis | |Heap implementation details, complexity analysis | ||
Line 279: | Line 279: | ||
|- | |- | ||
|15 | |15 | ||
− | |Oct. | + | |Oct. 17 |
|MIDTERM | |MIDTERM | ||
| | | | ||
Line 293: | Line 293: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|16 | |style="background:rgb(102, 204, 255)"|16 | ||
− | |Oct. | + | |Oct. 22<br> |
|Disjoint sets | |Disjoint sets | ||
|Equivalence relations, classes; union-find algorithm | |Equivalence relations, classes; union-find algorithm | ||
Line 302: | Line 302: | ||
|- | |- | ||
|17 | |17 | ||
− | |Oct. | + | |Oct. 24 |
|Disjoint sets | |Disjoint sets | ||
|Smart union, path compression, maze generation application | |Smart union, path compression, maze generation application | ||
Line 316: | Line 316: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|18 | |style="background:rgb(102, 204, 255)"|18 | ||
− | |Oct. | + | |Oct. 29 |
|Compression | |Compression | ||
|Huffman coding, tries | |Huffman coding, tries | ||
Line 323: | Line 323: | ||
|- | |- | ||
|19 | |19 | ||
− | | | + | |Oct. 31 |
|Finish compression; maps | |Finish compression; maps | ||
| | | | ||
Line 337: | Line 337: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|20 | |style="background:rgb(102, 204, 255)"|20 | ||
− | |Nov. | + | |Nov. 5 |
|Graphs | |Graphs | ||
|Terminology, applications, representations: adjacency matrix, adjacency lists/sets | |Terminology, applications, representations: adjacency matrix, adjacency lists/sets | ||
Line 344: | Line 344: | ||
|- | |- | ||
|21 | |21 | ||
− | |Nov. | + | |Nov. 7 |
|Graphs | |Graphs | ||
|Traversals: depth-first, breadth-first | |Traversals: depth-first, breadth-first | ||
Line 359: | Line 359: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|22 | |style="background:rgb(102, 204, 255)"|22 | ||
− | |Nov. | + | |Nov. 12<br>''Withdraw deadline Nov. 13'' |
|Graphs | |Graphs | ||
|Dijkstra's shortest path algorithm, Kruskal's minimum spanning tree algorithm | |Dijkstra's shortest path algorithm, Kruskal's minimum spanning tree algorithm | ||
Line 366: | Line 366: | ||
|- | |- | ||
| | | | ||
− | |Nov. | + | |Nov. 14 |
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Instructor away'' | |style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Instructor away'' | ||
| | | | ||
Line 387: | Line 387: | ||
|- | |- | ||
| | | | ||
− | |Nov. | + | |Nov. 21 |
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Thanksgiving break'' | |style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Thanksgiving break'' | ||
| | | | ||
Line 401: | Line 401: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|23 | |style="background:rgb(102, 204, 255)"|23 | ||
− | |Nov. | + | |Nov. 26 |
|Hashing | |Hashing | ||
|Hash function, probing (linear, quadratic, double hashing), chaining | |Hash function, probing (linear, quadratic, double hashing), chaining | ||
Line 408: | Line 408: | ||
|- | |- | ||
|24 | |24 | ||
− | |Nov. | + | |Nov. 28 |
|Hashing | |Hashing | ||
|Deletions; applications to file integrity verification, password storage | |Deletions; applications to file integrity verification, password storage | ||
Line 422: | Line 422: | ||
|- | |- | ||
|style="background:rgb(102, 204, 255)"|25 | |style="background:rgb(102, 204, 255)"|25 | ||
− | |Dec. | + | |Dec. 3 |
|Sorting | |Sorting | ||
|Insertion sort, mergesort | |Insertion sort, mergesort | ||
Line 430: | Line 430: | ||
|- | |- | ||
|26 | |26 | ||
− | |Dec. | + | |Dec. 5 |
|Sorting | |Sorting | ||
|Actually less sorting | |Actually less sorting | ||
Line 458: | Line 458: | ||
|- | |- | ||
| | | | ||
− | |Dec. 14<br> | + | |Dec. 14<br> |
|FINAL EXAM | |FINAL EXAM | ||
− | | | + | |?? |
| | | | ||
| | | | ||
|} | |} |
Revision as of 09:34, 12 August 2024
Course information
Description | CISC 220 -- Data Structures 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-4 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 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, 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 bug-finding. 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 AI-generated 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 in-class 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
2024-2025 UD academic calendar
# | Date | Topic | Notes | Readings | Links |
---|---|---|---|---|---|
1 | Aug. 27 | Introduction | Big four topics in data structures and algorithms: abstraction, implementation, analysis, and applications | Drozdek 1.1-1.3 |
|
2 | Aug. 29 | 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. 3 | 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. 5 | C++ review | Function & class templates, STL | Drozdek 1.7-1.8 cplusplus.com tutorial: Classes II (class templates section in particular), STL reference |
template_test, anythingcell |
Sep. 7/Sep. 8 | LAB #2 | ||||
5 | Sep. 10 Register/add deadline |
Stacks | ADT (including STL) and applications, including stacks for postfix expression evaluation | Drozdek 4-4.1 codestepbystep practice site (registration required) |
stl_test |
6 | Sep. 12 | 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. 17 | 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 | |
8 | Sep. 19 | Trees | Terminology; representation in general case; pre- and post-order traversals; binary trees; recursion | Drozdek 6-6.2, 6.4-6.4.2 | More than you ever wanted to know about computing factorials |
Sep.21/Sep. 22 | LAB #4 | ||||
9 | Sep. 24 | 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) | |
10 | Sep. 26 | Trees | Deletions, findMin(), findMax() in binary search trees; lab #5 | ||
Sep.28/Sep. 29 | LAB #5 | ||||
11 | Oct. 1 | 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 | |
Oct. 3 | NO LECTURE TODAY Instructor at meeting |
||||
Oct. 5/Oct. 6 | LAB #6 | ||||
12 | Oct. 8 | Balanced binary trees | AVL trees: definition, balance notation, rotations | Drozdek 6.7-6.7.2 (skip 6.7.1) | Rotation applet |
13 | Oct. 10 | Balanced binary trees, priority queues (PQ) | AVL trees: applying rotations to restore balance property; PQ ADT, comparison of implementation efficiencies | Drozdek 6.7-6.7.2 (skip 6.7.1); 4.3, 4.6 (PQs) | STL PQ example |
Oct. 12/Oct. 13 | NO LAB THIS WEEK | ||||
14 | Oct. 15 | 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. 17 | MIDTERM | |||
Oct. 19/Oct. 20 | NO LAB THIS WEEK | ||||
16 | Oct. 22 |
Disjoint sets | Equivalence relations, classes; union-find algorithm |
Wikipedia entry, UW slides (first 5 pages of PDF) |
|
17 | Oct. 24 | Disjoint sets | Smart union, path compression, maze generation application | ||
Oct. 26/Oct. 27 | LAB #7 | ||||
18 | Oct. 29 | Compression | Huffman coding, tries | Drozdek 11-11.2 (skip 11.2.1) | |
19 | Oct. 31 | Finish compression; maps | Drozdek, 7.1.10 | STL map example | |
Nov. 2/Nov. 3 | LAB #8 | ||||
20 | Nov. 5 | Graphs | Terminology, applications, representations: adjacency matrix, adjacency lists/sets | Drozdek 8-8.1 | |
21 | Nov. 7 | Graphs | Traversals: depth-first, breadth-first | Drozdek 8.2, 8.3 (stop after Dijkstra's) Optional: Path-finding tutorial (stop at "Heuristic search") |
BFS pseudocode |
Nov. 9/Nov. 10 | LAB #9 | ||||
22 | Nov. 12 Withdraw deadline Nov. 13 |
Graphs | Dijkstra's shortest path algorithm, Kruskal's minimum spanning tree algorithm | Project assigned | |
Nov. 14 | NO LECTURE TODAY Instructor away |
||||
Nov. 16/Nov. 17 | NO LAB THIS WEEK | ||||
Nov. 21 | NO LECTURE TODAY Thanksgiving break |
||||
Nov. 21 | NO LECTURE TODAY Thanksgiving break |
||||
Nov. 23/Nov. 24 | NO LAB THIS WEEK Thanksgiving break |
||||
23 | Nov. 26 | Hashing | Hash function, probing (linear, quadratic, double hashing), chaining | Drozdek 10-10.2.2 Why choose a prime for hash table size? |
|
24 | Nov. 28 | 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. 3 | Sorting | Insertion sort, mergesort | Drozdek 9.1.1, 9.3.4 Optional: Sorting algorithms animated |
|
26 | Dec. 5 | 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. 11-12 | Final project demos | Project due | |||
Dec. 14 |
FINAL EXAM | ?? |