Difference between revisions of "CISC220 F2021"
(→Schedule) 
(→Schedule) 

Line 446:  Line 446:  
28  28  
    
−  Final review on YouTube  +  Final review on YouTube 
    
<![http://nameless.cis.udel.edu/class_data/220_f2014/CISC_220_Final_Review.pdf Final review slides]>  <![http://nameless.cis.udel.edu/class_data/220_f2014/CISC_220_Final_Review.pdf Final review slides]>  
<![http://nameless.cis.udel.edu/class_data/220_f2014/cisc220_f2010_final.pdf 2010 final] (ignore question 4, but see question 2 on [http://nameless.cis.udel.edu/class_data/220_f2014/220_2010_midterm.pdf 2010 midterm])>  <![http://nameless.cis.udel.edu/class_data/220_f2014/cisc220_f2010_final.pdf 2010 final] (ignore question 4, but see question 2 on [http://nameless.cis.udel.edu/class_data/220_f2014/220_2010_midterm.pdf 2010 midterm])>  
+    
+    
+  Dec. 10  
+  Final project demos  
+    
+    
+    
    
   
Revision as of 08:26, 18 November 2021
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, 2:304:30 pm 
URL 
Full: http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021 
TA 
Emma Adelmann, Email: eadel@udel.edu, office hours: 56 pm on Mondays, 12 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 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. 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 = 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, 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 COVID19 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
20212022 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.11.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.71.8 
template_test, anythingcell 
5  Sep. 14 Register/add deadline 
Stacks  ADT (including STL) and applications, including stacks for postfix expression evaluation  Drozdek 44.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 doublylinked lists for stacks and queues  Drozdek 33.2, 3.7, 3.8, 4.2, 4.4, 4.5  sll_stack 
Sep. 22  NO INPERSON LAB THIS WEEK  BUT LAB #4 ASSIGNED  
8  Sep. 23  Trees  Terminology; representation in general case; pre and postorder traversals; binary trees  Drozdek 66.2, 6.46.4.2  
9  Sep. 28  LECTURE ON YOUTUBE 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)  recording 
Sep. 29  NO INPERSON LAB THIS WEEK  BUT LAB #5 ASSIGNED  
Sep. 30  NO LECTURE TODAY Instructor away 

10  Oct. 5  Algorithm analysis  BigO notation and common complexity classes; analyzing code to obtain bigO estimates  Drozdek 22.3, 2.52.6, 2.7  
Oct. 6  LAB #6  
11  Oct. 7  Balanced binary trees  AVL trees: definition, balance notation, rotations  Drozdek 6.76.7.2 (skip 6.7.1)  Rotation applet 
12  Oct. 12  NO LECTURE TODAY Class cancelled 

Oct. 13  LAB #7  
13  Oct. 14  Balanced binary trees  AVL trees: applying rotations to restore balance property  Drozdek 6.76.7.2 (skip 6.7.1)  UD Capture is audio only today :( 
14  Oct. 19  Midterm review  Midterm review slides 
2010 midterm (ignore questions 2 and 6)  
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  STL PQ example 
Oct. 27  NO LAB THIS WEEK  
17  Oct. 28  Priority queues  Finish heap details  
18  Nov. 2  Disjoint sets  Unionfind 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  Compression  Huffman coding, tries  Drozdek 1111.2 (skip 11.2.1)  
Nov. 10  LAB #9  
21  Nov. 11  Finish compression; maps  Drozdek, 7.1.10  STL map example  
22  Nov. 16  Hashing  Hash function, probing (linear, quadratic, double hashing), chaining  Drozdek 1010.2.2  
Nov. 17  NO INPERSON LAB THIS WEEK  BUT LAB #10 ASSIGNED  
23  Nov. 18  Hashing  Deletions; applications to file integrity verification, password storage  Drozdek 10.3 Illustrated Guide to Cryptographic Hashes 
Project assigned 
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 unionfind  Drozdek 88.1, 8.5 (Kruskal's only)  
Dec. 1  NO LAB THIS WEEK  
25  Dec. 2  Graphs  Traversals: depthfirst, breadthfirst; shortest path: Dijkstra's algorithm  Drozdek 8.2, 8.3 (stop after Dijkstra's) Optional: Pathfinding tutorial (stop at "Heuristic search") 

26  Dec. 7  Sorting  Selection/insertion sorts, start mergesort  Drozdek 99.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. 10  Final project demos  
Tuesday, Dec. 14  FINAL EXAM  10:30 am12:30 pm (ISE305) 