Data Structures COP3530 Spring 2013

This course lies at the core of computer science and aims to teach you effective ways to represent data and to develop and implement most important computer algorithms in use today. You will learn how the choice of data structures and algorithm design methods impacts the performance of your code. This course will also make you proficient in C++ and solidify your Object Oriented Design concepts.

Credits: 4
Small URL for this site: cop.ufadventure.com
Lectures: MWF 8th Period (3-3:50PM) Little Hall 101
Final Exam: Wednesday, April 24th, 3PM (in-class)
Discussion:M9 (4:05PM) in CSE119 for section 6723
T8 (3PM) in CSE222 for section 1079

Instructor: Jeff DePree (Office Hours: Tuesday 9-10AM, Thursday 10-11AM, Friday 1-2PM in E309) - Google Calendar - or email me to set up an appointment.
TAs: Louis Cheung (discussions) - Office Hours: Thursdays and Fridays 4:05-6PM in E309 - lcheung [at] cise [dot] ufl [dot] edu
    Qi Zeng (grading) - Office Hours: Mondays and Wednesdays 1:50-2:50PM in E309
Textbook: Data Structures, Algorithms and Applications in C++, 2nd Edition by Sartaj Sahni. Free Ebook at UF library (you will probably need the Gatorlink VPN client to access it from off campus).
    Programs in Text: Zip File
    Louis did some research and found that the following text was highly recommended by many in the field: Introduction to Algorithms
Piazza: Please use this system for all your questions on homework/course material/etc. Follow this link to sign up: https://piazza.com/ufl/spring2013/cop3530/home
Prereqs: Strong programming skills, Discrete Math (COT3100), and Calculus. No C++ requirement but you should be proficient in OOP concepts or Java as is taught in COP3502, COP3503, COP3504.
Syllabus
Projects: Project 1 - Project 2 - Project 3 - Project 4 - Extra Credit (Deadlines clarified)
Video Lectures from past semester (Java): http://www.cise.ufl.edu/~sahni/cop3530/lectures.htm Old Sample Exams: Exam 2, Exam 3
Calculate your grade: Widget
Programming Contest Problems (searchable by type): UVA Toolkit Topcoder USACO

Anonymous Comment/Feedback Box

Calendar

