Difference between revisions of "CISC220 F2023"

From class_wiki
Jump to: navigation, search
(→‎Course information)
Line 5: Line 5:
 
|-
 
|-
 
|valign="top"|'''Description'''
 
|valign="top"|'''Description'''
−
|CISC 220-080 -- Data Structures (Honors)<br>
+
|CISC 220 -- Data Structures (Honors)<br>
 
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.
 
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.
 
|-
 
|-
 
|valign="top"|'''Requirements'''
 
|valign="top"|'''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 MATH 210 or 241.   
+
|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.   
 
|-
 
|-
 
|valign="top"|'''Instructor'''
 
|valign="top"|'''Instructor'''
−
|Christopher Rasmussen<br>E-mail: cer@cis.udel.edu<br>Office: Smith 446<br>Office hours: ??, ?? pm  
+
|Christopher Rasmussen<br>E-mail: cer@cis.udel.edu<br>Office: Smith 446<br>Office hours: Wednesdays, 2:30-4:30 pm  
 +
|-
 +
|valign="top"|'''URL'''
 +
|
 +
Full: http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021<br>
 
|-
 
|-
 
|valign="top"|'''TA'''
 
|valign="top"|'''TA'''
 
|
 
|
−
* ??, E-mail: ??, office hours: ?? pm on ?? in Smith ??
+
Emma Adelmann, E-mail: eadel@udel.edu, office hours: 5-6 pm on Mondays, 1-2 pm on Thursdays in Smith 102A
 
|-
 
|-
 
|valign="top"|'''Schedule'''
 
|valign="top"|'''Schedule'''
−
|Lectures are in ???, labs in ???.  In the schedule below note that there is NOT a lab every week
+
|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
 
−
* Lab times: (080L) Thursdays 2:20 to 3:15 pm, (081L) Fridays 3:00 to 3:55 pm
 
 
|-
 
|-
 
|valign="top"|'''Grading'''
 
|valign="top"|'''Grading'''
 
|
 
|
−
* 40%  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 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
−
* 20% Programming projects (10% each).  These are larger two-week projects.   
+
* 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.   
−
* 40%  Quizzes (5% each)
+
* 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.
+
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 [http://www.udel.edu/stuguide/22-23/code.html here].  
+
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 40: Line 43:
 
|valign="top"|'''Textbook'''
 
|valign="top"|'''Textbook'''
 
|
 
|
−
''Data Structures and Algorithms in C++'' (3rd ed. or 4th ed.), Adam Drozdek.  Will be at the textbook store Aug. 29, but I don't recommend buying it unless you can get a cheap used version.  Other options:
+
''Data Structures and Algorithms in C++'' (4th ed.), Adam Drozdek.  It is NOT at the textbook store, don't look for it there
−
* 3rd edition [http://www.amazon.com/Data-Structures-Algorithms-Adam-Drozdek/dp/0534491820/ref=sr_1_2_rfb_1_har Amazon] $53.49 e-book rental, $25.25 hardcover rental
+
* 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
−
* 4th edition: [http://www.amazon.com/Data-Structures-Algorithms-Adam-Drozdek/dp/1133608426/ref=dp_ob_title_bk Amazon] $67.49 e-book rental, $44.93 hardcover rental
+
* 4th edition: [http://www.cengagebrain.com/shop/ISBN/9781133608424?cid=APL1 Publisher (Cengage)]  ~$35 e-book rental as of Aug. 30
−
* 4th edition: [http://www.cengagebrain.com/shop/ISBN/9781133608424?cid=APL1 Publisher (Cengage)]  $67.49 e-book rental, $44.99 hardcover rental
 
  
 
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'''
 +
|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 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:
 +
* Must wear a cloth mask that covers your nose and mouth
 +
* Must not eat or drink in class
 +
* 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.
 +
<!--
 
|-
 
|-
 
|valign="top"|'''Set-up instructions'''
 
|valign="top"|'''Set-up instructions'''
Line 74: Line 88:
 
** To untar a file named ''foo.tar'' from the command line: ''tar -xvf foo.tar'' while you are in the same directory as foo.tar
 
** To untar a file named ''foo.tar'' from the command line: ''tar -xvf foo.tar'' while you are in the same directory as foo.tar
 
** To tar a directory named ''foo'' into a a tarfile named ''foo.tar'': ''tar -cvf foo.tar foo'' while you are at the directory level ''ABOVE'' foo.
 
