Difference between revisions of "CISC220 F2023"

From class_wiki
Jump to: navigation, search
(→‎Schedule)
(→‎Schedule)
 
(134 intermediate revisions by the same user not shown)
Line 12: Line 12:
 
|-
 
|-
 
|valign="top"|'''Instructor'''
 
|valign="top"|'''Instructor'''
−
|Christopher Rasmussen<br>E-mail: cer@cis.udel.edu<br>Office: Smith 446<br>Office hours: Wednesdays, 2:30-4:30 pm  
+
|Christopher Rasmussen<br>E-mail: cer@cis.udel.edu<br>Office: Smith 446<br>Office hours: Wednesdays, 2-4 pm in Smith 211 
 
|-
 
|-
 
|valign="top"|'''URL'''
 
|valign="top"|'''URL'''
 
|
 
|
−
Full: http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021<br>
+
http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023
 
|-
 
|-
−
|valign="top"|'''TA'''
+
|valign="top"|'''TAs'''
 
|
 
|
−
Emma Adelmann, E-mail: eadel@udel.edu, office hours: 5-6 pm on Mondays, 1-2 pm on Thursdays in Smith 102A
+
* Benita Abraham, E-mail: beniabra@udel.edu, Friday lab, office hours Tuesdays 4-5 pm in Smith 203
 +
* Connor Nagle, E-mail: cnagle@udel.edu, Thursday lab, office hours Tuesdays 3-4 pm in Smith 203
 
|-
 
|-
 
|valign="top"|'''Schedule'''
 
