Wolf Bein

CS 302 Introduction to Data Structures


ANNOUNCEMENTS




Posted 08-25-18:
The pages for this course are now ready. The syllabus is subject to change.


Posted 08-25-18:
If you do not have an account in the lab yet: Here is the account application.


Posted 08-31-18:
For assignment 1: Complex numbers explained. Also, headers, output, and code snippets for assignment 1.


Posted 08-31-18:
Seiden's Theoretical Computer Science Cheat Sheet.


Posted 08-31-18:
Current Reading: 1.4 - 1.7 in the 45 page handout, Chapter 2.


Posted 09-13-18:
Here is the Big-Oh Slide.


Posted 09-13-18:
Linked Lists: Reading is 3.5 and 3.6, see 45 page handout , the code is here list_class.cxx
How to generate random numbers.


Posted 09-13-18:
This is how to print the list:
for(ni=the_List.begin(); ni!=the_List.end(); ni++) { cout << *ni << " "; }


Posted 09-13-18:

For assignment 3, here is how to measure the run of your program:

You need to use the command time. The syntax for using time is
time ./a.out
The output for time will have three lines like these.
real 59.95
user 55.24
sys 0.09
Use is the one called `user'. (55.24 in the example below.)
The other ones (real, sys) take operating system overhead
into account.

How to generate random numbers.


Posted 09-13-18:
Here is the Master Theorem.


Posted 09-17-18:
Current Reading: Chapter 3.


Posted 09-27-18:
More on Postfix Expressions.


Posted 09-27-18:
Note that substraction and division do not commute, ab/ means a/b and not b/a (similarly ab- means a-b).
Here are a few more examples to test your program:
4572+-*$ -16
34+2*7/$ gives 2
57+62-*$ gives 48
42351-+*+$ gives 18
42+351-*+$ gives 18



Posted 09-27-18:
Here is a simple function to convert a character, which represents a number to a n integer value: int CharToInt(const char c)
{
switch (c)
{
case '0': return 0;
case '1': return 1;
case '2': return 2;
case '3': return 3;
case '4': return 4;
case '5': return 5;
case '6': return 6;
case '7': return 7;
case '8': return 8;
case '9': return 9;
default: return 0; }
}



Posted 09-27-18:
Reminder: The first midterm is on Friday, October 5.
Reading (study guide) for the first midterm.

Study Guide
Chapter 1 (Math and Code review)
Chapter 2 (Algorithmic Complexity).
Chapter 3: 3.1,3.5 (Lists), 3.6 (Stacks), 3.7 (Queues).
Chapter 7: 7.1, 7.2 (Insertion Sort).
Review assignments 1 - 5.


Posted 10-02-18:
Here are the solutions for assignment 4.


Posted 10-04-18:
Here is the dot-h file TaskTree.h for assignment 6. Additionally, here is main.cxx.
You may modify the files.
Here is a code snippet to set up the tree and another code snippet which shows you how to print out such a tree in preorder. Here are constructors.


Posted 10-16-18:
Reading: Chapter 4: 4.1 (Tree Traversals), 4.2 (Binary Trees), 4.3 (Binary Serach Trees), 4.4 (AVL Trees). By Friday, October 19, make sure to have carefully studied the Binary Search Tree code given in 4.3.


Posted 10-18-18:
There is regular class tomorrow, Friday, October 19. Please be in class tomorrow. Due to a new committee assignment, my Thursday office hours have changed: They are now from 12:00 pm - 1:00 pm and 4:00 pm to 6:00 pm.



Posted 10-18-18:
There is no class on October 26 due to Nevada day, instead as indicated on the syllabus here are the intructions for our October 26 virtual meeting:
1. Read 4.5 (Splay Trees) in our text book.
2. Study the following Splay Tree Notes.
3. Look at 11.5 which discusses amortized run time analysis for splay trees.
4. Have questions ready for our next class meeting
Note that next week's Thursday office hour (October 25) is canceled.


Posted 10-28-18:
Current reading: Chapter 4. 2-3 Tree Slides.


Posted 10-28-18:
As announced in class the date of Test 2 is November 16.

Posted 11-07-18:
Regarding assignment 8, note the typo: Then n random numbers between 1 and 1,000,000 are inserted into a BST.


Posted 11-07-18:
Here is the Binary Search Tree code.


Posted 11-07-18:
Milestone design component (roughly one page in length):
- design document
- data structure used and how they were implemented; explain why the use of these structures fosters efficiency.
- what machine used to compile and run
Here are prointers for a good design document. As discussed our design documents will be somewhat simpler.


Posted 11-07-18:
Reminder: The second midterm is on Friday, November 16.
Reading (study guide) for the second midterm.

Study Guide
Chapter 4: 4.1 (Tree Traversals), 4.2 (Binary Trees), 4.3 (Binary Serach Trees), 4.4 (AVL Trees)
Chapter 6: 6.1, 6.2, 6.3 (Heaps), 6.4 (Event Simulation), 6.8 (Binomial Trees), 6.9 (Priority Queues).

Review: Assignment 6 (Tree Traversals), assignment 7 (Binary Search Trees, AVL Trees), assignment 8 (Binary Search Tree Sort), assignment 9 (Airport Simulation).




Posted 11-09-18: Fun with sorting: Dance routines for
mergesort, quicksort, and heapsort. As well Super Mario Heapsort Here slowsort visualization.


Posted 11-14-18:
The new deadline for assignment 9 is Monday November 19.


Posted 12-03-18:
Here is an example graph and the text file text file for Assignmemt 11.


Posted 12-05-18:
The final is on Friday, December 14, 10 am - 12:00 pm. It is comprehensive.
Reading:
Chapter 1
Chapter 2
Chapter 3
Chapter 4: 4.1, 4.2, 4.3, 4.4, 4.6, 4.7,
Chapter 5: 5.1, 5.2, 5.3, 5.4, 5.5
Chapter 6: 6.1, 6.2, 6.3, 6.4, 6.8
Chaper 7: 7.1, 7.2, 7.3, 7.6, 7.5, 7.7, 7.9
Chapter 8: 8.1, 8.2, 8.3, 8.4
Chapter 9: 9.1, 9.2, 9.5, 9.6
Review assignments 1 - 11.