** To tar a directory named ''foo'' into a a tarfile named ''foo.tar'': ''tar -cvf foo.tar foo'' while you are at the directory level ''ABOVE'' foo.
 +
-->
 +
<!--|-
 +
|valign="top"|'''Discussion/questions'''
 +
|We will be using [https://piazza.com/ Piazza] as a forum for questions about labs, homeworks, exams, and any other course topic.  Rather than sending e-mail to a TA or the professor, post your question there so that everyone else can see the answer, and other students can contribute their knowledge. 
 +
* To enroll: http://piazza.com/udel/fall2014/cisc220
 +
* After you enroll: http://piazza.com/udel/fall2014/cisc220/home
 +
-->
 +
<!--
 
|-
 
|-
 
|valign="top"|'''UD Capture'''
 
|valign="top"|'''UD Capture'''
Line 79: Line 101:
 
* [http://udcapture.udel.edu/2014f/cisc220-010/ 010 (9:30 am lecture)]
 
* [http://udcapture.udel.edu/2014f/cisc220-010/ 010 (9:30 am lecture)]
 
* [http://udcapture.udel.edu/2014f/cisc220-011/ 011 (11 am lecture)]
 
* [http://udcapture.udel.edu/2014f/cisc220-011/ 011 (11 am lecture)]
−
+
-->
 
|}
 
|}
  
 
==Schedule==
 
==Schedule==
  
−
''Note'': The blue squares in the "#" column below indicate Tuesdays
+
''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
 
<br>
 
<br>
−
[http://www.udel.edu/registrar/cal/calendars/2014-2015.pdf 2014-2015 UD academic calendar]
+
[https://www1.udel.edu/registrar/cal/calendars/2021-2022.pdf 2021-2022 UD academic calendar]
 
<br><br>
 
<br><br>
  
Line 98: Line 120:
 
|-
 
|-
 
|style="background:rgb(102, 204, 255)"|1
 
|style="background:rgb(102, 204, 255)"|1
−
|Aug. 26
+
|Aug. 31
 
|Introduction  
 
|Introduction  
−
|ADTs, C++ basics: syntax, pointers, arrays, I/O, random numbers
+
|Big four topics on data structures and algorithms: abstraction, implementation, analysis, and applications
 
|Drozdek 1.1-1.3<br>
 
|Drozdek 1.1-1.3<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://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]-->
−
|-
 
−
|2
 
−
|Aug. 28
 
−
|C++ review
 
−
|More on pointers, new/delete, static vs. dynamic memory allocation
 
−
|
 
−
|<!--[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. 29
+
|style="background:rgb(245, 222, 179)"|Sep. 1
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Lab1 LAB #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)"|
 
|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)"|
 +
|-
 +
|2
 +
|Sep. 2
 +
|C++ review
 +
|C++ basics: differences with C, arrays, I/O, random numbers, new/delete, static vs. dynamic memory allocation
 +
|[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://nameless.cis.udel.edu/class_data/220_f2014/code/cplusplus_2.tar intcell, intcellarray, big3]<br>-->
 
|-
 
|-
 
|style="background:rgb(102, 204, 255)"|3
 
|style="background:rgb(102, 204, 255)"|3
−
|Sep. 2
+
|Sep. 7
 
|C++ review
 
|C++ review
−
|Classes, destructors, constructors, assignments
+
|ADTs, classes, destructors, constructors, assignments
 
|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]
−
| <!--[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] <!--[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]-->
 +
|-
 +
|style="background:rgb(245, 222, 179)"|
 +
|style="background:rgb(245, 222, 179)"|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)"|
 +
|style="background:rgb(245, 222, 179)"|
 +
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
 
|4
 
|4
−
|Sep. 4
+
|Sep. 9
 
|C++ review  
 
|C++ review  
 
|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], [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/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)"|Sep. 5
 
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Lab2 LAB #2]
 
−
|style="background:rgb(245, 222, 179)"|
 
−
|style="background:rgb(245, 222, 179)"|
 
−
|style="background:rgb(245, 222, 179)"|
 
 
|-
 
|-
 
|style="background:rgb(102, 204, 255)"|5
 
|style="background:rgb(102, 204, 255)"|5
−
|Sep. 9<br>
+
|Sep. 14<br>
 
''Register/add deadline''<br>
 
''Register/add deadline''<br>
 
|Stacks
 
|Stacks
−
|ADT (including STL) and applications
+
|ADT (including STL) and applications, including stacks for postfix expression evaluation
 
|Drozdek 4-4.1
 
|Drozdek 4-4.1
−
|[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]
+
|
−
|-
 
−
|6
 
−
|Sep. 11
 
−
|Stacks and queues
 
−
|Stacks for postfix expression evaluation; implementing stacks with linear arrays; queue ADT, applications, and linear array implementation 
 
−
|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-->
 
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Sep. 12
+
|style="background:rgb(245, 222, 179)"|Sep. 15
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Lab3 LAB #3]
+
|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)"|
 
|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)"|
+
|6
 
|Sep. 16
 
|Sep. 16
−
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Instructor away''
+
|Stacks and queues
−
|
+
|Implementing stacks with linear arrays; queue ADT, applications, and linear array implementation 
−
|
+
|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-->
 
|-
 
|-
−
|7
+
|style="background:rgb(102, 204, 255)"|7
−
|Sep. 18
+
|Sep. 21
 
|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
 
|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
−
|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Project1 Project #1]
+
|[https://drive.google.com/file/d/1Pany4gsFBmGp41xOi_A1O_wHc7bg_hmo/view?usp=sharing sll_stack]
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Sep. 19
+
|style="background:rgb(245, 222, 179)"|Sep. 22
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Lab4 LAB #4]
+
|style="background:rgb(255, 102, 0)"|NO IN-PERSON LAB THIS WEEK -- BUT [http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab4 LAB #4] ASSIGNED
 
|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)"|8
+
|8
 
|Sep. 23
 
|Sep. 23
 
|Trees
 
|Trees
Line 193: Line 207:
 
|
 
|
 
|-
 
|-
−
|9
+
|style="background:rgb(102, 204, 255)"|9
−
|Sep. 25
+
|Sep. 28
−
|Trees
+
|style="background:rgb(255, 102, 0)"|LECTURE ON YOUTUBE<br>Trees
 
|Binary trees for arithmetic expressions; in-order traversals; binary search 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)
 
|Drozdek 6.3, 6.5-6.6 (skip 6.6.1), 6.12 (expression trees)
−
|
+
|[https://youtu.be/5CWhQ4Pjs9U recording]<!--[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Project1 Project #1]-->
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Sep. 26
+
|style="background:rgb(245, 222, 179)"|Sep. 29
−
|style="background:rgb(255, 102, 0)"|NO LAB THIS WEEK
+
|style="background:rgb(255, 102, 0)"|NO IN-PERSON LAB THIS WEEK -- BUT [http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_Lab5 LAB #5] ASSIGNED
 
|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)"|
 +
|-
 +
|
 +
|Sep. 30
 +
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Instructor away''
 +
|
 +
|
 +
|
 
|-
 
|-
 
|style="background:rgb(102, 204, 255)"|10
 
|style="background:rgb(102, 204, 255)"|10
−
|Sep. 30
+
|Oct. 5
 
|Algorithm analysis
 
|Algorithm analysis
−
|Big-O notation and common complexity classes
+
|Big-O notation and common complexity classes; analyzing code to obtain big-O estimates
−
|Drozdek 2-2.3, 2.5-2.6
+
|Drozdek 2-2.3, 2.5-2.6, 2.7
 
|
 
|
−
|-
 
−
|11
 
−
|Oct. 2
 
−
|Finish algorithm analysis
 
−
|Analyzing code to obtain big-O estimates
 
−
|Drozdek 2.7
 
−
|''Project #1 due''
 
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Oct. 3
+
|style="background:rgb(245, 222, 179)"|Oct. 6
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Lab5 LAB #5]
+
|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)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|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
+
|11
 
|Oct. 7
 
|Oct. 7
 
|Balanced binary trees
 
|Balanced binary trees
−
|AVL trees
+
|AVL trees: definition, balance notation, rotations
−
|Drozdek 6.7-6.7.2 (skip 6.7.1)
+
|Drozdek 6.7-6.7.2 (skip 6.7.1)  
 
|[http://research.cs.queensu.ca/home/jstewart/applets/bst/bst-rotation.html Rotation applet]
 
|[http://research.cs.queensu.ca/home/jstewart/applets/bst/bst-rotation.html Rotation applet]
 
|-
 
|-
−
|13
+
|style="background:rgb(102, 204, 255)"|12
−
|Oct. 9
+
|Oct. 12
−
|Balanced binary trees
+
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Class cancelled''
−
|AVL trees
+
|
−
|Drozdek 6.7-6.7.2 (skip 6.7.1)
+
|
 
|
 
|
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Oct. 10
+
|style="background:rgb(245, 222, 179)"|Oct. 13
−
|style="background:rgb(255, 102, 0)"|NO LAB THIS WEEK
+
|style="background:rgb(255, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021_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)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 +
|-
 +
|13
 +
|Oct. 14
 +
|Balanced binary trees
 +
|AVL trees: applying rotations to restore balance property
 +
|Drozdek 6.7-6.7.2 (skip 6.7.1)
 +
|UD Capture is audio only today :(
 
|-
 
|-
 
|style="background:rgb(102, 204, 255)"|14
 
|style="background:rgb(102, 204, 255)"|14
−
|Oct. 14
+
|Oct. 19
 
|Midterm review
 
|Midterm review
 
|
 
|
−
|[http://nameless.cis.udel.edu/class_data/220_f2014/CISC220_Midterm_Review.pdf Midterm review slides]
+
|[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]
 
|[http://nameless.cis.udel.edu/class_data/220_f2014/220_2010_midterm.pdf 2010 midterm] (ignore questions 2 and 6)
 
|[http://nameless.cis.udel.edu/class_data/220_f2014/220_2010_midterm.pdf 2010 midterm] (ignore questions 2 and 6)
 +
|-
 +
|style="background:rgb(245, 222, 179)"|
 +
|style="background:rgb(245, 222, 179)"|Oct. 20
 +
|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)"|
 
|-
 
|-
 
|15
 
|15
−
|Oct. 16
+
|Oct. 21
 
|MIDTERM
 
|MIDTERM
 
|
 
|
 
|
 
|
 
|
 
|
−
|-
 
−
|style="background:rgb(245, 222, 179)"|
 
−
|style="background:rgb(245, 222, 179)"|Oct. 17
 
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Lab6 LAB #6]
 
−
|style="background:rgb(245, 222, 179)"|
 
−
|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)"|16
−
|Oct. 21<br>
+
|Oct. 26<br>
 
''Withdraw deadline''
 
''Withdraw deadline''
 
|Priority queues  
 
|Priority queues  
 
|ADT, heap implementation
 
|ADT, heap implementation
 
|Drozdek 4.3, 4.6, 6.9
 
|Drozdek 4.3, 4.6, 6.9
−
|
+
|[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)"|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)"|
 +
|style="background:rgb(245, 222, 179)"|
 +
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
 
|17
 
|17
−
|Oct. 23
+
|Oct. 28
 
|Priority queues
 
|Priority queues
 
|Finish heap details
 
|Finish heap details
 
|
 
|
 
|
 
|
−
|-
 
−
|style="background:rgb(245, 222, 179)"|
 
−
|style="background:rgb(245, 222, 179)"|Oct. 24
 
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Lab7 LAB #7]
 
−
|style="background:rgb(245, 222, 179)"|
 
−
|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)"|18
−
|Oct. 28
+
|Nov. 2
 
|Disjoint sets
 
|Disjoint sets
 
|Union-find algorithm
 
|Union-find algorithm
Line 301: Line 323:
 
|
 
|
 
|-
 
|-
−
|19
 
−
|Oct. 30
 
−
|Disjoint sets
 
−
|Smart union, path compression, maze generation application
 
−
|
 
−
|
 
−
|-
 
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Oct. 31
+
|style="background:rgb(245, 222, 179)"|Nov. 3
−
|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_F2021_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)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Project2 Project #2]
 
 
|-
 
|-
−
|style="background:rgb(102, 204, 255)"|
+
|19
 
|Nov. 4
 
|Nov. 4
−
|style="background:rgb(255, 102, 0)"|NO CLASS<br>''Election Day''
+
|Disjoint sets
−
|
+
|Smart union, path compression, maze generation application
 
|
 
|
 
|
 
|
 
|-
 
|-
−
|20
+
|style="background:rgb(102, 204, 255)"|20
−
|Nov. 6
+
|Nov. 9
 
|Compression
 
|Compression
−
|Huffman coding
+
|Huffman coding, tries
 
|Drozdek 11-11.2 (skip 11.2.1)
 
|Drozdek 11-11.2 (skip 11.2.1)
 
|
 
|
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Nov. 7
+
|style="background:rgb(245, 222, 179)"|Nov. 10
−
|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_F2021_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)"|
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
−
|style="background:rgb(102, 204, 255)"|21
+
|21
 
|Nov. 11
 
|Nov. 11
 +
|Finish compression; maps
 +
|
 +
|Drozdek, 7.1.10
 +
|[https://drive.google.com/file/d/14kkP7Nz1_dFFHNvMwGixrryrkgbk1AyK/view?usp=sharing STL map example]
 +
|-
 +
|style="background:rgb(102, 204, 255)"|22
 +
|Nov. 16
 
|Hashing
 
|Hashing
 
|Hash function, probing (linear, quadratic, double hashing), chaining
 
|Hash function, probing (linear, quadratic, double hashing), chaining
 
|Drozdek 10-10.2.2
 
|Drozdek 10-10.2.2
 
|
 
|
−
|-
 
−
|22
 
−
|Nov. 13
 
−
|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]
 
−
|''Project #2 due''
 
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Nov. 14
+
|style="background:rgb(245, 222, 179)"|Nov. 17
−
|style="background:rgb(245, 222, 179)"|[http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014_Lab8 LAB #8]
+
|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(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)"|23
+
|23
 
|Nov. 18
 
|Nov. 18
−
|Graphs
+
|Hashing
−
|Terminology, applications, representations: adjacency matrix, adjacency lists; minimum spanning tree with union-find
+
|Deletions; applications to file integrity verification, password storage
−
|Drozdek 8-8.1, 8.5 (Kruskal's only)
+
|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''-->
 +
|-
 +
|style="background:rgb(102, 204, 255)"|
 +
|Nov. 23
 +
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Thanksgiving''
 +
|
 
|
 
|
−
|-
 
−
|24
 
−
|Nov. 20
 
−
|Graphs
 
−
|Traversals: depth-first, breadth-first; shortest path: Dijkstra's algorithm
 
−
|Drozdek 8.2, 8.3 (stop after Dijkstra's)<br>
 
−
Optional: [http://www.redblobgames.com/pathfinding/a-star/introduction.html Path-finding tutorial] (stop at "Heuristic search")
 
 
|
 
|
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Nov. 21
+
|style="background:rgb(245, 222, 179)"|Nov. 24
 
|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 379: Line 393:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
−
|style="background:rgb(102, 204, 255)"|25
+
|
 
|Nov. 25
 
|Nov. 25
−
|Sorting
 
−
|Selection/insertion sorts, start mergesort
 
−
|Drozdek 9-9.1.2, 9.3.2
 
−
|
 
−
|-
 
−
|
 
−
|Nov. 27
 
 
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Thanksgiving''
 
|style="background:rgb(255, 102, 0)"|NO LECTURE TODAY<br>''Thanksgiving''
 
|
 
|
 
|
 
|
 
|
 
|
 +
|-
 +
|style="background:rgb(102, 204, 255)"|24
 +
|Nov. 30
 +
|Graphs
 +
|Terminology, applications, representations: adjacency matrix, adjacency lists
 +
|Drozdek 8-8.1
 +
|[https://docs.google.com/presentation/d/1V1_q89gF3kX1lLTVltJl4sH2u87tERpkh6X2C5aXQSs/edit?usp=sharing slides]
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Nov. 28
+
|style="background:rgb(245, 222, 179)"|Dec. 1
 
|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)"|
 
|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
 +
|Dec. 2
 +
|Graphs
 +
|Traversals: depth-first, breadth-first
 +
|Drozdek 8.2, 8.3 (stop after Dijkstra's)<br>
 +
Optional: [http://www.redblobgames.com/pathfinding/a-star/introduction.html Path-finding tutorial] (stop at "Heuristic search")
 +
|[https://docs.google.com/presentation/d/1Y3demwUDnWeAEpeIU23pdvSrfdo1sAtzRt_zrlVu_PI/edit?usp=sharing slides]
 
|-
 
|-
 
|style="background:rgb(102, 204, 255)"|26
 
|style="background:rgb(102, 204, 255)"|26
−
|Dec. 2<br>''Last lecture''
+
|Dec. 7
−
|Sorting
+
|Graphs
−
|Mergesort, quicksort
+
|Shortest path: Dijkstra's algorithm
−
|Drozdek 9.3.3, 9.3.4<br>
 
−
Optional: [http://www.sorting-algorithms.com Sorting algorithms animated]
 
−
|
 
−
|-
 
−
|
 
−
|Dec. 4
 
−
|
 
−
|
 
 
|
 
|
 
|
 
|
 
|-
 
|-
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
−
|style="background:rgb(245, 222, 179)"|Dec. 5
+
|style="background:rgb(245, 222, 179)"|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 422: Line 436:
 
|style="background:rgb(245, 222, 179)"|
 
|style="background:rgb(245, 222, 179)"|
 
|-
 
|-
 +
|27
 +
|Dec. 9
 +
|Sorting (abbreviated)
 +
|Insertion sort, mergesort
 +
|Drozdek 9.1.1, 9.3.4<br>
 +
Optional: [http://www.sorting-algorithms.com Sorting algorithms animated]
 
|
 
|
−
|???
+
|-
−
|Final review
+
|28
 
|
 
|
−
|[http://nameless.cis.udel.edu/class_data/220_f2014/CISC_220_Final_Review.pdf Final review slides]
+
|Final review on YouTube
−
|[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])
+
|
 +
|[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]
 +
|[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])
 
|-
 
|-
 
|
 
|
−
|Dec. 8
+
|Dec. 10
 +
|Final project demos
 +
|
 +
|
 +
|''Project due''
 +
|-
 +
|style="background:rgb(102, 204, 255)"|
 +
|Dec. 14
 
|FINAL EXAM
 
|FINAL EXAM
−
|3:30-5:30 pm (both sections)<br>[http://maps.rdms.udel.edu/map/index.php?id=NW34 Smith 130]
+
|''10:30 am-12:30 pm (ISE305)''
 
|
 
|
 
|
 
|
 
|}
 
|}

Revision as of 12:12, 14 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_F2021

TA

Emma Adelmann, E-mail: eadel@udel.edu, office hours: 5-6 pm on Mondays, 1-2 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
  • 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 ~$35 e-book rental, ~$44 hardcover rental as of Aug. 30
  • 4th edition: Publisher (Cengage) ~$35 e-book rental as of Aug. 30

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

  • Must wear a cloth mask that covers your nose and mouth
  • Must not eat or drink in class
  • 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.

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

cplusplus_2a.tar
Sep. 8 LAB #2
4 Sep. 9 C++ review Function & class templates, STL Drozdek 1.7-1.8

cplusplus.com tutorial: Classes II, STL reference

template_test, anythingcell
5 Sep. 14

Register/add deadline

 Stacks ADT (including STL) and applications, including stacks for postfix expression evaluation Drozdek 4-4.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 doubly-linked lists for stacks and queues Drozdek 3-3.2, 3.7, 3.8, 4.2, 4.4, 4.5 sll_stack
Sep. 22 NO IN-PERSON LAB THIS WEEK -- BUT LAB #4 ASSIGNED
8 Sep. 23 Trees Terminology; representation in general case; pre- and post-order traversals; binary trees Drozdek 6-6.2, 6.4-6.4.2
9 Sep. 28 LECTURE ON YOUTUBE
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) recording
Sep. 29 NO IN-PERSON LAB THIS WEEK -- BUT LAB #5 ASSIGNED
Sep. 30 NO LECTURE TODAY
Instructor away
10 Oct. 5 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. 6 LAB #6
11 Oct. 7 Balanced binary trees AVL trees: definition, balance notation, rotations Drozdek 6.7-6.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.7-6.7.2 (skip 6.7.1) UD Capture is audio only today :(
14 Oct. 19 Midterm review Midterm review slides

Post-C++ lecture notes

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 Union-find algorithm Drozdek 8.4.1

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

Nov. 3 LAB #8
19 Nov. 4 Disjoint sets Smart union, path compression, maze generation application
20 Nov. 9 Compression Huffman coding, tries Drozdek 11-11.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 10-10.2.2
Nov. 17 NO IN-PERSON 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 Drozdek 8-8.1 slides
Dec. 1 NO LAB THIS WEEK
25 Dec. 2 Graphs Traversals: depth-first, breadth-first Drozdek 8.2, 8.3 (stop after Dijkstra's)

Optional: Path-finding tutorial (stop at "Heuristic search")

slides
26 Dec. 7 Graphs Shortest path: Dijkstra's algorithm
Dec. 8 NO LAB THIS WEEK
27 Dec. 9 Sorting (abbreviated) Insertion sort, mergesort Drozdek 9.1.1, 9.3.4

Optional: Sorting algorithms animated

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. 10 Final project demos Project due
Dec. 14 FINAL EXAM 10:30 am-12:30 pm (ISE305)
Retrieved from "http://nameless.cis.udel.edu/class_wiki/index.php?title=CISC220_F2023&oldid=2815"