CISC220 F2021

From class_wiki
Revision as of 10:43, 30 August 2021 by Cer (talk | contribs) (Schedule)
Jump to: navigation, search

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 MATH 210 or 241.
Instructor Christopher Rasmussen
E-mail: cer@cis.udel.edu
Office: Smith 446
Office hours: Mondays, 2-4 pm
URL

Full: http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2021

TA

Emma Adelmann, E-mail: eadel@udel.edu, office hours: ??-?? am/pm on ?? in Smith 201?

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
  • 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
  • 20% Programming projects (10% each). These are larger two-week projects.
  • 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 $67.49 e-book rental, $44.93 hardcover rental
  • 4th edition: Publisher (Cengage) $67.49 e-book rental, $44.99 hardcover rental

Code examples from the book can be downloaded here

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 ADTs, C++ basics: syntax, pointers, arrays, I/O, random numbers Drozdek 1.1-1.3

C++ for Java programmers cheat sheets: [1], [2]
cplusplus.com tutorial: Basics, Program Structure, Compound Data Types

2 Sep. 2 C++ review More on pointers, new/delete, static vs. dynamic memory allocation
Sep. 1 LAB #1
3 Sep. 7 C++ review Classes, destructors, constructors, assignments Drozdek 1.4 (skip 1.4.5)

cplusplus.com tutorial: Classes I & II, Special Members

4 Sep. 9 C++ review Function & class templates, STL Drozdek 1.7-1.8

cplusplus.com tutorial: Classes II, STL reference

mystring_final
Sep. 8 LAB #2
5 Sep. 14

Register/add deadline

Stacks ADT (including STL) and applications Drozdek 4-4.1 template_test, anythingcell
6 Sep. 16 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 array_stack, array_queue
Sep. 15 LAB #3
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
7 Sep. 23 Trees Terminology; representation in general case; pre- and post-order traversals; binary trees Drozdek 6-6.2, 6.4-6.4.2
Sep. 22 LAB #4
8 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) Project #1
9 Sep. 30 NO LECTURE TODAY
Instructor away
Sep. 29 NO LAB THIS WEEK
10 Oct. 5 Algorithm analysis Big-O notation and common complexity classes Drozdek 2-2.3, 2.5-2.6
11 Oct. 7 Finish algorithm analysis Analyzing code to obtain big-O estimates Drozdek 2.7 Project #1 due
Oct. 6 LAB #5 Lab #5 solutions to 2.11.7, 2.11.8, and 2.11.10
12 Oct. 12 Balanced binary trees AVL trees Drozdek 6.7-6.7.2 (skip 6.7.1) Rotation applet
13 Oct. 14 Balanced binary trees AVL trees Drozdek 6.7-6.7.2 (skip 6.7.1)
Oct. 13 NO LAB THIS WEEK
14 Oct. 19 Midterm review Midterm review slides 2010 midterm (ignore questions 2 and 6)
15 Oct. 21 MIDTERM
Oct. 20 LAB #6
16 Oct. 26

Withdraw deadline

Priority queues ADT, heap implementation Drozdek 4.3, 4.6, 6.9
17 Oct. 28 Priority queues Finish heap details
Oct. 27 LAB #7
18 Nov. 2 Disjoint sets Union-find algorithm Drozdek 8.4.1

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

19 Nov. 4 Disjoint sets Smart union, path compression, maze generation application
Nov. 3 NO LAB THIS WEEK Project #2
Nov. 9 Tries Drozdek, 7.2
20 Nov. 11 Compression Huffman coding Drozdek 11-11.2 (skip 11.2.1)
Nov. 10 NO LAB THIS WEEK
21 Nov. 16 Hashing Hash function, probing (linear, quadratic, double hashing), chaining Drozdek 10-10.2.2
22 Nov. 18 Hashing Deletions; applications to file integrity verification, password storage Drozdek 10.3
Illustrated Guide to Cryptographic Hashes
Project #2 due
Nov. 17 LAB #8
23 Nov. 23 NO LECTURE TODAY
Thanksgiving
24 Nov. 25 NO LECTURE TODAY
Thanksgiving
Nov. 24 NO LAB THIS WEEK
25 Nov. 30 Graphs Terminology, applications, representations: adjacency matrix, adjacency lists; minimum spanning tree with union-find Drozdek 8-8.1, 8.5 (Kruskal's only)
Dec. 2 Graphs Traversals: depth-first, breadth-first; shortest path: Dijkstra's algorithm Drozdek 8.2, 8.3 (stop after Dijkstra's)

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

Dec. 1 NO LAB THIS WEEK
26 Dec. 7 Sorting Selection/insertion sorts, start mergesort Drozdek 9-9.1.2, 9.3.2
Dec. 9 Sorting Mergesort, quicksort Drozdek 9.3.3, 9.3.4

Optional: Sorting algorithms animated

Dec. 8 NO LAB THIS WEEK
Dec. 13-18 Final review on YouTube
FINAL EXAM
Time and place TBD Final review slides 2010 final (ignore question 4, but see question 2 on 2010 midterm)