IT327 - Data Structures - December 2008

After you read about these algorithms, you must implement them to sort arrays of type double (input will be from a file). This is due by the beginning of week 4. Email me a copy of your cpp files. If you work in groups, include all names of the students who worked on the assignment. Note that the less students on the assignment means more extra credit to whoever programmed the solutions. Also note that Merge sort, Quicksort and Randomized Quick sort will be worth more extra credit than the others, since they are harder to implement. Remember, no plagiarism (if you programmed it then I can ask you questions about it the code).

There will be a quiz next week related to information we covered through the end of this class (includes, power points, homeworks, labs, links, etc.).

Week 3 - Monday, December 15, 2008

We will have a quiz/programming quiz first thing today. We will then review grades up to the point before the quiz.

Next we will go over the course material, work on the lab, homework, and supplimental tutorials.

In order to save on wasted papger, students will print their own Lab and Homework Assignments in class, I will provide the hard copies of the quizes.

Unit 3 - Using a Stack

Lab 3

Unit 3 - Homework Assignment

Related Topic Links:

Backtracking

Palindrome

Queens Puzzle

Stack

Tree Traversal - Read about how Preorder traversal uses a stack

For advanced students (extra credit):

Part 1 - Write a program that solves the Queen puzzle for any NxN board, where N>=4 (user input required for N). Test your program in Part 1... you'll find that it takes a while to run especially the larger N you type in. What is the biggest N you found the solution for? Please provide a printout of the solutions you found. Lastly, if you can, provide me with the time complexity class of your algorithm.

Part 2 - Modify your program to output the maximum number of queens possible on a MxN board and output a solution, where M>=N>=4. Provide some printouts of some solutions you came up with.

Due date is at the beginning of week 5.

If you haven't yet, read through the following links related to data structures on your own: Data Structures

The following are additional problems/tutorials I gave to my IT116 students, try doing them in C++ and see how far you can get before the end of class:

Write code that sums all integers from 1 to 1000
Write code that sums all even integers from 100 to 2000
Write code that will sum all integers between two user inputted integers
Write code that outputs the first 100 prime numbers
Write code that initializes some basic data and then casting between the following datatypes: Byte, Double, Integer, Long, Single, and String.
What has higher precidence, a variable name that is more global or more local to a loop? Write some code that proves your answer.
Use google to find 5 useful webpages that can help you through out your future vb.net (visual C++ for this course) programming career (single tutorials do not work, a successful reference would be something like: http://www.devguru.com/Technologies/vbscript/quickref/vbscript_list.html for VB).
Do the following tutorials from "Hello World" through "Noughts and Crosses" VB Tutorials (See if you can do any of these in Visual C++, note some will be easy and some will be hard)

Week 4 - Monday,

We will not have a quiz today. This will allow the students to get back into the swing of things. We will have a quiz at the beginning of next week.

Unit 4 - Using a Queue

Lab 4

Unit 4 - Homework

You should know the difference between a stack and a queue.
You should be able to describe what queue overflow/underflow is
You should be able to explain how queues are used with buffers adn simulation programs.
You should know how the member functions of queues in the STL such as Pop(), Push(), Empty(), Size(), and Front(). You should also be able to answer questions that have code with these methods in them.
You should know what a palindrome is.
On your own, use the sample code in Figures 8.6 and 8.7 of the book to demonstrate the application of queues in a simulation program.
You should be able to explain how an array can be used to implement a queue.
You should be able to explain how a list can be used to implement a stack.
You should be able to explain how a priority queue works.

If you haven't yet, read through the following links related to data structures on your own: Data Structures

Extra Credit: Challenge yourself with some ACM programming problems. You'll then want to click on "browse problems" on the left, then "problem set volumes." You'll have to create an account, submit your code and verify that it is correct through their system. Once you have successfully coded problem(s), send me an email with the code which references the website description and problem number and have your class name and your name documented in the code as well. Some problems are easier than others, which can be judged by me on the solving percent shown by the UVA system. The harder the problem, the more extra credit you'll receive.

Week 5 - Monday,

We will start today with a quiz.

Unit 5 - Recursive Thinking

Lab 5

Unit 5 - Homework

Links for further Understanding:

Recursion Tutorial

Recursion in Computer Science

Recursion - General

Merge Sort - An Application of Recursion

If you finish early, please see me and we'll think of some extra credit assignments, perhaps some ACM problems that were linked to in Week 4.

Week 6 - Monday, January 19th, 2009

Midterm Today.

Unit 6 - Complete Binary Trees

Lab 6

Unit 6 - Homework

Useful Links:

Binary Search Tree

Binary Tree

Tree

Week 7 - Monday January 26th, 2009

Unit 7 - Binary Search Trees - Read on your own.

Lab 7

Unit 7 - Homework

Useful Links:

Binary Search Tree

Other Topics for Today:

Graph

Shortest Path Problem

Bellman-Ford Algorithm

Breath First Search

Depth First Search

Dijkstra's Algorithm

Links for Advanced Students:

Maximum Flow Problem

Max Flow Min Cut

Week 8 - Monday February 2nd, 2009

Unit 8 - Hash Tables

Unit 9 - Quadratic Sorting

Unit 10 - Graphs

Unit 8 - Homework

Lab 8

Lab 9

Hash Table

Selection Sort

Insertion Sort

Graph

Week 9 - Monday February 9th, 2009

Lab 10

C++ Graph Tutorial

Graph Theory

Graph - List Structure

Graph - Matrix Structure

Traveling Salesman Problem

Four Color Theorem

Minimum Spanning Tree

Cycle

Bridge (graph theory)

Connect Component

Strongly Connected Component

Bipartite Graph

Complete Bipartite Graph

Planar Graph

Additional Topics:

Combinatorial Optimization

Linear Programming

Knapsack Problem

Cryptography

Cutting Stock Problem

Dynamic Programming

Turing Award

NP-Complete

Famous Computer Scientists:

Nancy Lynch

Books that most serious programmers have:

The Art of Computer Programming

Introduction to Algorithms

Project Assignments:

1. On your own, pick topic(s) above and give a 2,500 word technical summary of the topic(s).

2. On your own, pick a famous computer scientist above and give a 1,000 word summary of their contributions to the field.

3. Program Dijkstra's Algorithm with your project team.

4. Program Prim's Algorithm with your project team.

5. Program Floyd-Warshall Algorithm with your project team.

6. Program Shell Sort with your project team.

7. Program Bucket Sort with your project team.

8. With your project team, write a 2,000 word summary about NP-Completeness and why it is an important problem. Give examples of NP-Complete problems and describe the importance if P=NP and if P!=NP.

Week 10 - Monday February 16th, 2009

We will continue working on the assigned class projects and review for the final.

Week 11 - Monday,

Class projects are due at the beginning of class.

Final Exam Today.

Power Points:

Unit 1 - Template Functions
Unit 2 - Linked Lists In Action
Unit 3 - Using a Stack
Unit 4 - Using a Queue
Unit 5 - Recursive Thinking
Unit 6 - Complete Binary Trees
Unit 7 - Binary Search Trees
Unit 8 - Hash Tables
Unit 9 - Quadratic Sorting
Unit 10 - Graphs

ITT - IT327Data StructuresDecember 2008

Notes and Assignments:

Power Points:

ITT - IT327
Data Structures
December 2008