CISC220 F2023

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 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_F2014 Shortened: http://goo.gl/9EuTAv
TAs	Maria Ruiz Varela (MRV), E-mail: mruizv@udel.edu, office hours: 12-2 pm on Wednesdays in Smith 201 Narayanan Seshan (NS), E-mail: nseshan@udel.edu, office hours: 1-3 pm on Thursdays in Smith 201 (2-3 pm only on Sept. 4)
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 Section 010 lectures: 9:30 am to 10:45 am Section 011 lectures: 11 am to 12:15 pm Lab times (TA): 9:05 am (MRV), 10:10 am (MRV), 11:15 am (MRV), 12:20 pm (NS), 1:25 pm (NS), 2:30 pm (NS)
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 Sakai--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++ (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: 3rd edition Amazon $53.49 e-book rental, $25.25 hardcover rental 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
Set-up 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: Access UD compute machines remotely. hoek.eecis.udel.edu runs Linux and strauss.udel.edu runs SunOS. The latter typically requires some Makefile path changes. A very basic option for playing around, which is not enough for homeworks, is an online C++ shell. Try it! Run Linux on your own Windows/MacOS laptop/desktop. I recommend Ubuntu desktop (version 12.04 or 14.04). If you don't have a Linux distribution already, there are 3 standard approaches: Install Linux to a DVD or USB stick and run it "live" by booting your machine from it (details in Ubuntu install instructions). This may require fiddling with your BIOS boot order settings, but it offers the advantages of (a) not changing your hard drive at all, and (b) theoretically you can walk up to any machine and run Linux on it. Unfortunately the Spencer 010 machines will not boot from the USB port without an admin password, but a DVD should work. Add a boot-time Linux option (aka "dual-booting"). This is pretty easy and built into the Ubuntu installer (again, see Ubuntu install instructions). Usually I make a USB stick first to test that everything works on my machine (trackpad/mouse buttons, wifi, graphics drivers, and power button/lid closing are the most common issues with laptops), and then inside Ubuntu there is an option to install it to the hard drive permanently. Create a virtual machine, which lets you run Linux from within Windows or MacOS without rebooting. Performance is generally slower than the above options, but for CISC 220 it should be entirely acceptable. Here are two free options: VirtualBox. I found these instructions helpful when setting up VirtualBox for Ubuntu. If you have VirtualBox with Ubuntu left over from CPEG 202, I recommend doing a fresh install -- several students had problems trying to reuse this installation. If you are having trouble with low screen resolution, try this fix VMWare, an alternative if/when VirtualBox doesn't work for you 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: In Ubuntu, apt-get install g++ will install the compiler and related basic libraries gedit is Ubuntu's built-in text editor and is what will open if you double-click a code file in the file explorer. It has syntax highlighting and should work just fine. xemacs is my old-school text editor of choice. It has mouse-and-menu options like gedit, but also keyboard shortcuts to speed things up. apt-get install xemacs21 to get it, and untar this in your home directory to get one flavor of syntax highlighting. Here's a getting started guide Code::Blocks and Eclipse are cross-platform, full-featured IDEs for C++ and geany is an Ubuntu coding-oriented text editor with IDE features. I will not explain how to install or use them beyond what is written below, but feel free to try them if just a bare-bones text editor doesn't do it for you. Code::Blocks: Make a new C++ project of type "Console Application" and follow the wizard instructions to name it, choose a directory, etc. Once it's created, put the CISC220-supplied main.cpp and any .txt files into the project directory, overwriting the Code::Blocks-created main.cpp. To compile, choose "Build and run" from the "Build" menu. If the program expects command-line input (like the name of a file to read), go to the Project / Set Programs' Arguments menu and type the filename or whatever into the Program Arguments text box. Further links for help in Unix: To invoke the terminal (aka command line) in Ubuntu, click on the Ubuntu icon in the upper-left of the start bar to bring up the "dashboard". Type "terminal" in the search box and an icon for the terminal app will appear. Click this, or you can drag it to the start bar so it's always there. Once you are in the terminal, here is a tutorial on commands, but the key ones are: ls: List directory contents. This tells you what files and subdirectories are in the current directory. cd: Change directory. This is how you move around between directories/folders. cd all by itself takes you back to your home directory, cd <name of subdirectory> takes you down to a subdirectory of the one you're in, and cd .. takes you up to the next higher-level directory. tar/untar General instructions here. You can do both operations from the file explorer: right-click on a tar file and choose "Extract Here", or right-click on a directory and choose "Compress". 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.
Discussion/questions	We will be using 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
UD Capture	Capture of lectures started on Sep. 18. Links to the recordings for each section are here (login required): 010 (9:30 am lecture) 011 (11 am lecture)

Schedule

Note: The blue squares in the "#" column below indicate Tuesdays
2014-2015 UD academic calendar

#	Date	Topic	Notes	Readings	Links
1	Aug. 26	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	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) cplusplus.com tutorial: Classes I & II, Special Members
4	Sep. 4	C++ review	Function & class templates, STL	Drozdek 1.7-1.8 cplusplus.com tutorial: Classes II, STL reference	mystring_final
	Sep. 5	LAB #2
5	Sep. 9 Register/add deadline	Stacks	ADT (including STL) and applications	Drozdek 4-4.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 doubly-linked lists for stacks and queues	Drozdek 3-3.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 post-order traversals; binary trees	Drozdek 6-6.2, 6.4-6.4.2
9	Sep. 25	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)
	Sep. 26	NO LAB THIS WEEK
10	Sep. 30	Algorithm analysis	Big-O notation and common complexity classes	Drozdek 2-2.3, 2.5-2.6
11	Oct. 2	Finish algorithm analysis	Analyzing code to obtain big-O 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.7-6.7.2 (skip 6.7.1)	Rotation applet
13	Oct. 9	Balanced binary trees	AVL trees	Drozdek 6.7-6.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	Union-find algorithm	Drozdek 8.4.1 Wikipedia entry, UW slides (first 5 pages of PDF) Optional: Princeton slides
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 11-11.2 (skip 11.2.1)
	Nov. 7	NO LAB THIS WEEK
21	Nov. 11	Hashing	Hash function, probing (linear, quadratic, double hashing), chaining	Drozdek 10-10.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 union-find	Drozdek 8-8.1, 8.5 (Kruskal's only)
24	Nov. 20	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")
	Nov. 21	NO LAB THIS WEEK
25	Nov. 25	Sorting	Selection/insertion sorts, start mergesort	Drozdek 9-9.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:30-5:30 pm (both sections) Smith 130