CISC220 F2014
Course information
Description  CISC 220  Data Structures Comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation. Topics include recursion, stacks, queues, lists, heaps, hash tables, search trees, sorting, and graphs. 
Requirements  This is a course for undergraduates who have obstained a grade of C or better in CISC 181, and have taken or are currently taking MATH 210 or 241. 
Instructor  Christopher Rasmussen Email: cer@cis.udel.edu Office: Smith 446 Office hours: Mondays, 24 pm 
URL 
Full: http://nameless.cis.udel.edu/class_wiki/index.php/CISC220_F2014 
TAs 

Schedule  Lectures are Tuesdays and Thursdays in Memorial 111, all labs are Fridays in Spencer 010 (basement). In the schedule below note that there is NOT a lab every Friday

Grading 
Your labs and programming projects are due by midnight of the deadline day (with a small grace period afterward). All should be submitted directly to Sakaiemail submissions will not be accepted. A late homework is a 0 without a valid prior excuse. To give you a little flexibility, you have 6 "late days" to use over the semester to extend the deadline by one day each without penalty. No more than two late days may be used per assignment. Late days will automatically be subtracted, but as a courtesy please notify the instructor and TA in an email of your intention to use them before the deadline. Students can discuss problems with one another in general terms, but must work independently on all assignments. This also applies to online and printed resources: you may consult them as references (as long as you cite them), but the words you turn in must be yours alone. Any quoting must be clear and appropriately cited. The University's policies on academic dishonesty are set forth in the student code of conduct here. For the overall course grade, a preliminary absolute mark will be assigned to each student based on the percentage of the total possible points they earn according to the standard formula: A = 90100, B = 8090, C = 7080, etc., with +'s and 's given for the upper and lower third of each range, respectively. Based on the distribution of preliminary grades for all students (i.e., "the curve"), the instructor may increase these grades monotonically to calculate final grades. This means that your final grade can't be lower than your preliminary grade, and your final grade won't be higher than that of anyone who had a higher preliminary grade. I will try to keep you informed about your standing throughout the semester. If you have any questions about grading or expectations at any time, please feel free to ask me. 
Textbook 
Data Structures and Algorithms in C++ (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:
Code examples from the book can be downloaded here 
Setup instructions  All example code and template code for this course has been developed and tested on a Linux system. To do labs and programming projects, you should have access to one as well for coding, compiling, and debugging. Options:
After Ubuntu is installed, you need to make sure there's a C++ compiler and a text editor or integrated development environment (IDE) as well:
Further links for help in Unix:

Discussion/questions  We will be using Piazza as a forum for questions about labs, homeworks, exams, and any other course topic. Rather than sending email 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.

UD Capture  Capture of lectures started on Sep. 18. Links to the recordings for each section are here (login required): 
Schedule
Note: The blue squares in the "#" column below indicate Tuesdays
20142015 UD academic calendar
#  Date  Topic  Notes  Readings  Links 

1  Aug. 26  Introduction  ADTs, C++ basics: syntax, pointers, arrays, I/O, random numbers  Drozdek 1.11.3 C++ for Java programmers cheat sheets: [1], [2] 

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

4  Sep. 4  C++ review  Function & class templates, STL  Drozdek 1.71.8 
mystring_final 
Sep. 5  LAB #2  
5  Sep. 9 Register/add deadline 
Stacks  ADT (including STL) and applications  Drozdek 44.1  template_test, 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  array_stack, array_queue 
Sep. 12  LAB #3  
Sep. 16  NO LECTURE TODAY Instructor away 

7  Sep. 18  Queues, deques, and lists  Circular arrays for queues, singly and doublylinked lists for stacks and queues  Drozdek 33.2, 3.7, 3.8, 4.2, 4.4, 4.5  Project #1 
Sep. 19  LAB #4  
8  Sep. 23  Trees  Terminology; representation in general case; pre and postorder traversals; binary trees  Drozdek 66.2, 6.46.4.2  
9  Sep. 25  Trees  Binary trees for arithmetic expressions; inorder traversals; binary search trees  Drozdek 6.3, 6.56.6 (skip 6.6.1), 6.12 (expression trees)  
Sep. 26  NO LAB THIS WEEK  
10  Sep. 30  Algorithm analysis  BigO notation and common complexity classes  Drozdek 22.3, 2.52.6  
11  Oct. 2  Finish algorithm analysis  Analyzing code to obtain bigO estimates  Drozdek 2.7  Project #1 due 
Oct. 3  LAB #5  Lab #5 solutions to 2.11.7, 2.11.8, and 2.11.10  
12  Oct. 7  Balanced binary trees  AVL trees  Drozdek 6.76.7.2 (skip 6.7.1)  Rotation applet 
13  Oct. 9  Balanced binary trees  AVL trees  Drozdek 6.76.7.2 (skip 6.7.1)  
Oct. 10  NO LAB THIS WEEK  
14  Oct. 14  Midterm review  Midterm review slides  2010 midterm (ignore questions 2 and 6)  
15  Oct. 16  MIDTERM  
Oct. 17  LAB #6  
16  Oct. 21 Withdraw deadline 
Priority queues  ADT, heap implementation  Drozdek 4.3, 4.6, 6.9  
17  Oct. 23  Priority queues  Finish heap details  
Oct. 24  LAB #7  
18  Oct. 28  Disjoint sets  Unionfind algorithm  Drozdek 8.4.1 Wikipedia entry, UW slides (first 5 pages of PDF) 

19  Oct. 30  Disjoint sets  Smart union, path compression, maze generation application  
Oct. 31  NO LAB THIS WEEK  Project #2  
Nov. 4  NO CLASS Election Day 

20  Nov. 6  Compression  Huffman coding  Drozdek 1111.2 (skip 11.2.1)  
Nov. 7  NO LAB THIS WEEK  
21  Nov. 11  Hashing  Hash function, probing (linear, quadratic, double hashing), chaining  Drozdek 1010.2.2  
22  Nov. 13  Hashing  Deletions; applications to file integrity verification, password storage  Drozdek 10.3 Illustrated Guide to Cryptographic Hashes 
Project #2 due 
Nov. 14  LAB #8  
23  Nov. 18  Graphs  Terminology, applications, representations: adjacency matrix, adjacency lists; minimum spanning tree with unionfind  Drozdek 88.1, 8.5 (Kruskal's only)  
24  Nov. 20  Graphs  Traversals: depthfirst, breadthfirst; shortest path: Dijkstra's algorithm  Drozdek 8.2, 8.3 (stop after Dijkstra's) Optional: Pathfinding tutorial (stop at "Heuristic search") 

Nov. 21  NO LAB THIS WEEK  
25  Nov. 25  Sorting  Selection/insertion sorts, start mergesort  Drozdek 99.1.2, 9.3.2  
Nov. 27  NO LECTURE TODAY Thanksgiving 

Nov. 28  NO LAB THIS WEEK  
26  Dec. 2 Last lecture 
Sorting  Mergesort, quicksort  Drozdek 9.3.3, 9.3.4 Optional: Sorting algorithms animated 

Dec. 4  
Dec. 5  NO LAB THIS WEEK  
???  Final review  Final review slides  2010 final (ignore question 4, but see question 2 on 2010 midterm)  
Dec. 8  FINAL EXAM  3:305:30 pm (both sections) Smith 130 