WDayTopicResources/Activities
1Monday 1/7Syllabus - Lecture Slides (Course Motivation)
First assignment posted		Syllabus
Discussion (Development Environments)
Resources from last year's class
Wednesday 1/9Transitioning Java -> C++ SlidesRead Chapter 1
Friday 1/11Strings and Vectors Slides
2Monday 1/14Insertion Sort and Complexity - SlidesSkim through Chapters 2-4
Discussion (Compilation)
Wednesday 1/16Linear Lists SlidesRead Chapter 5
HW (not graded): 5.5, 5.17, 5.22, 5.25, 5.26
Friday 1/18Iterators and Chains Slides
3Monday 1/21Martin Luther King Holiday -
Makeup Discussion 8:20PM Tuesday, CSE 121		Discussion (Pointers)
Wednesday 1/23Applications of Chains SlidesRead Chapter 6
HW (not graded): 6.4, 6.16
Friday 1/25First assignment due before class
(worth 10% of grade) - Distribution - (student) Solution posted (.zip)
Optional extremely open-ended extra credit
Updated: Extra opportunity for people who received <75% on Assignment 1
Simulated Pointers Slides
Execution Time Measurement Slides
4Monday 1/28Dictionaries - Slides
Second Assignment posted - Update: JSON Parsing Example added		Discussion (Project 2)
Wednesday 1/30Overflow Handling - Slides
Read Chapter 10
HW (not graded) 10.17, 10.33, 10.48
Feel free to ignore Skip Lists
Friday 2/1LZW Compression - SlidesHackathon Infosession: Thursday at 6:15pm in CSE 114
Competition Saturday at 3PM in Turlington L005 (Additional Info)
5Monday 2/4Matrices - SlidesCDW - Monday 6-10PM at the Hilton - lots of jobs and free food - Flyer
Pre-register (so they'll buy more food)
Discussion Slides
Wednesday 2/6Stacks and applications - SlidesRead Chapter 7
HW: 7.41
Friday 2/8More Stacks - Slides
6Monday 2/11Queues and applications - SlidesRead Chapters 8 and 9
HW: 8.22, 9.34
Rat-in-maze linked variant (tunnels.cpp)
Wednesday 2/13Trees, binary trees, and properties - Slides
Friday 2/15Binary tree representation and operations - Slides
Second Assignment due before class
(worth 15% of grade) - Distribution - (student) Solution posted (.zip)
7Monday 2/18Binary tree traversal methods - Slidesreconstruct.cpp
Wednesday 2/20First Exam (in-class)
(worth 15% of grade) - Solution - Distribution
Practice Exam (Solution)
Test Study Guide
Friday 2/22Applications of Trees - Slides
Third Assignment posted
Please do not cheat on this one		Read Chapters 11
HW: 11.12, 11.20, 11.27, 11.29, 11.30, 11.45, 11.64
8Monday 2/25Application of priority queues. Min and max heaps - SlidesDiscussion (Trees/XML) Slides
Wednesday 2/27Min/max heaps cont., Leftist trees - SlidesRead Chapters 12, 13
HW: 12.23, 12.36, 12.39, 12.42, 13.25, 13.30
Friday 3/1Winner/Loser/Tournament Trees - Slides
XMonday 3/4Spring Break
Wednesday 3/6Spring Break
Friday 3/8Spring Break
9Monday 3/11Binary Search Trees - Slides
Wednesday 3/13Balanced/AVL/Red-Black Trees and Graphs - SlidesRead Chapters 14, 15
Friday 3/15Graph operations and representation - Slides
Third Assignment due before class
(worth 15% of grade)
Assignment 3 Solution - Distribution
10Monday 3/18Breadth-first and depth-first search - SlidesRead Chapter 16
HW 16.21, 16.24, 16.28, 16.32, 16.48, 16.50, 16.52
UF/Sears Internship meeting (free pizza), 4th Period, details
Wednesday 3/20Second Exam (in-class) - Exam - Solution (code) Solution (drawing)
(worth 15% of grade) - Distribution
Practice Exams
One double-sided hand-written cheat sheet allowed.
Dramatic Reading of Student's Tribute to Second Exam
Friday 3/22Greedy Method - Slides
Fourth Assignment posted		Read Chapter 17
17.4, 17.13, 17.17, 17.41
11Monday 3/25Single source all destinations - SlidesDiscussion Slides
Wednesday 3/27Minimum-cost spanning tree - Slides
Friday 3/29Divide and conquer - Slides
Project 4 Route Specification Extra Credit Deadline		Read Chapter 18
HW 18.3, 18.14
12Monday 4/1Sorting with divide and conquer - SlidesDiscussion Slides
Wednesday 4/3Selection and closest pair of points - Slides
Friday 4/5Dynamic Programming - SlidesRead Chapter 19
HW 19.6, 19.18, 19.24
Topcoder tutorials for DP, greedy algorithms, etc. here
13Monday 4/8More Dynamic Programming - SlidesDiscussion Slides
Alternative map approach to DP: mapApproach.cpp
Wednesday 4/10Matrix multiplication chains - SlidesReading on Edit Distance
Friday 4/12All pairs shortest paths - Slides
14Monday 4/15Single source shortest paths - Slides
Due date (3PM) for early-graded submissions for Project 4
(submit to e-learning - ask for early grading in the comments - grades returned by Wednesday)
Wednesday 4/17Hard Problems - Slides Enrichment (not on exam): Chapter on Backtracking
Friday 4/19Backtracking/Branch and Bound - Slides
Fourth Assignment due before class
(worth 15% of grade)
Late Penalty: 1pt per hour after deadline		Enrichment: Chapter on Branch and Bound
15Monday 4/22Exam Review
Wednesday 4/24Final Exam (in-class)
(worth 15% of grade)
Sample Exams

Typical C++ Program with Links to Relevant Resources

"sample.cpp"

#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#define IMPORTANT_NUMBER 10

using namespace std;

class SampleCode {
    public:
        SampleCode() { memberInt = new int(5); memberArray = new char[15]; }
        ~SampleCode() { delete memberVar; delete [] memberArray; }
        template<class T>
        int& doNothing(T x, int y, int& z) {
            int *ptrToY = &y;
            float *varSizeArray = new float[z];
            char phrase[14] = "Enter age: ";
            string s = "Hello Mom!";
            return z;
        }

        SampleCode operator+(const SampleCode&) const;

        void sampleException(int x) {
            if (x < 0) {
                throw runtime_error("Parameter cannot be less than zero");
            }
        }
    private:
        int *memberVar;
        char *memberArray;
};

int main() {
    SampleCode obj;
    SampleCode* ptrToObj = new SampleCode();

    vector sample;
    sample.push_back(0.0);
    int refVar = 5;
    obj.doNothing(1, IMPORTANT_NUMBER, refVar);
    try {
        ptrToObj->sampleException(refVar);
    } catch (exception& ex) {
        cerr << "The following exception was thrown: " << ex.what() << endl;
        return 1;
    }

    delete ptrToObj;

    return 0;
}


Console:

g++ sample.cpp
./a

General C++ References

CS50
Video Tutorials (recommended by Jorge)

Instructor's Application and Research Interests (Contact me if you would like to work on any of these)

AdventureAnywhere - Non-profit aiming to provide a worldwide network of ecotourism clubs, outfitters, and guide services. (PHP/MySQL)
FoodNextDoor - Buy food from your neighbors. (PHP/MySQL)
Microenterprise Templates (pdf) - System to aid in starting/running microenterprises. (Pre-Development)