|valign="top"|'''Schedule'''
−
|Lectures are Tuesdays and Thursdays 9:30 am to 10:45 am in [https://css-rdms1.win.udel.edu/maps/?find=NE67 ISE 305], all labs are Wednesdays 4:40 pm to 5:30 pm in [https://css-rdms1.win.udel.edu/maps/?find=NW34 Smith 040] (basement).  In the schedule below note that there is NOT a lab every week
+
|
 +
* Lectures: Tuesdays and Thursdays 11:10 am to 12:30 pm in [https://css-rdms1.win.udel.edu/maps/?find=NC36 GORE 219]
 +
* Labs: Thursdays 2:20 to 3:15 pm in [https://css-rdms1.win.udel.edu/maps/?find=NC15 CLB 046] and Fridays 3:00 to 3:55 pm in [https://css-rdms1.win.udel.edu/maps/?find=NE67 ISE 202].  In the schedule below note that there is NOT a lab every week
 
|-
 
|-
 
|valign="top"|'''Grading'''
 
|valign="top"|'''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
+
* 50%  Labs (5% each).  These are problem sets/smaller programming exercises which are assigned in lab most weeks and '''due by the beginning of class each Thursday before the next lab'''.  All written answers must be in PDF form.  Attendance at labs is expected if you have not yet submitted--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.   
 
* 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%  Midterm (Oct. 19)
 
* 20% Final (essentially a midterm for the second half of the course)
 
* 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 [http://www.udel.edu/canvas 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.
 
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 [http://www.udel.edu/canvas 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 [https://www1.udel.edu/stuguide/21-22/code.html 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.   
 
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.   
Line 43: Line 44:
 
|valign="top"|'''Textbook'''
 
|valign="top"|'''Textbook'''
 
|
 
|
−
''Data Structures and Algorithms in C++'' (4th ed.), Adam Drozdek.  It is NOT at the textbook store, don't look for it there
+
''Data Structures and Algorithms in C++'' (4th ed.), Adam Drozdek.  It is NOT at the textbook store (at least not new).  Suggested sources:
−
* 4th edition: [http://www.amazon.com/Data-Structures-Algorithms-Adam-Drozdek/dp/1133608426/ref=dp_ob_title_bk Amazon] ~$35 e-book rental, ~$44 hardcover rental as of Aug. 30
+
* [http://www.amazon.com/Data-Structures-Algorithms-Adam-Drozdek/dp/1133608426/ref=dp_ob_title_bk Amazon] $10+ used, $33 paperback
−
* 4th edition: [http://www.cengagebrain.com/shop/ISBN/9781133608424?cid=APL1 Publisher (Cengage)]  ~$35 e-book rental as of Aug. 30
+
* [https://play.google.com/store/books/details?id=PRgLAAAAQBAJ&rdid=book-PRgLAAAAQBAJ&rdot=1&source=gbs_vpt_read Google Play e-book]  $40 rental, $70 purchase
  
 
Code examples from the book can be downloaded [http://www.cengage.com/cgi-wadsworth/course_products_wp.pl?fid=M63&product_isbn_issn=9781133608424&chapter_number=0&resource_id=21&altname=Student%20Data%20Files%20and%20Source%20Code here]
 
Code examples from the book can be downloaded [http://www.cengage.com/cgi-wadsworth/course_products_wp.pl?fid=M63&product_isbn_issn=9781133608424&chapter_number=0&resource_id=21&altname=Student%20Data%20Files%20and%20Source%20Code here]
  
 
|-
 
|-
−
|valign="top"|'''University Covid policy'''
+
|valign="top"|'''Collaboration and AI 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
+
|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 [https://www.udel.edu/students/community-standards/student-guide/ here].
−
keeping with CDC guidelines to slow the transmission of COVID-19 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:
+
On certain assignments where the instructions explicitly grant permission, students may use generative AI tools such as [https://openai.com/chatgpt OpenAI's ChatGPT], [https://github.com/features/copilot GitHub's Copilot], [https://github.com/facebookresearch/codellama 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 [https://subjectguides.uwaterloo.ca/chatgpt_generative_ai/aigeneratedcontentcitation 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.
−
* Must wear a cloth mask that covers your nose and mouth
+
 
−
* Must not eat or drink in class
+
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.
−
* Upon entering the classroom, wipe down your seat and desk area
 
−
As necessary, the University may announce modifications to these practices. In that event,
 
−
these guidelines will be updated to reflect those modifications.
 
 
<!--
 
<!--
 
|-
 
|-
Line 106: Line 104:
 
==Schedule==
 
==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
+
''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/2023-2024.pdf 2023-2024 UD academic calendar]
 
[https://www1.udel.edu/registrar/cal/calendars/2023-2024.pdf 2023-2024 UD academic calendar]
Line 122: Line 120:
 
|Aug. 29
 
|Aug. 29
 
|Introduction  
 
|Introduction  
−
|Big four topics on data structures and algorithms: abstraction, implementation, analysis, and applications
+
|Big four topics in data structures and algorithms: abstraction, implementation, analysis, and applications
 
|Drozdek 1.1-1.3<br>
 
|Drozdek 1.1-1.3<br>
 
|<!--[http://nameless.cis.udel.edu/class_data/220_f2014/code/cplusplus_1.tar singledyn, multidyn, wordbyword, mutatefile]-->
 
|<!--[http://nameless.cis.udel.edu/class_data/220_f2014/code/cplusplus_1.tar singledyn, multidyn, wordbyword, mutatefile]-->
Line 132: Line 130:
 
|[https://www.softwaretestinghelp.com/c-vs-cpp/ C vs. C++]<br>C++ for Java programmers cheat sheets: [http://www.horstmann.com/ccj2/ccjapp3.html], [http://www.cprogramming.com/java/c-and-c++-for-java-programmers.html]<br>
 
|[https://www.softwaretestinghelp.com/c-vs-cpp/ C vs. C++]<br>C++ for Java programmers cheat sheets: [http://www.horstmann.com/ccj2/ccjapp3.html], [http://www.cprogramming.com/java/c-and-c++-for-java-programmers.html]<br>
 
[http://www.cplusplus.com/doc/tutorial/ cplusplus.com tutorial: Basics, Program Structure, Compound Data Types]
 
[http://www.cplusplus.com/doc/tutorial/ cplusplus.com tutorial: Basics, Program Structure, Compound Data Types]
−
|<!--[http://nameless.cis.udel.edu/class_data/220_f2014/code/cplusplus_2.tar intcell, intcellarray, big3]<br>-->
+
|[https://www.w3schools.com/cpp/cpp_exercises.asp Basic C++ exercises with tutorial]
 +
<!--[http://nameless.cis.udel.edu/class_data/220_f2014/code/cplusplus_2.tar intcell, intcellarray, big3]<br>-->
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Aug. 31/Sep. 1
 
|style="background:rgb(245, 222, 179)"|Aug. 31/Sep. 1
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab1 LAB #1]  
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab1 LAB #1]  
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 147: Line 146:
 
|Drozdek 1.4 (skip 1.4.5)<br>
 
|Drozdek 1.4 (skip 1.4.5)<br>
 
[http://www.cplusplus.com/doc/tutorial/ cplusplus.com tutorial: Classes I & II, Special Members]
 
[http://www.cplusplus.com/doc/tutorial/ cplusplus.com tutorial: Classes I & II, Special Members]
−
|[https://drive.google.com/file/d/1Yih9IhBmdcSlQo8PweUANbsoPozSQAh9/view?usp=sharing cplusplus_2a.tar] <!--[http://nameless.cis.udel.edu/class_data/220_f2014/code/cplusplus_3.tar functemplate], [http://nameless.cis.udel.edu/class_data/220_f2014/code/cplusplus_4.tar anythingcell, generalarray, STL_vector]-->
+
|[https://drive.google.com/file/d/1Yih9IhBmdcSlQo8PweUANbsoPozSQAh9/view?usp=sharing cplusplus_2a.tar]<br>[https://www.w3resource.com/cpp-exercises/oop/index.php Simple C++ class creation exercises with solutions]<!--[http://nameless.cis.udel.edu/class_data/220_f2014/code/cplusplus_3.tar functemplate], [http://nameless.cis.udel.edu/class_data/220_f2014/code/cplusplus_4.tar anythingcell, generalarray, STL_vector]-->
 
|-
 
|-
 
|4
 
|4
Line 154: Line 153:
 
|Function & class templates, STL
 
|Function & class templates, STL
 
|Drozdek 1.7-1.8<br>
 
|Drozdek 1.7-1.8<br>
−
[http://www.cplusplus.com/doc/tutorial/ cplusplus.com tutorial: Classes II], [http://www.cplusplus.com/reference/stl STL reference]
+
[http://www.cplusplus.com/doc/tutorial/ cplusplus.com tutorial: Classes II] (class templates section in particular), [http://www.cplusplus.com/reference/stl STL reference]
 
|<!--[http://nameless.cis.udel.edu/class_data/220_f2014/code/mystring_final.tar mystring_final]-->[http://nameless.cis.udel.edu/class_data/220_f2014/code/template_test.tar template_test], [http://nameless.cis.udel.edu/class_data/220_f2014/code/anythingcell.tar anythingcell]
 
|<!--[http://nameless.cis.udel.edu/class_data/220_f2014/code/mystring_final.tar mystring_final]-->[http://nameless.cis.udel.edu/class_data/220_f2014/code/template_test.tar template_test], [http://nameless.cis.udel.edu/class_data/220_f2014/code/anythingcell.tar anythingcell]
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Sep. 7/Sep. 8
 
|style="background:rgb(245, 222, 179)"|Sep. 7/Sep. 8
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab2 LAB #2]
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab2 LAB #2]
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 169: Line 168:
 
|Stacks
 
|Stacks
 
|ADT (including STL) and applications, including stacks for postfix expression evaluation
 
|ADT (including STL) and applications, including stacks for postfix expression evaluation
−
|Drozdek 4-4.1
+
|Drozdek 4-4.1<br>[https://www.codestepbystep.com/ codestepbystep practice site] (registration required)
−
|
+
|[https://drive.google.com/file/d/17Be8jYUeeNPfXuaX0Qh-QxI3LX2sbHCM/view?usp=sharing stl_test]
 
|-
 
|-
 
|6
 
|6
Line 177: Line 176:
 
|Implementing stacks with linear arrays; queue ADT, applications, and linear array implementation   
 
|Implementing stacks with linear arrays; queue ADT, applications, and linear array implementation   
 
|Drozdek 4.1, 4.2
 
|Drozdek 4.1, 4.2
−
|[http://nameless.cis.udel.edu/class_data/220_f2014/code/array_stack.tar array_stack], [http://nameless.cis.udel.edu/class_data/220_f2014/code/array_queue.tar array_queue] <!-- sll_stack-->
+
|[http://nameless.cis.udel.edu/class_data/220_f2014/code/array_stack.tar array_stack], [http://nameless.cis.udel.edu/class_data/220_f2014/code/array_queue.tar array_queue]<!-- sll_stack-->
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Sep.14/Sep. 15
 
|style="background:rgb(245, 222, 179)"|Sep.14/Sep. 15
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab3 LAB #3]
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab3 LAB #3]
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 191: Line 190:
 
|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
 
|Drozdek 3-3.2, 3.7, 3.8, 4.2, 4.4, 4.5
 
|Drozdek 3-3.2, 3.7, 3.8, 4.2, 4.4, 4.5
−
|[https://drive.google.com/file/d/1Pany4gsFBmGp41xOi_A1O_wHc7bg_hmo/view?usp=sharing sll_stack]
+
|<!--[https://drive.google.com/file/d/1Pany4gsFBmGp41xOi_A1O_wHc7bg_hmo/view?usp=sharing sll_stack]-->
 
|-
 
|-
 
|8
 
|8
 
|Sep. 21
 
|Sep. 21
 
|Trees
 
|Trees
−
|Terminology; representation in general case; pre- and post-order traversals; binary trees
+
|Terminology; representation in general case; pre- and post-order traversals; binary trees; recursion
 
|Drozdek 6-6.2, 6.4-6.4.2
 
|Drozdek 6-6.2, 6.4-6.4.2
−
|
+
|[https://www.luschny.de/math/factorial/FastFactorialFunctions.htm More than you ever wanted to know about computing factorials]
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Sep.21/Sep. 22
 
|style="background:rgb(245, 222, 179)"|Sep.21/Sep. 22
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab4 LAB #4]
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab4 LAB #4]
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 214: Line 213:
 
|<!--[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
−
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Instructor away''
+
|Trees
−
|
+
|Deletions, findMin(), findMax() in binary search trees; lab #5
 
|
 
|
 
|
 
|
Line 223: Line 222:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Sep.28/Sep. 29
 
|style="background:rgb(245, 222, 179)"|Sep.28/Sep. 29
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab5 LAB #5]
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab5 LAB #5]
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|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 235: Line 234:
 
|
 
|
 
|-
 
|-
−
|11
+
|
 
|Oct. 5
 
|Oct. 5
−
|Balanced binary trees
+
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Instructor at meeting''
−
|AVL trees: definition, balance notation, rotations
+
|
−
|Drozdek 6.7-6.7.2 (skip 6.7.1)
+
|
−
|[http://research.cs.queensu.ca/home/jstewart/applets/bst/bst-rotation.html Rotation applet]
+
|
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Oct. 5/Oct. 6
 
|style="background:rgb(245, 222, 179)"|Oct. 5/Oct. 6
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab6 LAB #6]
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab6 LAB #6]
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 251: Line 250:
 
|style="background:rgb(102, 204, 255)"|12
 
|style="background:rgb(102, 204, 255)"|12
 
|Oct. 10
 
|Oct. 10
−
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Class cancelled''
+
|Balanced binary trees
−
|
+
|AVL trees: definition, balance notation, rotations
−
|
+
|Drozdek 6.7-6.7.2 (skip 6.7.1)
−
|
+
|[http://research.cs.queensu.ca/home/jstewart/applets/bst/bst-rotation.html Rotation applet]
 
|-
 
|-
 
|13
 
|13
 
|Oct. 12
 
|Oct. 12
−
|Balanced binary trees
+
|Balanced binary trees, priority queues (PQ)
−
|AVL trees: applying rotations to restore balance property
+
|AVL trees: applying rotations to restore balance property; PQ ADT, comparison of implementation efficiencies
−
|Drozdek 6.7-6.7.2 (skip 6.7.1)
+
|Drozdek 6.7-6.7.2 (skip 6.7.1); 4.3, 4.6 (PQs)
−
|
+
|[https://drive.google.com/file/d/1xjRvqCxN_CH-xOlaofwY6A4O0D38_es7/view?usp=sharing STL PQ example]
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Oct. 12/Oct. 13
 
|style="background:rgb(245, 222, 179)"|Oct. 12/Oct. 13
−
|style="background:rgb(255, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab7 LAB #7]
+
|style="background:rgb(255, 102, 0)"|NO LAB THIS WEEK
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 272: Line 271:
 
|style="background:rgb(102, 204, 255)"|14
 
|style="background:rgb(102, 204, 255)"|14
 
|Oct. 17
 
|Oct. 17
−
|Midterm review
+
|Heap implementation of priority queues<br> (NOT on midterm -- see midterm review material in Links column)
−
|
+
|Heap implementation details, complexity analysis
−
|[https://docs.google.com/presentation/d/1UmeRYPvg_hUIg8SneK9lrYRK-c2QWFcPH9yBaiwIEx8/edit?usp=sharing Midterm review slides]<br>
+
|Drozdek 6.9<!--[https://docs.google.com/presentation/d/1UmeRYPvg_hUIg8SneK9lrYRK-c2QWFcPH9yBaiwIEx8/edit?usp=sharing Midterm review slides]<br>
−
[https://drive.google.com/file/d/1s0rUqxQ8dJLWLyo1HVcVsYOvo74Pv9wX/view?usp=sharing Post-C++ lecture notes]
+
[https://drive.google.com/file/d/1s0rUqxQ8dJLWLyo1HVcVsYOvo74Pv9wX/view?usp=sharing Post-C++ lecture notes]-->
−
|[http://nameless.cis.udel.edu/class_data/220_f2014/220_2010_midterm.pdf 2010 midterm] (ignore questions 2 and 6)
+
|[https://docs.google.com/presentation/d/1UOvLfQdfQph2SnJLgsUXePnykJghGkMYVU37CW6H7Tw/edit?usp=sharing Midterm review slides]<br>[http://nameless.cis.udel.edu/class_data/220_f2014/220_2010_midterm.pdf 2010 midterm] (ignore questions 2 and 6), [https://www.youtube.com/watch?v=NNTO_U6HgrE UDCapture going over 2010 exam]<br>
−
 
+
[https://drive.google.com/file/d/1zrrzlh3F43r8btG6NjewDq87muFvAPzn/view?usp=sharing 2021 midterm]
 
|-
 
|-
 
|15
 
|15
Line 295: Line 294:
 
|style="background:rgb(102, 204, 255)"|16
 
|style="background:rgb(102, 204, 255)"|16
 
|Oct. 24<br>
 
|Oct. 24<br>
−
|Priority queues
+
|Disjoint sets
−
|ADT, heap implementation
+
|Equivalence relations, classes; union-find algorithm
−
|Drozdek 4.3, 4.6, 6.9
+
|
−
|[https://drive.google.com/file/d/1xjRvqCxN_CH-xOlaofwY6A4O0D38_es7/view?usp=sharing STL PQ example]
+
[http://en.wikipedia.org/wiki/Disjoint-set_data_structure Wikipedia entry], [http://courses.cs.washington.edu/courses/cse332/12su/slides/lecture15-mst-dsuf-handout.pdf UW slides] (first 5 pages of PDF)<br>
 +
<!--Optional: [https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf Princeton slides]-->
 +
|<!--[https://drive.google.com/file/d/1xjRvqCxN_CH-xOlaofwY6A4O0D38_es7/view?usp=sharing STL PQ example]-->
 
|-
 
|-
 
|17
 
|17
 
|Oct. 26
 
|Oct. 26
−
|Priority queues
+
|Disjoint sets
−
|Finish heap details
+
|Smart union, path compression, maze generation application
 
|
 
|
 
|
 
|
Line 309: Line 310:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Oct. 26/Oct. 27
 
|style="background:rgb(245, 222, 179)"|Oct. 26/Oct. 27
−
|style="background:rgb(255, 102, 0)"|<!--[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab7 LAB #7]-->NO LAB THIS WEEK
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab7 LAB #7]
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 316: Line 317:
 
|style="background:rgb(102, 204, 255)"|18
 
|style="background:rgb(102, 204, 255)"|18
 
|Oct. 31
 
|Oct. 31
−
|Disjoint sets
+
|Compression
−
|Union-find algorithm
+
|Huffman coding, tries
−
|Drozdek 8.4.1<br>
+
|Drozdek 11-11.2 (skip 11.2.1)
−
[http://en.wikipedia.org/wiki/Disjoint-set_data_structure Wikipedia entry], [http://courses.cs.washington.edu/courses/cse332/12su/slides/lecture15-mst-dsuf-handout.pdf UW slides] (first 5 pages of PDF)<br>
 
−
Optional: [https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf Princeton slides]
 
 
|
 
|
 
|-
 
|-
 
|19
 
|19
 
|Nov. 2
 
|Nov. 2
−
|Disjoint sets
+
|Finish compression; maps
−
|Smart union, path compression, maze generation application
 
−
|
 
 
|
 
|
 +
|Drozdek, 7.1.10
 +
|[https://drive.google.com/file/d/14kkP7Nz1_dFFHNvMwGixrryrkgbk1AyK/view?usp=sharing STL map example]
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Nov. 2/Nov. 3
 
|style="background:rgb(245, 222, 179)"|Nov. 2/Nov. 3
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab8 LAB #8]
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab8 LAB #8]
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 339: Line 338:
 
|style="background:rgb(102, 204, 255)"|20
 
|style="background:rgb(102, 204, 255)"|20
 
|Nov. 7
 
|Nov. 7
−
|Compression
+
|Graphs
−
|Huffman coding, tries
+
|Terminology, applications, representations: adjacency matrix, adjacency lists/sets
−
|Drozdek 11-11.2 (skip 11.2.1)
+
|Drozdek 8-8.1
 
|
 
|
 
|-
 
|-
 
|21
 
|21
 
|Nov. 9
 
|Nov. 9
−
|Finish compression; maps
+
|Graphs
−
|
+
|Traversals: depth-first, breadth-first
−
|Drozdek, 7.1.10
+
|Drozdek 8.2, 8.3 (stop after Dijkstra's)<br>
−
|[https://drive.google.com/file/d/14kkP7Nz1_dFFHNvMwGixrryrkgbk1AyK/view?usp=sharing STL map example]
+
Optional: [http://www.redblobgames.com/pathfinding/a-star/introduction.html Path-finding tutorial] (stop at "Heuristic search")
 +
|[https://docs.google.com/document/d/1J5Qv_r82AkWHVus5b53saw98tQzlVK8c12-F3CxtiGY/edit?usp=sharing BFS pseudocode]
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Nov. 9/Nov. 10
 
|style="background:rgb(245, 222, 179)"|Nov. 9/Nov. 10
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab9 LAB #9]
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab9 LAB #9]
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 360: Line 360:
 
|style="background:rgb(102, 204, 255)"|22
 
|style="background:rgb(102, 204, 255)"|22
 
|Nov. 14<br>''Withdraw deadline Nov. 13''
 
|Nov. 14<br>''Withdraw deadline Nov. 13''
−
|Hashing
+
|Graphs
−
|Hash function, probing (linear, quadratic, double hashing), chaining
+
|Dijkstra's shortest path algorithm, Kruskal's minimum spanning tree algorithm
−
|Drozdek 10-10.2.2
 
 
|
 
|
 +
|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Project Project assigned]
 
|-
 
|-
−
|23
+
|
 
|Nov. 16
 
|Nov. 16
−
|Hashing
+
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Instructor away''
−
|Deletions; applications to file integrity verification, password storage
+
|
−
|Drozdek 10.3<br>[http://unixwiz.net/techtips/iguide-crypto-hashes.html Illustrated Guide to Cryptographic Hashes]
+
|
−
|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Project Project assigned]<!--''Project #2 due''-->
+
|<!--[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Project Project assigned]--><!--''Project #2 due''-->
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|Nov. 16/Nov. 17
 
|style="background:rgb(245, 222, 179)"|Nov. 16/Nov. 17
−
|style="background:rgb(255, 102, 0)"|NO IN-PERSON LAB THIS WEEK -- BUT [http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab10 LAB #10] ASSIGNED
+
|style="background:rgb(255, 102, 0)"|NO LAB THIS WEEK
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 381: Line 381:
 
|style="background:rgb(102, 204, 255)"|
 
|style="background:rgb(102, 204, 255)"|
 
|Nov. 21
 
|Nov. 21
−
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Thanksgiving''
+
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Thanksgiving break''
 
|
 
|
 
|
 
|
 
|
 
|
−
|-
 
−
|style="background:rgb(245, 222, 179)"|
 
−
|style="background:rgb(245, 222, 179)"|Nov. 24
 
−
|style="background:rgb(255, 102, 0)"|NO LAB THIS WEEK
 
−
|style="background:rgb(245, 222, 179)"|
 
−
|style="background:rgb(245, 222, 179)"|
 
−
|style="background:rgb(245, 222, 179)"|
 
 
|-
 
|-
 
|
 
|
 
|Nov. 23
 
|Nov. 23
−
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Thanksgiving''
+
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Thanksgiving break''
 
|
 
|
 
|
 
|
 
|
 
|
 
|-
 
|-
−
|style="background:rgb(102, 204, 255)"|24
+
|style="background:rgb(245, 222, 179)"|
 +
|style="background:rgb(245, 222, 179)"|Nov. 23/Nov. 24
 +
|style="background:rgb(255, 102, 0)"|NO LAB THIS WEEK<br>''Thanksgiving break''
 +
|style="background:rgb(245, 222, 179)"|
 +
|style="background:rgb(245, 222, 179)"|
 +
|style="background:rgb(245, 222, 179)"|
 +
|-
 +
|style="background:rgb(102, 204, 255)"|23
 
|Nov. 28
 
|Nov. 28
−
|Graphs
+
|Hashing
−
|Terminology, applications, representations: adjacency matrix, adjacency lists
+
|Hash function, probing (linear, quadratic, double hashing), chaining
−
|Drozdek 8-8.1
+
|Drozdek 10-10.2.2<br>[https://cs.stackexchange.com/questions/11029/why-is-it-best-to-use-a-prime-number-as-a-mod-in-a-hashing-function Why choose a prime for hash table size?]
−
|[https://docs.google.com/presentation/d/1V1_q89gF3kX1lLTVltJl4sH2u87tERpkh6X2C5aXQSs/edit?usp=sharing slides]
+
|<!--[https://docs.google.com/presentation/d/1V1_q89gF3kX1lLTVltJl4sH2u87tERpkh6X2C5aXQSs/edit?usp=sharing slides]-->
 +
|-
 +
|24
 +
|Nov. 30
 +
|Hashing
 +
|Deletions; applications to file integrity verification, password storage
 +
|Drozdek 10.3<br>[http://unixwiz.net/techtips/iguide-crypto-hashes.html Illustrated Guide to Cryptographic Hashes]
 +
|<!--[https://docs.google.com/presentation/d/1Y3demwUDnWeAEpeIU23pdvSrfdo1sAtzRt_zrlVu_PI/edit?usp=sharing slides]-->
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Dec. 1
+
|style="background:rgb(245, 222, 179)"|Nov. 30/Dec. 1
−
|style="background:rgb(255, 102, 0)"|NO LAB THIS WEEK
+
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023_Lab10 LAB #10]
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
−
|25
+
|style="background:rgb(102, 204, 255)"|25
−
|Nov. 30
+
|Dec. 5
−
|Graphs
+
|Sorting
−
|Traversals: depth-first, breadth-first
+
|Insertion sort, mergesort
−
|Drozdek 8.2, 8.3 (stop after Dijkstra's)<br>
+
|Drozdek 9.1.1, 9.3.4<br>
−
Optional: [http://www.redblobgames.com/pathfinding/a-star/introduction.html Path-finding tutorial] (stop at "Heuristic search")
+
Optional: [http://www.sorting-algorithms.com Sorting algorithms animated]
−
|[https://docs.google.com/presentation/d/1Y3demwUDnWeAEpeIU23pdvSrfdo1sAtzRt_zrlVu_PI/edit?usp=sharing slides]
+
|
 
|-
 
|-
−
|style="background:rgb(102, 204, 255)"|26
+
|26
−
|Dec. 5
+
|Dec. 7
−
|Graphs
+
|Sorting
−
|Shortest path: Dijkstra's algorithm
+
|Actually less sorting
 
|
 
|
 
|
 
|
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Dec. 8
+
|style="background:rgb(245, 222, 179)"|Dec. 7/Dec. 8
 
|style="background:rgb(255, 102, 0)"|NO LAB THIS WEEK
 
|style="background:rgb(255, 102, 0)"|NO LAB THIS WEEK
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
Line 436: Line 443:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
−
|27
 
−
|Dec. 7
 
−
|Sorting (abbreviated)
 
−
|Insertion sort, mergesort
 
−
|Drozdek 9.1.1, 9.3.4<br>
 
−
Optional: [http://www.sorting-algorithms.com Sorting algorithms animated]
 
 
|
 
|
−
|-
 
−
|28
 
 
|
 
|
 
|Final review on YouTube
 
|Final review on YouTube
 
|
 
|
−
|[https://docs.google.com/presentation/d/1eTXi-o6tkSFXhBPzU0S_BFHX3J8b0raZf0iL40SDZaw/edit?usp=sharing Final review slides]<br>[https://drive.google.com/file/d/1visePCtxvwxFJv7Yd3ILeqFxyCEGII4Y/view?usp=sharing Post-midterm lecture notes]
+
|<!--<br>[https://drive.google.com/file/d/1visePCtxvwxFJv7Yd3ILeqFxyCEGII4Y/view?usp=sharing Post-midterm lecture notes]-->
−
|[https://youtu.be/7u_zbb8fT6E recording] (with solutions to 2010 final linked below)<br>[http://nameless.cis.udel.edu/class_data/220_f2014/cisc220_f2010_final.pdf 2010 final] (ignore Q4 and Q5, but see Q2 on [http://nameless.cis.udel.edu/class_data/220_f2014/220_2010_midterm.pdf 2010 midterm])
+
|[https://docs.google.com/presentation/d/12Rtz_u6-lzD5NCi3toBN7D0VtZYnttR1WXC4tus14Q8/edit?usp=sharing Final review slides]<br>[https://youtu.be/7u_zbb8fT6E Review recording] -- start at 4:17 (with solutions to 2010 final linked below)<br>[http://nameless.cis.udel.edu/class_data/220_f2014/cisc220_f2010_final.pdf 2010 final] (ignore Q4 and Q5, but see Q2 on [http://nameless.cis.udel.edu/class_data/220_f2014/220_2010_midterm.pdf 2010 midterm])
 
|-
 
|-
 
|
 
|
−
|Dec. 12 -- this is past the end of classes
+
|Dec. 11-12  
 
|Final project demos  
 
|Final project demos  
 
|
 
|
Line 458: Line 457:
 
|''Project due''
 
|''Project due''
 
|-
 
|-
−
|style="background:rgb(102, 204, 255)"|
+
|
−
|Dec. 13-17
+
|Dec. 14<br>11:30 am - 1:30 pm
 
|FINAL EXAM
 
|FINAL EXAM
−
|Time and location???
+
|Gore 219 (this room!)
 
|
 
|
 
|
 
|
 
|}
 
|}

Latest revision as of 14:40, 8 December 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-4 pm in Smith 211
URL

http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2023

TAs
  • Benita Abraham, E-mail: beniabra@udel.edu, Friday lab, office hours Tuesdays 4-5 pm in Smith 203
  • Connor Nagle, E-mail: cnagle@udel.edu, Thursday lab, office hours Tuesdays 3-4 pm in Smith 203
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 the beginning of class each Thursday before the next lab. All written answers must be in PDF form. Attendance at labs is expected if you have not yet submitted--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 (Oct. 19)
  • 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, 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
2023-2024 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.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

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.com tutorial: Classes I & II, Special Members

cplusplus_2a.tar
Simple C++ class creation exercises with solutions
4 Sep. 7 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. 12

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. 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
8 Sep. 21 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. 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)
10 Sep. 28 Trees Deletions, findMin(), findMax() in binary search trees; lab #5
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
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.7-6.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.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. 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

2021 midterm

15 Oct. 19 MIDTERM
Oct. 19/Oct. 20 NO LAB THIS WEEK
16 Oct. 24
 Disjoint sets Equivalence relations, classes; union-find 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 11-11.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 8-8.1
21 Nov. 9 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. 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 10-10.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. 11-12 Final project demos Project due
Dec. 14
11:30 am - 1:30 pm 		FINAL EXAM Gore 219 (this room!)
Retrieved from "http://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2023&oldid=3360"